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.

## 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."