Opensource internals

ClickHouse Packs a HyperLogLog Rank Into Five Bits

19 min read Jay Hubbert

ClickHouse's CompactArray stores values narrower than a byte in a bitset and reads them through an unaligned 16-bit window, so a HyperLogLog's rank store costs 5 or 6 bits per bucket instead of a whole byte.

TL;DR: CompactArray packs content_width-bit values into a byte array and reads them through an unaligned 16-bit window: load two bytes, shift by the bit offset, mask. The shift-and-mask makes it branchless, and one extra padding byte at the end of the bitset keeps the last window in bounds. HyperLogLog uses it to store a 5- or 6-bit rank per bucket.

Cardinality estimation is a memory problem before it is a mathematics problem. If you want to count the distinct values in a billion-row column, the exact answer needs a set of a billion elements. An approximate answer needs a fixed-size structure, and the whole game is making that structure as small as possible without making the estimate useless.

ClickHouse’s HyperLogLog needs one small integer per bucket: the rank, which is the number of trailing zeros in the hash’s tail. For a 32-bit hash with 17 bits of precision, that rank is at most 16. For a 64-bit hash, at most 48. And yet the naive implementation stores each rank in a UInt8. That is 8 bits for a value that needs 5. For the default uniqCombined precision of 17, that is 2^17 = 131072 buckets, so the difference between 5 bits and 8 bits per bucket is 80 KiB versus 128 KiB — 48 KiB wasted per aggregate state, and there is one aggregate state per combination of groups.

ClickHouse’s answer is CompactArray, a bitset of sub-byte values with a branchless accessor. This article is about that class, the arithmetic that makes it work, and the HyperLogLog that consumes it.

The waste, quantified

The class documentation states the problem precisely:

cpp 
// src/Common/CompactArray.h:13
/** Compact array for data storage, size `content_width`, in bits, of which is
  * less than one byte. Instead of storing each value in a separate
  * bytes, which leads to a waste of 37.5% of the space for content_width = 5, CompactArray stores
  * adjacent `content_width`-bit values in the byte array, that is actually CompactArray
  * simulates an array of `content_width`-bit values.
  */

“a waste of 37.5% of the space for content_width = 5” — because 5 bits out of 8 is 62.5% utilisation, so 37.5% is waste. The class is generic: content_width can be anything from 1 to 7 bits.

The type parameters are the index type, the width, and the count:

cpp 
// src/Common/CompactArray.h:19
template <typename BucketIndex, UInt8 content_width, size_t bucket_count>
class CompactArray final
{
public:
    CompactArray() = default;

content_width and bucket_count are template parameters, so the bit layout is a compile-time constant and the compiler can fold everything.

The read: a 16-bit window

Here is the accessor, and it is the whole trick:

cpp 
// src/Common/CompactArray.h:30
    /// Cells are accessed through an unaligned 16-bit word, which makes the access branchless.
    /// The trailing padding byte of the bitset keeps the word in bounds for every bucket.
    UInt8 ALWAYS_INLINE get(BucketIndex bucket_index) const
    {
        chassert(bucket_index < bucket_count);

        size_t bit = static_cast<size_t>(bucket_index) * content_width;
        UInt16 word = unalignedLoadLittleEndian<UInt16>(&bitset[bit / 8]);
        return (word >> (bit % 8)) & ((1 << content_width) - 1);
    }

Four steps:

  1. bit = bucket_index * content_width. The absolute bit offset of the value. Multiplication, not addition — the buckets are contiguous.
  2. unalignedLoadLittleEndian<UInt16>(&bitset[bit / 8]). Load the 16-bit word that contains the value’s first bit. bit / 8 is the byte index; the load may start in the middle of a byte.
  3. word >> (bit % 8). Shift the window down so the value’s first bit is at bit 0 of the word.
  4. & ((1 << content_width) - 1). Mask off everything above the value’s width.

Why 16 bits and not 8

This is the part that makes the trick work, and it is worth doing the algebra.

The value starts at bit offset bit % 8 within its byte, which is anywhere from 0 to 7. The value is content_width bits wide. So the value’s last bit sits at position (bit % 8) + content_width - 1 within the first byte.

The maximum is 7 + 7 - 1 = 13. So the value spans at most bits 0..13 of a 16-bit window — it always fits in 16 bits, whatever the alignment and whatever the width (up to 7).

With an 8-bit load, a value that straddles a byte boundary would be split across two loads and require a branch:

text 
   8-bit load:                    16-bit load:

