Bitmap Scans: How PostgreSQL Combines Indexes

The one thing to understand first

A plain index scan is great for high selectivity (few rows) and a sequential scan is great for low selectivity (most rows). In between — say 1–15% of a table — both are suboptimal: the index scan jumps around the heap in random order, while the seq scan reads far too much. The bitmap scan fills this gap and is implemented in src/backend/executor/nodeBitmapHeapScan.c and the bitmap index scan nodes.

A bitmap scan trades index order for heap order: it collects all matching row locations first, then reads the heap once in physical block order. That single reordering is what turns thousands of random I/Os into mostly sequential ones — and it's why bitmaps can also intersect several indexes on the fly.

Two phases

A bitmap scan splits into a Bitmap Index Scan and a Bitmap Heap Scan:

• The bitmap index scan walks the index and, instead of immediately fetching heap rows, records the matching TIDs into an in-memory bitmap keyed by heap page.
• The bitmap heap scan then reads the heap in physical block order, visiting each needed page once and checking the flagged tuples.

Bitmap Heap Scan on orders
  Recheck Cond: (status = 'pending')
  ->  Bitmap Index Scan on idx_orders_status
        Index Cond: (status = 'pending')

Why physical order matters

Random heap access (a plain index scan over many rows) can cost one random I/O per row. By sorting access into block order, the bitmap heap scan turns that into largely sequential I/O and visits each page only once even if many matching rows live on it. This is the core performance advantage for medium-selectivity predicates.

Combining multiple indexes

Bitmaps compose with boolean logic — the headline capability. For WHERE status = 'pending' AND region = 'EU' with separate indexes on each column, PostgreSQL can build two bitmaps and BitmapAnd them; for an OR it uses BitmapOr:

Bitmap Heap Scan on orders
  ->  BitmapAnd
        ->  Bitmap Index Scan on idx_status
        ->  Bitmap Index Scan on idx_region

This means you do not always need a composite index for every predicate combination — several single-column indexes can be intersected on the fly. (A well-chosen composite index is still faster when the combination is hot.)

Lossy bitmaps

The bitmap has a memory budget (work_mem). If the exact per-tuple bitmap would exceed it, PostgreSQL degrades to a lossy bitmap that tracks whole pages rather than individual tuples. On a lossy page, the heap scan must recheck every tuple against the original condition — hence the Recheck Cond line, which does real work on lossy pages. You can spot pressure here:

EXPLAIN (ANALYZE, BUFFERS) SELECT ...;
-- Look for: "lossy=NNN" in the Bitmap Heap Scan,
-- meaning NNN page-level (rechecked) entries.

Heavy lossiness means the bitmap outgrew work_mem; raising it restores exact (tuple-level) tracking and removes recheck overhead.

Layer 3 — Watch it happen on your own database

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE status = 'pending' AND region = 'EU';

-- Bitmap Heap Scan on orders   (heap read in block order)
--   Recheck Cond: ...          (real work only on lossy pages)
--   Heap Blocks: exact=1203 lossy=0      <- exact = good
--   -> BitmapAnd
--        -> Bitmap Index Scan on idx_status
--        -> Bitmap Index Scan on idx_region

Two things to read here. First, BitmapAnd proves Postgres intersected two single-column indexes without a composite — you didn't need an index per predicate combination. Second, the Heap Blocks: exact=… lossy=… line: lossy > 0 means the bitmap outgrew work_mem and degraded to whole-page tracking, forcing a per-tuple Recheck. Raise work_mem and watch lossy drop back to zero.

Layer 4 — The levers this hands you

• **Raise work_mem** to keep bitmaps exact (tuple-level) and avoid lossy rechecks on large result sets.
• Keep statistics accurate so the planner switches between bitmap / plain index / seq scan at the right selectivity crossover.
• Promote hot AND-combinations to a composite index — an on-the-fly BitmapAnd is convenient, but a purpose-built composite index is faster when one combination dominates.
• Remember bitmaps return no order — if a query needs sorted output, a plain index scan may win by avoiding a later sort.

Layer 5 — What an Oracle DBA should expect vs what they get

The name "bitmap" means something very different in each engine — this trips up Oracle DBAs constantly:

• Transient bitmaps, not bitmap indexes. Oracle's bitmap indexes are a persistent on-disk structure for low-cardinality columns (and they serialize concurrent DML). PostgreSQL builds its bitmaps in memory at query time from ordinary B-tree indexes, then throws them away — no DML locking concern.
• Index combination is automatic. What Oracle achieves with BITMAP AND/BITMAP CONVERSION over bitmap indexes, Postgres does ad-hoc via BitmapAnd/BitmapOr over B-trees — no special index type required.
• **work_mem governs accuracy.** The exact-vs-lossy degradation has no Oracle analogue; it's a direct consequence of the per-operation memory budget covered earlier.
• No hint. You influence it through statistics and work_mem, not an INDEX_COMBINE hint.

Key takeaway

A bitmap scan walks the index into an in-memory bitmap of row locations, then reads the heap once in physical block order — ideal for medium selectivity and for intersecting several single-column indexes with BitmapAnd/BitmapOr. Watch Heap Blocks: lossy in EXPLAIN (ANALYZE, BUFFERS): lossy pages mean the bitmap exceeded work_mem and now pays a recheck cost. Keep stats accurate, raise work_mem to stay exact, and build a composite index when one AND-combination is permanently hot.