Bitmap heap scan: the node in between

A bitmap heap scan is the plan the executor uses when an index identifies many rows scattered across a table. The index is read first and every match is recorded in a bitmap of page locations; the heap is then read once, visiting each marked page in file order. It avoids the repeated random fetches of an index scan and the wasted reads of a sequential scan, and it always appears as a pair of nodes, one building the bitmap and one consuming it.

Three lines in the plan that carry the detail

The child node is where the index work happens and the parent is where the table is read, so a bitmap index scan never appears alone. Reading the pair as one operation is the right mental model; the split exists because more than one index can feed the same bitmap.

That is the capability most easily missed. Two indexes on the same table can be combined, their bitmaps intersected or unioned, and the heap read once for the result. It is the only plan shape in which a single table scan uses two indexes at once, and it is why adding a second single-column index sometimes helps a two-column predicate that a composite index would serve better.

Recheck Cond reads like duplicated work and usually is not performed. The bitmap is built in memory bounded by work_mem, and when it does not fit it degrades from recording individual rows to recording whole pages. At that point the condition genuinely has to be re-applied to every row on those pages, and the plan says so by splitting its heap block count into exact and lossy. A plan showing only exact blocks did not recheck anything; the line is printed because the node is capable of it.

Reading the block counts

The counts under the heap node are the measurement that matters.

CREATE TABLE event (id int, kind int, body text);
INSERT INTO event SELECT g, g % 500, repeat('x', 40) FROM generate_series(1, 400000) g;
CREATE INDEX event_kind_idx ON event (kind);
ANALYZE event;
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF, BUFFERS OFF)
SELECT count(*) FROM event WHERE kind IN (3, 17, 41);

CREATE TABLE
INSERT 0 400000
CREATE INDEX
ANALYZE
                                  QUERY PLAN                                   
-------------------------------------------------------------------------------
 Aggregate (actual rows=1.00 loops=1)
   ->  Bitmap Heap Scan on event (actual rows=2400.00 loops=1)
         Recheck Cond: (kind = ANY ('{3,17,41}'::integer[]))
         Heap Blocks: exact=1112
         ->  Bitmap Index Scan on event_kind_idx (actual rows=2400.00 loops=1)
               Index Cond: (kind = ANY ('{3,17,41}'::integer[]))
               Index Searches: 3
(7 rows)

Twenty-four hundred rows living on eleven hundred pages, which is the shape that makes this plan worth choosing: an index scan would have fetched a page for roughly every second row, in index order, while this reads each of those pages once going forwards. No lossy blocks appear, so the recheck cost nothing. The count of index searches on the last line is printed by 18.6 and by none of the older versions this ran on. When a lossy count does appear, the fix is more memory for that statement rather than a different index.

Where to take a plan you do not like

If the node is reading most of the table anyway, the question is the one in sequential scan versus index scan, and the answer usually lies in physical correlation rather than in the index definition. If the heap visit is the expensive part and the query only needs indexed columns, the plan to aim for is an index-only scan. Whether the index earns its place at all is the subject of unused and missing indexes.