Time Complexity: Index-only scans mental model
O(n)
0
0
Index-only scans mental model in PostgreSQL - Time & Space Complexity
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?