The idea: read the heap in page order, not index order
A PostgreSQL table is a heap: 8 KB pages with rows in no particular order. An index entry points at a row by its TID, (page, line pointer). When many rows match, the order in which the heap pages are read matters more than anything else. A plain Index Scan reads them in index order and may visit the same page many times. A bitmap scan first collects every matching TID, sorts them by page, and then reads each page once, in physical order.
CREATE TABLE t (a int, b int); CREATE INDEX t_a_idx ON t (a); CREATE INDEX t_b_idx ON t (b);
Index Scan: one heap fetch per index entry
An Index Scan walks the B-tree and, for each entry, fetches the row from the heap at once before it reads the next entry. The index is sorted by key, so for a range like a BETWEEN 1 AND 3 on a column that has nothing to do with where rows were inserted, consecutive entries point at unrelated pages. Each fetch is a random read, and a page needed again later may already have left the cache (Demo: Index Scan jumps between pages: 9 reads for 5 pages). An Index Scan is still the right plan for a few rows, and it returns rows in index order, which an ORDER BY or a merge join can use.
Bitmap Index Scan: build a TID bitmap
A Bitmap Index Scan reads the same index entries but does not touch the heap. It only records each TID in a TID bitmap in the backend's private memory: one entry per heap page, holding one bit per line pointer. When it is done, the bitmap is the set of matching rows, already grouped and sorted by page.
Bitmap Heap Scan: each page once, in order
The Bitmap Heap Scan above it walks the bitmap from the lowest page number to the highest. A page with no bits is skipped; every other page is read once and only the rows whose bits are set are fetched. Reads in increasing page order are close to sequential, and PostgreSQL issues prefetch requests ahead of them (effective_io_concurrency). The price: the whole bitmap must be built before the first row comes out, and the rows come out in page order, not key order (Demo: Bitmap scan reads each page once).
BitmapAnd and BitmapOr: two indexes, one heap pass
Because bitmaps are just sets of TIDs, two of them can be combined before the heap is read. For WHERE a = 1 AND b = 2 the executor builds one bitmap from t_a_idx and one from t_b_idx, and BitmapAnd keeps only the bits set in both. For a = 1 OR b = 2, BitmapOr keeps the bits set in either. A plain Index Scan can use only one index; it would have to fetch every a = 1 row and throw away the ones with the wrong b (Filter), and it cannot do an OR across two indexes at all.
In the animation Demo: BitmapAnd reads only 2 heap pages, although each index alone points to 3 and 5 pages. Demo: BitmapOr reads 5 pages once each for 7 rows.
work_mem and lossy pages
The bitmap lives in work_mem. If it would need more entries than fit, PostgreSQL makes some pages lossy: it throws away their per-row bits and keeps only one bit for the whole page, "some row here may match" (many lossy pages share one small chunk entry, so this frees memory). The scan still works, but for a lossy page the Bitmap Heap Scan must read every row on the page and evaluate the WHERE clause again. That is the Recheck Cond line in the plan. Rows that fail it are counted in Rows Removed by Index Recheck (Demo: lossy bitmap: work_mem has room for 3 entries, pages 0, 2 and 4 become lossy, and 3 extra rows are read and thrown away).
The Recheck Cond line is always printed, even when nothing was lossy; it is applied only to lossy pages (and to index types that return "maybe" matches, such as GIN or BRIN). Raise work_mem for the session if lossy= is large.
Reading EXPLAIN ANALYZE
Bitmap Heap Scan on t (actual rows=9 loops=1)
Recheck Cond: ((a >= 1) AND (a <= 3))
Rows Removed by Index Recheck: 3
Heap Blocks: exact=2 lossy=3
-> Bitmap Index Scan on t_a_idx (actual rows=9 loops=1)
Index Cond: ((a >= 1) AND (a <= 3))
| Line | Meaning |
|---|---|
Bitmap Index Scan … actual rows | TIDs the index put into the bitmap |
BitmapAnd / BitmapOr … actual rows=0 | the combine step; it does not count rows, so it always shows 0 |
Heap Blocks: exact=… lossy=… | heap pages read with per-row bits / as whole lossy pages |
Recheck Cond | the condition evaluated on rows of lossy pages |
Rows Removed by Index Recheck | rows read on lossy pages that did not match |
Index Scan … Filter, Rows Removed by Filter | rows fetched through one index and rejected by a condition that index could not check |
The page shows the mechanics. Which of these plans the planner picks, and why it uses a Seq Scan when most rows match, is on How a Query Planner Picks a Plan. See also How PostgreSQL Runs a Query (heap, TIDs, MVCC), PostgreSQL index types (BRIN always returns lossy results; GIN can only be used through a bitmap and often needs a recheck), the heap page layout and shared buffers, where the pages the scan reads are cached.
MySQL solves the same problem with Multi-Range Read and index merge: see MySQL Index Access Paths and EXPLAIN.
What the page leaves out
Real sizes: a heap page holds about a hundred rows and a lossy chunk covers 256 pages, so a few MB of work_mem hold bitmaps for millions of rows. The real tbm_lossify lossifies until the bitmap is half full, not just enough to fit. Also left out: MVCC visibility checks on every fetched row, Index Only Scans and the visibility map, the prefetching itself, parallel bitmap heap scans (one worker builds the bitmap, all share it), buffer statistics (BUFFERS), and the planner's cost model.