Bitmap and Roaring Indexes for Combining Predicates

A structure that answers “which documents have this term” one term at a time forces the query engine to intersect lists. A structure that answers “which documents have this term” by setting bits can answer a conjunction with a machine instruction: two bitmaps over the same document space are combined with a word-wise AND, and the matching documents are found by counting the bits. The trade is space, and the whole design space of bitmap indexes is the management of that trade.

One bit per document per value

A bitmap index for an attribute stores, for each distinct value, a bitmap with one bit per document. Bit d is set if document d has that value. A conjunction of predicates selects a bit per predicate and ANDs the bitmaps; the resulting set of set bits is the result.

The cost arithmetic is what makes this attractive. A 64-bit machine word ANDs 64 document membership bits in one instruction, so a conjunction over a billion documents costs about 16 million word operations — and a processor with 256-bit or 512-bit vector ANDs does four or eight times that per instruction. The same conjunction over posting lists costs one decode per posting per list, which for lists of comparable length is several orders of magnitude more instructions per document examined.

The space arithmetic is what limits it. One bit per document per distinct value means n·v / 8 bytes for n documents and v distinct values. For a billion documents and a single low-cardinality attribute with 256 values, that is 32 GB. For a high-cardinality attribute such as a user identifier, it is n²/8 bytes, which is absurd. Bitmaps are viable in the regime where the attribute has few distinct values and the document count is large — a status code, a country, a small enumerated type.

The intermediate regime is the interesting one, and it is where the chunked formats live.

Chunking so density varies locally

A raw bitmap is a single flat array, and the flat layout has no way to exploit sparsity. If an attribute with 65,536 distinct values is present uniformly, each value’s bitmap has one set bit per 65,536 document positions, so 99.998 percent of it is zeros, and ANDing two such bitmaps costs a full pass to produce a result that is almost certainly empty.

Roaring bitmaps fix this by partitioning the 32-bit value space into chunks of 65,536 consecutive values — the high 16 bits of the value select a chunk. Each chunk holds the set bits for values in its range, and the chunk’s representation varies by how dense those values are. A lookup or an operation touches only the chunks that both operands share, and within a chunk the representation is chosen to be cheap for the local density.

Three representations cover the cases:

• Array container. A sorted array of 16-bit offsets. Costs 2 bytes per present value. Used for sparse chunks.
• Bitmap container. A fixed 8 KiB block: 65,536 bits, or 1,024 64-bit words. Used for dense chunks.
• Run container. A sorted list of (start, length) pairs, each two 16-bit values. Used for chunks that are dense but arranged in long contiguous runs.

The chunk is 65,536 values rather than some other size because that is exactly 8 KiB of bitmap — a fixed-size block that never changes with the density, so it can be indexed and accessed at a known offset — and because 16-bit offsets address it exactly. A chunk key fits in 16 bits, so the container list is a sorted array of 16-bit keys paired with container pointers.

The two container thresholds, and why 4096

The choice between an array and a bitmap container is settled by pure arithmetic. A bitmap container is 8,192 bytes. An array container holding c values is 2c bytes. The two are equal when c = 4096. Below 4096 present values the array is smaller and, being sorted, supports galloping intersection; above it the bitmap is smaller and supports word-parallel intersection.

The same reasoning gives the run container’s thresholds. A run container costs 4 bytes per run, so it beats a bitmap when the number of runs is below 8192 / 4 = 2048, and it beats an array when 4r < 2c, that is, when r < c/2 — which holds whenever runs are longer than two values on average. A chunk that is a single run of 60,000 values stores 4 bytes where the bitmap stores 8,192 and the array would store 120,000.

The thresholds are not arbitrary tuning constants; they are the points where the byte counts cross. That property is what makes the format analysable: the cost of a container is a known function of its density, and the container chosen is the minimum of three linear functions.

Container	Bytes for c values in r runs	Best when
Array	2c	c < 4096 and runs are short
Bitmap	8192	c ≥ 4096 and runs are short
Run	4r	r < 2048 and r < c/2

Intersecting containers of different types

A conjunction between two bitmaps proceeds chunk by chunk. Chunks present in both operands are combined; chunks present in only one can be dropped, because the intersection cannot have values there. The combination dispatches on the pair of container types, and the dispatch has nine cases in principle, reduced by symmetry to six.

The cases that matter:

Array with array. A merge of two sorted 16-bit arrays, or a galloping intersection when one is much shorter than the other. The output is an array container unless the count exceeds the threshold, in which case the result is converted to a bitmap.

Bitmap with bitmap. A word-wise AND over 1,024 words, which is 512 vector operations at 128 bits or 128 at 512 bits. The result is a bitmap, unless the resulting cardinality falls below the threshold, in which case it is converted to an array. Computing the cardinality requires a popcount over each word, which on current x86 is a single instruction per word and is the only thing that makes the conversion decision possible.

