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)?"