ClickHouse Packs Short Strings Into Hash Table Keys: No Allocation Per Key

TL;DR: ClickHouse never stores a std::string in a hash table cell. It splits keys into size classes and packs strings of up to 24 bytes into plain integers, so your GROUP BY allocates nothing per key.

Strings are the most common GROUP BY key you’ll ever write. They’re also the worst case for a hash table.

Put a std::string in a cell and you get one heap allocation per distinct key. Put a std::string_view in a cell and the bytes have to outlive the table — which for an aggregation means copying them into an arena first.

ClickHouse’s answer is a hash table that is not a hash table. Instead of one table with a variable-size key, StringHashTable keeps five separate tables, one per key size class, and packs short keys into fixed-width integers.

The payoff: every cell is the same size, no key ever allocates, and the compiler can dispatch on key length at compile time.

The whole thing lives in src/Common/HashTable/StringHashTable.h, with the map specialisation in StringHashMap.h.

Five tables, one per size class

The composite table is five sub-tables:

cpp
// src/Common/HashTable/StringHashTable.h:234
template <typename SubMaps>
class StringHashTable : private boost::noncopyable
{
protected:
    static constexpr size_t NUM_MAPS = 5;
    // Map for storing empty string
    using T0 = typename SubMaps::T0;

    // Short strings are stored as numbers
    using T1 = typename SubMaps::T1;
    using T2 = typename SubMaps::T2;
    using T3 = typename SubMaps::T3;

    // Long strings are stored as std::string_view along with saved hash
    using Ts = typename SubMaps::Ts;
    using Self = StringHashTable;

and the storage:

cpp
// src/Common/HashTable/StringHashTable.h:254
    T0 m0;
    T1 m1;
    T2 m2;
    T3 m3;
    Ts ms;

Here’s what lives where:

Table	Key type	Holds
`m0`	—	the empty string, in a dedicated slot
`m1`	`StringKey8` (`UInt64`)	1..8 bytes
`m2`	`StringKey16` (`UInt128`)	9..16 bytes
`m3`	`StringKey24`	17..24 bytes
`ms`	`std::string_view` + saved hash	25+ bytes, or short strings with a trailing zero

And the key types are just integers:

cpp
// src/Common/HashTable/StringHashTable.h:10
using StringKey8 = UInt64;
using StringKey16 = UInt128;
struct StringKey24
{
    UInt64 a;
    UInt64 b;
    UInt64 c;