   byte0    byte1                 byte0    byte1
   |----0000|11111111|            |----0000|11111111|
         ^              ^                ^
    value starts here   value ends       both in one 16-bit window
    -> needs 2 loads, needs a branch

Loading 16 bits unconditionally and shifting covers both cases with the same instruction sequence. No branch. That is what “branchless” in the comment means, and it matters: this accessor is called in the inner loop of a HyperLogLog insert, millions of times per query.

The load is unaligned — bit / 8 is rarely even — which is why the code uses unalignedLoadLittleEndian rather than a plain UInt16* dereference. On x86 an unaligned 16-bit load is a single instruction; on architectures that trap on unaligned access, the helper does a byte-wise assembly.

Why the shift is bit % 8 and not something else

bit / 8 gives the byte, bit % 8 gives the bit within that byte. The division and the modulo are related: bit % 8 == bit - 8 * (bit / 8). A compiler will emit one shift-and-subtract for the byte index and one and for the bit offset; on x86 the and with 7 is a single instruction.

Why little-endian

unalignedLoadLittleEndian reads the bytes and interprets them as a little-endian 16-bit integer. On a little-endian machine that is just a memcpy-shaped load; on a big-endian machine the helper byte-swaps. The point is that the bit numbering is defined as little-endian regardless of the machine, so the serialized format is portable. The HyperLogLogCounter serialiser relies on that:

cpp 
// src/Common/HyperLogLogCounter.h:367
    void write(DB::WriteBuffer & out) const
    {
        auto rank_state = rank_store.getSerializableState();
        out.write(reinterpret_cast<const char *>(rank_state.data()), rank_state.size());

        if constexpr (std::endian::native == std::endian::little)
        {
            out.write(reinterpret_cast<const char *>(&denominator), sizeof(DenominatorCalculatorType));
            out.write(reinterpret_cast<const char *>(&zeros), sizeof(ZerosCounterType));
        }
        else
        {
            constexpr size_t denom_size = sizeof(DenominatorCalculatorType);
            std::array<char, denom_size> denominator_copy;
            memcpy(denominator_copy.data(), reinterpret_cast<const char *>(&denominator), denom_size);

            for (size_t i = 0; i < denominator_copy.size(); i += (sizeof(UInt32) / sizeof(char)))
            {
                UInt32 * cur = reinterpret_cast<UInt32 *>(&denominator_copy[i]);
                DB::transformEndianness<std::endian::little, std::endian::native>(*cur);
            }
            out.write(denominator_copy.data(), denom_size);

            auto zeros_copy = zeros;
            DB::transformEndianness<std::endian::little, std::endian::native>(zeros_copy);
            out.write(reinterpret_cast<const char *>(&zeros_copy), sizeof(ZerosCounterType));
        }
    }

The bitset needs no endianness handling because its bit order is defined by the accessor, not by the machine. The scalar fields — the denominator and the zero counter — are machine words, so they need an explicit transform on a big-endian machine. The if constexpr makes the little-endian path free.

The write: read-modify-write

cpp 
// src/Common/CompactArray.h:41
    void ALWAYS_INLINE set(BucketIndex bucket_index, UInt8 content)
    {
        chassert(bucket_index < bucket_count);

        size_t bit = static_cast<size_t>(bucket_index) * content_width;
        constexpr UInt16 mask = (1 << content_width) - 1;
        UInt16 word = unalignedLoadLittleEndian<UInt16>(&bitset[bit / 8]);
        word = static_cast<UInt16>((word & ~(mask << (bit % 8))) | (static_cast<UInt16>(content) << (bit % 8)));
        unalignedStoreLittleEndian<UInt16>(&bitset[bit / 8], word);
    }

The write is the mirror of the read: load the 16-bit window, clear the value’s bits (word & ~(mask << shift)), OR in the new value (content << shift), store the window back.

Note that mask is constexpr — the shift amount is the only runtime part. And note that the store writes 16 bits, potentially touching a byte that belongs to a neighbouring bucket. That is safe precisely because the read-modify-write preserved the neighbour’s bits in the upper half of the word.

This is why set() is not atomic and why CompactArray is not thread-safe on its own: two threads writing adjacent buckets in the same 16-bit window would lose each other’s updates. The HyperLogLog that uses it is single- threaded per aggregate state.

The padding byte

cpp 
// src/Common/CompactArray.h:58
private:
    /// number of bytes in bitset
    static constexpr size_t BITSET_SIZE = (bucket_count * content_width + 7) / 8;

