Between a plain index lookup with per-row table fetches and a full table scan, some engines offer a third option that first builds an in-memory bitmap of matching row locations and only then reads the table. What does that buy, and when would an optimizer choose it?

middleshould knowfreq 40%

answer

find first, read later
sort and dedupe page addresses
AND intersects, OR unions bitmaps
middle of the selectivity range
lossy to page level, then recheck

basics

~20 s

Collecting matches into a bitmap first lets the engine sort and deduplicate page addresses, then read table pages once each in physical order. That converts scattered random reads into a mostly sequential pass, and lets several indexes be combined before touching the table.

solid answer

~1 min

Two wins follow. I/O ordering: scattered random single-page reads become an ordered, deduplicated pass that benefits from read-ahead, and a page containing twenty matches is read once, not twenty times. Index combination: because bitmaps can be intersected and unioned, two separate single-column indexes can serve AND or OR predicates together, applying both filters before any table access.

The optimizer picks it in the middle of the selectivity range: too many matching rows for per-row random fetches to be sensible, too few to justify reading the entire table. If memory is insufficient to hold exact row locations, the bitmap degrades to page granularity, and the engine re-checks the predicate on rows within those pages.

Costs: the bitmap must be built before any row is returned, so it is not suited to fetching the first few rows quickly, and it produces rows in physical order, not index order, so it does not deliver sorted output for free.

The path runs in two stages. First the engine scans one or more indexes and records the locations of matching rows into a bitmap in memory rather than fetching each row immediately. Then it reads the table, walking pages in **physical order**, visiting each qualifying page exactly once and picking out the marked rows. Two wins follow. **I/O ordering**: scattered random single-page reads become an ordered, deduplicated pass that benefits from read-ahead, and a page containing twenty matches is read once, not twenty times. **Index combination**: because bitmaps can be intersected and unioned, two separate single-column indexes can serve `AND` or `OR` predicates together, applying both filters before any table access. The optimizer picks it in the middle of the selectivity range: too many matching rows for per-row random fetches to be sensible, too few to justify reading the entire table. If memory is insufficient to hold exact row locations, the bitmap degrades to page granularity, and the engine re-checks the predicate on rows within those pages. Costs: the bitmap must be built before any row is returned, so it is not suited to fetching the first few rows quickly, and it produces rows in physical order, not index order, so it does not deliver sorted output for free.

code

text · 6 lines

text

Bitmap Heap Scan on orders
  Recheck Cond: (status = 'NEW' AND region = 'EU')
  ->  BitmapAnd
        ->  Bitmap Index Scan on orders_status_idx  (status = 'NEW')
        ->  Bitmap Index Scan on orders_region_idx  (region = 'EU')
-- stage 1 builds and intersects bitmaps; stage 2 reads qualifying pages in order

go deeper

for a junior

Explain the core trick: list all the places the rows live first, then read those pages once each in order instead of jumping back and forth.

for a middle

Add the two benefits, ordered deduplicated page access and combining several indexes with AND or OR, and place it in the middle of the selectivity range.

for a senior

Discuss the trade-offs the optimizer weighs: startup versus total cost, lost output ordering, memory budget and the lossy fallback, and how poor clustering widens the band where it wins.

for a principal

Use it to argue about index strategy: a few well-chosen single-column indexes plus this path can cover unpredictable ad-hoc predicate combinations, while predictable hot paths still deserve purpose-built composite or covering indexes.

Why a third path exists

The two familiar paths fail in the middle. A per-row index fetch is excellent for tens of rows and awful for hundreds of thousands, because it issues that many scattered single-page reads and revisits pages. A full scan is excellent when most of the table qualifies and wasteful when five percent does. Between them is a wide band where neither is good, and that band is common in reality.

The bitmap-based path fills it by separating finding rows from reading them.

Stage one: build the bitmap

The engine walks the index for the predicate and, instead of fetching each row, records its location into an in-memory bitmap keyed by page and slot. Nothing from the table is read yet.

Because the result is a set of locations rather than a stream of rows, it supports set algebra:

