Postgres Bitmap Heap Scan Explained with Examples

TL;DR

A Bitmap Heap Scan isn’t Postgres giving up. It’s a deliberate trade: the planner knows that bouncing row-by-row through an index causes too much random I/O. Instead, it builds an in-memory bitmap of matching row locations, sorts them by physical block order, and reads the table mostly sequentially. You spend a little CPU and memory to slash heap fetches. Once you understand that arithmetic, “why didn’t my index work?” turns into “right, that makes sense.”

---

The Setup: When Your Index “Should” Work

Someone adds a composite index on (customer_id, order_date), then queries on order_date alone. They expect a fast Index Scan. Instead, Postgres chooses a Bitmap Heap Scan.

Build the example:

CREATE TABLE orders (
    id          SERIAL PRIMARY KEY,
    customer_id INTEGER NOT NULL,
    order_date  DATE    NOT NULL,
    total       NUMERIC(8,2),
    filler      TEXT
);

INSERT INTO orders (customer_id, order_date, total, filler)
SELECT
    (random()*99999)::int + 1,
    '2023-01-01'::date + (random()*729)::int,
    (random()*1000)::numeric(8,2),
    repeat('x', (random()*100)::int)
FROM generate_series(1, 2000000);

CREATE INDEX idx_orders_customer_date
    ON orders (customer_id, order_date);

ANALYZE orders;

Query using only the second column:

EXPLAIN (ANALYZE, BUFFERS, COSTS ON)
SELECT * FROM orders
WHERE order_date = '2024-03-15';

Bitmap Heap Scan on orders  (cost=12.04..1541.59 rows=1362 width=62)
                            (actual time=1.844..6.101 rows=1372 loops=1)
   Recheck Cond: (order_date = '2024-03-15'::date)
   Heap Blocks: exact=1012
   Buffers: shared hit=1020 read=8
   ->  Bitmap Index Scan on idx_orders_customer_date
         (cost=0.00..11.70 rows=1362 width=0)
         (actual time=1.644..1.644 rows=1372 loops=1)
         Index Cond: (order_date = '2024-03-15'::date)
         Buffers: shared hit=12 read=4
 Planning Time: 0.215 ms
 Execution Time: 6.349 ms

The composite index column order means order_date is not the leading key. A plain Index Scan would jump randomly through the heap because the index is sorted by customer_id first. Instead, the Bitmap Heap Scan collects all matching tuple IDs, sorts them, and visits heap pages in order.

---

Bitmap Index Scan vs Index Scan: How They Differ

An Index Scan traverses the index tree row by row, fetches the corresponding heap page for each match, and may revisit the same page many times if rows are scattered. That random access pattern kills performance when many rows match.

A Bitmap Index Scan reads only the index entries, builds a bitmap, and defers all heap access to the subsequent Bitmap Heap Scan. That scan sorts page references so each heap page is read at most once, even if it holds dozens of matching rows. You trade memory (for the bitmap) and CPU (for sorting) for drastically reduced I/O.

The planner picks this when the estimated row count is too high for efficient single-pointer lookups but low enough to fit the bitmap in work_mem.

---

Heap Blocks Exact vs Lossy and the work_mem Limit

The work_mem setting controls how much memory the bitmap can use. If the bitmap would exceed work_mem, Postgres switches to lossy mode: it tracks heap pages instead of individual rows. Each set bit means “at least one match on this page” rather than a specific tuple ID. This reduces precision but keeps the operation within memory bounds.

Look at your EXPLAIN output:

• Heap Blocks: exact=1012 — every set bit pointed to a precise row; no lossy compression.
• Heap Blocks: exact=800 lossy=1200 — the bitmap ran out of memory and fell back to page-level tracking for part of the scan.

When lossy pages appear, the Recheck Cond line in the plan becomes critical.

---

Understanding Recheck Cond in Postgres EXPLAIN

Recheck Cond is the filter condition the Bitmap Heap Scan reapplies after fetching a heap page. Why the redundancy? The bitmap stores (page, offset) pairs. But when lossy, it only knows that a page contains at least one matching row—not which rows. Every row on that lossy page must be re-evaluated against the original WHERE clause.

Even with an exact bitmap, visibility checks (transaction isolation) may require rechecking condition to discard dead tuples. The Recheck Cond in EXPLAIN shows that Postgres performs this step. It does not mean the index condition was ignored; it’s a safeguard.

---

BitmapAnd and BitmapOr: Combining Multiple Bitmaps

When your query has WHERE clauses on two indexed columns connected by AND or OR, Postgres may build separate bitmaps and combine them:

• BitmapAnd performs a bitwise AND. Both indexes must flag a page for a row to qualify. Common when you filter on two columns with separate single-column indexes.
• BitmapOr performs a bitwise OR. Either index can flag a page. Common with OR conditions.

Example combining order_date and customer_id:

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders
WHERE order_date = '2024-01-01'
   OR customer_id = 50000;

You’ll see BitmapOr with two Bitmap Index Scan children, followed by a single Bitmap Heap Scan that uses the merged bitmap. The plan avoids scanning the table twice.

---

Composite Index Column Order and Bitmap Plans

This is where knowledge turns into design power. Our idx_orders_customer_date has customer_id first. Queries that filter on both columns or just customer_id get fast Index Scans or Index Only Scans. Queries that filter on only order_date get Bitmap Heap Scans, which work surprisingly well for moderate selectivity.

If your workload runs that lone order_date predicate frequently, you might add a separate index on (order_date). But first check whether the Bitmap Heap Scan is already fast enough. Composite index column order matters most when you want to avoid bitmap plans entirely for latency-critical single-value lookups.

---

When the Planner Chooses a Bitmap Heap Scan

It comes down to cost estimates:

• Selectivity is moderate: very few rows → Index Scan; very many rows → Sequential Scan; in between → Bitmap Heap Scan.
• Rows are scattered: if matching rows are physically co-located, a Bitmap Heap Scan’s advantage shrinks.
• Effective cache: shared hit counts show whether pages are already in memory, lowering the penalty of scattered heap access.

Next time you see that node in EXPLAIN, read it as “Postgres is batching my heap I/O to keep things efficient” rather than a fallback path.

Monitoring Bitmap Heap Scans in Practice

Knowing how Bitmap Heap Scans work is half the battle; spotting when they degrade is the other. In production, you'll want to watch for plans where Heap Blocks flips to mostly lossy pages, or where the Bitmap Heap Scan consistently accounts for a disproportionate share of I/O. Higher-than-expected Buffers counts or spikes in work_mem consumption can signal that the planner's cost estimates are drifting and a different index or query pattern would serve better.

Tools like MyDBA can automatically flag queries with excessive lossy bitmap scans, track the work_mem usage per-plan node, and alert you before a routine query starts thrashing the buffer cache. That kind of visibility turns a happy accident of the planner into a deliberate, monitored optimization.

Indexing Desk builds MyDBA, a Postgres monitoring and health-check tool — https://mydba.dev/?utm_source=devto&utm_medium=platform&utm_campaign=postgres-bitmap-heap-scan-explained

Ready to stop guessing about your query plans? Give MyDBA a spin at https://mydba.dev/?utm_source=devto&utm_medium=platform&utm_campaign=postgres-bitmap-heap-scan-explained and see what your Bitmap Heap Scans are really up to.