A query plan on a table that has only ordinary B+Tree indexes shows a bitmap being built from an index scan and then used to read the table. What is the engine doing there, why does it bother building a bitmap, and what does it cost?

## What the operator is Several engines can build a bitmap **at query time**, in memory, from an ordinary B+Tree index. It is a two-phase access path: - **Phase 1 (index side):** scan the index for entries matching the predicate. Rather than fetching each row as it goes, set a bit for each matching row location in an in-memory bitmap sized to cover the table's pages/rows. - **Phase 2 (table side):** walk the bitmap in ascending order and fetch the marked rows from the table. Engines name this differently — a bitmap index scan feeding a bitmap heap scan; index intersection or index merge; bitmap conversion from row ids. The mechanism is the same, and it does **not** require any bitmap index to exist on disk. ## Why bother **Turn random I/O into ordered I/O.** A plain index scan produces row locations in *key* order, which relative to the table is essentially random. If 50,000 matching rows are spread across a table, the engine issues 50,000 fetches in an unpredictable order and may touch the same page dozens of times (once per matching row on it). Buffered pages soften this, but on a table larger than memory it is brutal. A bitmap sorts the work implicitly: bits are in physical position order, so pages are visited once, in ascending order, and the storage layer can prefetch. **Combine indexes.** Two or more index scans can each produce a bitmap, which are then ANDed (conjunction) or ORed (disjunction) before touching data. This is how an engine serves `WHERE a = 1 AND b = 2` with two single-column indexes when no composite index exists, and how it serves `WHERE a = 1 OR b = 2` at all — an OR across different columns cannot be served by a single index scan without duplicates, but a bitmap OR deduplicates for free because a bit is either set or not. **Deduplication.** Because each row has exactly one bit, a row matched by several branches of an OR is fetched once. Merging row-id lists would require an explicit dedup step. ## When the planner chooses it Think of three bands of selectivity: - **Very selective** (a handful of rows): plain index scan wins. Building a bitmap is pointless overhead, and the index scan can stream results in key order. - **Middle band** (enough rows that random fetches hurt, few enough that reading everything is wasteful): bitmap access wins. This band is often surprisingly wide — roughly from a fraction of a percent up to a few percent of a large table. - **Unselective** (a large fraction of rows): full scan wins; the index and the bitmap are both overhead. The planner also reaches for it whenever combining multiple indexes is the only way to use indexes at all for the predicate. ## The costs, in the order they bite **Blocking.** The bitmap must be built (at least for the relevant index) before the first result row can be produced. For a query with `ORDER BY indexed_col LIMIT 10`, a plain index scan returns the first ten rows almost immediately; a bitmap path builds the entire matching set, fetches it, sorts it, and only then returns ten. This is a classic plan regression when statistics mis-estimate row counts. **Loss of ordering.** Output is in physical row order. Any required ordering becomes an explicit sort operator, with its own memory and possible spill to disk. **Memory bound and lossy degradation.** The bitmap is sized against a memory budget. If the matching set is large enough that an exact row-granular bitmap will not fit, the engine degrades to **page granularity**: the bit means "this page contains at least one candidate row". The plan then must **re-check the original predicate against every row on each fetched page**, because it no longer knows which rows on the page qualified. That recheck is real CPU and it can discard the majority of rows examined. Plans surface this as a recheck step and often as a count of rows removed by it. **CPU to build and merge.** Setting bits and ANDing bitmaps is cheap per row but not free, and merging several large bitmaps costs memory bandwidth. ## How to read and act on it Signs worth acting on: - **Lossy/page-granular bitmaps with a large recheck count**: the memory budget for the operation is too small for the result size, or the query is simply matching far more rows than a good plan would. Raising the operation's memory allowance helps; a better-matched composite index usually helps more, because it eliminates the need to combine at all. - **A bitmap combination of many indexes on the same table appearing repeatedly**: strong evidence that a composite index on the commonly-filtered columns would serve better, or that the table wants a different physical organisation. - **A bitmap path chosen for a small `LIMIT` with an `ORDER BY`**: usually a row-estimate error; fix the statistics rather than the plan. - **Bitmap paths dominating a table whose rows are physically scattered**: clustering the table by the filtering key reduces the number of pages the bitmap touches dramatically. ## Relationship to on-disk bitmap indexes The conceptual machinery is identical — bit vectors over row positions, bitwise combination, ordered fetch. The difference is lifetime and storage: an on-disk bitmap index is persistent, maintained by DML (badly, under concurrency), and available for any query; a query-time bitmap is built fresh per execution from ordinary indexes, costs nothing to maintain, and never causes write contention. That is why engines that decline to implement persistent bitmap indexes still get most of the read-side benefit. ## One-liner "It is an in-memory bitmap built from a B+Tree scan so the table can be read once, in physical order, and so several indexes can be intersected before any row is fetched — at the price of blocking, lost ordering, and a memory-bounded degradation to page granularity that forces a predicate recheck."