Partial indexes with WHERE clause in PostgreSQL - Time & Space Complexity

Time Complexity: Partial indexes with WHERE clause

O(log m + k)

Understanding Time Complexity

We want to understand how using a partial index affects the speed of database queries.

Specifically, how the time to find data changes as the table grows when the index only covers some rows.

Scenario Under Consideration

Analyze the time complexity of this partial index creation and usage.

CREATE INDEX idx_active_users ON users (last_login) WHERE active = true;

SELECT * FROM users WHERE active = true AND last_login > now() - interval '7 days';
    

This code creates an index only on users who are active, then queries recent active users.

Identify Repeating Operations

Look at what repeats when the query runs.

• Primary operation: Searching the partial index for matching rows.
• How many times: Depends on the number of active users, not all users.

How Execution Grows With Input

The query only searches the smaller set of active users, so as total users grow, work grows slower.

Input Size (total users)	Approx. Operations (active users)
10	5 (if half active)
100	50
1000	500

Pattern observation: Work grows with the number of active users, not total users.

Final Time Complexity

Time Complexity: O(log m + k)

This means the query time grows with the size of the indexed subset (active users), not the whole table, where m is the number of indexed rows and k is the number of rows returned.

Common Mistake

[X] Wrong: "The partial index speeds up queries on the whole table equally."

[OK] Correct: The index only helps queries that match the WHERE condition; other queries still scan the full table.

Interview Connect

Understanding partial indexes shows you can make queries faster by focusing on important data, a useful skill in real projects.

Self-Check

"What if the WHERE clause in the partial index covered more rows? How would that affect the time complexity?"