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

Practice

1. What does a sequential scan do in PostgreSQL?

easy

A. Reads only the first 10 rows of a table

B. Uses an index to find specific rows quickly

C. Deletes rows based on a condition

D. Reads every row in the table one by one

Solution

1. Step 1: Understand sequential scan behavior

   A sequential scan reads all rows in the table from start to end without using any index.

2. Step 2: Compare with other options

   Using an index is an index scan, reading only first 10 rows or deleting rows are unrelated actions.

3. Final Answer:

   Reads every row in the table one by one -> Option D

4. Quick Check:

   Sequential scan = full table read [OK]

Hint: Sequential scan reads all rows, no index used [OK]

Common Mistakes:

• Confusing sequential scan with index scan
• Thinking sequential scan reads only some rows
• Assuming sequential scan deletes rows

2. Which of the following is the correct way to see if PostgreSQL uses an index scan or sequential scan?

easy

A. SELECT * FROM table WHERE id = 1;

B. EXPLAIN SELECT * FROM table WHERE id = 1;

C. CREATE INDEX ON table(id);

D. DROP INDEX index_name;

Solution

1. Step 1: Identify command to check query plan

   The EXPLAIN command shows how PostgreSQL executes a query, including scan type.

2. Step 2: Eliminate other options

   SELECT runs query but doesn't show plan; CREATE and DROP INDEX modify indexes, not show plans.

3. Final Answer:

   EXPLAIN SELECT * FROM table WHERE id = 1; -> Option B

4. Quick Check:

   EXPLAIN shows scan type [OK]

Hint: Use EXPLAIN before query to see scan type [OK]

Common Mistakes:

• Running SELECT without EXPLAIN to check scan
• Confusing index creation with scan checking
• Using DROP INDEX to check scans

3. Given a table users(id SERIAL PRIMARY KEY, name TEXT) with 1 million rows, which scan is PostgreSQL likely to use for this query?
SELECT * FROM users WHERE id = 500000;

medium

A. Index scan using the primary key index

B. Sequential scan scanning all 1 million rows

C. Bitmap heap scan reading random rows

D. No scan, query will fail

Solution

1. Step 1: Analyze query condition and table size

   The query filters by primary key id, which has an index, and the table is large (1 million rows).

2. Step 2: Determine efficient scan type

   PostgreSQL uses an index scan to quickly find the single matching row instead of scanning all rows.

3. Final Answer:

   Index scan using the primary key index -> Option A

4. Quick Check:

   Selective query on indexed column = index scan [OK]

Hint: Selective query on indexed column uses index scan [OK]

Common Mistakes:

• Assuming sequential scan for large tables with indexed filter
• Confusing bitmap heap scan with index scan
• Thinking query fails without reason

4. You wrote this query:
SELECT * FROM orders WHERE customer_id = 123;
But EXPLAIN shows a sequential scan instead of an index scan. What could be the reason?

medium

A. There is no index on customer_id

B. The table is empty

C. The query syntax is incorrect

D. PostgreSQL always uses sequential scan

Solution

1. Step 1: Check index presence on filter column

   If no index exists on customer_id, PostgreSQL must scan all rows sequentially.

2. Step 2: Evaluate other options

   Empty table would still show scan but no rows; syntax is correct; PostgreSQL chooses scan type based on indexes.

3. Final Answer:

   There is no index on customer_id -> Option A

4. Quick Check:

   No index on filter column = sequential scan [OK]

Hint: No index on filter column causes sequential scan [OK]

Common Mistakes:

• Assuming syntax error causes scan type
• Thinking PostgreSQL always uses sequential scan
• Ignoring missing index as cause

5. You have a large table products with millions of rows and an index on category_id. You run:
SELECT * FROM products WHERE category_id IN (1, 2, 3, 4, 5);
PostgreSQL chooses a sequential scan instead of an index scan. Why might this happen?

hard

A. The index on category_id is corrupted

B. Sequential scan is always faster for any query

C. The query is not selective enough; many rows match

D. The IN clause is invalid syntax

Solution

1. Step 1: Understand query selectivity

   The query matches many rows because it filters on multiple categories, reducing selectivity.

2. Step 2: Explain PostgreSQL scan choice

   When many rows match, PostgreSQL prefers sequential scan as it can be faster than many index lookups.

3. Final Answer:

   The query is not selective enough; many rows match -> Option C

4. Quick Check:

   Low selectivity = sequential scan preferred [OK]

Hint: Low selectivity queries often use sequential scan [OK]

Common Mistakes:

• Assuming index corruption without evidence
• Thinking sequential scan is always slower
• Believing IN clause is invalid syntax