Two predicates joined by AND can each drive their own index; the bitmaps are intersected, so only rows satisfying both are marked.
Two predicates joined by OR produce bitmaps that are unioned, deduplicating rows matched by both.

This is why a schema with several single-column indexes can serve multi-column predicates decently without a composite index for every combination. It is not as good as one well-chosen composite index, since each index is walked in full for its own condition, but it generalises to combinations you did not anticipate.

Stage two: read the table in physical order

The bitmap is then traversed in page order. Each page containing at least one marked row is read exactly once, and the marked rows are extracted from it. Consequences:

Deduplication. A page with twenty matching rows costs one read, whereas the per-row path could read it up to twenty times.
Ordering. Pages are visited ascending, so the access pattern is far friendlier to read-ahead and to storage that rewards contiguous requests. It is not a pure sequential scan, since non-qualifying pages are skipped, but it is much closer to one than random fetching.
Bounded worst case. Total page reads cannot exceed the table's page count, unlike the per-row path.

Lossy mode

Exact row-level bitmaps consume memory proportional to matches. When the work budget is exceeded, the engine degrades parts of the bitmap to page granularity: it remembers that a page contains matches, but not which rows. During stage two it then re-evaluates the original predicate against every row in those pages. Signs of this in a plan are a reported recheck condition and a lossy-block count. It is a graceful degradation, still bounded by table size, but it burns CPU re-checking rows.

When the optimizer chooses it

Inputs to the decision are the same as for the other paths: estimated matching rows, physical clustering, and the relative price of random and sequential reads. The pattern is:

Very few rows: plain index path wins; building a bitmap is pointless overhead.
Middle range, often roughly one to twenty percent of rows: the bitmap path wins, and the band is widest when clustering is poor, because that is exactly when per-row fetching is most punished and ordering helps most.
Most of the table: full scan wins; skipping a small minority of pages does not pay for the index reads.

Multi-predicate queries shift the balance further toward bitmaps, because index combination filters rows before any table access.

What it does not give you

No fast first row. The whole bitmap is built before the first row is emitted, so it is a poor fit for a query fetching a handful of rows and stopping early. Optimizers weigh startup cost separately from total cost for exactly this reason.
No ordering. Output arrives in physical order, so a query wanting index order must sort afterwards. A plain index scan, by contrast, can deliver sorted rows for free, which sometimes makes it the better choice even when its raw I/O is higher.
Memory use. The bitmap is real memory in the query's work budget, and exceeding it triggers the lossy behaviour described above.

The takeaway

The bitmap path exists because the expensive part of index-driven access is not finding rows, it is the disorder of fetching them. Separating the two phases lets the engine impose order on the reads, deduplicate them, and combine multiple indexes, at the price of a blocking build step and lost output ordering. Being able to state that trade cleanly is what the question is testing.

