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

Practice

1. What is the main purpose of a partial index with a WHERE clause in PostgreSQL?

easy

A. To index only rows that meet a specific condition

B. To index all rows in the table regardless of condition

C. To create a backup of the table

D. To delete rows that do not meet the condition

Solution

1. Step 1: Understand partial index concept

   A partial index indexes only a subset of rows based on a condition.

2. Step 2: Role of WHERE clause

   The WHERE clause defines which rows to include in the index.

3. Final Answer:

   To index only rows that meet a specific condition -> Option A

4. Quick Check:

   Partial index = conditional indexing [OK]

Hint: Partial indexes use WHERE to limit indexed rows [OK]

Common Mistakes:

• Thinking partial indexes index all rows
• Confusing partial index with table backup
• Assuming partial index deletes rows

2. Which of the following is the correct syntax to create a partial index on a table orders for rows where status = 'pending'?

easy

A. CREATE INDEX idx_pending ON orders (status) WHERE status = 'pending';

B. CREATE INDEX idx_pending ON orders WHERE status = 'pending';

C. CREATE INDEX idx_pending ON orders WHERE status = 'pending' (status);

D. CREATE INDEX idx_pending ON orders (status) WHERE status == 'pending';

Solution

1. Step 1: Check index creation syntax

   CREATE INDEX requires index name, table, columns, and optional WHERE clause.

2. Step 2: Validate WHERE clause and operators

   Use single equals (=) for comparison, and specify columns to index.

3. Final Answer:

   CREATE INDEX idx_pending ON orders (status) WHERE status = 'pending'; -> Option A

4. Quick Check:

   Correct syntax includes columns and WHERE with = [OK]

Hint: Include columns before WHERE; use single = for condition [OK]

Common Mistakes:

• Omitting columns in index definition
• Using double equals (==) instead of single =
• Placing WHERE before columns

3. Given the partial index:
CREATE INDEX idx_active_users ON users (last_login) WHERE active = true;
What will be the result of this query?
SELECT * FROM users WHERE active = true AND last_login > '2024-01-01';

medium

A. The query will return no rows because partial indexes exclude all rows

B. The query will ignore the partial index and perform a full table scan

C. The query will cause a syntax error due to the partial index

D. The query will use the partial index and return matching rows quickly

Solution

1. Step 1: Understand partial index condition

   The index covers rows where active = true, indexing last_login.

2. Step 2: Analyze query filter

   The query filters on active = true and last_login > '2024-01-01', matching the index condition.

3. Final Answer:

   The query will use the partial index and return matching rows quickly -> Option D

4. Quick Check:

   Query matches partial index condition = uses index [OK]

Hint: Query filters must match partial index WHERE to use it [OK]

Common Mistakes:

• Assuming partial index causes syntax errors
• Thinking partial index excludes all rows
• Believing query ignores partial index if condition partially matches

4. You created a partial index:
CREATE INDEX idx_recent_orders ON orders (order_date) WHERE order_date > CURRENT_DATE - INTERVAL '30 days';
But queries filtering order_date > CURRENT_DATE - INTERVAL '30 days' are not using the index. What is the likely problem?

medium

A. Partial indexes cannot use date intervals

B. The index is missing the column order_date

C. The partial index condition uses a non-immutable function, so it cannot be used

D. The WHERE clause in the index is invalid syntax

Solution

1. Step 1: Check partial index WHERE clause

   The WHERE clause uses CURRENT_DATE, which is non-immutable (changes daily).

2. Step 2: Understand index usage limitation

   PostgreSQL partial indexes require immutable conditions to be used by queries.

3. Final Answer:

   The partial index condition uses a non-immutable function, so it cannot be used -> Option C

4. Quick Check:

   Non-immutable functions block partial index usage [OK]

Hint: Partial index WHERE must use immutable expressions [OK]

Common Mistakes:

• Assuming syntax error causes issue
• Thinking partial indexes can't use date columns
• Ignoring function immutability rules

5. You want to speed up queries on a products table filtering only active products with price < 100. Which partial index is best to create?

hard

A. CREATE INDEX idx_active_price ON products (price);

B. CREATE INDEX idx_active_price ON products (price) WHERE active = true AND price < 100;

C. CREATE INDEX idx_active_price ON products (price) WHERE active = true OR price < 100;

D. CREATE INDEX idx_active_price ON products WHERE active = true AND price < 100;

Solution

1. Step 1: Define index condition matching query filters

   The query filters active = true AND price < 100, so index WHERE must match both.

2. Step 2: Check syntax and columns

   Index must specify columns (price) and use AND in WHERE clause for correct filtering.

3. Final Answer:

   CREATE INDEX idx_active_price ON products (price) WHERE active = true AND price < 100; -> Option B

4. Quick Check:

   Partial index WHERE matches query filters exactly [OK]

Hint: Use AND in WHERE to match all query conditions [OK]

Common Mistakes:

• Using OR instead of AND in WHERE clause
• Omitting columns in index definition
• Trying to create index without columns