    bool operator==(const StringKey24 rhs) const { return a == rhs.a && b == rhs.b && c == rhs.c; }
};

So a 20-byte string becomes three UInt64s and nothing else. No length field. No pointer. No allocation.

The length is implicit — it’s recovered from the position of the first zero byte.

The packing: how a string becomes a number

The heart of the file is dispatchOnKeyClass. It classifies a key, packs it, hashes it, and calls a callback with the right sub-table. It’s written for speed, and the comment says so out loud:

cpp
// src/Common/HashTable/StringHashTable.h:357
    // Dispatch is written in a way that maximizes the performance:
    // 1. Always memcpy 8 times bytes
    // 2. Use switch case extension to generate fast dispatching table
    // 3. Funcs are named callables that can be force_inlined
    //
    /// Note: the key bytes must be readable in 8-byte chunks (a `std::string` cannot be passed
    /// here, while e.g. `ColumnString::getDataAt` can), because the packing copies 8 bytes at a
    /// time.
    template <typename Resolver, typename KeyHolder, typename HashProvider, typename Func>
    static auto ALWAYS_INLINE dispatchOnKeyClass(Resolver && resolver, KeyHolder && key_holder, HashProvider && hash_of, Func && func)
    {
        const auto & x = keyHolderGetKey(key_holder);
        const size_t sz = x.size();
        if (sz == 0)
        {
            keyHolderDiscardKey(key_holder);
            return func(resolver(std::integral_constant<size_t, 0>{}, 0), VoidKey{}, 0);
        }

        if (x[sz - 1] == 0)
        {
            // Strings with trailing zeros are not representable as fixed-size
            // string keys. Put them to the generic table.
            const size_t res = hash_of(x);
            return func(resolver(std::integral_constant<size_t, 4>{}, res), std::forward<KeyHolder>(key_holder), res);
        }

        const char * p = x.data();
        // pending bits that needs to be shifted out
        const char s = (-sz & 7) * 8;

The switch ((sz - 1) >> 3) that follows turns the length into one of four cases, and the compiler turns that into a jump table or a chain of comparisons:

cpp
// src/Common/HashTable/StringHashTable.h:394
        switch ((sz - 1) >> 3)
        {
            case 0: // 1..8 bytes
            {
                // first half page
                if ((reinterpret_cast<uintptr_t>(p) & 2048) == 0)
                {
                    memcpy(&n[0], p, 8);
                    if constexpr (std::endian::native == std::endian::little)
                        n[0] &= -1ULL >> s;
                    else
                        n[0] &= -1ULL << s;
                }
                else
                {
                    const char * lp = x.data() + x.size() - 8;
                    memcpy(&n[0], lp, 8);
                    if constexpr (std::endian::native == std::endian::little)
                        n[0] >>= s;
                    else
                        n[0] <<= s;
                }
                const size_t res = hash_of(k8);
                keyHolderDiscardKey(key_holder);
                return func(resolver(std::integral_constant<size_t, 1>{}, res), k8, res);
            }

Three tricks are hiding in those twenty lines. This is the part people get wrong the first time they read it.

Trick one: the trailing-zero test. A fixed-size string key encodes its length implicitly, by the position of the first zero byte. That means a string whose last byte is zero cannot be represented at all: "ab\0" and "ab" would pack to the same 8 bytes. So such strings get pushed to the generic table before the switch:

cpp
// src/Common/HashTable/StringHashTable.h:376
        if (x[sz - 1] == 0)
        {
            // Strings with trailing zeros are not representable as fixed-size
            // string keys. Put them to the generic table.
            const size_t res = hash_of(x);
            return func(resolver(std::integral_constant<size_t, 4>{}, res), std::forward<KeyHolder>(key_holder), res);
        }

Trick two: the mask/shift pair. s = (-sz & 7) * 8 is the number of padding bits you need to round the length up to a multiple of 8. In the first branch, the 8 bytes are read forwards from the start of the string and the padding bits are cleared with a mask. In the second branch, the 8 bytes are read backwards from the end of the string and the padding bits are shifted out.

Trick three: the “first half page” rule. Reading 8 bytes from a 3-byte string reads 5 bytes past its end. That’s only safe if those bytes are mapped. The condition

cpp
// src/Common/HashTable/StringHashTable.h:399
                if ((reinterpret_cast<uintptr_t>(p) & 2048) == 0)

tests whether the address is 2048-byte aligned. If it is, at least 2048 bytes of the page are still ahead of it, so reading 8 bytes forward cannot fault. Otherwise the code reads backwards instead, ending exactly at the last byte of the string.

The bytes before the string that this reads are then shifted out — the >>= s discards exactly the (-sz & 7) bytes that belong to the previous string or to the column’s offset array. So the garbage is read but never used.

The 9..16 and 17..24 byte cases use the same trick with two and three words:

cpp
// src/Common/HashTable/StringHashTable.h:420
            case 1: // 9..16 bytes
            {
                memcpy(&n[0], p, 8);
                const char * lp = x.data() + x.size() - 8;
                memcpy(&n[1], lp, 8);
                if constexpr (std::endian::native == std::endian::little)
                    n[1] >>= s;
                else
                    n[1] <<= s;
                const size_t res = hash_of(k16);
                keyHolderDiscardKey(key_holder);
                return func(resolver(std::integral_constant<size_t, 2>{}, res), k16, res);
            }

Notice that the first word is always read forwards from p — for a 9-byte string that’s inside the string — while the last word is read backwards from the end. The overlap between them is harmless: the bytes in the middle get read twice with the same values.

Unpacking: getting the string back

Going the other way, the length is recovered from the number of leading zero bytes:

cpp
// src/Common/HashTable/StringHashTable.h:21
inline std::string_view ALWAYS_INLINE toStringView(const StringKey8 & n)
{
    chassert(n != 0);
    if constexpr (std::endian::native == std::endian::big)
        return {reinterpret_cast<const char *>(&n), 8ul - (std::countr_zero(n) >> 3)};
    else
        return {reinterpret_cast<const char *>(&n), 8ul - (std::countl_zero(n) >> 3)};
}

countl_zero(n) >> 3 is the number of whole zero bytes at the end of the word, so 8 - that is the string length. On a big-endian machine the zero bytes sit at the other end, hence the countr_zero variant.

The empty-cell rule, specialised per size class

The “empty cell is a zeroed cell” rule from the generic table needs a sensible notion of “zero” for a packed string key. For StringKey16 the rule is “the last word is zero”:

cpp
// src/Common/HashTable/StringHashMap.h:20
template <typename TMapped>
struct StringHashMapCell<StringKey16, TMapped> : public HashMapCell<StringKey16, TMapped, StringHashTableHash, HashTableNoState>
{
    using Base = HashMapCell<StringKey16, TMapped, StringHashTableHash, HashTableNoState>;
    using value_type = typename Base::value_type;
    using Base::Base;
    static constexpr bool need_zero_value_storage = false;
    bool isZero(const HashTableNoState & state) const { return isZero(this->value.first, state); }

    // Zero means unoccupied cells in hash table. Use key with last word = 0 as
    // zero keys, because such keys are unrepresentable (no way to encode length).
    static bool isZero(const StringKey16 & key, const HashTableNoState &) { return key.items[1] == 0; }
    void setZero() { this->value.first.items[1] = 0; }

The reasoning is the same as in the generic table. A packed key with a zero last word would have to encode the length “16” with no room for a terminating zero byte, so such a key cannot exist. The encoding is injective on all valid keys, and the all-zero pattern is unreachable. That makes it safe to use as the empty marker.

Same for StringKey24, where the marker is the third word:

cpp
// src/Common/HashTable/StringHashMap.h:49
    // Zero means unoccupied cells in hash table. Use key with last word = 0 as
    // zero keys, because such keys are unrepresentable (no way to encode length).
    static bool isZero(const StringKey24 & key, const HashTableNoState &)
    { return key.c == 0; }
    void setZero() { this->value.first.c = 0; }

The generic std::string_view cell can’t do this. A string_view is a pointer and a length, and a zeroed one is a null pointer with length 0 — which is a legal key, namely the empty string. So the generic cell declares that it needs no zero storage, and the empty string gets its own slot instead:

cpp
// src/Common/HashTable/StringHashTable.h:134
template <typename Cell>
struct StringHashTableEmpty // NOLINT(cppcoreguidelines-pro-type-member-init,hicpp-member-init) - `zero_value_storage` is raw storage for placement new, only written when `has_zero` becomes true
{
    using Self = StringHashTableEmpty;

    bool has_zero = false;
    alignas(Cell) std::byte zero_value_storage[sizeof(Cell)];

public:
    bool hasZero() const { return has_zero; }

And that empty slot isn’t a hash table at all — it’s a single cell with an emplace that ignores the key entirely:

cpp
// src/Common/HashTable/StringHashTable.h:172
    template <typename KeyHolder>
    void ALWAYS_INLINE emplace(KeyHolder &&, LookupResult & it, bool & inserted, size_t = 0)
    {
        if (!hasZero())
        {
            setHasZero();
            inserted = true;
        }
        else
            inserted = false;
        it = zeroValue();
    }

Hashing: CRC32C where it can, CityHash where it can’t

The hash function is chosen per class, and for the fixed-size classes it’s the hardware CRC32C instruction:

cpp
// src/Common/HashTable/StringHashTable.h:46
struct StringHashTableHash
{
#if defined(__SSE4_2__)
    size_t ALWAYS_INLINE operator()(StringKey8 key) const
    {
        size_t res = -1ULL;
        res = _mm_crc32_u64(res, key);
        return res;
    }
    size_t ALWAYS_INLINE operator()(StringKey16 key) const
    {
        size_t res = -1ULL;
        res = _mm_crc32_u64(res, key.items[0]);
        res = _mm_crc32_u64(res, key.items[1]);
        return res;
    }

with an AArch64 CRC32 path, an s390x path, and CityHash as the portable fallback:

cpp
// src/Common/HashTable/StringHashTable.h:114
#else
    size_t ALWAYS_INLINE operator()(StringKey8 key) const
    {
        return CityHash_v1_0_2::CityHash64(reinterpret_cast<const char *>(&key), 8);
    }

CRC32 is a poor hash function in the abstract — the header of the generic hash file says so — but it’s one instruction per 8 bytes with a three-cycle latency, and the table is small enough to fit in cache most of the time.

There’s another requirement, and it’s the one that actually constrains the design: the hash has to be consistent with the packing. The hash is computed over the packed word, not over the original bytes, so "abc" and "abc\0..." can’t collide by accident. They hash different words.

The lookup result: why you never see the key

The string table doesn’t return a pointer to a cell. It returns a pointer to the mapped value, wrapped in a small type:

cpp
// src/Common/HashTable/StringHashTable.h:214
template <typename Mapped>
struct StringHashTableLookupResult
{
    Mapped * mapped_ptr;
    StringHashTableLookupResult() {} /// NOLINT
    StringHashTableLookupResult(Mapped * mapped_ptr_) : mapped_ptr(mapped_ptr_) {} /// NOLINT
    StringHashTableLookupResult(std::nullptr_t) {} /// NOLINT
    const VoidKey getKey() const { return {}; } /// NOLINT
    auto & getMapped() { return *mapped_ptr; }
    auto & operator*() { return *this; }
    auto & operator*() const { return *this; }
    auto * operator->() { return this; }
    auto * operator->() const { return this; }
    explicit operator bool() const { return mapped_ptr; }

The reason is that the key lives in the cell, and the caller usually only wants the aggregate state. But the key is still there — just in a different sub-table with a different representation. Returning a pointer to it would mean returning a pointer to a StringKey8 or to a string_view, which have different types depending on the size class.

So the key is erased from the interface: getKey() returns a VoidKey.

Reserving and growing: where the heuristic leaks

The string table grows differently from the generic one:

cpp
// src/Common/HashTable/StringHashTable.h:207
template <size_t initial_size_degree = 8>
struct StringHashTableGrower : public HashTableGrowerWithPrecalculation<initial_size_degree>
{
    // Smooth growing for string maps
    void increaseSize() { this->increaseSizeDegree(1); }
};

The generic grower doubles the buffer on overflow. The string grower grows by a factor of two in the exponent, i.e. by one power of two — the same thing, but expressed as a single degree increment so it composes with the precalculated mask.

Reserving is divided evenly over the four real sub-maps, because the caller only knows the total number of keys:

cpp
// src/Common/HashTable/StringHashTable.h:317
    explicit StringHashTable(size_t reserve_for_num_elements)
        : m1{reserve_for_num_elements / 4}
        , m2{reserve_for_num_elements / 4}
        , m3{reserve_for_num_elements / 4}
        , ms{reserve_for_num_elements / 4}
    {
    }

That guess is often wrong. A table of 20-byte strings uses m3 only, and m1, m2, ms reserve space they will never touch.

The aggregator knows this, and refuses to pre-reserve the string tables:

cpp
// src/Interpreters/Aggregator.cpp:5214
    /// `StringHashTable::reserve` splits the hint evenly over its four size-class sub-maps,
    /// while a real key set concentrates in one of them, so it is not reserved.
    constexpr bool can_reserve = requires { dst.reserve(size_t{}); } && !requires { dst.emptyStringSlot(); };

And the emptyStringSlot() method exists precisely so that this requires expression can tell a StringHashTable from an ordinary hash table:

cpp
// src/Common/HashTable/StringHashTable.h:312
    /// The dedicated slot of the empty-string key, which the sub-table dispatch hashes to 0.
    T0 & emptyStringSlot() { return m0; }

Where it’s used: three string-key aggregation variants

The string map is one of the standard aggregation data variants:

cpp
// src/Interpreters/AggregatedData.h:53
using AggregatedDataWithPackedStringKey = HashMap<PackedStringRef, AggregateDataPtr>;
using AggregatedDataWithShortStringKey = StringHashMap<AggregateDataPtr>;
using AggregatedDataWithStringKey = HashMapWithSavedHash<std::string_view, AggregateDataPtr>;

Three flavours of string key, three tables:

AggregatedDataWithPackedStringKey — a PackedStringRef, a pointer plus a length, with the payload inline for short strings;
AggregatedDataWithShortStringKey — the composite StringHashMap of this article;
AggregatedDataWithStringKey — a plain std::string_view map with a saved hash, where the key bytes live in an arena.

The StringHashMap variant is the interesting one, because it’s the only one where the key doesn’t live anywhere else. The string is in the table, as three machine words.

Trade-offs: what you win and what you pay

What the packed string table buys you:

No allocation per key. A 20-byte key is three UInt64s inside the cell. Nothing is copied into an arena, nothing is freed.
A uniform cell size. Every cell of m1 is 8 bytes of key plus the mapped value; every cell of m3 is 24 bytes plus the mapped value. The table can be scanned, and the compiler can generate good code for it.
A compile-time dispatch on length. dispatchOnKeyClass is a template over the size class, so each branch is specialised: the m1 path hashes one word, the m3 path hashes three.
A hash over the packed form. The hash is computed over exactly the bytes that are stored, so the stored key and the hashed key can never disagree.

What it costs you:

The bytes of the key are duplicated. The cell holds the packed key, and if the caller needs the original string it has to be reconstructed with toStringView.
The trailing-zero case is a wart. A string ending in \0 — which happens with binary data, and with FixedString columns padded with zeros — can’t use the packed classes and falls back to the generic table, where the key is a string_view into the arena.
The reservation heuristic is bad. Reserving n/4 for each of the four sub-maps wastes memory whenever the keys concentrate in one class, which is the normal case.
The empty string needs its own slot, and the key type of the generic sub-table isn’t the same as the key type of the packed ones, so the composite has to be written as a template over a SubMaps bundle rather than as a plain HashTable.

This is a good example of a general principle: when the key type has a size distribution, splitting the table by size class turns a variable-size-cell problem into a set of fixed-size-cell problems, and lets the compiler specialise each one.

Wrapping up

Worth internalizing: a GROUP BY over strings is a memory-bound benchmark before it’s a CPU-bound one. ClickHouse’s whole trick here is to make the key be the data — no arena, no pointer chasing, no allocator traffic.

So if you’re tuning an aggregation and it feels allocation-heavy, check what your key type maps to. Short, non-zero-terminated strings hit the fast path. FixedString padded with zeros and raw binary blobs do not — and that’s a silent cliff, not an error message.

Next time you’re profiling, watch for memcpy traffic coming out of the aggregator rather than out of the storage layer. That’s the signature of this code path not doing what you expect.