Sequential scan vs index scan in PostgreSQL - Performance Comparison

Time Complexity: Sequential scan vs index scan

O(n) for sequential scan, O(log n + k) for index scan

Understanding Time Complexity

When a database looks for data, it can check every row or use a shortcut called an index.

We want to understand how the time to find data changes with more rows using these two methods.

Scenario Under Consideration

Analyze the time complexity of these two queries:

-- Sequential scan example
SELECT * FROM employees WHERE department = 'Sales';

-- Index scan example
CREATE INDEX idx_department ON employees(department);
SELECT * FROM employees WHERE department = 'Sales';
    

The first query checks every row to find matches. The second uses an index to jump to matching rows faster.

Identify Repeating Operations

Look at what repeats when the database runs these queries:

• Primary operation: Checking rows one by one (sequential scan) or jumping to matching rows using the index (index scan).
• How many times: Sequential scan checks all rows; index scan checks only matching rows plus some index steps.

How Execution Grows With Input

As the table grows, the time to find data changes like this:

Input Size (n)	Approx. Operations (Sequential Scan)	Approx. Operations (Index Scan)
10	10 checks	Few index steps + matching rows
100	100 checks	Few more index steps + matching rows
1000	1000 checks	Still few index steps + matching rows

Pattern observation: Sequential scan grows linearly with table size; index scan grows slowly, mostly depending on matching rows.

Final Time Complexity

Time Complexity: O(n) for sequential scan, O(log n + k) for index scan where k is matching rows.

This means checking every row takes longer as the table grows, but using an index mostly depends on how many matches there are.

Common Mistake

[X] Wrong: "Using an index always makes queries faster no matter what."

[OK] Correct: If many rows match, scanning the index plus fetching rows can be slower than just checking all rows once.

Interview Connect

Understanding when databases use sequential or index scans helps you explain how queries stay fast as data grows.

Self-Check

"What if the index was on multiple columns instead of one? How would the time complexity change?"