## Why a third path exists The two familiar paths fail in the middle. A per-row index fetch is excellent for tens of rows and awful for hundreds of thousands, because it issues that many scattered single-page reads and revisits pages. A full scan is excellent when most of the table qualifies and wasteful when five percent does. Between them is a wide band where neither is good, and that band is common in reality. The bitmap-based path fills it by separating **finding** rows from **reading** them. ## Stage one: build the bitmap The engine walks the index for the predicate and, instead of fetching each row, records its location into an in-memory bitmap keyed by page and slot. Nothing from the table is read yet. Because the result is a set of locations rather than a stream of rows, it supports set algebra: - Two predicates joined by `AND` can each drive their own index; the bitmaps are **intersected**, so only rows satisfying both are marked. - Two predicates joined by `OR` produce bitmaps that are **unioned**, deduplicating rows matched by both. This is why a schema with several single-column indexes can serve multi-column predicates decently without a composite index for every combination. It is not as good as one well-chosen composite index, since each index is walked in full for its own condition, but it generalises to combinations you did not anticipate. ## Stage two: read the table in physical order The bitmap is then traversed in page order. Each page containing at least one marked row is read exactly once, and the marked rows are extracted from it. Consequences: - **Deduplication.** A page with twenty matching rows costs one read, whereas the per-row path could read it up to twenty times. - **Ordering.** Pages are visited ascending, so the access pattern is far friendlier to read-ahead and to storage that rewards contiguous requests. It is not a pure sequential scan, since non-qualifying pages are skipped, but it is much closer to one than random fetching. - **Bounded worst case.** Total page reads cannot exceed the table's page count, unlike the per-row path. ## Lossy mode Exact row-level bitmaps consume memory proportional to matches. When the work budget is exceeded, the engine degrades parts of the bitmap to **page granularity**: it remembers that a page contains matches, but not which rows. During stage two it then re-evaluates the original predicate against every row in those pages. Signs of this in a plan are a reported recheck condition and a lossy-block count. It is a graceful degradation, still bounded by table size, but it burns CPU re-checking rows. ## When the optimizer chooses it Inputs to the decision are the same as for the other paths: estimated matching rows, physical clustering, and the relative price of random and sequential reads. The pattern is: - **Very few rows:** plain index path wins; building a bitmap is pointless overhead. - **Middle range, often roughly one to twenty percent of rows:** the bitmap path wins, and the band is widest when clustering is poor, because that is exactly when per-row fetching is most punished and ordering helps most. - **Most of the table:** full scan wins; skipping a small minority of pages does not pay for the index reads. Multi-predicate queries shift the balance further toward bitmaps, because index combination filters rows before any table access. ## What it does not give you - **No fast first row.** The whole bitmap is built before the first row is emitted, so it is a poor fit for a query fetching a handful of rows and stopping early. Optimizers weigh startup cost separately from total cost for exactly this reason. - **No ordering.** Output arrives in physical order, so a query wanting index order must sort afterwards. A plain index scan, by contrast, can deliver sorted rows for free, which sometimes makes it the better choice even when its raw I/O is higher. - **Memory use.** The bitmap is real memory in the query's work budget, and exceeding it triggers the lossy behaviour described above. ## The takeaway The bitmap path exists because the expensive part of index-driven access is not finding rows, it is the disorder of fetching them. Separating the two phases lets the engine impose order on the reads, deduplicate them, and combine multiple indexes, at the price of a blocking build step and lost output ordering. Being able to state that trade cleanly is what the question is testing.

A query needs only the first ten rows and stops. Why might the optimizer avoid the bitmap path even though its total cost is lower?
Because the bitmap must be fully built before a single row can be returned, so its startup cost is high while a plain index scan can emit matching rows as it walks the leaves. Optimizers track startup cost separately from total cost and prefer the low-startup path when the consumer stops early, for example with a row limit. Choosing the bitmap path there would mean paying to locate every match in order to return ten of them.
What does it mean when a plan reports a recheck condition and lossy blocks for this path?
It means the exact row-level bitmap did not fit in the query's memory budget, so parts of it were degraded to page granularity, recording that a page contains matches without recording which rows. During the table pass the engine therefore re-evaluates the original predicate against every row in those pages, which costs extra CPU. Raising the work-memory budget, or making the predicate more selective, restores exact bitmaps.

Rather than walking to a shelf each time you find a title in the catalogue, you list every shelf position first, sort the list, then walk the aisles once in order.

saying these in an interview costs you the question

Describing it as a bitmap index on disk rather than a transient in-memory structure built per query
Claiming it returns rows in index order, so no sort is needed afterwards
Assuming combining two single-column indexes is always as good as one composite index
Ignoring that the build step blocks output, making it a poor fit for early-terminating queries
Thinking it eliminates table access entirely rather than reordering and deduplicating it

Between a plain index lookup with per-row table fetches and a full table scan, some engines offer a third option that first builds an in-memory bitmap of matching row locations and only then reads the table. What does that buy, and when would an optimizer choose it?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Why a third path exists

Stage one: build the bitmap

Stage two: read the table in physical order

Lossy mode

When the optimizer chooses it

What it does not give you

The takeaway

▾common follow-ups2 questions

▾analogy~10 s

▾red flags5 flags

§ context

▾related questions4 questions

▾related topics3 topics

Why a third path exists

Stage one: build the bitmap

Stage two: read the table in physical order

Lossy mode

When the optimizer chooses it

What it does not give you

The takeaway

answer

go deeper

context