ClickHouse Marks Empty Hash Table Cells With Zeroed Memory

TL;DR: ClickHouse’s hash table has no occupancy bit, no tombstone, and no sentinel pointer. A cell is empty when its key is all zero bytes, and the buffer starts zeroed because the allocator uses calloc. That one decision ripples through the cell layout, the zero-key special case, deletion, and even why the hash function has to be good.

Every GROUP BY in ClickHouse is a hash table. The table has to hold millions of keys, be probed once per input row, and be resized while it is being filled — all while the query is competing for memory with everything else on the machine.

std::unordered_map is simply not competitive here: it allocates a node per element, keeps a pointer chain, and pays a pointer chase for every collision.

So ClickHouse ships its own hash table in src/Common/HashTable/HashTable.h: a flat array of cells, open addressing, linear probing. The probing is textbook. The interesting part is the bookkeeping around emptiness.

There is no “occupied” bit. No tombstone. No sentinel pointer. No version counter. A cell is empty when its key is all zero bytes, and the whole buffer starts out zeroed by the allocator.

That single decision shapes the entire file: the allocator, the cell layout, the way the zero key is handled, the way deletion works, and the reason the hash function has to be good.

The shape of the table

cpp
// src/Common/HashTable/HashTable.h:518
template <typename Key, typename Cell, typename Hash, typename Grower, typename Allocator>
class HashTable : private boost::noncopyable,
                  protected Hash,
                  protected Allocator,
                  protected Cell::State,
                  public ZeroValueStorage<Cell::need_zero_value_storage, Cell> /// empty base optimization
{

The table is one contiguous buffer of Cells plus a Grower that knows the buffer size:

cpp
// src/Common/HashTable/HashTable.h:550
    size_t m_size = 0;        /// Amount of elements
    Cell * buf;               /// A piece of memory for all elements except the element with zero key.
    Grower grower;

Cell is a policy class. The simplest one stores nothing but a key:

cpp
// src/Common/HashTable/HashTable.h:154
template <typename Key, typename Hash, typename TState = HashTableNoState>
struct HashTableCell
{
    using State = TState;

    using key_type = Key;
    using value_type = Key;
    using mapped_type = VoidMapped;

    Key key;

The map flavour stores a pair, and the variant that ClickHouse uses for aggregation additionally caches the hash so that a rehash does not have to recompute it:

cpp
// src/Common/HashTable/HashMap.h:165
template <typename Key, typename TMapped, typename Hash, typename TState = HashTableNoState>
struct HashMapCellWithSavedHash : public HashMapCell<Key, TMapped, Hash, TState> // NOLINT(cppcoreguidelines-pro-type-member-init,hicpp-member-init) - `saved_hash` is set by `setHash` immediately after placement construction on insert; on the hot aggregation/join path we must avoid the redundant store
{
    using Base = HashMapCell<Key, TMapped, Hash, TState>;

    size_t saved_hash;

Empty means zero

Here is the whole emptiness protocol:

cpp
// src/Common/HashTable/HashTable.h:191
    /// Whether the key is zero. In the main buffer, cells with a zero key are considered empty.
    /// If zero keys can be inserted into the table, then the cell for the zero key is stored separately, not in the main buffer.
    /// Zero keys must be such that the zeroed-down piece of memory is a zero key.
    bool isZero(const State & state) const { return isZero(key, state); }
    static bool isZero(const Key & key, const State & /*state*/) { return ZeroTraits::check(key); }

    /// Set the key value to zero.
    void setZero() { ZeroTraits::set(key); }

and the generic part:

cpp
// src/Common/HashTable/HashTable.h:89
namespace ZeroTraits
{

template <typename T>
bool check(const T x)
{
    return bitEquals(x, T{});
}

template <typename T>
void set(T & x) { x = T{}; }

}

bitEquals is bitwise, not ==, and that matters for floating point:

cpp
// src/Common/HashTable/HashTable.h:77
template <typename T>
inline ALWAYS_INLINE bool bitEquals(T a, T b)
{
    if constexpr (is_floating_point<T>)
        /// Note that memcmp with constant size is a compiler builtin.
        return 0 == memcmp(&a, &b, sizeof(T)); /// NOLINT
    else
        return a == b;
}

The comment above it explains why bit equality is mandatory rather than merely nice:

cpp
// src/Common/HashTable/HashTable.h:71
/** Numbers are compared bitwise.
  * Complex types are compared by operator== as usual (this is important if there are gaps).
  *
  * This is needed if you use floats as keys. They are compared by bit equality.
  * Otherwise the invariants in hash table probing do not met when NaNs are present.
  */

NaN never equals itself, so a ==-based emptiness test could never recognise an empty float cell — and the probe loop would run right off the end of the buffer.

The zeroed buffer comes from the allocator:

cpp
// src/Common/HashTable/HashTableAllocator.h:8
/**
  * We are going to use the entire memory we allocated when resizing a hash
  * table, so it makes sense to pre-fault the pages so that page faults don't
  * interrupt the resize loop. Set the allocator parameter accordingly.
  */
using HashTableAllocator = Allocator<true /* clear_memory */, true /* populate */>;

clear_memory becomes calloc:

cpp
// src/Common/Allocator.cpp:79
    if (alignment <= MALLOC_MIN_ALIGNMENT) [[likely]]
    {
        if constexpr (clear_memory)
            buf = __real_calloc(size, 1);
        else
            buf = __real_malloc(size);

So the invariant is: the bytes of a fresh buffer are zero, therefore a fresh cell is empty. Nothing more is needed to track occupancy. The diagram of the buffer is therefore very simple:

text
     buf                                                        buf + bufSize()
      |                                                              |
      v                                                              v
      +--------+--------+--------+--------+--------+--------+--------+--------+
      | cell 0 | cell 1 | cell 2 | cell 3 | cell 4 | cell 5 | cell 6 | cell 7 |
      +--------+--------+--------+--------+--------+--------+--------+--------+
        key=A      (zero)    key=C    (zero)    key=B    (zero)    (zero)
        [used]    [empty]   [used]   [empty]   [used]   [empty]   [empty]

Note what is not there: no occupancy byte, no pointer, no version. A HashMapCell<UInt64, AggregateState*> is 16 bytes of pure payload. The empty/used distinction is free.

The zero key gets its own slot

There is one hole in the “zero means empty” scheme: 0 is a perfectly legal key. If it were stored in the buffer, it would be indistinguishable from an empty cell. So it is stored outside the buffer, in a ZeroValueStorage that the table inherits from:

cpp
// src/Common/HashTable/HashTable.h:474
template <typename Cell>
struct ZeroValueStorage<true, Cell> // 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
{
private:
    bool has_zero = false;
    alignas(Cell) std::byte zero_value_storage[sizeof(Cell)];

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

    void setHasZero()
    {
        has_zero = true;
        new (zeroValue()) Cell();
    }

and the insert path routes the zero key to it:

cpp
// src/Common/HashTable/HashTable.h:1354
    bool ALWAYS_INLINE emplaceIfZero(const Key & x, LookupResult & it, bool & inserted, size_t hash_value)
    {
        /// If it is claimed that the zero key can not be inserted into the table.
        if constexpr (!Cell::need_zero_value_storage)
            return false;

        if (unlikely(Cell::isZero(x, *this)))
        {
            it = this->zeroValue();

            if (!this->hasZero())
            {
                ++m_size;
                this->setHasZero();
                this->zeroValue()->setHash(hash_value);
                inserted = true;
            }
            else
                inserted = false;

            return true;
        }

        return false;
    }

The zero key lives at a fixed address, so a lookup for it is a branch and a pointer, never a probe. The cost of the scheme is one bool plus one Cell of storage per table, and a slightly awkward iteration order (the zero cell is visited first, then the buffer).

And this is not an exotic corner. 0 is a perfectly ordinary grouping key:

sql
SELECT k, count() FROM t GROUP BY k;

with a k column full of zeros produces a group whose key is the zero key, and that group is the one stored in the separate slot.

Note also that the design is conditional: a cell type can declare that zero keys are impossible (need_zero_value_storage = false), and then ZeroValueStorage<false, Cell> degenerates to nothing at all. The string tables do exactly that — see the article on the string-specialised map.

Probing

The probe sequence is the simplest possible one: linear probing with a mask.

cpp
// src/Common/HashTable/HashTable.h:232
    /// The size of the hash table in the cells.
    size_t bufSize() const               { return 1ULL << size_degree; }

    size_t maxFill() const               { return 1ULL << (size_degree - 1); }
    size_t mask() const                  { return bufSize() - 1; }

    /// From the hash value, get the cell number in the hash table.
    size_t place(size_t x) const         { return x & mask(); }

    /// The next cell in the collision resolution chain.
    size_t next(size_t pos) const        { ++pos; return pos & mask(); }

    /// Whether the hash table is sufficiently full. You need to increase the size of the hash table, or remove something unnecessary from it.
    bool overflow(size_t elems) const    { return elems > maxFill(); }

The load factor is 0.5: maxFill() is half the buffer. And the probe loop itself:

cpp
// src/Common/HashTable/HashTable.h:559
    size_t ALWAYS_INLINE findCell(const Key & x, size_t hash_value, size_t place_value) const
    {
        while (!buf[place_value].isZero(*this) && !buf[place_value].keyEquals(x, hash_value, *this))
        {
            place_value = grower.next(place_value);
#ifdef DBMS_HASH_MAP_COUNT_COLLISIONS
            ++collisions;
#endif
        }

        return place_value;
    }

Two things to note. First, isZero is checked before keyEquals: the loop stops at the first empty cell, because with linear probing an empty cell terminates the chain. Second, the comparison is a bitwise equality against the key, and for the HashMapCellWithSavedHash variant it is short-circuited by the cached hash.

The zero key is handled before the probe:

cpp
// src/Common/HashTable/HashTable.h:1617
    LookupResult ALWAYS_INLINE find(const Key & x)
    {
        if (Cell::isZero(x, *this))
            return this->hasZero() ? this->zeroValue() : nullptr;

        return findNonZeroCell(x, hash(x));
    }

Insertion

emplace computes the hash, routes the zero key, and otherwise finds a place:

cpp
// src/Common/HashTable/HashTable.h:1380
    template <typename KeyHolder>
    void ALWAYS_INLINE emplaceNonZeroImpl(size_t place_value, KeyHolder && key_holder,
                                          LookupResult & it, bool & inserted, size_t hash_value)
    {
        it = &buf[place_value];

        if (!buf[place_value].isZero(*this))
        {
            keyHolderDiscardKey(key_holder);
            inserted = false;
            return;
        }

        keyHolderPersistKey(key_holder);
        const auto & key = keyHolderGetKey(key_holder);

        new (&buf[place_value]) Cell(key, *this);
        buf[place_value].setHash(hash_value);
        inserted = true;
        ++m_size;

        if (unlikely(grower.overflow(m_size)))
        {
            try
            {
                resize();
            }
            catch (...)
            {
                /** If we have not resized successfully, then there will be problems.
                  * There remains a key, but uninitialized mapped-value,
                  *  which, perhaps, can not even be called a destructor.
                  */
                --m_size;
                buf[place_value].setZero();
                inserted = false;
                keyHolderDiscardKey(key_holder);
                throw;
            }

            // The hash table was rehashed, so we have to re-find the key.
            it = findNonZeroCell(key, hash_value);
            chassert(it);
        }
    }

Two details worth pausing on. The cell is placement-newed; the buffer is raw memory, and the destructor of a non-trivial cell is only run for cells that were actually constructed (destroyElements walks the table and calls the destructor only for non-zero cells).

And the resize happens after the insert, not before. That means the table can exceed its nominal capacity by one element, and it means the iterator has to be re-found afterwards, because the rehash moved the cell. The exception handler is careful to undo the insert (decrement the size, zero the cell) so that a failed allocation does not leave a half-built cell behind.

Growing: the wrap-around special case

The resize path is where the linear-probing invariants get hairy. When the buffer grows, every element has to be re-placed, and an element that was at the end of the old buffer may belong at the beginning of the new one because its collision chain wrapped around:

cpp
// src/Common/HashTable/HashTable.h:837
    void resize(size_t for_num_elems = 0, size_t for_buf_size = 0)
    {
#ifdef DBMS_HASH_MAP_DEBUG_RESIZES
        Stopwatch watch;
#endif

        size_t old_size = grower.bufSize();

        /** In case of exception for the object to remain in the correct state,
          *  changing the variable `grower` (which determines the buffer size of the hash table)
          *  is postponed for a moment after a real buffer change.
          * The temporary variable `new_grower` is used to determine the new size.
          */
        Grower new_grower = grower;

and the re-placement loop:

cpp
// src/Common/HashTable/HashTable.h:884
            size_t i = 0;
            for (; i < old_size; ++i)
                if (!buf[i].isZero(*this))
                    reinsert(buf[i], buf[i].getHash(*this));

            /** There is also a special case:
              *    if the element was to be at the end of the old buffer,                  [        x]
              *    but is at the beginning because of the collision resolution chain,      [o       x]
              *    then after resizing, it will first be out of place again,               [        xo        ]
              *    and in order to transfer it where necessary,
              *    after transferring all the elements from the old halves you need to     [         o   x    ]
              *    process tail from the collision resolution chain immediately after it   [        o    x    ]
              */
            size_t new_size = grower.bufSize();
            for (; i < new_size && !buf[i].isZero(*this); ++i)
                reinsert(buf[i], buf[i].getHash(*this));

The picture in that comment is the whole problem: after the buffer is doubled, the element at the very end of the old buffer (x) is now in the middle of the new one, and the element that was pushed behind it (o) belongs before it. The second loop therefore keeps going past the end of the old buffer, as long as the cells it finds are non-empty, re-inserting them.

The re-insertion itself is a memcpy of a trivially-copyable cell into the new position:

cpp
// src/Common/HashTable/HashTable.h:918
    void reinsert(Cell & x, size_t hash_value)
    {
        size_t place_value = grower.place(hash_value);

        /// If the element is in its place.
        if (&x == &buf[place_value])
            return;

        /// Compute a new location, taking into account the collision resolution chain.
        place_value = findCell(Cell::getKey(x.getValue()), hash_value, place_value);

        /// If the item remains in its place in the old collision resolution chain.
        if (!buf[place_value].isZero(*this))
            return;

        /// Copy to a new location and zero the old one.
        x.setHash(hash_value);
        memcpy(static_cast<void*>(&buf[place_value]), &x, sizeof(x)); /// NOLINT(bugprone-undefined-memory-manipulation)
        x.setZero();
    }

The grower doubles the size until max_size_degree (23) and then grows by one step at a time:

cpp
// src/Common/HashTable/HashTable.h:247
    /// Increase the size of the hash table.
    void increaseSize()
    {
        size_degree += size_degree >= max_size_degree ? 1 : 2;
    }

Robin Hood: what changed recently

The most interesting recent addition to the file is a second probing discipline. The classic HashTableGrower keeps the load factor at 0.5; the new HashTableGrowerWithPrecalculationAndRobinHood keeps 0.5 until the table reaches 2^16 cells, and then switches to Robin Hood hashing with a 90% load factor — in place, without reallocating:

cpp
// src/Common/HashTable/HashTable.h:336
/** Like `HashTableGrowerWithPrecalculation`, but adapts to large hash tables.
  *
  * For large hash tables, random memory access is the main bottleneck, not the computations.
  * When the buffer reaches 2^robin_hood_size_degree cells, the grower switches the hash table to the Robin Hood mode:
  * the max load factor is increased from 0.5 to robin_hood_max_load_factor_percent / 100 (the hash table becomes up to two times smaller),
  * and the elements inside collision resolution chains are ordered by their optimal positions,
  * so a lookup of a missing key can stop early instead of walking to the end of the chain.
  *
  * The memory layout is the same in both modes, and switching happens in place, without growing the buffer.
  * Hash tables check the mode only if the grower has the `isRobinHood` method (see `GrowerWithRobinHood`),
  * so there is no cost for other growers.
  *
  * Requirements to the cell: obtaining the hash value with `getHash` must be cheap (the hash is saved or cheap to compute),
  * and the hash table must not keep pointers to cells while inserting other elements,
  * because an insertion may move other elements along the collision resolution chain.
  */

The payoff is twofold. The table becomes up to twice as small (0.9 vs 0.5 load factor), which halves the number of cache misses in a random probe; and a failed lookup can stop early, because the chain is sorted by “distance from the ideal position”:

cpp
// src/Common/HashTable/HashTable.h:607
    size_t ALWAYS_INLINE findCellRobinHood(const Key & x, size_t hash_value, size_t place_value, bool & found) const
    {
        for (size_t distance = 0;; ++distance)
        {
            const Cell & cell = buf[place_value];
            if (cell.isZero(*this))
            {
                found = false;
                return place_value;
            }
            if (cell.keyEquals(x, hash_value, *this))
            {
                found = true;
                return place_value;
            }
            /// The element at the optimal position of the key cannot be closer to its own optimal position, so do not compute its hash.
            if (distance && distanceFromOptimalPosition(cell, place_value) < distance)
            {
                found = false;
                return place_value;
            }
            place_value = grower.next(place_value);
#ifdef DBMS_HASH_MAP_COUNT_COLLISIONS
            ++collisions;
#endif
        }
    }

“Distance from the optimal position” is just the difference between where the key would go and where it is, measured modulo the buffer size:

cpp
// src/Common/HashTable/HashTable.h:597
    size_t ALWAYS_INLINE distanceFromOptimalPosition(const Cell & cell, size_t place_value) const
    {
        return grower.place(place_value - grower.place(cell.getHash(*this)));
    }

Robin Hood ordering also changes insertion: the new key may have to be placed before an existing one, which means shifting the rest of the chain to the right:

cpp
// src/Common/HashTable/HashTable.h:664
    void NO_INLINE shiftCellsRight(size_t place_value)
    {
        size_t empty_place = findEmptyCell(place_value);

        if (empty_place < place_value)
        {
            /// The chain wraps around the end of the buffer.
            size_t last_place = grower.bufSize() - 1;
            memmove(static_cast<void *>(&buf[1]), static_cast<const void *>(&buf[0]), empty_place * sizeof(Cell));
            memcpy(static_cast<void *>(&buf[0]), static_cast<const void *>(&buf[last_place]), sizeof(Cell));
            empty_place = last_place;
        }

        memmove(static_cast<void *>(&buf[place_value + 1]), static_cast<const void *>(&buf[place_value]), (empty_place - place_value) * sizeof(Cell));
        buf[place_value].setZero();
    }

and the chains have to be re-sorted when the mode is switched on — by an insertion sort, since the chains are “already almost ordered” in practice:

cpp
// src/Common/HashTable/HashTable.h:681
    /** Reorder the elements in every collision resolution chain by their optimal positions, as required in the Robin Hood mode.
      * Used after the elements were placed by the ordinary linear probing: on resize, or when switching to the Robin Hood mode.
      * It is an insertion sort, which is fast for the chains that are already almost ordered.
      */

Deletion without tombstones

Deleting from an open-addressing table usually means writing a tombstone, so that the probe chain is not cut short. Tombstones accumulate, they need to be cleaned up, and they slow down every subsequent lookup.

ClickHouse does not use tombstones. Instead it moves the elements of the chain:

cpp
// src/Common/HashTable/HashTable.h:731
    /// Remove the element at place_value without calling its destructor, moving the following elements of the collision resolution chain to keep them reachable.
    /// Not inlined to keep the code of inserts small.
    void eraseCellAt(size_t erased_key_position)
    {
        /// We need to guarantee loop termination because there will be empty position
        chassert(m_size < grower.bufSize());

        size_t next_position = erased_key_position;

        /**
         * During element deletion there is a possibility that the search will be broken for one
         * of the following elements, because this place erased_key_position is empty. We will check
         * next_element. Consider a sequence from (erased_key_position, next_element], if the
         * optimal_position of next_element falls into it, then removing erased_key_position
         * will not break search for next_element.
         * If optimal_position of the element does not fall into the sequence (erased_key_position, next_element]
         * then deleting a erased_key_position will break search for it, so we need to move next_element
         * to erased_key_position. Now we have empty place at next_element, so we apply the identical
         * procedure for it.
         * If an empty element is encountered then means that there is no more next elements for which we can
         * break the search so we can exit.
         *
         * In the Robin Hood mode, the elements of a chain are ordered by their optimal positions,
         * and this procedure moves them one cell to the left, keeping the order.
        */

The rule the comment spells out is the classic one: an element may stay where it is if its ideal position is not before the hole; otherwise it has to slide left into the hole, which moves the hole one step further right, and the procedure repeats:

cpp
// src/Common/HashTable/HashTable.h:798
            /// Move the element to the freed place
            memcpy(static_cast<void *>(&buf[erased_key_position]), static_cast<void *>(&buf[next_position]), sizeof(Cell));

            /// Now we have another freed place
            erased_key_position = next_position;
        }

        buf[erased_key_position].setZero();
        --m_size;
    }

This costs a memcpy per displaced element but keeps the table free of garbage: the buffer is always exactly as full as m_size says, and a probe chain never walks over a tombstone.

The allocator: zeroed and pre-faulted

HashTableAllocator is Allocator<true /* clear_memory */, true /* populate */>. The second flag is the interesting one: it pre-faults the pages of a large allocation with MADV_POPULATE_WRITE, so that the resize loop does not stop for page faults:

cpp
// src/Common/Allocator.cpp:59
void prefaultPages([[maybe_unused]] void * buf_, [[maybe_unused]] size_t len_)
{
#if defined(MADV_POPULATE_WRITE)
    if (len_ < POPULATE_THRESHOLD)
        return;

    if (!is_supported_by_kernel) [[unlikely]]
        return;

    auto [buf, len] = adjustToPageSize(buf_, len_, ::getPageSize());
    ::madvise(buf, len, MADV_POPULATE_WRITE);
#endif
}

cpp
// src/Common/Allocator.cpp:132
/// Constant is chosen almost arbitrarily, what I observed is 128KB is too small, 1MB is almost indistinguishable from 64MB and 1GB is too large.
extern const size_t POPULATE_THRESHOLD = std::max(Int64{16 * 1024 * 1024}, ::getPageSize());

The rationale is spelled out in HashTableAllocator.h itself: the whole allocation will be used, so pre-faulting it costs nothing extra and removes a source of latency spikes from the middle of a rehash. The kernel support check is a version test (Linux 5.14+), not an EINVAL probe, because madvise returns EINVAL for many unrelated reasons.

And note how calloc and the “zero means empty” invariant fit together perfectly: calloc of a large block is free on Linux for big allocations (the kernel hands out zero pages), so the “clear the buffer” requirement that the emptiness protocol imposes costs nothing at all.

Prefetching

A hash table probe is a random memory access; at 90% load factor with Robin Hood ordering, a lookup of a missing key can touch several cache lines. ClickHouse tries to hide that latency by prefetching the cell a few iterations ahead. The helper measures its own iteration latency to decide how far ahead to look:

cpp
// src/Common/HashTable/Prefetching.h:33
class PrefetchingHelper
{
public:
    size_t calcPrefetchLookAhead()
    {
        static constexpr auto assumed_load_latency_ns = 100;
        static constexpr auto just_coefficient = 4;
        static constexpr auto numerator = just_coefficient * assumed_load_latency_ns * iterations_to_measure;
        size_t elapsed_ns = watch.elapsedNanoseconds();
        if (unlikely(elapsed_ns == 0))
            return max_look_ahead_value;
        size_t look_ahead = (numerator + elapsed_ns - 1) / elapsed_ns;
        return std::clamp<size_t>(look_ahead, min_look_ahead_value, max_look_ahead_value);
    }

    static constexpr size_t getInitialLookAheadValue() { return min_look_ahead_value; }

    static constexpr size_t iterationsToMeasure() { return iterations_to_measure; }

private:
    static constexpr size_t iterations_to_measure = 100;
    static constexpr size_t min_look_ahead_value = 4;
    static constexpr size_t max_look_ahead_value = 32;

The look-ahead is thus between 4 and 32 cells, tuned to the machine: the formula is 4 * 100ns * 100 / elapsed, i.e. four times the assumed memory latency, expressed in iterations.

The prefetching iterator of the table uses it, and also prefetches the key bytes of the cell it is about to look at, not just the cell:

cpp
// src/Common/HashTable/HashTable.h:1021
        void prefetch()
        {
            static_assert(CouldPrefetchKey<cell_type>);
            auto * buf_end = container->buf + container->grower.bufSize();
            iter_count++;
            if (prefetch_ptr < buf_end && prefetched_count < prefetch_ahead) [[likely]]
            {
                if (iter_count == DB::PrefetchingHelper::iterationsToMeasure()) [[unlikely]]
                    prefetch_ahead = prefetching.calcPrefetchLookAhead();
                auto n = prefetch_ahead - prefetched_count;
                cell_type * last_ptr = nullptr;
                for (size_t i = 0; i < n; ++i)
                {
                    while (prefetch_ptr < buf_end && prefetch_ptr->isZero(*container))
                        ++prefetch_ptr;

                    if (prefetch_ptr < buf_end) [[likely]]
                    {
                        last_ptr = prefetch_ptr;
                        prefetch_ptr++;
                        prefetched_count++;
                    }
                    else
                        break;
                }

                if (last_ptr) [[likely]]
                    keyPrefetch(last_ptr->getKey());
            }
        }

keyPrefetch touches up to four cache lines of the key data:

cpp
// src/Common/HashTable/HashTableKeyHolder.h:182
inline void keyPrefetch(const std::string_view key)
{
    const size_t cache_line_size = 64;
    // Prefetch up to 4 cache lines.
    const size_t max_prefetch = cache_line_size * 4;
    const size_t n = std::min(key.size(), max_prefetch);
    const char * ptr = key.data();
    const char * end = ptr + n;
    for (; ptr < end; ptr += cache_line_size)
    {
        __builtin_prefetch(ptr);
    }
}

Keys that live outside the table

Not every key can live inside the cell. A std::string_view key points at data owned by somebody else — often a column that will be gone by the time the aggregation is finalised. ClickHouse solves this with a key holder: a small policy object that knows how to make a temporary key persistent, and when to throw it away.

cpp
// src/Common/HashTable/HashTableKeyHolder.h:53
/**
  * Returns the key. Can return the temporary key initially.
  * After the call to keyHolderPersistKey(), must return the persistent key.
  */
template <typename Key>
inline Key & ALWAYS_INLINE keyHolderGetKey(Key && key) { return key; }  /// NOLINT(bugprone-return-const-ref-from-parameter)

/**
  * Make the key persistent. keyHolderGetKey() must return the persistent key
  * after this call.
  */
template <typename Key>
inline void ALWAYS_INLINE keyHolderPersistKey(Key &&) {}

/**
  * Discard the key. Calling keyHolderGetKey() is ill-defined after this.
  */
template <typename Key>
inline void ALWAYS_INLINE keyHolderDiscardKey(Key &&) {}

The default is a no-op: for a key stored by value, there is nothing to do, and the branch is optimised away. The ArenaKeyHolder version copies the bytes into an Arena when the key turns out to be new:

cpp
// src/Common/HashTable/HashTableKeyHolder.h:98
inline void ALWAYS_INLINE keyHolderPersistKey(DB::ArenaKeyHolder & holder)
{
    // Normally, our hash table shouldn't ask to persist a zero key,
    // but it can happened in the case of clearable hash table (ClearableHashSet, for example).
    // The clearable hash table doesn't use zero storage and
    // distinguishes empty keys by using cell version, not the value itself.
    // So, when an empty std::string_view is inserted in ClearableHashSet we'll get here key of zero size.
    holder.key = std::string_view{holder.pool.insert(holder.key.data(), holder.key.size()), holder.key.size()};
}

The elegance is in where the decision is made. The hash table knows whether the key it just found was new; the caller does not. So the table calls keyHolderDiscardKey when the key already existed (nothing to persist, and the arena allocation is rolled back) and keyHolderPersistKey when it did not:

cpp
// src/Common/HashTable/HashTable.h:1386
        if (!buf[place_value].isZero(*this))
        {
            keyHolderDiscardKey(key_holder);
            inserted = false;
            return;
        }

        keyHolderPersistKey(key_holder);

The hash function has to be good

Because the table uses linear probing and the low bits of the hash to pick the bucket, a poor hash function is catastrophic: the low bits of a timestamp-like key are nearly constant, and every key lands in the same few cells. The header says so bluntly:

cpp
// src/Common/HashTable/Hash.h:15
/** Hash functions that are better than the trivial function std::hash.
  *
  * Example: when we do aggregation by the visitor ID, the performance increase is more than 5 times.
  * This is because of following reasons:
  * - in Metrica web analytics system, visitor identifier is an integer that has timestamp with seconds resolution in lower bits;
  * - in typical implementation of standard library, hash function for integers is trivial and just use lower bits;
  * - traffic is non-uniformly distributed across a day;
  * - we are using open-addressing linear probing hash tables that are most critical to hash function quality,
  *   and trivial hash function gives disastrous results.
  */

The default integer hash is the MurmurHash finalizer:

cpp
// src/Common/HashTable/Hash.h:26
/** Taken from MurmurHash. This is Murmur finalizer.
  * Faster than intHash32 when inserting into the hash table UInt64 -> UInt64, where the key is the visitor ID.
  */
inline UInt64 intHash64(UInt64 x)
{
    x ^= x >> 33;
    x *= 0xff51afd7ed558ccdULL;
    x ^= x >> 33;
    x *= 0xc4ceb9fe1a85ec53ULL;
    x ^= x >> 33;

    return x;
}

Five instructions and two multiplies turn “the low bits are constant” into “the low bits are random”. For string keys and general keys, the CRC32 hardware instruction is used where it exists — three cycles of latency and one per cycle of throughput, which is why the string tables use it even though CRC32 is a poor hash in the abstract:

cpp
// src/Common/HashTable/Hash.h:40
/** CRC32C is not very high-quality as a hash function,
  *  according to avalanche and bit independence tests (see SMHasher software), as well as a small number of bits,
  *  but can behave well when used in hash tables,
  *  due to high speed (latency 3 + 1 clock cycle, throughput 1 clock cycle).
  * Works only with SSE 4.2 support.
  */

Trade-offs

What the “zero means empty” scheme buys:

Zero bytes of metadata per cell. A HashMapCell<UInt64, T*> is 16 bytes, all of it payload. A scheme with an occupancy bit would need to steal a bit from the key or add a byte.
A free calloc. The kernel can hand out pre-zeroed pages; the emptiness protocol costs nothing at allocation time.
No tombstones, ever. Deletion moves cells instead of marking them, so the table never degrades.
A cheap scan. for (auto & cell : buf) if (!cell.isZero()) ... is the iteration order; no indirection, no linked list.

What it costs:

The key must be zero-comparable, and bit-comparable. Floating point keys are compared with memcmp, and NaN semantics have to be papered over.
The zero key is special. It lives in a separate slot, it is visited first during iteration, and its handling adds a branch to every insert and lookup.
The hash must be excellent, because linear probing amplifies clustering, and the low bits of the hash are used directly.
Rehashing is a memcpy storm. Growing the table means moving every cell, and the wrap-around case needs a second pass over the head of the new buffer.

And the recent Robin Hood addition changes the balance again: it trades a little CPU (reordering chains, occasionally shifting cells on insert) for a halving of the memory footprint at large sizes — which, for a table that is probed randomly, is exactly the right trade, because the cost is cache misses, not instructions.

Wrapping up

The one thing to remember: “empty means all-zero bytes” buys you a cell layout that is 100% payload, with no occupancy bit to steal from your key.

The part people get wrong: this is not free. The zero key becomes a special case, float keys need bitwise comparison, and the hash function has to be genuinely good — a five-line Murmur finalizer stands between you and a 5× slower aggregation.

What to go do about it: if you ever profile a GROUP BY and see the cost dominated by cache misses on a huge hash table, remember that the Robin Hood grower exists precisely for that case: it halves the footprint at large sizes.