Roaring Bitmap: The Compressed Bitset That Powers Search Engines

Splitting the Integer Range into Chunks

A Roaring Bitmap begins with a simple idea borrowed from how computers already represent numbers. Any thirty-two-bit unsigned integer can be split into two sixteen-bit halves: a high half and a low half. The high sixteen bits can take any of sixty-five thousand five hundred thirty-six distinct values, so they are used to select which chunk, sometimes called a container group, a number belongs to. The low sixteen bits, which can also take sixty-five thousand five hundred thirty-six distinct values, describe the position of that number within its chunk. In other words, the entire four-billion-plus range of thirty-two-bit integers is carved into sixty-five thousand five hundred thirty-six buckets, each responsible for exactly sixty-five thousand five hundred thirty-six possible values. Crucially, a chunk is only created and stored at all if at least one number belonging to it is actually present in the set. If your data only ever uses integers below one hundred thousand, only the first two chunks will ever need to exist, and every other chunk consumes zero memory. This lazy, on-demand allocation of chunks is the first big source of Roaring Bitmap's efficiency: it never pays a memory cost for ranges of numbers that are entirely empty. Within each active chunk, the numbers that belong to it, meaning their low sixteen bits, need to be stored somehow, and that storage format is chosen independently for every single chunk. This two-level design, a sparse top level of chunk identifiers paired with independently optimized containers underneath, is what lets Roaring Bitmap adapt smoothly to wildly different distributions of numbers, from a handful of scattered identifiers to nearly continuous ranges spanning millions of values, all within one unified structure.

Three Container Types for Three Kinds of Data

Inside each chunk, Roaring Bitmap keeps a container holding the low sixteen bits of every value present, and it selects between three container formats based on how many values actually live there. The first is the array container, used when a chunk is sparse, typically holding no more than about four thousand values. It simply lists the low-order values in sorted order, each stored compactly, so a chunk containing only a handful of numbers out of the possible sixty-five thousand five hundred thirty-six costs almost nothing to store. The second is the bitmap container, used when a chunk is dense. It allocates a fixed block of eight thousand one hundred ninety-two bytes, one bit for every possible value in the chunk, and simply flips bits on or off. Once a chunk holds more than a few thousand values, a raw bitmap becomes more compact than a sorted list of individual numbers, because the array container's per-value storage cost starts to exceed the fixed cost of one bit per possible position. The third is the run-length-encoded container, used when a chunk contains long unbroken stretches of consecutive integers. Instead of storing every value in a run individually, it stores only the starting value and the length of each run, so a chunk representing, say, ten thousand consecutive document identifiers can be described with just one small pair of numbers instead of ten thousand separate entries. Roaring Bitmap's implementation continually estimates, and in many implementations dynamically converts between, whichever of these three representations would occupy the least space for a chunk's actual contents, so the overall structure never pays for a wasteful format when a cheaper one would do exactly the same job.

Why Adaptive Containers Beat Plain Bitmaps and Plain Arrays

The motivation for this three-way adaptive design becomes clear once you consider the failure modes of the two simpler alternatives it replaces. A plain, uncompressed bitmap over the full thirty-two-bit range would need five hundred twelve megabytes just to exist, regardless of whether the set contains ten numbers or ten million, because every possible value needs a reserved bit whether it is used or not. That is an enormous, often prohibitive, fixed cost for representing sparse sets, which are extremely common in real workloads such as search results matching a narrow filter. On the other end, a plain sorted array or hash set avoids that fixed cost and stores only the numbers that are actually present, but it pays a different price when the set becomes large or when you need to combine several sets. Computing the intersection or union of two large sorted arrays generally requires comparing and merging elements one at a time, an operation whose cost grows with the total number of elements involved, and hash sets make matters worse by giving up the sorted order that makes fast merging possible in the first place. Roaring Bitmap sidesteps both problems by never applying a single strategy uniformly across the whole range. Sparse regions of the number space are handled by the compact array container, so no memory is wasted on emptiness. Dense regions are handled by the raw bitmap container, so no per-element bookkeeping overhead accumulates. Regions with long consecutive runs, common in workloads like time-ordered identifiers or contiguous row ranges, are handled by the run-length-encoded container, which can represent millions of values in a tiny fixed amount of space. Because the choice is made independently per chunk, a single Roaring Bitmap can simultaneously contain some chunks that are nearly empty, some that are nearly full, and some that are long unbroken runs, each stored in the format best suited to it, without any global compromise.

Fast Set Operations, Container by Container

The real payoff of this design shows up when you need to combine sets, which is the operation search engines and databases perform constantly, for example intersecting the set of documents containing one search term with the set of documents containing another. Roaring Bitmap performs a union, intersection, or difference by walking through the chunk identifiers of both bitmaps in sorted order, much like merging two sorted lists, and processing matching chunks together. If a chunk identifier exists in only one of the two bitmaps, for a union the whole chunk can simply be copied across unchanged, and for an intersection it can be skipped entirely, since no matching values can exist in the other bitmap's absent chunk. This alone eliminates enormous amounts of wasted work compared to a bit-by-bit or element-by-element approach, because whole sixty-five-thousand-five-hundred-thirty-six-value chunks are resolved with a single comparison. When a chunk identifier exists in both bitmaps, the two corresponding containers are combined, and the exact method depends on which container types are involved. Two bitmap containers can be combined using extremely fast bitwise processor instructions that operate on many bits simultaneously. Two array containers can be merged the way two sorted lists are merged, in time proportional to their combined size. A run-length-encoded container can be combined with another container by comparing runs and ranges directly, often touching far fewer individual values than either container actually represents. Because every container format keeps its contents in a predictable, sorted internal order, these container-level merges never need to fall back to a slow generic comparison, and the overall operation's cost tracks the true complexity of the data rather than the theoretical size of the number range. This is what allows systems processing billions of identifiers to compute set intersections and unions in milliseconds.

Roaring Bitmap in Real Systems

Roaring Bitmap was first described in a two thousand sixteen research paper and quickly moved from an academic idea into production use across some of the most widely deployed data infrastructure in the world. Apache Lucene, the search library underlying Elasticsearch and Apache Solr, uses Roaring-style structures to represent posting lists, the sets of document identifiers associated with each indexed term, so that combining the results of a multi-term query stays fast even across indexes holding hundreds of millions of documents. Apache Spark uses Roaring Bitmap to track which partitions or rows have already been processed during large-scale distributed computations, avoiding both the memory blow-up of plain bitmaps and the merge overhead of plain lists. Column-oriented analytical databases such as ClickHouse and Apache Druid use it to represent bitmap indexes over categorical columns, where a query might need to find all rows matching several filter conditions simultaneously by intersecting several such bitmaps. In every one of these systems, the underlying workload has the same shape: identifiers arrive across a huge numeric range, their distribution is unpredictable and can range from extremely sparse to extremely dense, and the system needs to combine many such sets under strict latency budgets. Roaring Bitmap's combination of adaptive per-chunk compression and fast container-aware set operations directly answers all three requirements at once, which explains why it has become close to a standard choice wherever large integer sets need to be indexed, stored, and combined efficiently, rather than a niche technique confined to a single product.

Frequently asked questions

Try it live

Everything above runs in your browser — open Roaring Bitmap: The Compressed Bitset That Powers Search Engines and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.