Expression indexes in PostgreSQL - Time & Space Complexity

Time Complexity: Expression indexes

O(log n)

Understanding Time Complexity

We want to understand how using expression indexes affects the speed of database queries.

Specifically, how the time to find data changes as the table grows.

Scenario Under Consideration

Analyze the time complexity of this index creation and query:

CREATE INDEX idx_lower_name ON users ((lower(name)));

SELECT * FROM users WHERE lower(name) = 'alice';

This code creates an index on the lowercase version of the name column, then queries using that lowercase expression.

Identify Repeating Operations

Look at what repeats when searching with this index.

• Primary operation: The database uses the index to quickly find matching rows by comparing the expression result.
• How many times: The search compares parts of the index tree, which grows with the number of rows.

How Execution Grows With Input

As the number of rows increases, the index helps keep search fast.

Input Size (n)	Approx. Operations
10	About 3-4 comparisons
100	About 7 comparisons
1000	About 10 comparisons

Pattern observation: The number of steps grows slowly, not directly with the number of rows.

Final Time Complexity

Time Complexity: O(log n)

This means the search time grows slowly as the table gets bigger, thanks to the index.

Common Mistake

[X] Wrong: "Using an expression index makes the query run in constant time no matter how big the table is."

[OK] Correct: Even with an index, the database still needs to do some comparisons that grow slowly with table size, so it's not instant but very efficient.

Interview Connect

Knowing how expression indexes affect query speed shows you understand how databases keep searches fast even with complex conditions.

Self-Check

"What if we removed the expression index and only had a normal index on the name column? How would the time complexity change when querying with lower(name)?"

Practice

1. What is the main purpose of an expression index in PostgreSQL?

easy

A. To create a backup of the database

B. To store data in a compressed format

C. To speed up queries that filter or sort by a calculated expression

D. To enforce foreign key constraints

Solution

1. Step 1: Understand what expression indexes do

   Expression indexes are special indexes built on the result of an expression or function, not just a column.

2. Step 2: Identify their main use

   They help speed up queries that filter or sort using that expression, improving performance.

3. Final Answer:

   To speed up queries that filter or sort by a calculated expression -> Option C

4. Quick Check:

   Expression index purpose = speed up expression queries [OK]

Hint: Expression indexes speed up queries using expressions [OK]

Common Mistakes:

• Confusing expression indexes with data compression
• Thinking expression indexes create backups
• Mixing expression indexes with constraints

2. Which of the following is the correct syntax to create an expression index on the lowercased username column in PostgreSQL?

easy

A. CREATE INDEX idx_lower_username ON users (LOWER(username));

B. CREATE INDEX idx_lower_username ON users ((LOWER(username)));

C. CREATE INDEX idx_lower_username ON users [LOWER(username)];

D. CREATE INDEX idx_lower_username ON users {LOWER(username)};

Solution

1. Step 1: Recall expression index syntax

   Expression indexes require double parentheses around the expression inside the index definition.

2. Step 2: Check each option

   CREATE INDEX idx_lower_username ON users ((LOWER(username))); uses double parentheses correctly: ((LOWER(username))). Options B, C, and D use incorrect syntax.

3. Final Answer:

   CREATE INDEX idx_lower_username ON users ((LOWER(username))); -> Option B

4. Quick Check:

   Expression index syntax = double parentheses [OK]

Hint: Use double parentheses for expressions in CREATE INDEX [OK]

Common Mistakes:

• Using single parentheses instead of double
• Using square or curly brackets
• Missing parentheses around the expression

3. Given the table products(id INT, price NUMERIC) and the index:
CREATE INDEX idx_discounted_price ON products ((price * 0.9));
What will the query below use to speed up filtering?
SELECT * FROM products WHERE price * 0.9 < 100;

medium

A. It will perform a full table scan ignoring the index

B. It will use a default index on price if it exists

C. It will cause a syntax error due to the expression

D. It will use the expression index on (price * 0.9) to speed up the query

Solution

1. Step 1: Understand the expression index usage

   The index is created on the expression (price * 0.9), matching the WHERE clause expression exactly.

2. Step 2: Match query filter with index expression

   Since the query filters on price * 0.9 < 100, PostgreSQL can use the expression index to speed up filtering.

3. Final Answer:

   It will use the expression index on (price * 0.9) to speed up the query -> Option D

4. Quick Check:

   Matching expression in WHERE = index used [OK]

Hint: Expression index used if query expression matches exactly [OK]

Common Mistakes:

• Assuming default indexes are used instead
• Thinking expression indexes cause errors
• Believing full table scan always happens

4. You tried to create an expression index with:
CREATE INDEX idx_expr ON sales (price * discount);
But PostgreSQL returned a syntax error. What is the problem?

medium

A. Expression indexes require double parentheses around the expression

B. You cannot create indexes on expressions involving multiplication

C. The table name is missing

D. The index name is invalid

Solution

1. Step 1: Check expression index syntax

   Expression indexes must have the expression enclosed in double parentheses to be valid.

2. Step 2: Identify the syntax error cause

   The given statement uses single parentheses, causing a syntax error.

3. Final Answer:

   Expression indexes require double parentheses around the expression -> Option A

4. Quick Check:

   Double parentheses fix syntax error [OK]

Hint: Use double parentheses for expressions to avoid syntax errors [OK]

Common Mistakes:

• Using single parentheses for expressions
• Thinking multiplication is not allowed
• Ignoring syntax error details

5. You want to speed up queries filtering by the first 3 letters of a city column in a locations table. Which expression index will best help?
CREATE INDEX idx_city_prefix ON locations (???);

hard

A. LEFT(city, 3)

B. SUBSTRING(city FROM 1 FOR 3)

C. city[1:3]

D. city LIKE '___%'

Solution

1. Step 1: Identify correct expression syntax for substring

   PostgreSQL supports the function LEFT(string, n) to get the first n characters.

2. Step 2: Evaluate options for expression index

   LEFT(city, 3) uses LEFT(city, 3) correctly inside the index. SUBSTRING(city FROM 1 FOR 3) uses SUBSTRING but syntax is less common and may be less efficient. city[1:3] is invalid syntax. city LIKE '___%' is a condition, not an expression.

3. Final Answer:

   LEFT(city, 3) -> Option A

4. Quick Check:

   LEFT function best for prefix expression index [OK]

Hint: Use LEFT(column, n) for prefix expression indexes [OK]

Common Mistakes:

• Using invalid substring syntax
• Confusing LIKE pattern with expression
• Using array slice syntax on strings