    /// The last byte is padding for the branchless 16-bit access; it stays zero and is not serialized.
    UInt8 bitset[BITSET_SIZE + 1] = { 0 };

The bitset is BITSET_SIZE + 1 bytes — one more than strictly needed.

Why? Because the accessor always loads 16 bits starting at bitset[bit / 8]. For the last bucket, bit / 8 is close to BITSET_SIZE, and the 16-bit load would read one byte past the end of the array.

Let’s check the worst case. The last bucket is at bit bucket_count * content_width - content_width, so bit / 8 is at most (bucket_count * content_width - content_width) / 8. The load touches bytes bit/8 and bit/8 + 1.

With bucket_count = 1 and content_width = 5: bit = 0, bit / 8 = 0, the load touches bytes 0 and 1. BITSET_SIZE = (5 + 7) / 8 = 1. So the array must be at least 2 bytes — and it is, because of the + 1.

With bucket_count = 1 and content_width = 1: bit = 0, load touches bytes 0 and 1. BITSET_SIZE = (1 + 7) / 8 = 1. Array is 2 bytes. Fine.

The padding byte is therefore loadable but never loaded-from — it stays zero, which is why the comment says so. And it is not part of the serialised form:

cpp 
// src/Common/CompactArray.h:52
    /// The serialized state is the bitset without the trailing padding byte.
    /// The serialization format must not be changed.
    std::span<const UInt8> getSerializableState() const { return {bitset, BITSET_SIZE}; }
    std::span<UInt8> getSerializableState() { return {bitset, BITSET_SIZE}; }
    static constexpr size_t serializedSize() { return BITSET_SIZE; }

“The serialization format must not be changed” is a load-bearing comment. The bitset is written to disk as part of an aggregate function’s serialised state, and an older server must be able to read a state written by a newer one. The format is the raw bitset, so any change to the bit layout — or to content_width — would break compatibility.

There is a companion test that exercises every width from 1 to 7 and every bucket count from 1 to 1024, round-tripping through the serialised form:

cpp 
// src/Common/examples/compact_array.cpp:28
template <size_t width, size_t bucket_count, typename Generator>
struct Test
{
    static void perform()
    {
        bool ok = true;

        std::string filename;

        try
        {
            using Store = DB::CompactArray<UInt64, width, bucket_count>;

            Store store;

            for (size_t i = 0; i < bucket_count; ++i)
                store.set(i, Generator::execute(i, width));

            for (size_t i = 0; i < bucket_count; ++i)
            {
                if (store.get(i) != Generator::execute(i, width))
                    throw std::runtime_error("Stored value differs from the generated one");
            }

and the width is checked against a static assertion:

cpp 
// src/Common/CompactArray.h:65
    /// Checks
    static_assert((content_width > 0) && (content_width < 8), "Invalid parameter value");
    static_assert(bucket_count <= (std::numeric_limits<size_t>::max() / content_width), "Invalid parameter value");

content_width < 8 — because the class is for values narrower than a byte. content_width == 8 would be a plain byte array, and the whole point is gone. The second assertion prevents bucket_count * content_width from overflowing size_t at compile time.

Who uses it: the HyperLogLog rank store

Now the consumer. HyperLogLogCounter stores one rank per bucket in a CompactArray:

cpp 
// src/Common/HyperLogLogCounter.h:276
    /// Size of counter's rank in bits.
    static constexpr UInt8 rank_width = details::RankWidth<HashValueType>::get();

    using Value = UInt64;
    using RankStore = DB::CompactArray<HashValueType, rank_width, bucket_count>;

And the width comes from a two-entry lookup table:

cpp 
// src/Common/HyperLogLogCounter.h:219
/// Size of counter's rank in bits.
template <typename T>
struct RankWidth;

template <>
struct RankWidth<UInt32>
{
    static constexpr UInt8 get()
    {
        return 5;
    }
};

template <>
struct RankWidth<UInt64>
{
    static constexpr UInt8 get()
    {
        return 6;
    }
};

Five bits for a 32-bit hash, six for a 64-bit hash. Where do those numbers come from?

The rank is the number of trailing zeros in the hash’s tail, capped at max_rank:

cpp 
// src/Common/HyperLogLogCounter.h:551
    static constexpr int max_rank = sizeof(HashValueType) * 8 - precision + 1;

So the maximum rank depends on both the hash width and the precision. For a 32-bit hash at precision 17, max_rank = 32 - 17 + 1 = 16; at precision 12 it is 21; at precision 20 it is 13.

The RankWidth table is a fixed constant per hash type, so it has to cover the worst case over the whole legal precision range [12, 20]:

  • UInt32: the largest max_rank is 21 (at precision 12). A rank in [0, 21] needs 5 bits, since 5 bits hold 0..31.
  • UInt64: the largest max_rank is 53 (at precision 12). A rank in [0, 53] needs 6 bits, since 6 bits hold 0..63.

So the widths are exactly “the smallest number of bits that fits the maximum possible rank”, and the maximum rank is a function of the hash width and the precision.

With the default precision of 17 and a 64-bit hash, 6 bits per bucket over 2^17 buckets is:

text 
131072 buckets x 6 bits = 786432 bits = 98304 bytes = 96 KiB

Which is exactly what the user-facing documentation says:

cpp 
// src/AggregateFunctions/AggregateFunctionUniqCombined.cpp:98
        {"HLL_precision", "Optional. The base-2 logarithm of the number of cells in HyperLogLog. The default value is 17, which is effectively 96 KiB of space (2^17 cells, 6 bits each). Range: [12, 20].", {"UInt8"}}

“2^17 cells, 6 bits each” — the bit-packing is visible in the public documentation. And the same arithmetic appears in the aggregate function’s own comment, comparing the HyperLogLog’s cost against a hash set’s:

cpp 
// src/AggregateFunctions/AggregateFunctionUniqCombined.h:112
    // We want to migrate from |HashSet| to |HyperLogLogCounter| when the sizes in memory become almost equal.
    // The size per element in |HashSet| is sizeof(Key)*2 bytes, and the overall size of |HyperLogLogCounter| is 2^K * 6 bits.
    // For Key=UInt32 we can calculate: 2^X * 4 * 2 ≤ 2^(K-3) * 6 ⇒ X ≤ K-4.

The inequality is the crossover point: a hash set of 2^X elements costs 2^X * sizeof(Key) * 2 bytes (the * 2 for the load factor), and the HyperLogLog costs 2^(K-3) * 6 bytes. Solving for X gives X ≤ K - 4, so for K = 17 the crossover is at 8192 distinct values. That is why the estimator switches to HyperLogLog so early.

The insert path

cpp 
// src/Common/HyperLogLogCounter.h:286
    /// ALWAYS_INLINE is required to have better code layout for uniqCombined function
    void ALWAYS_INLINE insert(Value value)
    {
        HashValueType hash = getHash(value);

        /// Divide hash to two sub-values. First is bucket number, second will be used to calculate rank.
        HashValueType bucket = extractBitSequence(hash, 0, precision);
        HashValueType tail = extractBitSequence(hash, precision, sizeof(HashValueType) * 8);
        UInt8 rank = calculateRank(tail);

        /// Update maximum rank for current bucket.
        update(bucket, rank);
    }

The hash is split: the low precision bits select the bucket, the remaining bits are the “tail” whose trailing-zero count is the rank. That split is the standard HyperLogLog construction — the bucket index and the rank must come from disjoint bits of the hash, or the estimate is biased.

The update: a monotonic max

cpp 
// src/Common/HyperLogLogCounter.h:456
    /// Update maximum rank for current bucket.
    /// ALWAYS_INLINE is required to have better code layout for uniqCombined function
    void ALWAYS_INLINE update(HashValueType bucket, UInt8 rank)
    {
        UInt8 cur_rank = rank_store.get(bucket);

        if (rank > cur_rank)
        {
            if (cur_rank == 0)
                --zeros;
            denominator.update(cur_rank, rank);
            rank_store.set(bucket, rank);
        }
    }

The rank store is a max, not a counter: a bucket’s rank only ever increases. So update reads the current rank, compares, and writes only if the new one is larger.

That comparison is why the branchless accessor matters less for the write path than for the read path — there is a branch here. But the branch is well-predicted (usually the rank does not increase), and the read is branchless, which is the hot case: every insert reads a bucket, and most inserts find the rank unchanged and skip the write entirely.

The zeros counter is a separate optimisation: it tracks how many buckets still have rank 0, which lets the linear-counting correction work:

cpp 
// src/Common/HyperLogLogCounter.h:540
        if (zeros != 0)
            fixed_estimate = bucket_count * (log_lut.getLog(bucket_count) - log_lut.getLog(zeros));
        else
            fixed_estimate = raw_estimate;

zeros is maintained with a dedicated narrow type, chosen at compile time by the maximum value it has to hold:

cpp 
// src/Common/HyperLogLogCounter.h:559
    /// Number of zeros in rank storage.
    using ZerosCounterType = typename details::MinCounterType<bucket_count>::Type;
    ZerosCounterType zeros = bucket_count;

And MinCounterType is the “compact the number type to the smallest that fits” trick in its purest form:

cpp 
// src/Common/HyperLogLogCounter.h:67
/// Auxiliary structure for automatic determining minimum size of counter's type depending on its maximum value.
/// Used in HyperLogLogCounter in order to spend memory efficiently.
template <UInt64 MaxValue> struct MinCounterType
{
    using Type = typename MinCounterTypeHelper<
        (MaxValue >= 1 << 8) +
        (MaxValue >= 1 << 16) +
        (MaxValue >= 1ULL << 32)
        >::Type;
};

The three comparisons evaluate to 0, 1, 2 or 3, and the helper maps that to a type:

cpp 
// src/Common/HyperLogLogCounter.h:61
template <UInt8 K> struct MinCounterTypeHelper;
template <> struct MinCounterTypeHelper<0>    { using Type = UInt8; };
template <> struct MinCounterTypeHelper<1>    { using Type = UInt16; };
template <> struct MinCounterTypeHelper<2>    { using Type = UInt32; };
template <> struct MinCounterTypeHelper<3>    { using Type = UInt64; };

So a zeros counter that can hold at most 131072 (bucket_count for precision 17) gets a UInt32 — 4 bytes instead of 8. It is a single field in the aggregate state, so the saving is trivial in absolute terms, but the technique is the point: the type of a counter is derived from its maximum value at compile time, and the same trick would apply to a counter with a million entries.

The prefetch

There is one more thing, and it is a nice touch:

cpp 
// src/Common/HyperLogLogCounter.h:300
    void ALWAYS_INLINE prefetch(Value value) const
    {
        const auto bucket = extractBitSequence(getHash(value), 0, precision);
        __builtin_prefetch(rank_store.getSerializableState().data() + static_cast<size_t>(bucket) * rank_width / 8);
    }

The HyperLogLog’s rank store is a random-access array: every insert touches a bucket chosen by the hash, which is essentially a random byte offset in a 96 KiB structure. That is a cache miss every time. The prefetch computes the byte offset of the bucket’s bits (bucket * rank_width / 8) and asks the CPU to start fetching it.

The prefetch is issued one step ahead of the access — the caller prefetches for value N+1 while inserting value N — which is the standard way to hide the latency. The CombinedCardinalityEstimator exposes it:

cpp 
// src/Common/CombinedCardinalityEstimator.h:80
    void ALWAYS_INLINE prefetch(Key value) const
    {
        const auto container_type = getContainerType();
        if (container_type == details::ContainerType::MEDIUM)
            getContainer<Medium>().prefetch(value);
        else if (container_type == details::ContainerType::LARGE)
            getContainer<Large>().prefetch(value);
    }

Note that the prefetch is not issued for the SMALL container — a linear array of at most 16 elements is already in cache.

Seeing it from SQL

sql 
SELECT uniqCombined(number) FROM numbers(1e6);
text 
┌─uniqCombined(number)─┐
│              1001148 │
└──────────────────────┘

And the precision parameter directly controls the memory:

sql 
SELECT uniqCombined(15)(number) FROM numbers(1e5);
text 
┌─uniqCombined(15)(number)─┐
│                   100768 │
└──────────────────────────┘

The accuracy improves with precision and the memory grows with it: 2^12 cells at 6 bits is 3 KiB, 2^17 is 96 KiB, 2^20 is 768 KiB. The relative error of a HyperLogLog is roughly 1.04 / sqrt(2^precision), so 2^12 gives about 1.6% error and 2^17 about 0.29%.

The bit-packing is why the absolute numbers are small: a UInt8 rank store at precision 20 would be 1 MiB, and the packed one is 768 KiB.

You can also watch the estimator switch representations:

sql 
SELECT uniqCombined(x) FROM numbers(1000000) GROUP BY x % 10;

Each group gets its own CombinedCardinalityEstimator, which starts as a 16-element array, becomes a hash set, and becomes a HyperLogLog only if it needs to. The small and medium containers have no rank store at all.

Trade-offs

What the packing buys you. For the default uniqCombined, 5-6 bits per bucket instead of 8. That is 80 KiB instead of 128 KiB per aggregate state (2^17 buckets, 64-bit hash), and the saving scales with the number of groups. For a query with 10 000 groups, that is 470 MiB versus 1.25 GiB of aggregate state — the difference between fitting in memory and not.

What it costs. The accessor is three instructions more than a byte array load, and it does an unaligned load. On x86 an unaligned 16-bit load is free; on other architectures the helper does more work. The set() path is a read-modify-write, so it is not atomic and adjacent-bucket updates from two threads would conflict. The class is not thread-safe on its own.

Why not just use 8 bits and be done? You could, and for a small number of buckets you should. The packing only pays off when the structure is large enough that the memory dominates the cache behaviour — which is exactly the HyperLogLog’s situation.

Why the padding byte rather than a bounds check? The bounds check would be a branch on the hot path, and the branch would be perfectly predicted (never taken) — but it would still be a branch, and it would inhibit some optimisations. One extra byte per bitset is cheaper than one extra branch per access.

Why not use 32-bit words instead of 16? A 32-bit load would also work and would need fewer padding bytes, but it would read up to 4 bytes per access instead of 2, doubling the memory traffic on a structure that is already cache-missing. Sixteen bits is exactly enough to hold any content_width < 8 value at any alignment, and no more.

The part people get wrong. The serialised format is the raw bitset, so content_width is part of the on-disk contract. Changing the width changes the format, and an old server reading a new server’s aggregate state would read garbage. That is why the comment says “must not be changed”, and why the width is baked into the type rather than being a runtime parameter.

What to go do about it. If you are using uniqCombined with a high precision and many groups, the memory is the thing to watch:

sql 
SELECT
    query,
    formatReadableSize(memory_usage) AS state_size
FROM system.query_log
WHERE type = 'QueryFinish' AND memory_usage > 100000000
ORDER BY memory_usage DESC
LIMIT 10;

A query whose aggregate states dominate its memory is a candidate for a lower precision — uniqCombined(14) instead of uniqCombined(20) — if you can accept the accuracy loss.

Wrapping up

The one thing to remember: the width of a stored value is a compile-time constant, and the access is a shift-and-mask over an unaligned 16-bit window. That is why a HyperLogLog rank costs 5 or 6 bits and not 8.

The part people get wrong: the accessor always reads 16 bits, so the bitset has one extra byte at the end. That byte is not padding you can remove — it is what makes the last bucket’s load in bounds.

What to go do about it: the next time you see a CompactArray, notice that the width is not arbitrary. It is ceil(log2(max_rank + 1)) where max_rank is derived from the hash width and the precision, and the whole design follows from that one number.

ClickhouseInternalsPerformanceBit tricksMemory