Bitmap Heap Scan vs Index Scan Thresholds #

Between “look up one row by key” and “read the whole table” sits a third access path that most plans use more often than either: the bitmap scan. It reads the index first, collects every matching tuple pointer into a bitmap, sorts that bitmap into physical page order, and only then touches the heap — once per page, in order.

Understanding when the planner switches to it, and how to read its two distinctive fields, explains a large fraction of real plans. The broader access-path comparison is in sequential vs index scans.

The Condition That Triggers the Switch #

A plain Index Scan interleaves index and heap access: read an index entry, fetch its heap tuple, repeat. That is optimal for a handful of rows, and increasingly bad as matches multiply, because the heap accesses arrive in index order rather than page order and the same page may be visited many times.

A Bitmap Heap Scan decouples the two phases. The Bitmap Index Scan beneath it produces the bitmap; the heap scan above walks it in physical order. Each heap page is read once, and the access pattern is friendly to readahead.

The planner switches when estimated matching rows are high enough that page revisits become likely. Two inputs move the threshold:

Access order: plain index scan versus bitmap scan The top row shows heap pages visited in index order, jumping back and forth and revisiting pages. The bottom row shows the same pages visited once each in ascending physical order after the bitmap is sorted. Index Scan — heap touched in index order p1p2 p3p4 p5p6 p7p8 random order pages revisited Bitmap Heap Scan — bitmap sorted into page order first single forward pass, each page read once readahead-friendly

Reading the Two Distinctive Fields #

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM events WHERE account_id IN (91, 204, 771) AND created_at > '2026-06-01';

Bitmap Heap Scan on events  (actual time=48.2..612.4 rows=184220 loops=1)
  Recheck Cond: (account_id = ANY ('{91,204,771}') AND created_at > '2026-06-01')
  Rows Removed by Index Recheck: 2841022        -- work caused by lossy pages
  Heap Blocks: exact=18402 lossy=91204          -- 83% of pages degraded
  Buffers: shared hit=41208 read=68398
  ->  Bitmap Index Scan on events_account_created_idx  (actual time=44.1..44.1 rows=184220 loops=1)
        Index Cond: (account_id = ANY ('{91,204,771}') AND created_at > '2026-06-01')

Heap Blocks: exact=… lossy=… is the field to read first. Exact pages carry individual tuple pointers, so only the matching tuples are examined. Lossy pages are marked whole, because the bitmap outgrew work_mem and the executor compressed it. Every tuple on a lossy page must be re-tested against the Recheck Cond, and the ones that fail are counted in Rows Removed by Index Recheck.

Here 2.8 million rows were fetched and discarded to return 184,220 — roughly fifteen wasted rows per useful one. That is not a plan-choice problem; it is a memory problem with a one-line fix.

Step-by-Step Resolution #

  1. Check for lossy pages first. lossy=0 means the bitmap fit and the scan is behaving as designed; there is nothing to fix.

  2. Raise the allowance for the statement when the bitmap was degraded:

    BEGIN;
SET LOCAL work_mem = '256MB';
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM events
  WHERE account_id IN (91,204,771) AND created_at > '2026-06-01';
COMMIT;

    The bitmap needs about one bit per heap page for lossy mode and considerably more for exact pointers, so the required memory scales with the number of matching rows.

  3. Check correlation to understand why the bitmap path was chosen at all:

    SELECT attname, correlation, n_distinct
  FROM pg_stats WHERE tablename = 'events' AND attname IN ('account_id','created_at');

    A correlation near zero on the leading column means scattered matches; near one means the plain index scan would have been nearly sequential.

  4. Improve locality if the query is important enough. CLUSTER physically reorders a table by an index, raising correlation — at the price of an exclusive lock and no maintenance of the ordering afterwards.

  5. Or remove the heap access entirely with a covering index, so no bitmap is needed:

    CREATE INDEX CONCURRENTLY events_account_created_covering
  ON events (account_id, created_at) INCLUDE (payload_id, status);

    The trade-offs are set out in building effective covering indexes.

  6. Re-measure and compare Buffers, not just time. A successful fix shows fewer heap reads, lossy=0, and a Rows Removed by Index Recheck of zero.

Exact and lossy heap blocks before and after Two stacked bars. Before, a small exact segment and a large lossy segment, with nearly three million rows removed by recheck. After raising work_mem, the bar is entirely exact with zero rows removed. before exact 18,402 lossy 91,204 — every tuple re-checked Rows Removed by Index Recheck: 2,841,022 · 612 ms after exact 41,208 Rows Removed by Index Recheck: 0 · 108 ms exact pages lossy pages

Before and After #

-- BEFORE: work_mem = 4MB
Bitmap Heap Scan  Heap Blocks: exact=18402 lossy=91204
                  Rows Removed by Index Recheck: 2841022
Execution Time: 612.4 ms

-- AFTER: SET LOCAL work_mem = '256MB'
Bitmap Heap Scan  Heap Blocks: exact=41208
                  (no lossy, no recheck removals)
Execution Time: 108.2 ms

The plan node type never changed. Only the bitmap’s fidelity did, which is why this failure is so easy to miss when reading plans by node name alone.

Common Pitfalls #

Reading a bitmap scan as a mistake. It is usually the right path for medium selectivity. Diagnostic signal: lossy=0 and a reasonable buffer count. Fix: none.

Fixing lossy pages with an index change. The bitmap’s fidelity depends on work_mem, not on the index. Diagnostic signal: lossy pages with a perfectly appropriate index. Fix: raise the allowance for that statement.

Ignoring Rows Removed by Index Recheck. It is the direct measure of wasted heap work and is easy to overlook beside the row counts. Diagnostic signal: a recheck count far above the returned rows. Fix: eliminate lossy pages.

Running CLUSTER casually. It takes an ACCESS EXCLUSIVE lock, rewrites the table, and the ordering decays with subsequent writes. Diagnostic signal: someone proposing it as routine maintenance. Fix: use it only for stable, read-mostly tables, and measure correlation afterwards.

Access path by selectivity band A horizontal band from very selective to very broad. Index scan occupies the leftmost region, bitmap heap scan the middle, and sequential scan the right, with a note that low column correlation shifts the boundaries leftward. Index Scan Bitmap Heap Scan Seq Scan 0.01% of rows ~1–15% most of the table low correlation moves both boundaries to the left; high correlation moves them right

Frequently Asked Questions #

What does Heap Blocks: lossy mean? The bitmap exceeded work_mem, so entries were degraded from tuple pointers to whole-page markers. Those pages are read in full and every tuple is re-tested against the Recheck Cond, with the failures counted as Rows Removed by Index Recheck.

Why a bitmap scan instead of a plain index scan? Because it sorts matching tuple pointers into physical page order before touching the heap, so each page is read once and in a readahead-friendly order. That wins as soon as enough rows match that a plain index scan would revisit pages.

How does correlation affect the choice? Directly. High correlation means the plain index scan already reads nearly sequentially, so it stays cheap over wide ranges. Low correlation scatters the matches, and the bitmap path takes over at much lower selectivity.