A bitmap is one of the most honest data structures.

If integer x is present, bit x is one. If it is absent, bit x is zero. Union is OR. Intersection is AND. Difference is AND-NOT. The CPU knows how to do those operations very quickly.

The problem is that honesty can be large.

A bitmap over a billion possible document IDs costs a billion bits even if only a few thousand documents match the term. Compression helps, but it can also turn set algebra into a decoding chore. Run-length encodings love long clean runs. Sparse arrays love isolated IDs. Dense bitsets love crowded chunks.

Roaring’s small idea is not to pick one representation for the whole set.

It asks locally.

split the integer universe by high 16 bits
store the low 16 bits in a per-chunk container
choose the container from the chunk's shape

That is the map.

The High Bits Choose the Room

For a 32-bit integer, Roaring uses the high 16 bits as a key. Each key owns a container for the low 16 bits. So every container describes a local universe of size

\[2^{16}=65{,}536.\]

Inside that local universe, several representations make sense:

  • an array container for sparse sets, storing sorted 16-bit integers;
  • a bitmap container for dense sets, storing 65,536 bits, or 8 KiB;
  • a run container for long contiguous ranges, storing starts and lengths.

The original Roaring paper by Chambi, Lemire, Kaser, and Godin introduced a hybrid built around packed arrays and uncompressed bitmaps, comparing it against RLE-oriented compressed bitmap schemes such as WAH and CONCISE.1 A later Roaring paper added run containers for cases where long sorted runs make RLE genuinely better.2

The design is wonderfully impolite to grand theories of compression. It says:

this chunk is sparse, use an array
this chunk is dense, use a bitmap
this chunk is mostly intervals, use runs

There is no single winner because the data does not have a single shape.

Why Not Just Run-Length Encode Everything?

Bitmap indexes were already an old idea. Word-aligned hybrid compression, WAH, made compressed bitmaps practical by aligning runs and literals to machine words, so logical operations could run without fully expanding the bitmap.3 CONCISE tightened that family, improving space over WAH while keeping similar or better operation time in the authors’ experiments.4

Those formats are especially natural when the bitmap has long stretches of all zeros or all ones. That often happens after sorting rows by correlated columns.

But a search index or analytical predicate does not promise you long runs everywhere. One part of the ID space might be sparse, another might be dense, and another might contain runs. A global RLE strategy can spend bookkeeping on chunks where sorted arrays would be simpler. A global array strategy can become terrible when a chunk gets dense.

Roaring’s 16-bit containers make the branch local. The top-level map keeps chunks separate, and set operations merge matching chunk keys. Within a chunk, the implementation can use algorithms specialized for the two container types it sees.

That is the central systems lesson:

compression is not only smaller bytes
it is choosing an execution shape for algebra

A Container Lab

The lab below builds two deterministic integer sets over several 16-bit chunks. For each chunk it estimates three local encodings:

array:  2 bytes per value
bitmap: 8192 bytes for the whole 16-bit chunk
run:    4 bytes per contiguous run

The byte model is intentionally simplified; production formats also have headers, cardinality fields, alignment details, SIMD paths, and container conversion thresholds. The point is to expose the local choice.

The lab computes exact chunk-wise union, intersection, and difference over sorted arrays, then chooses the cheapest container for every result chunk.

The Audit tile is generated by the same JavaScript as the lab. It checks parameter sanitation, run extraction, container-choice examples, hand-checked union/intersection/difference cases, sorted 16-bit invariants, default exact set algebra against a naive implementation, inclusion-exclusion, summary accounting, multi-container defaults, and a 384-case grid over profiles, chunk counts, densities, shifts, and seeds.

Array container Bitmap container Run container Union Intersection

Deterministic toy model. It uses one 16-bit universe per chunk and a simplified byte estimate. Real Roaring implementations include additional metadata, thresholds, vectorized kernels, and serialization details.

At the default setting, set A has 23,559 integers and set B has 21,753. Their union has 41,760 integers; their intersection has 3,552. The union uses all three local shapes: 2 array containers, 1 bitmap container, and 3 run containers. Under the lab’s simplified byte model, A costs 9,956 bytes, B costs 9,956 bytes, the union costs 11,640 bytes, and the intersection costs only 2,052 bytes.

Change Profile to sparse. The array containers dominate because storing the present values is cheaper than reserving 8 KiB for every chunk. Change it to dense; bitmap containers become natural. Change it to runs; the run strips become visibly long and the run containers take over.

The operation is still exact. The container choice only changes how each chunk is stored and how the next operation can be implemented.

The Shape Is the Index

The reason this matters is that bitmap indexes are not just storage. They are a query execution format.

If a search engine has postings lists for terms, or an analytical database has bitmap indexes for predicates, a query often becomes set algebra:

(country = "US")
AND (plan in {"pro", "team"})
AND NOT (status = "deleted")

If those sets are represented as compressed bitmaps, the engine wants to compute the Boolean expression without expanding every set into individual integers. Roaring makes this plausible by keeping containers small enough to choose specialized kernels. Array-array intersection can look like a merge or SIMD set intersection. Bitmap-bitmap intersection can be word-wise AND plus popcount. Run containers can skip whole intervals.

The structure is not merely “compressed.” It is a dispatch table for set operations.

Lemire and coauthors’ CRoaring paper makes that systems angle explicit: Roaring sets support union, intersection, difference, and symmetric difference, and optimized implementations use processor features such as SIMD for container operations.5 The algorithmic idea and the implementation idea are connected. A chunk chooses a representation; representation chooses an execution kernel.

The Caution

Roaring’s success should not be read as “arrays beat RLE” or “bitmaps beat arrays.” The more accurate lesson is:

local shape beats global allegiance

RLE is excellent when the data are runs. Arrays are excellent when the data are sparse. Bitmaps are excellent when density makes raw bit operations worthwhile. A workload that mixes all three should be allowed to mix representations.

That is also why benchmarks matter. Row ordering, clustering, deletion patterns, chunk cardinalities, and operation mix all change which containers appear and which kernels dominate. The lab is deliberately small, but it makes one thing hard to unsee:

the same integer set abstraction
can be a sorted array here
a dense bitset there
and a run list next door

The bitmap is not a flat bitstring anymore. It is a container map.

  1. Samy Chambi, Daniel Lemire, Owen Kaser, and Robert Godin, “Better Bitmap Performance with Roaring Bitmaps”, Software: Practice and Experience 46(5), 2016. Wiley record: https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.2325. ↩

  2. Daniel Lemire, Gregory Ssi-Yan-Kai, and Owen Kaser, “Consistently Faster and Smaller Compressed Bitmaps with Roaring”, Software: Practice and Experience 46(11), 2016. ↩

  3. Kesheng Wu, Ekow J. Otoo, and Arie Shoshani, “Optimizing Bitmap Indices with Efficient Compression”, ACM Transactions on Database Systems 31(1), 2006. The FastBit page summarizes the word-aligned hybrid compression approach. ↩

  4. Alessandro Colantonio and Roberto Di Pietro, “CONCISE: Compressed ‘n’ Composable Integer Set”, Information Processing Letters 110(16), 2010. ↩

  5. Daniel Lemire, Owen Kaser, Nathan Kurz, Luca Deri, Chris O’Hara, François Saint-Jacques, and Gregory Ssi-Yan-Kai, “Roaring Bitmaps: Implementation of an Optimized Software Library”, 2017. ↩