A query filters a very large table on five different columns at once, none of which is selective on its own. Explain how a bitmap-based access path combines those predicates, and why that can beat choosing the single best index and filtering the rest.
answer
- One bitmap per predicate, then AND/OR
- 64 rows per machine word, before touching data
- Fetches ∝ final intersection, not best single predicate
- k single-column indexes cover all 2^k filter combinations
- Costs: CPU/memory, blocking, ordering lost, correlation breaks estimates
basics
~20 sThe engine gets a bitmap of matching rows for each predicate, then bitwise ANDs them — 64 rows per machine word — producing the final row set before touching the table. Only surviving rows are fetched, and in physical order, instead of fetching everything one predicate matched.
solid answer
~60 sEach predicate is turned into a bitmap of matching row positions — read directly from a bitmap index, or built in memory from a B+Tree scan. Those bitmaps are then combined with bitwise **AND** for conjunctions and **OR** for disjunctions, word at a time, so 64 row positions are evaluated per CPU instruction. Only the surviving positions are converted to row locators, and they come out in ascending physical order. The alternative is to pick the single most selective index, fetch every row it matches, and evaluate the other four predicates on each fetched row. If each predicate keeps 10% of a billion-row table, the single-index plan fetches 100 million rows at random to keep 10,000. The bitmap plan intersects first and fetches 10,000. So the win is that **table access is proportional to the final result, not to the best individual predicate** — and it is sequential rather than random. The costs: building and merging bitmaps consumes CPU and memory, ordering is lost, and it only pays when the intersection is far smaller than each input.
code
text · 7 linesTable Access by row-id (rows=10,000)
<- BitmapAnd
<- Bitmap index scan region = 'EU' (bitmap covers ~100,000,000 rows)
<- Bitmap index scan channel = 'WEB' (bitmap covers ~100,000,000 rows)
<- BitmapOr
<- Bitmap index scan status = 'NEW'
<- Bitmap index scan status = 'HELD'go deeper
Say that each condition produces a bitmap and the engine ANDs them together, so only rows satisfying everything are read from the table.
Quantify it with selectivities, explain why fetching by a single index is worse, and mention that results come back in physical order.
Discuss the plan-choice boundaries: memory budget and degradation, blocking behaviour versus a LIMIT with ordering, and mis-estimation when predicates are correlated.
Argue the schema-level point — composable single-column indexes covering all filter subsets versus a combinatorial explosion of composite indexes — and where columnar scanning replaces the whole approach.
## The problem this solves Consider a fact table of one billion rows and a query filtering on five dimensions — region, channel, product category, customer segment, and a status flag. Suppose each predicate individually keeps about 10% of rows. Their conjunction, if roughly independent, keeps 0.1⁵ = 0.001% — about 10,000 rows. A planner with only single-column B+Tree indexes has three options, all bad: 1. **Full scan**: read all one billion rows and evaluate five predicates. Sequential, but a billion rows of I/O. 2. **Best single index**: pick the most selective of the five, fetch its 100 million matching rows *by random locator*, and filter. One hundred million random row fetches is typically far worse than the full scan. 3. **A composite index** on all five columns in some order. This works for the queries whose predicates match that column order and leading prefix, but ad-hoc analytics filters on arbitrary subsets — you would need many composite indexes to cover all combinations, and each is expensive to store and maintain. ## What bitmap combination does The access path becomes: 1. **Produce a bitmap per predicate.** With a bitmap index, this is reading (and OR-ing, for an IN list or a range of values) the relevant stored vectors. Without one, the engine can scan an ordinary index and set a bit for each matching row position, materialising a bitmap in memory. 2. **Combine with bitwise operators.** `AND` for conjunctions, `OR` for disjunctions, complement for negation. These operate on machine words: one 64-bit AND settles 64 candidate rows. The work is CPU-bound, cache-friendly, and involves no table access at all. 3. **Convert the surviving bits to row locators** and fetch, in ascending physical order. The decisive property: **table access is proportional to the size of the final intersection**, not to the size of the most selective single predicate. In the example, 10,000 fetches instead of 100 million. A second, quieter benefit: the fetches are in physical order. Each data page is visited at most once even if 50 result rows live on it, and the access pattern is friendly to read-ahead. Random locator-by-locator fetching does neither. ## Why this suits many single-column indexes rather than one wide composite A composite B+Tree serves predicates that match its leading columns. Five columns filtered in arbitrary subsets would need an impractical number of composite indexes to cover every combination. Five *separate* bitmap-friendly indexes cover all 2⁵ combinations, because any subset can be intersected. That composability is the real architectural argument for bitmaps in ad-hoc analytical workloads, and it is why data-warehouse schemas with many low-cardinality dimension keys are their classic home. ## Costs and when it does not pay - **CPU and memory.** Building and merging bitmaps is real work. Each bitmap must be materialised at least in part, and memory is bounded; exceeding the budget forces degradation (typically to coarser, page-level granularity, which then requires re-checking the predicates on fetched rows). - **Blocking.** The bitmap must be substantially built before the first row is emitted. For a query with a small LIMIT and an ordering that an index could satisfy directly, that is strictly worse — a tree scan streams the first rows immediately. - **Ordering is lost.** The result comes out in physical order. Any required sort order becomes a separate sort operation. - **No benefit when the intersection is not much smaller than the inputs.** If one predicate is already highly selective, plain index access is simpler and cheaper. If all five predicates are correlated so the intersection is still 8% of the table, a full scan probably wins. - **Estimation risk.** The planner assumes some degree of independence between predicates when estimating the size of the intersection. Correlated columns make it under-estimate the result, choose the bitmap path, and then fetch far more rows than expected. ## Negation and NULLs A conjunct like `NOT status = 'X'` becomes the complement of that value's bitmap, but complementing must account for NULLs: rows where the column is NULL satisfy neither the predicate nor its negation under SQL three-valued logic, so the engine excludes them using the NULL bitmap rather than blindly flipping bits. ## What to say "Turn each predicate into a bitmap, AND them together in registers, then fetch only the survivors, in physical order. That makes table access proportional to the final result rather than to the best single predicate, and a handful of single-column indexes covers every subset of filters instead of needing a composite index per combination."
- Why can five single-column indexes be preferable to one five-column composite index for this workload?A composite index only serves predicates matching its leading columns in order, so covering arbitrary subsets of five filters would require an impractical number of composite indexes. Bitmaps from five separate indexes can be intersected in any combination, covering all subsets with five structures. The trade is CPU and memory to merge bitmaps versus a single tree descent that a well-matched composite index would give.
- When would the planner reject the bitmap combination in favour of a plain index scan or a full scan?It rejects it when one predicate is already highly selective, since a direct tree descent to a few rows is cheaper than building bitmaps; and when the combined result is still a large fraction of the table, since a sequential full scan then beats any indexed access. It is also a poor choice when the query needs the first few rows in index order, because building a bitmap blocks before any row is emitted.
- What goes wrong when the filtered columns are strongly correlated?The optimizer typically estimates the intersection by multiplying selectivities, which assumes independence. Correlated columns make the true intersection much larger than estimated, so the plan is chosen on the promise of fetching a few thousand rows and then fetches millions. Multi-column statistics, or a composite index matching the real access pattern, are the usual remedies.
saying these in an interview costs you the question
- Thinking the engine fetches rows for each predicate and then joins the row sets, rather than merging bitmaps before any table access
- Claiming bitmap combination is always better than a single selective index
- Forgetting that bitmap output loses index ordering and blocks before the first row
- Assuming the intersection estimate is reliable when the filtered columns are correlated
- Believing bitwise AND requires decompressing the whole table's worth of bits row by row