Array with bitmap. The array is used as the probe set: for each 16-bit offset in the array, test the corresponding bit in the bitmap. This is c bit tests, cheaper than a full word-wise AND whenever the array is short. The container’s bit-test is a shift and a mask into a word, plus a load.

Anything with a run. The run container is usually converted to a bitmap first, because the run-based intersection logic is more complex than the conversion cost. That conversion is 8192 bytes of bit-setting regardless of how many runs there were, so a run container with two runs pays a large penalty to intersect; implementations that care add a direct run-against-run case, which is a merge of two sorted interval lists and costs the number of runs.

The conversion direction matters for performance and not for correctness. A bitmap-to-array conversion must scan all 1,024 words to collect the set bits, which is why the threshold check happens after the AND has produced the result rather than before.

/* Intersect two dense containers; write the result and return its cardinality. */
int and_bitmap(uint64_t *restrict dst,
               const uint64_t *restrict a,
               const uint64_t *restrict b,
               size_t words)              /* 1024 for a full 16-bit chunk */
{
    int card = 0;
    for (size_t i = 0; i < words; i++) {
        uint64_t w = a[i] & b[i];
        dst[i] = w;
        card += __builtin_popcountll(w);  /* hardware POPCNT / vector popcount */
    }
    return card;
}

__builtin_popcountll is the compiler intrinsic that maps to the hardware population count. Where the target has vector population count, compilers can vectorise the loop, and the AND plus popcount becomes four or eight words per instruction pair. Where it does not, each word costs one AND and one popcount, and the loop is bound by the popcount’s throughput, which on older processors is a few cycles per word. The array container of the same cardinality costs one load and one compare per present value, so for a chunk at the threshold the two representations are within a small factor of each other — which is exactly what the threshold equality predicts.

Where the model breaks

Fragmentation. A chunk whose values alternate between the extremes of its 65,536-value range has no long runs and a cardinality below 4096, so it is stored as an array — but if the cardinality is just above the threshold it becomes a bitmap that is more than ninety percent empty. The worst case for a bitmap container is 4,097 values spread as evenly as possible, which spends a full 8 KiB on a block that is only about six percent full. The format bounds this waste at the crossover; it does not eliminate it.

Container count. A value space with 65,536 chunks has a container list of that length at worst, and each chunk carries its key and its type. The overhead is proportional to the number of non-empty chunks, so a sparse value space with one value per chunk pays for a container per value. The array representation costs 2 bytes per value plus a few bytes per container, which is still small, but the per-chunk overhead dominates for very sparse data — the point at which a sorted posting list of document identifiers or a hash-based lookup is the better structure.

Updates. Inserting a value into an array container is a sorted insert, which is a memmove of the tail. In a bitmap container it sets one bit, which is constant time. Crossing the threshold converts the container, which is a linear pass and changes the storage class; an insert-heavy workload that oscillates around 4,096 values will convert repeatedly. The same issue appears in open-addressed hash tables when the load factor hovers at the resize threshold, and the mitigations are similar: a hysteresis band rather than a single threshold, or a buffer of recent updates that is merged in batch.

Compression on disk versus in memory. The chunked format has two serialisations. The in-memory form is a structure of pointers into container objects, chosen for fast operation. The portable format is a byte-exact serialisation with the container types recorded, designed so that the same bytes deserialise identically everywhere. A file format stores the portable form, and a query loads or memory-maps it and may convert to the in-memory form. The two are not interchangeable: the portable form is not indexable in place, and reading a single container from it requires walking the header structure.

How this fits the rest of the lookup toolkit

Bitmap indexes answer a different question than the point-lookup structures in this cluster. A hash table answers “where is the record with this key” in an expected constant number of probes; a bitmap index answers “which records satisfy this combination of predicates” without touching the records at all. The two compose: a bitmap intersection produces candidate document identifiers, and a hash or B-tree lookup then fetches the records. For a highly selective predicate the bitmap is a wasteful prefilter, because a B-tree point lookup already resolves the record in a few page reads. For a moderately selective conjunction across several attributes, the bitmap’s word-parallel intersection is what makes the query cheap.

The same chunking idea recurs in the posting-list structures used for text, where the equivalent problem is compressing gaps in a sorted list rather than membership in a bit array. A term’s posting list and an attribute’s bitmap are both representations of a set of document identifiers, and the choice between them follows the same density argument: a set that is dense over a small universe is cheapest as bits, and a set that is sparse over a large universe is cheapest as sorted deltas. The container thresholds are the arithmetic that decides where the boundary lies.