Bitmap indexes are conventionally recommended for low-cardinality columns. Explain why that guidance exists, and what actually happens to the index as the number of distinct values grows into the millions.
answer
- Size ≈ rows × distinct values before compression
- Compressed total tracks set bits, ~O(rows)
- Payoff needs many rows per value
- High cardinality → sparse vectors + per-value overhead
- Criterion is rows-per-value, not absolute distinct count
basics
~20 sStorage grows with distinct values because each value needs its own bit vector, and the benefit comes from each value matching many rows. At very high cardinality the bitmaps become extremely sparse, per-value overhead dominates, and each value matches so few rows that a B+Tree does the job better.
solid answer
~60 sTwo things drive the guidance. **Size.** Uncompressed the index is *rows × distinct values* bits, so every additional distinct value adds a whole vector. Compression rescues the sparse case — long zero runs collapse — so the total does not truly explode, but per-value metadata and chunk overhead accumulate, and the index stops being dramatically smaller than a B+Tree. **Benefit.** Bitmaps pay off when a predicate matches *many* rows: representing 20% of a table as a compact bit vector and returning positions in physical order is far better than millions of random row fetches from a tree. At million-value cardinality each value matches a handful of rows — exactly the case a B+Tree descent handles optimally — so the advantage disappears. The honest criterion is not "few distinct values" but **many rows per value, with queries that combine several such predicates**. On a ten-billion-row table, a column with 100,000 distinct values still averages 100,000 rows per value and bitmaps remain viable. Cardinality relative to row count is what matters.
go deeper
Say that each distinct value needs its own bit vector, so more values means more vectors, and that bitmaps help most when lots of rows share a value.
Separate the two arguments — storage and benefit — and note that compression blunts the storage argument while the benefit argument still holds.
Reframe the rule as rows-per-value plus query shape, justify why unselective predicates are the bitmap's home turf, and mention ordering loss and batch-load assumptions.
Treat the guidance as a heuristic over a cost model: reason from selectivity, combination breadth, load pattern and the availability of columnar alternatives rather than a cardinality number.
## Restating the structure so the reasoning follows A bitmap index stores one bit vector per distinct value of the column, each vector holding one bit per row. Two quantities therefore control everything: **d**, the number of distinct values, and **n**, the number of rows. ## The size argument Uncompressed size is `n × d` bits. For n = 100 million: - d = 4 (a status flag): 50 MB. - d = 1,000 (a product category): 12.5 GB. - d = 10 million (a customer id): 125 TB. The naive extrapolation says bitmap indexes explode with cardinality. Real implementations compress, and this is where the naive story is wrong in an important way. Across all d vectors, exactly n bits are set in total (each row belongs to exactly one value). As d rises, each individual vector becomes overwhelmingly zeros, and run-length or word-aligned compression collapses those zero runs to almost nothing. The compressed total stays roughly O(n) — proportional to the number of set bits, not to `n × d`. So the real high-cardinality costs are subtler: - **Per-value overhead.** Each distinct value needs a lookup entry and at least one physical chunk. With ten million values that is ten million small objects — metadata, fragmentation, and a directory as large as a B+Tree's. - **Poor compression on scattered singletons.** A value appearing in one row still needs a chunk describing where that bit lives; the encoded form is not free. - **Maintenance overhead per changed row** grows because chunks become small and numerous. The end state is an index roughly the size of a B+Tree with none of a B+Tree's advantages. ## The benefit argument, which matters more Sizing is the lesser half. The decisive question is what the access path *does with* the result. A B+Tree index scan fetches rows one locator at a time, in key order, which is effectively random against the table. That is optimal when few rows match: three tree levels then one row fetch. It is terrible when many rows match — retrieving 20% of a large table by random fetches typically costs more than reading the whole table sequentially, which is why planners abandon indexes above a selectivity threshold. A bitmap represents "the 20% of rows that match" in a compact form, combines it with other predicates using bitwise operations before touching any data, and then produces row positions in **ascending physical order**, so table access is sequential and no page is visited twice. That is precisely the regime a B+Tree cannot serve. So the value of a bitmap is highest when **many rows share a value** — low cardinality relative to row count — and vanishes when each value is nearly unique, because then the tree's strength (going straight to one row, in order, supporting ranges and top-N) is what you need. ## The correct criterion "Low cardinality" is a proxy that misleads on very large tables. The criteria that actually predict a good fit: 1. **Rows per value is large** (equivalently, d is small relative to n — a classic rule of thumb is d below roughly 1% of n, though modern engines stretch this considerably). 2. **Queries combine several such predicates**, so bitwise AND across columns produces a small final set from individually unselective inputs. This is where bitmaps are unbeatable and where a single composite B+Tree cannot cover every ad-hoc combination. 3. **The table is loaded in batches and read heavily**, because in-place bitmap maintenance under concurrent writes is the structure's fatal weakness. 4. **Ordered access is not required** from this index, since bitmap output is in physical order. If all four hold, cardinality in the tens or hundreds of thousands can still be perfectly fine on a multi-billion-row table. ## What actually degrades as cardinality rises - Compression ratio per vector improves (more zeros) but per-value fixed cost multiplies, so total size flattens out near a B+Tree's. - Query benefit collapses: each predicate now yields few rows, so combining bitmaps buys nothing over a single tree descent. - Maintenance worsens: more, smaller chunks to rewrite per DML statement. - The value-lookup structure itself becomes large enough that finding the right bitmap is no longer trivially cheap. ## Practical guidance - Judge by *rows per distinct value*, not by an absolute distinct count. - Prefer bitmaps on the columns that appear together in filters, especially dimension keys and flags on a large fact table. - Use a B+Tree where the predicate is selective, where ranges or ordering matter, or where uniqueness must be enforced — a bitmap cannot enforce uniqueness. - Expect the engine's own cost model to decide anyway; a bitmap index that is never selected still costs load time and maintenance, so drop it. ## One-liner "Size grows with distinct values and the payoff grows with rows per value, so the index makes sense exactly when many rows share each value — and 'low cardinality' is shorthand for that ratio, not an absolute count."
- If compression keeps the total size roughly proportional to the number of rows, why is high cardinality still bad?Because the cost stops being about bytes. Each distinct value still needs a lookup entry and at least one physical chunk, so millions of values mean millions of small objects to manage and maintain. More importantly the benefit disappears: a nearly-unique value matches a handful of rows, which is exactly the case a B+Tree descent handles optimally and where bitwise combination buys nothing.
- Is a bitmap index on a 100,000-distinct-value column ever reasonable?Yes, if the table is large enough that each value still covers many rows — on a ten-billion-row fact table that is 100,000 rows per value on average. The criterion is rows per distinct value together with the query pattern, not an absolute cardinality threshold. It also requires the table to be batch-loaded rather than concurrently updated.
saying these in an interview costs you the question
- Claiming bitmap index size is literally rows × distinct values in practice, ignoring compression
- Using an absolute distinct-value threshold with no reference to table size
- Saying bitmap indexes are 'only for boolean or flag columns'
- Assuming a bitmap index can replace a unique index or enforce uniqueness
- Recommending bitmap indexes for selective point lookups on a large table