Bitmap indexes and Roaring bitmaps

Why do bitmaps turn predicates into word-parallel algebra, and how does Roaring remove the cardinality limit?

Bitmap index and Roaring bitmaps

A bitmap index keeps, for each distinct value of a column, a bit vector with one bit per row: bit i is 1 if row i has that value.

The constraint, and the folklore it produced. A naive bitmap index over a column of cardinality c (number of distinct values) and n rows costs c · n bits. Gender over a billion rows: 2 × 10⁹ bits = 250 MB. Fine. User ID at cardinality 10⁸ over the same rows: 10¹⁷ bits. That is where "bitmap indexes are only for low-cardinality columns" comes from. That rule is now obsolete. Keep reading.

Why bitmaps are attractive in the first place is not space but algebra. Predicate evaluation becomes boolean operations on machine words. WHERE region = 'EU' AND status = 'active' AND NOT flagged is two ANDs and a NOT over bit vectors, 512 rows per instruction. The number of matching rows comes free from popcount (an instruction that counts set bits), which the optimizer can use to order operations cheapest-first. The result of a predicate is a set of row IDs in exactly the form the next predicate wants. B-tree indexes lack this property: intersecting two sorted row-ID lists is a merge, not an AND.

The escape from the cardinality problem is compression that survives the operation. Word-aligned RLE schemes (WAH, EWAH, Concise) store alternating literal words (raw bits) and fill words (a long run of zeros or ones, stored as a count). Two compressed bitmaps can be ANDed by walking both run streams in lockstep, never expanding either. That is this article's core idea in its first form. Their weakness is real: a bitmap that is sparse but scattered (one set bit every hundred positions) has no runs to encode. RLE gains nothing, adds decode cost, and the encoded form allows only sequential scanning.

Roaring's answer is a per-chunk choice of representation, and its threshold is derivable, not tuned. Split the row space into chunks of 2¹⁶ = 65,536 positions. Inside a chunk, store either:

• a sorted array of 16-bit offsets (16 bits per set element), or
• a dense bitmap of 65,536 bits = 8 KB (the same cost whatever the density).

Break-even: 16 · k = 65,536, so k = 4,096. Below 4,096 set bits the array is smaller; above it the bitmap is smaller. A third container type handles long runs. The magic number in every Roaring implementation is just the chunk's universe size divided by the element width.

The principle is worth naming: local density adaptivity. Switch representation at a computed break-even, based on the observed density of the local piece of data. It has now appeared three times: ART's adaptive nodes (4, 16, 48 or 256 children depending on actual fanout, Lookup structures), the sparse-to-dense switch in HLL++ (Probabilistic structures), and Roaring containers. Three independent designs that all arrive at "measure the density of this chunk and pick a container" is the sign of a deep constraint, not of copying. It is a design technique, not a law, but it will recur wherever data is sparse but not uniformly so.

The operations adapt too. Three container types give six pairwise intersection algorithms: merge or galloping search for array ∩ array, probing for array ∩ bitmap, word-by-word AND for bitmap ∩ bitmap, and so on, each best for its case. The complexity lives in the implementation, not in the model, which is where you want it.

Correct the folklore properly. With Roaring, a high-cardinality column's per-value bitmaps are individually sparse and are stored as short arrays. Total space is O(n) postings regardless of cardinality. The structure degrades gracefully into an inverted index (a map from value to the list of rows that contain it). Cardinality is no longer the constraint. Update cost is. Bitmaps are expensive to modify in place, so they belong in immutable segments, the same placement conclusion as for XOR filters, succinct tries and minimal perfect hashes.

Bit-sliced indexes close the gap between "bitmaps do equality" and "bitmaps do arithmetic". Store an integer column as one bitmap per bit position (bitmap 0 holds bit 0 of every row's value, and so on). Then range predicates such as value > 100, and even sums, can be computed directly with bitmap operations.

Where this is live: Lucene and Elasticsearch document-ID sets and filter caches, Druid and Pinot inverted indexes, ClickHouse, and most directly, deletion vectors in Iceberg and Delta. A deletion vector is a Roaring bitmap of deleted row positions in a data file. Merge-on-read deletion (do not rewrite the file; record which rows are deleted and filter them when reading) is therefore a bitmap-index problem.