Bitmap index scan behavior in PostgreSQL - Deep Dive

Overview - Bitmap index scan behavior

What is it?

Bitmap index scan is a method PostgreSQL uses to find rows in a table by first scanning an index and creating a bitmap of matching row locations. Instead of fetching rows immediately, it collects all matching row positions and then fetches them in an efficient order. This helps speed up queries that match many rows but not all.

Why it matters

Without bitmap index scans, PostgreSQL might fetch rows one by one from the table, causing many slow random disk reads. Bitmap scans reduce disk access by grouping row fetches, making queries faster and more efficient, especially on large tables. This improves user experience and resource use in real applications.

Where it fits

Before learning bitmap index scans, you should understand basic indexes and sequential scans in PostgreSQL. After this, you can explore advanced query optimization, multi-index scans, and how PostgreSQL's planner chooses scan methods.

Mental Model

Core Idea

Bitmap index scan collects all matching row positions first, then fetches rows in a single, efficient pass to reduce random disk reads.

Think of it like...

Imagine you want to find all your friends' houses in a city. Instead of visiting each street immediately, you first mark all their locations on a map (bitmap). Then you plan one efficient route to visit all houses, saving time and travel.

┌───────────────┐       ┌───────────────┐       ┌───────────────┐
│ Index Scan    │──────▶│ Bitmap Created│──────▶│ Heap Fetch    │
│ (Find matches)│       │ (Mark rows)   │       │ (Fetch rows)  │
└───────────────┘       └───────────────┘       └───────────────┘

Build-Up - 7 Steps

1

Foundation

Understanding Basic Index Scans

Concept: Learn how PostgreSQL uses indexes to find rows quickly by scanning index entries.

PostgreSQL uses indexes like a phone book to find rows matching a condition. A basic index scan reads the index and fetches each matching row one by one from the table (heap). This works well for few matches but can be slow for many.

Result

You get matching rows but may have many random disk reads if many rows match.

Knowing how basic index scans work helps you see why fetching rows one by one can be inefficient for large result sets.

2

Foundation

What is a Bitmap Index Scan?

Concept: Bitmap index scan separates finding matches and fetching rows into two steps using a bitmap.

Instead of fetching rows immediately, PostgreSQL scans the index and records matching row positions in a bitmap. Later, it fetches all rows in one go, reducing random disk access.

Result

The query runs faster when many rows match because disk reads are grouped.

Understanding this two-step process is key to grasping how PostgreSQL optimizes large result queries.

3

Intermediate

How Bitmap Indexes Store Row Positions

Concept: Bitmap index scan uses a bitmap data structure to mark matching rows efficiently.

A bitmap is like a map of bits where each bit represents a row in the table. If a row matches, its bit is set to 1. This compactly stores many row positions without listing them individually.

Result

PostgreSQL can quickly combine bitmaps from multiple indexes or conditions.

Knowing the bitmap structure explains why bitmap scans can combine multiple conditions efficiently.

4

Intermediate

Combining Multiple Bitmap Scans

🤔Before reading on: do you think PostgreSQL can combine multiple index scans by fetching rows separately or by merging their results first? Commit to your answer.

Concept: PostgreSQL merges bitmaps from multiple index scans before fetching rows to optimize performance.

When a query uses multiple indexes, PostgreSQL creates bitmaps for each and combines them using AND, OR, or NOT operations. Then it fetches rows matching the combined bitmap in one pass.

Result

This reduces the number of heap fetches and speeds up complex queries.

Understanding bitmap merging reveals how PostgreSQL efficiently handles multi-condition queries.

5

Intermediate

Heap Fetch Phase and Reordering

Concept: After bitmap creation, PostgreSQL fetches rows from the table in physical order to minimize disk seeks.

The bitmap is sorted by physical location on disk. Fetching rows in this order reduces random disk reads, improving speed compared to fetching rows as found in the index.

Result

Queries run faster because disk head movement is minimized.

Knowing that heap fetches are reordered explains the performance gain of bitmap scans over simple index scans.

6

Advanced

When PostgreSQL Chooses Bitmap Index Scan

🤔Before reading on: do you think PostgreSQL always uses bitmap scans for many matches or only sometimes? Commit to your answer.

Concept: PostgreSQL's planner chooses bitmap scans based on cost estimates and data distribution.

The planner estimates how many rows match and the cost of different scan methods. Bitmap scans are chosen when many rows match but not all, balancing index and heap access costs.

Result

Efficient query plans that adapt to data and query shape.

Understanding planner decisions helps you tune queries and indexes for better performance.

7

Expert

Surprising Behavior: Bitmap Heap Scan Visibility Checks

🤔Quick: do you think bitmap heap scans check row visibility during bitmap creation or during heap fetch? Commit to your answer.

Concept: Row visibility is checked only during heap fetch, not during bitmap creation.

Bitmap index scan marks all rows matching the index condition, even if some are not visible due to transactions. Visibility checks happen later when fetching rows from the heap, ensuring correctness.

Result

Bitmap may include invisible rows, but final results exclude them after visibility checks.

Knowing visibility checks happen late explains why bitmap scans can be faster but require careful handling of concurrent data changes.

Under the Hood

PostgreSQL first scans the index to find matching row pointers (TIDs) and sets bits in a bitmap representing these rows. This bitmap is a compact structure that can be combined with others using bitwise operations. After building the bitmap, PostgreSQL sorts the row pointers by physical location and fetches rows from the heap in that order. Visibility checks are done during heap fetch to ensure only visible rows are returned. This two-phase approach reduces random disk I/O and improves cache efficiency.

