Index-only scans mental model in PostgreSQL - Time & Space Complexity

Time Complexity: Index-only scans mental model

O(n)

Understanding Time Complexity

We want to understand how fast an index-only scan works as the data grows.

How does the time to find data change when using only the index?

Scenario Under Consideration

Analyze the time complexity of this index-only scan query.

SELECT column1, column2
FROM table_name
WHERE column1 = 'value';
-- Assume an index exists on column1 including column2
    

This query uses an index that has all needed data, so it does not read the main table rows.

Identify Repeating Operations

Look for repeated steps in the scan process.

• Primary operation: Scanning index entries matching the condition.
• How many times: Once per matching index entry, no extra table row fetch needed.

How Execution Grows With Input

As the number of matching rows grows, the work grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 10 index entries read
100	About 100 index entries read
1000	About 1000 index entries read

Pattern observation: The time grows linearly with the number of matching rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the scan grows directly with how many rows match.

Common Mistake

[X] Wrong: "Index-only scans always take constant time no matter how many rows match."

[OK] Correct: The scan still reads each matching index entry, so more matches mean more work.

Interview Connect

Knowing how index-only scans scale helps you explain query speed and optimization clearly.

Self-Check

What if the index did not include all needed columns and the query had to fetch table rows? How would the time complexity change?

Practice

1. What is the main advantage of an index-only scan in PostgreSQL?

easy

A. It reads data only from the index without accessing the main table.

B. It updates the index faster than a normal scan.

C. It locks the table to prevent concurrent writes.

D. It creates a new index automatically during query execution.

Solution

1. Step 1: Understand what an index-only scan does

   An index-only scan uses the index to get all needed data without reading the main table.

2. Step 2: Compare options to this behavior

   Only It reads data only from the index without accessing the main table. describes reading data solely from the index, which is the key benefit.

3. Final Answer:

   It reads data only from the index without accessing the main table. -> Option A

4. Quick Check:

   Index-only scan = reads from index only [OK]

Hint: Index-only scans avoid table reads by using index data only [OK]

Common Mistakes:

• Thinking index-only scans update data
• Assuming they lock tables
• Believing they create indexes automatically

2. Which of the following is a correct condition for PostgreSQL to use an index-only scan?

easy

A. The table has no indexes defined.

B. The index contains all columns needed by the query.

C. The query uses aggregate functions only.

D. The table is empty.

Solution

1. Step 1: Recall index-only scan requirements

   PostgreSQL can use index-only scans only if the index has all columns the query needs.

2. Step 2: Evaluate each option

   The index contains all columns needed by the query. matches the requirement; others do not enable index-only scans.

3. Final Answer:

   The index contains all columns needed by the query. -> Option B

4. Quick Check:

   Index-only scan requires full column coverage in index [OK]

Hint: Index-only scans need all query columns in the index [OK]

Common Mistakes:

• Thinking index-only scans work without indexes
• Assuming aggregates always use index-only scans
• Believing empty tables affect index-only scans

3. Given a table users(id, name, email) with an index on (id, email), which query can use an index-only scan?

medium

A. SELECT id, email FROM users WHERE id = 10;

B. SELECT name FROM users WHERE id = 10;

C. SELECT email FROM users WHERE name = 'Alice';

D. SELECT * FROM users WHERE email = '[e-mail]';

Solution

1. Step 1: Check index columns and query columns

   The index covers columns id and email. Query C requests only id and email.

2. Step 2: Determine if index-only scan is possible

   Query C can use index-only scan because all requested columns are in the index. Others request columns not in the index.

3. Final Answer:

   SELECT id, email FROM users WHERE id = 10; -> Option A

4. Quick Check:

   Query columns ⊆ index columns = index-only scan [OK]

Hint: Index-only scan if query columns are subset of index columns [OK]

Common Mistakes:

• Choosing queries requesting columns not in index
• Ignoring WHERE clause columns
• Assuming * always uses index-only scan

4. You have an index on (username, email) but your query SELECT email FROM users WHERE username = 'bob'; is not using an index-only scan. What could be the reason?

medium

A. The query uses a WHERE clause on username, so index-only scan is impossible.

B. The index does not include the email column.

C. The table's visibility map is not updated, so PostgreSQL must check the table.

D. PostgreSQL never uses index-only scans on text columns.

Solution

1. Step 1: Confirm index covers needed columns

   The index includes username and email, so columns are covered.

2. Step 2: Understand visibility map role

   Index-only scans require the visibility map to confirm tuples are visible without table access. If not updated, PostgreSQL reads the table.

3. Final Answer:

   The table's visibility map is not updated, so PostgreSQL must check the table. -> Option C

4. Quick Check:

   Visibility map must be updated for index-only scan [OK]

Hint: Visibility map must be updated for index-only scans [OK]

Common Mistakes:

• Assuming index missing columns
• Believing WHERE clause blocks index-only scan
• Thinking data type prevents index-only scans

5. You want to optimize a query SELECT id, status FROM orders WHERE status = 'shipped'; for index-only scans. The current index is on (id). What is the best way to enable index-only scans?

hard

A. Add a WHERE clause to filter only 'shipped' status.

B. Create a partial index on (id) where status = 'shipped'.

C. Drop the existing index and rely on sequential scan.

D. Create a new index on (status, id) including both columns.

Solution

1. Step 1: Identify columns needed for index-only scan

   The query selects id and status, so the index must cover both columns.

2. Step 2: Choose index that covers all columns

   Creating an index on (status, id) includes both columns, enabling index-only scans.

3. Final Answer:

   Create a new index on (status, id) including both columns. -> Option D

4. Quick Check:

   Index covering all query columns enables index-only scan [OK]

Hint: Index must cover all selected columns for index-only scan [OK]

Common Mistakes:

• Thinking partial index alone enables index-only scan
• Dropping index reduces performance
• Adding WHERE clause doesn't affect index structure