What is a bitmap index, and how does it physically represent the set of rows that match a particular column value?
answer
- One bitmap per distinct value, one bit per row
- Set bit position → row locator
- AND / OR of bitmaps combines predicates
- Compressed in chunks covering row ranges
- NULL gets its own bitmap; COUNT via popcount
basics
~20 sA bitmap index stores one bit vector per distinct column value, with one bit per row: bit set means that row has that value. Answering a predicate means fetching one bitmap and turning its set bits back into row locations, and combining predicates is bitwise AND or OR.
solid answer
~50 sInstead of one index entry per row, a bitmap index keeps **one bitmap per distinct value** of the indexed column, and each bitmap has **one bit per row** of the table. For a `status` column with values `NEW`, `PAID`, `SHIPPED`, there are three bit vectors. Bit *i* of the `PAID` vector is 1 exactly when row *i* has `status = 'PAID'`. To answer `WHERE status = 'PAID'`, the engine reads that one bitmap, decompresses it, and maps each set bit position back to a physical row locator. `IN ('PAID','SHIPPED')` is the bitwise OR of two bitmaps; combining with another indexed predicate is a bitwise AND. The bitmaps are stored compressed — long runs of zeros and ones collapse — and usually chunked into segments each covering a range of row positions, so the engine can read only the relevant chunk. Because of that shape it also stores a bitmap for NULL, and can answer counts by popcount without touching the table.
code
text · 6 linesrow # 1 2 3 4 5 6 7 8
status='NEW' 1 0 0 1 0 0 1 0
status='PAID' 0 1 0 0 1 0 0 0
status='SHIPPED' 0 0 1 0 0 1 0 1
WHERE status IN ('NEW','SHIPPED') -> OR -> 1 0 1 1 0 1 1 1go deeper
Get the structure right in one sentence — a bit vector per distinct value, one bit per row — and give a small worked example.
Add compression and chunking, the mapping from bit position to row locator, and why the output is in physical rather than key order.
Contrast the access-path economics with a B+Tree: fraction of rows matched, bitwise combination before table access, loss of ordering, and the read-optimised context this structure assumes.
Position it among alternatives — columnar storage, zone maps, in-memory bitmap conversion — and be explicit that the structure encodes an assumption of batch loading and read-heavy access.
## The structure Start from what a conventional B+Tree index stores: one entry per row, holding the key plus a locator for the row (a row id, or the primary key). Its size therefore scales with the number of *rows*, and each entry costs tens of bytes. A bitmap index flips the layout. For each **distinct value** in the indexed column it stores a **bit vector** whose length is the number of rows in the table. Position *i* in the vector corresponds to the *i*-th row slot; the bit is 1 if that row has that value, 0 otherwise. ``` rows: 1 2 3 4 5 6 7 8 color = 'RED' 1 0 0 1 0 0 1 0 color = 'GREEN' 0 1 0 0 1 0 0 0 color = 'BLUE' 0 0 1 0 0 1 0 1 ``` The three vectors together describe the column completely. Any row has exactly one bit set across the set of vectors (plus a separate NULL bitmap when nulls are present). ## Answering a query `WHERE color = 'RED'` is: locate the `RED` bitmap in the index's own lookup structure (usually a small B+Tree keyed by value), read it, decompress it, and walk its set bits. Each set-bit position is converted back into a physical row locator using the mapping the engine defines between bit positions and row addresses — typically position within a page range. The engine then fetches those rows, and because the bits come out in position order, the fetches are in **physical order**, which is friendly to sequential reads and never visits the same page twice. `WHERE color IN ('RED','BLUE')` is a bitwise OR of two vectors. `WHERE color <> 'RED'` is a complement (with care around NULLs). And `SELECT count(*) WHERE color = 'RED'` can be answered by counting set bits — a popcount over the compressed vector — without touching the table at all. ## Compression Stored naively the index would be *rows × distinct values* bits: a 100-million-row table with 8 distinct values would be 100 MB. That is already competitive with a B+Tree, but real implementations compress. Because each vector is mostly zeros (only the rows with that value are set), run-length encoding and word-aligned hybrid schemes collapse long zero runs to a few bytes. Compressed bitmaps for skewed or clustered data can be orders of magnitude smaller than the raw bit count. Compression has a structural consequence that shows up everywhere else in this topic: bitmaps are stored as **compressed chunks covering ranges of rows**, and any change to one bit means decompressing, editing and recompressing the whole chunk. That is why bitmap indexes read beautifully and write badly. ## NULLs Because representation is "a bitmap per value", NULL is naturally just another bitmap. `WHERE col IS NULL` is a direct bitmap lookup — a query that some B+Tree implementations handle poorly or not at all through the index. This is a small but genuine advantage worth mentioning. ## Where it beats a B+Tree, and where it does not **Bitmap wins when:** - Each value matches a large fraction of rows. A B+Tree returning 20% of a table is usually worse than a full scan (millions of random row fetches); a bitmap represents that 20% compactly and hands back sorted positions. - Several predicates must be combined. Bitwise AND across independent columns is done 64 rows per CPU word, before any table access happens. - The query is an aggregate that can be answered by counting bits. **B+Tree wins when:** - The predicate is highly selective (a point lookup on a unique-ish key) — a tree descent goes straight to the row. - Ordered access matters. A B+Tree can return rows in key order and supports range scans and top-N without a sort; a bitmap loses key ordering entirely and produces rows in physical order. - The table is written concurrently by many transactions. ## Where they live in practice Bitmap indexes as an on-disk structure are classic data-warehouse machinery: large, mostly-read fact tables loaded in batches, queried with ad-hoc combinations of dimension filters. Some engines expose them as an explicit index type; others do not offer them on disk but build equivalent bitmaps *in memory* at query time from ordinary indexes — which is why plans sometimes mention bitmap operations on tables that have no bitmap index at all. ## Interview shape The answer that lands is short and structural: "one bitmap per distinct value, one bit per row, set bits mark matching rows, compressed in chunks; predicates combine with bitwise AND/OR before touching the table." Everything else — cardinality fit, write weakness, plan operators — follows from that sentence.
- How does the engine turn a set bit back into an actual row?The index defines a mapping from bit position to physical row address — typically a page number plus a slot within a range of pages that the bitmap chunk covers. Walking set bits therefore yields row locators in ascending physical order, which makes the subsequent table access sequential and ensures each page is visited at most once.
- Can a bitmap index answer 'IS NULL' predicates?Yes, naturally. NULL is represented as just another value with its own bitmap, so an IS NULL predicate is a direct bitmap lookup. That contrasts with some B+Tree implementations where nulls are not indexed and such a predicate falls back to a full scan.
A stack of transparent sheets, one per colour, each punched with a hole for every row of that colour. Hold two sheets up together and only the rows matching both let light through.
saying these in an interview costs you the question
- Describing a bitmap index as one bit per row for the whole column rather than one bitmap per distinct value
- Assuming bitmap indexes support ordered range scans like a B+Tree
- Claiming bitmaps are stored uncompressed and therefore always huge
- Thinking a bitmap index can enforce uniqueness or serve as a primary key structure
- Believing bitmap indexes are always faster than B+Trees regardless of workload