Counting an Overlap Without Building It: A 64-Bit Bitmap Fix in ClickHouse

A bitmap is a way to store a set of integers as bits. If a set can hold the numbers 0 to 63, you can store any such set in a single 64-bit word: bit 5 is on if 5 is in the set. Asking "is 5 in the set?" becomes one instruction, and combining two sets becomes a bitwise AND.

That works beautifully until the numbers get big and the set gets sparse. A set holding only the number four billion should not need four billion bits.

Roaring bitmaps are the standard fix. Split the number line into chunks of 65,536, and store each chunk in whichever of three forms is smallest: a sorted array when the chunk holds a handful of values, a plain bitset when it is dense, or run lengths when the values are consecutive. To combine two Roaring bitmaps you walk only the chunks they have in common.

ClickHouse builds these with groupBitmap, and under the hood it uses CRoaring, the C implementation, vendored in the repository as contrib/croaring. The same library also backs the text index, MergeTree delete bitmaps, and the deletion vectors in the Iceberg and Delta Lake formats — that detail comes back later.

One more thing matters here. Roaring is a *32-bit* structure by design: the chunk key is 16 bits, the value within a chunk is 16 bits. For 64-bit IDs there is a second class, Roaring64Map, which is essentially a map from the top 32 bits of a number to an ordinary 32-bit Roaring bitmap holding the bottom 32.

ClickHouse picks between them by how wide your column is:

using RoaringBitmap = std::conditional_t<sizeof(T) >= 8, roaring::Roaring64Map, roaring::Roaring>;

UInt8, UInt16, UInt32 get the 32-bit class. UInt64 and Int64 get the 64-bit one. Remember that fork in the road.

Here is what bitmapAndCardinality used to do for 64-bit IDs:

/// Roaring64Map exposes no and_cardinality, so the intersection must be materialized.
ret = (*roaring_bitmap & *r1.roaring_bitmap).cardinality();

Read it right to left. The & allocates a brand new bitmap and fills it with every ID the two sets share. .cardinality() then counts what is inside. Then the whole thing is freed.

If the two sets share a million IDs, you allocate room for a million IDs to learn the number 1,000,000.

bitmapHasAny was the same trick, and worse, because its question is even smaller:

/// Roaring64Map exposes no intersect, so the intersection must be materialized.
if ((*roaring_bitmap & *r1.roaring_bitmap).cardinality() > 0)
    return 1;

"Do these two sets share anything?" is a question you can stop answering the moment you find one shared value. Instead, the old code found *every* shared value, wrote them all down, counted them, and then compared the count to zero.

Both routines are read-only in spirit. Neither one needs the intersection to exist.

Someone had already noticed. PR #117478 had landed earlier, and it did exactly the right thing: use the routines that walk both sets and count matches as they go, without ever writing a result.

• and_cardinality(other) — walk, count, return the number.
• intersect(other) — walk, and return true at the first shared value.

But that PR had a fence around it:

else if constexpr (sizeof(T) < 8)
{
    ret = roaring_bitmap->and_cardinality(*r1.roaring_bitmap);
}
else
{
    /// Roaring64Map exposes no and_cardinality, so the intersection must be materialized.
    ret = (*roaring_bitmap & *r1.roaring_bitmap).cardinality();
}

The comment is the whole explanation, and it was honest: the 32-bit Roaring class had those two methods, and Roaring64Map did not. So the fast path was written for the types that could use it, and 64-bit kept the slow one.

The awkward part is which types those are. When people reach for bitmaps in ClickHouse, they are usually holding user IDs, device IDs, order IDs or hashes — and the natural column type for those is UInt64. The optimization had been applied everywhere *except* the case it was most needed for.

The missing methods are not something you can add from inside ClickHouse — they belong to the vendored library. Happily, CRoaring 5.2.0 added them in RoaringBitmap/CRoaring#875: and_cardinality, intersect, or_cardinality, xor_cardinality and andnot_cardinality, all on Roaring64Map.

They work the way you would guess. A Roaring64Map is a map keyed by the top 32 bits, so the new methods walk the keys the two maps have in common and hand each matching pair to the 32-bit routine that already existed. intersect returns as soon as one pair reports a hit.

That makes the ClickHouse side small:

1. Bump contrib/croaring from v5.1.1 to v5.2.1.
2. Delete both sizeof(T) < 8 branches. The calls are now unconditional, and the materializing fallbacks are gone.
3. Name the condition once, so it cannot drift:

static constexpr bool use_roaring64 = sizeof(T) >= 8;
using RoaringBitmap = std::conditional_t<use_roaring64, roaring::Roaring64Map, roaring::Roaring>;
using Value = std::conditional_t<use_roaring64, UInt64, UInt32>;

That third point is the one I care about most. There were two separate copies of "is this the 64-bit case?" living in the file — one choosing the class, one guarding the call — and nothing forcing them to agree. Writing sizeof(T) >= 8 in one place and sizeof(T) < 8 in another is exactly the kind of pair that quietly goes out of step during the next refactor. Now there is one name, used by both.

Five SQL functions get faster for 64-bit element types: bitmapAndCardinality and bitmapHasAny directly, and bitmapOrCardinality, bitmapXorCardinality and bitmapAndnotCardinality for free, because all three derive their answer from the AND cardinality by inclusion and exclusion.

Measured directly against Roaring64Map so the numbers are about the change and not about ClickHouse's per-row overhead. Median of 5 runs, g++ 13.3.0 at -O3, one pinned core. "old" is build-then-count, "new" is the direct routine, and both are asserted to produce the same answer before timing.

and_cardinality:

operands                              old ns/op   new ns/op   speedup
dense 2M, 50% overlap                     54677        1637       33x
64 chunks x 20K, 50% overlap             322962        8824       37x
evens vs odds, 1.5M, nothing shared      105904        5766       18x
identical 2M                             128574        3328       39x

intersect, the path behind bitmapHasAny:

operands                               old ns/op   new ns/op   speedup
dense 2M, 50% overlap                      55652          91      610x
64 chunks x 20K, 50% overlap              344089          58     5936x
evens vs odds, 1.5M, nothing shared       113148       16017        7x
identical 2M, shares the first value      133575           6    23420x

The eye-watering rows are early exit doing its job: when the two sets share their very first value, the answer is available almost immediately, and the old code was still busy allocating.

The honest row is the third one in each table — sets that occupy the same chunks but share no value at all, so every pair has to be examined and there is no early exit to take. Even there, simply not writing a result is worth 7x.

These are library-level figures. The gain on an actual SQL call is smaller, because the function layer has its own per-row work to do either way.

The interesting review comment was not about the C++ at all. A review bot pushed back on the one-line submodule change:

This CRoaring bump is materially broader than the rest of the PR [...] so we are also changing every other ClickHouse surface backed by the vendored library under the guise of a narrow bitmap*Cardinality optimization.

Which is a fair challenge, and this is where that earlier detail comes back: croaring is not only the bitmap functions. It also backs the text index, MergeTree delete bitmaps, and Iceberg and Delta Lake deletion vectors. A library bump touches all of it.

The answer was to stop hand-waving and account for the range file by file. Between v5.1.1 and v5.2.1 there are four upstream commits, and most of the diff is under tests/, tools/ and .github/. Outside those:

• the new Roaring64Map methods — pure addition, nothing existing touched;
• an AVX2 intrinsic renamed at 102 call sites, _mm256_lddqu_si256 to _mm256_loadu_si256, which has been the same instruction since Nehalem;
• two build guards for platforms ClickHouse does not build (32-bit ARM, and an x86 header on non-x86);
• one genuine upstream fix to a reference-counting helper for shared chunks.

So exactly one behaviour-affecting change to an existing code path in the whole range. And pinning something narrower was not really on the table: the commit that adds the methods is the same one carrying the rest, so narrowing would mean pinning an arbitrary mid-range commit instead of a release tag, and losing the ability to say which upstream release ships.

The PR was reviewed and approved by Alexey Milovidov, ClickHouse's co-founder and CTO. At the time of writing it is approved and waiting on CI and merge.

The bug here was not a mistake. Every line of the slow path was correct, well commented, and deliberate on the day it was written. Roaring64Map really did lack those methods.

What went stale was the reason. Upstream filled the gap in the next release, and the fence stayed up because a comment explaining a limitation reads exactly like a comment explaining a decision. Nobody re-reads it and asks "is this still true?"

So: when you gate a fast path on something another project is missing, you are leaving a note for the future, not settling the question. It is worth going back to check whether the thing you were waiting for has arrived.

And the small one, which generalises well past bitmaps: the cheapest intersection is the one you never write down.