Why architecture matters here
The architecture matters because it targets a workload where the default index is genuinely weak. Analytic queries routinely combine several low-selectivity predicates, and the combination is what is selective — 'EU' alone matches a third of rows, but 'EU and active and mobile and enrolled-this-quarter' matches a small slice. A B-tree per column can resolve at most one predicate efficiently and must then fetch and filter; there is no cheap way to intersect the row sets of several low-cardinality predicates. Bitmap indexes make that intersection the fundamental operation.
It matters for performance because the operations map onto hardware. Bitwise AND, OR, and NOT over bit arrays, and population count to tally set bits, are among the cheapest things a CPU does, and they stream linearly through memory with excellent cache behavior. Combining five predicates is five bitmap operations, regardless of how many rows each matches. Aggregations like COUNT and GROUP BY over indexed columns can often be answered from the bitmaps alone, without touching the base table, which is why columnar analytic engines lean on bitmap (and bitmap-like) indexing so heavily.
It matters for size because low-cardinality bitmaps compress extraordinarily well. A raw bitmap uses one bit per row, which is already tiny compared to storing row pointers, but real bitmaps for skewed low-cardinality data are dominated by long runs of identical bits. Run-length encoding and modern hybrid schemes like Roaring bitmaps shrink them further while still supporting fast boolean operations directly on the compressed form, so the index can be a small fraction of the data it indexes and still be queried without full decompression.
And it matters to know the boundary, because the same design that makes bitmaps fast on the right column makes them a liability on the wrong one. Cardinality is the axis: a bitmap per distinct value is wonderful for a dozen values and a disaster for a million. Update pattern is the other axis: flipping a row's value touches multiple bitmaps and, in traditional implementations, locks coarsely, so a table under heavy transactional churn suffers. Choosing a bitmap index is therefore an explicit statement that the column is low-cardinality and the table is read-heavy — get either wrong and the index hurts more than it helps.
The architecture: every piece explained
The per-value bitmap is the core structure. For each distinct value v in the indexed column, there is a bitmap of length N (the number of rows), where bit i is 1 if row i has value v and 0 otherwise. A column with k distinct values thus has k bitmaps, and every row contributes exactly one set bit across the whole set (since each row has one value). This is why low k is essential: storage and query cost scale with the number of distinct values.
Bitwise operators are the query engine. AND intersects predicates (both true), OR unions them (either true), and NOT negates (the complement bitmap, all rows without that value). Any boolean combination of equality predicates over bitmap-indexed columns reduces to a tree of these operations, evaluated bitmap by bitmap, producing a final result bitmap of matching rows.
Compression keeps the bitmaps small and fast. Naively, k bitmaps of N bits could be large, but low-cardinality data produces long runs, so run-length encoding (and word-aligned hybrid schemes, or Roaring bitmaps that switch representation per chunk based on density) compress them massively. The important property is that these encodings support boolean operations on the compressed representation — you do not decompress to a full bit array to AND two bitmaps, you operate on the runs/containers directly, which is what keeps queries fast at low storage cost.
Row identification connects bitmaps back to data. The set bits of the final result bitmap are row positions (or map to row IDs) in the base table; the engine iterates the set bits to fetch the matching rows, or, for pure aggregates, never fetches at all. A population count over the result bitmap answers COUNT directly, and GROUP BY over an indexed column can be computed by popcounting each value's bitmap ANDed with the filter bitmap.
Bitmap-encoded variants extend the idea. Bit-sliced indexing encodes numeric values across a set of bitmaps (one per bit position) to support range predicates, and binned bitmaps group ranges of a higher-cardinality column into buckets so bitmaps stay manageable. These variants push bitmap indexing beyond pure equality on tiny domains, but they trade some of the simplicity — and the operational guidance below still centers on the classic low-cardinality equality case where bitmaps are unambiguously the right tool.
End-to-end flow
Trace the query WHERE region = 'EU' AND status = 'active' AND channel = 'mobile' with a COUNT. The planner recognizes all three columns are bitmap-indexed and low-cardinality. It fetches the 'EU' bitmap from the region index, the 'active' bitmap from the status index, and the 'mobile' bitmap from the channel index — three compressed bit arrays.
It computes the bitwise AND of the three bitmaps. Because the encodings support boolean operations directly, this walks the compressed runs/containers without materializing full N-bit arrays, producing a result bitmap whose set bits are exactly the rows satisfying all three predicates. The combined selectivity is high even though each predicate alone is not, so the result bitmap is sparse.
For the COUNT, the engine runs a population count over the result bitmap and returns the number of set bits — no base table access at all. Had the query selected columns instead, the engine would iterate the set bits, translate them to row IDs, and fetch just those rows, so even the fetch phase touches only matching rows rather than scanning and filtering.
Now consider a write that changes a row's status from 'active' to 'churned'. The engine must clear that row's bit in the 'active' bitmap and set it in the 'churned' bitmap — an update touching two bitmaps for one column change. In a read-heavy, append-mostly warehouse this is rare and cheap relative to the query savings. In a high-churn OLTP table it happens constantly, and because bitmap updates historically lock at a coarse granularity, concurrent writers contend heavily — which is precisely why the same index that accelerates the analytic query above would throttle a transactional workload, and why the workload fit, not just the cardinality, decides whether a bitmap index belongs on a column.
The same trace also shows why bitmap indexes pair so well with columnar storage. A column store already keeps each column contiguous, so building and scanning a per-value bitmap aligns with how the data is laid out on disk, and the bitmaps can be co-located with the column segments they describe. The engine can skip entire segments whose bitmap has no set bits for the predicate, prune before it reads, and combine the surviving segments' bitmaps — turning the multi-predicate filter into a small amount of bitwise work over exactly the data that could possibly match, rather than a scan of the whole column.