Bitmap index scan behavior in PostgreSQL - Time & Space Complexity

Time Complexity: Bitmap index scan behavior

O(n)

Understanding Time Complexity

We want to understand how the time to find rows using a bitmap index scan changes as the table grows.

How does the scan's work increase when there are more rows or matching entries?

Scenario Under Consideration

Analyze the time complexity of this bitmap index scan query.

EXPLAIN ANALYZE
SELECT * FROM orders
WHERE customer_id = 12345;
-- Assume customer_id has a bitmap index
    

This query uses a bitmap index scan to find all orders for a specific customer.

Identify Repeating Operations

Look at what repeats during the scan.

• Primary operation: Reading index entries matching the condition and then fetching table rows.
• How many times: Once for each matching index entry, then once per matching row in the table.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10 matching rows	About 10 index reads + 10 table fetches
100 matching rows	About 100 index reads + 100 table fetches
1000 matching rows	About 1000 index reads + 1000 table fetches

Pattern observation: The total work grows roughly linearly with the number of matching rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the bitmap index scan grows in direct proportion to the number of matching rows.

Common Mistake

[X] Wrong: "Bitmap index scans always take constant time regardless of data size."

[OK] Correct: The scan time depends on how many rows match the condition, so it grows as more rows match.

Interview Connect

Understanding how bitmap index scans scale helps you explain query performance clearly and shows you know how databases handle large data efficiently.

Self-Check

What if we changed the query to use multiple conditions combined with AND? How would the time complexity of the bitmap index scan change?