Why designed this way?

Bitmap index scans were designed to optimize queries that return many rows but not the entire table. Traditional index scans fetch rows one by one, causing many random disk reads. Sequential scans read the whole table, which is wasteful if only some rows match. Bitmap scans balance these by using index information to limit heap access and fetching rows in physical order to minimize disk seeks. This design evolved from the need to handle large datasets efficiently with limited memory and disk speed.

┌───────────────┐
│ Index Scan    │
│ (Find matches)│
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Bitmap Created│
│ (Set bits)    │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Bitmap Merge  │
│ (Combine if   │
│ multiple)     │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Sort by Heap  │
│ Location      │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Heap Fetch    │
│ (Check visibility,
│  return rows) │
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Do bitmap index scans fetch rows immediately during index scan? Commit to yes or no.

Common Belief: Bitmap index scans fetch rows immediately as they find matches in the index.

Reality: Bitmap index scans only mark matching rows in a bitmap during the index scan phase; actual row fetching happens later in a separate heap fetch phase.

Why it matters: Believing rows are fetched immediately can lead to misunderstanding query performance and why bitmap scans reduce random disk reads.

Quick: Do bitmap index scans always improve performance for any query? Commit to yes or no.

Common Belief: Bitmap index scans always make queries faster than other scan methods.

Reality: Bitmap scans are beneficial mainly when many rows match but not all; for very few or almost all rows, other scans like index or sequential scans may be faster.

Why it matters: Misusing bitmap scans can cause slower queries and wasted resources.

Quick: Do bitmap index scans exclude invisible rows during bitmap creation? Commit to yes or no.

Common Belief: Bitmap index scans exclude rows invisible to the current transaction during bitmap creation.

Reality: Visibility checks happen only during heap fetch; the bitmap may include invisible rows temporarily.

Why it matters: This affects concurrency and correctness understanding, especially in complex transactional environments.

Quick: Can bitmap index scans combine multiple indexes efficiently? Commit to yes or no.

Common Belief: Bitmap index scans cannot combine multiple indexes; they scan only one index at a time.

Reality: Bitmap scans can combine bitmaps from multiple indexes using bitwise operations before fetching rows.

Why it matters: Knowing this helps understand how PostgreSQL optimizes complex queries with multiple conditions.

Expert Zone

1

Bitmap index scans can spill to disk if the bitmap grows too large, which affects performance but prevents out-of-memory errors.

2

The planner's cost estimates for bitmap scans depend heavily on accurate statistics; outdated stats can cause suboptimal plan choices.

3

Bitmap heap scans do not lock rows during bitmap creation, but locks are acquired during heap fetch, affecting concurrency behavior.

When NOT to use

Avoid bitmap index scans when queries return very few rows (use simple index scans) or nearly all rows (use sequential scans). For highly selective queries, bitmap scans add overhead. Also, if the bitmap size exceeds memory, performance may degrade due to disk spills. Alternatives include using index-only scans or tuning indexes for better selectivity.

Production Patterns

In production, bitmap index scans are common in complex reporting queries with multiple filters. DBAs monitor planner choices and update statistics to ensure bitmap scans are chosen appropriately. Combining bitmap scans with parallel query execution further improves performance on large datasets.

Connections

Query Optimization

Bitmap index scans are a key technique used by query optimizers to reduce I/O costs.

Understanding bitmap scans deepens knowledge of how query planners balance different scan methods to improve performance.

Bitwise Operations

Bitmap index scans use bitwise operations to combine multiple index results efficiently.

Knowing bitwise logic helps understand how PostgreSQL merges multiple index conditions quickly.

Cache Management in Operating Systems

Bitmap scans reduce random disk reads, improving cache utilization similar to OS disk scheduling.

Recognizing this connection explains why grouping disk accesses improves overall system performance.

Common Pitfalls

#1 Expecting bitmap index scan to always be faster than other scans.

Wrong approach:

SELECT * FROM large_table WHERE id = 12345; -- expecting bitmap scan for single row

Correct approach:

SELECT * FROM large_table WHERE id = 12345; -- planner uses simple index scan for single row

Root cause:

Misunderstanding that bitmap scans are best for many matches, not single-row lookups.

#2 Assuming bitmap index scan excludes invisible rows during bitmap creation.

Wrong approach:

Trusting bitmap creation phase to filter out uncommitted rows, leading to stale data reads.

Correct approach:

Relying on heap fetch phase for visibility checks to ensure correct results.

Root cause:

Confusing index match with row visibility in MVCC systems.

#3 Forcing bitmap scans by disabling sequential scans without considering data size.

Wrong approach:

SET enable_seqscan = off; -- forcing bitmap scans on small tables

Correct approach:

Allowing planner to choose scan method based on cost estimates.

Root cause:

Overriding planner decisions without understanding cost-based optimization.

Key Takeaways

Bitmap index scans improve query performance by separating index scanning and row fetching into two phases.

They use a bitmap to mark matching rows, allowing efficient combination of multiple index conditions.

Rows are fetched in physical order to minimize disk seeks and improve speed.

Visibility checks happen during heap fetch, ensuring correct results in concurrent environments.

Understanding when and how bitmap scans are chosen helps optimize PostgreSQL queries effectively.