ClickHouse Estimates topK with a Space-Saving Counter and an Error Bound

TL;DR: topK cannot keep every value it has seen — that would be groupArray. It keeps a bounded number of candidates, each with a count and an error bound. When a new value arrives and the table is full, the evicted level is tracked in an alpha_map: a hash-bucketed array of approximate minimum counts, so admission is O(1) instead of a scan for the minimum. The counts are exact while the number of distinct values fits in the reserved space, and approximate-with-an-error-bound after that.

SELECT topK(10)(user_agent) FROM hits sounds like it wants an exact answer: the ten most common user agents. But an exact answer requires counting every distinct user agent, and there might be ten million of them. The whole point of a topK aggregate is to run in constant memory over an unbounded stream.

So the algorithm has to make a promise weaker than “exact”. The promise ClickHouse makes is the classic one from the streaming literature: every reported count is an over-estimate, and the over-estimate is bounded.

The algorithm, named

The implementation is not a house invention. The file says so:

cpp
// src/Common/SpaceSaving.h:16
/*
 * Implementation of the Filtered Space-Saving for TopK streaming analysis.
 *   http://www.l2f.inesc-id.pt/~fmmb/wiki/uploads/Work/misnis.ref0a.pdf
 * It implements suggested reduce-and-combine algorithm from Parallel Space Saving:
 *   https://arxiv.org/pdf/1401.0702.pdf
 */

and so does the function’s documentation:

cpp
// src/AggregateFunctions/AggregateFunctionTopK.cpp:632
    FunctionDocumentation::Description description_topK = R"(
Returns an array of the approximately most frequent values in the specified column. The resulting array is sorted in descending order of approximate frequency of values (not by the values themselves).

Implements the [Filtered Space-Saving](https://doi.org/10.1016/j.ins.2010.08.024) algorithm for analyzing TopK, based on the reduce-and-combine algorithm from [Parallel Space Saving](https://doi.org/10.1016/j.ins.2015.09.003).

This function does not provide a guaranteed result. In certain situations, errors might occur and it might return frequent values that aren't the most frequent values.

Three phrases carry the whole design: Filtered Space-Saving (only the candidates are kept, not the whole stream), Parallel Space-Saving (the merge step is designed to combine two partial tables, so shards can be merged), and approximately most frequent.

The counter: a count and an error

The unit of storage is a Counter, and it has four fields:

cpp
// src/Common/SpaceSaving.h:100
    struct Counter
    {
        Counter() = default;

        explicit Counter(const TKey & k, UInt64 c = 0, UInt64 e = 0, size_t h = 0)
            : key(k)
            , hash(h)
            , count(c)
            , error(e)
        {
        }

cpp
// src/Common/SpaceSaving.h:142
        TKey key{};
        size_t hash{};
        UInt64 count{};
        UInt64 error{};
    };

count is the estimated count and error is how much that estimate might be off. The intent of the pair is:

text

count(key) - error(key)  <=  true_count(key)  <=  count(key)

so count - error is a lower bound on the truth and count is an upper bound. That is why the comparison operator below subtracts the error before comparing: a counter that was inflated by a large eviction should not out-rank a counter that is merely accurate.

The error is not a heuristic fudge. In textbook Space-Saving it is the minimum count among all counters in the table at the moment the key was admitted: the new key’s count is set to min + 1 and its error to min, because the true count of a brand-new key is at most min + 1 (if it had occurred more often, the minimum counter would not have been the minimum). Every counter therefore carries the same error value at insertion time, and errors do not grow afterwards.

The comparison operator encodes the same idea, and it is the only place the error is consulted:

cpp
// src/Common/SpaceSaving.h:136
        // greater() taking error into account
        bool operator> (const Counter & b) const
        {
            return ((count - error) > (b.count - b.error)) || ((count - error) == (b.count - b.error) && count > b.count);
        }

count - error is the lower bound of the true count. So the ordering compares lower bounds first (a counter that might be much bigger wins) and breaks ties on the raw count. This matters: without the error term, a counter that was inflated by a large eviction would always look like the winner, and the algorithm would systematically prefer stale entries.

The hash field is a third thing: the hash of the key, stored in the counter so it does not have to be recomputed. The counter is looked up in a hash map keyed by the value, but the map cell only stores the index into a flat vector of counters:

cpp
// src/Common/SpaceSaving.h:453
    ALWAYS_INLINE Counter * findCounter(const TKey & key, size_t hash)
    {
        auto it = counter_map.find(key, hash);
        if (!it)
            return nullptr;

        return &counter_list[it->getMapped()];
    }

So the layout is a hash map from key to index, plus a flat vector of counters. The vector is what gets sorted and truncated; the map is what gets probed.

Insertion: three cases

The insert path is short and each branch is a different case of the algorithm:

cpp
// src/Common/SpaceSaving.h:183
    void insert(const TKey & key, UInt64 increment = 1, UInt64 error = 0)
    {
        // Increase weight of a key that already exists
        auto hash = counter_map.hash(key);

        if (auto * counter = findCounter(key, hash))
        {
            counter->count += increment;
            counter->error += error;
            return;
        }

        // Key doesn't exist, but can fit in the top K
        if (unlikely(counter_list.size() < capacity()))
        {
            push(arena.emplace(key), increment, error, hash);
            return;
        }

        const UInt64 alpha_mask = alpha_map.size() - 1;
        auto & alpha = alpha_map[hash & alpha_mask];
        push(arena.emplace(key), alpha + increment, alpha + error, hash);
    }

Case 1: the key is already known. Bump the count. The error stays where it is — the bound only depends on what was evicted at admission time.

Case 2: the key is new and there is room. Insert it with count = increment, error = 0. It is exact: we have seen it exactly once and nothing has been evicted yet. This is why topK gives exact counts when the number of distinct values fits in the reserved space.

Case 3: the key is new and the table is full. Here is the whole trick. The new counter is given:

text

count = alpha + increment
error = alpha

(error on the right-hand side is the error argument of insert, which is zero for the plain and weighted topK.) Note that count - error comes out as exactly increment — the new counter’s lower bound on the truth is just “I have seen this once”.

alpha is the per-bucket estimate of the level at which counters have been evicted. In textbook Space-Saving, when the table is full you evict the minimum counter (call its count m) and replace it with the new key at count m + 1, recording an error of m: the new key’s true count is somewhere in [1, m+1], so m+1 over-counts by at most m.

The difference is that the minimum is not tracked exactly. alpha comes from a hash-bucketed array and is local to the bucket rather than global. Textbook Space-Saving would have to maintain the exact global minimum, which means a heap or a linear scan on every insertion; the bucketised estimate is O(1).

The price is that the error bound is no longer derived from the true global minimum. That is why the function’s own documentation says This function does not provide a guaranteed result rather than promising a specific error bound, and why the 'counts' output includes the error term at all: the user is told how much slack there is rather than being promised a guarantee.

That is the “Filtered” in Filtered Space-Saving.

The alpha map: an O(1) approximate minimum

The alpha_map is an array of UInt64, indexed by hash & mask. Each entry accumulates the eviction level of the counters that hashed into that bucket and were later dropped — see the truncation code below.

Its size is chosen to be a power of two, so the index is a mask rather than a modulo:

cpp
// src/Common/SpaceSaving.h:85
    // Suggested constants in the paper "Finding top-k elements in data streams", chap 6. equation (24)
    // Round to nearest power of 2 for cheaper binning without modulo
    constexpr UInt64 nextAlphaSize(UInt64 x)
    {
        constexpr UInt64 alpha_map_elements_per_counter = 6;
        return 1ULL << (sizeof(UInt64) * 8 - std::countl_zero(x * alpha_map_elements_per_counter));
    }

alpha_map_elements_per_counter = 6 is the paper’s suggested constant: six alpha slots per retained counter. nextAlphaSize rounds 6 * capacity up to the next power of two.

And there is a hard cap on the alpha values, so that a pathological merge cannot overflow the counter:

cpp
// src/Common/SpaceSaving.h:93
    /// Limit the max alpha value to avoid overflow with merges or topKWeighted with huge weights
    /// Better to have a less precise value than an overflow (which will lead to incorrect results)
    static constexpr UInt64 MAX_ALPHA_VALUE = UInt64{UINT32_MAX};

Better to have a less precise value than an overflow — the comment is a good summary of the whole philosophy of approximate algorithms: degrade the precision, never the correctness of the arithmetic.

Truncation: the eviction

The table does not evict on every insert. It grows to twice the requested capacity and then truncates in one batch:

cpp
// src/Common/SpaceSaving.h:170
    void resize(size_t new_capacity)
    {
        if (requested_capacity != new_capacity)
        {
            chassert(empty());
            alpha_map.resize(nextAlphaSize(new_capacity), 0);
            requested_capacity = new_capacity;
            /// If the requested capacity is really small we would end up sorting and truncating too often
            target_capacity = std::max(size_t{64}, requested_capacity * 2);
            counter_list.reserve(target_capacity);
        }
    }

Two numbers: requested_capacity (the k the user asked for) and target_capacity (the high-water mark, max(64, 2k)). The comment explains the 64 floor: with a tiny k you would truncate on nearly every insert, and each truncation is O(n).

The truncation itself:

cpp
// src/Common/SpaceSaving.h:410
    ALWAYS_INLINE void truncateIfNeeded(bool force_counter_map_rebuild)
    {
        if (unlikely(counter_list.size() >= target_capacity))
        {
            ::nth_element(
                counter_list.begin(),
                counter_list.begin() + capacity(),
                counter_list.end(),
                [](const auto & l, const auto & r) { return l > r; });

            const UInt64 alpha_mask = alpha_map.size() - 1;
            for (size_t i = requested_capacity; i < counter_list.size(); ++i)
            {
                size_t pos = counter_list[i].hash & alpha_mask;
                alpha_map[pos] = std::min(alpha_map[pos] + counter_list[i].count - counter_list[i].error, MAX_ALPHA_VALUE);
                arena.free(counter_list[i].key);
            }

            counter_list.resize(requested_capacity);
            force_counter_map_rebuild = true;
        }

        if (force_counter_map_rebuild)
        {
            /// Rebuild the counter map
            counter_map.clear();
            for (size_t i = 0; i < counter_list.size(); ++i)
                counter_map.insertIfNotPresent(counter_list[i].key, counter_list[i].hash, i);
        }
    }

nth_element is the right tool: it is O(n) on average and only partially sorts, putting the capacity() best counters at the front. The rest are evicted.

Now the crucial line, the one that closes the loop:

cpp
alpha_map[pos] = std::min(alpha_map[pos] + counter_list[i].count - counter_list[i].error, MAX_ALPHA_VALUE);

count - error is the evicted counter’s lower bound on its true count. That lower bound is added into the alpha map of its hash bucket, so the bucket’s “eviction level” rises. The next new key that hashes into that bucket is admitted with alpha as its error and alpha + increment as its count — the same shape as the textbook rule, but with a bucketed estimate of the minimum in place of the exact one.

arena.free(counter_list[i].key) releases the key’s storage. For String keys that memory lives in a freelist arena; for POD keys free is a no-op:

cpp
// src/Common/SpaceSaving.h:50
/*
 * Specialized storage for std::string_view with a freelist arena.
 * Keys of this type that are retained on insertion must be serialized into local storage,
 * otherwise the reference would be invalid after the processed block is released.
 */
template <>
struct SpaceSavingArena<std::string_view>
{
    std::string_view emplace(std::string_view key)
    {
        if (!key.data())
            return key;

        return copyStringInArena(arena, key);
    }

    void free(std::string_view key)
    {
        if (key.data())
            arena.free(const_cast<char *>(key.data()), key.size());
    }

private:
    ArenaWithFreeLists arena;
};

The if (!key.data()) guard is a small but important detail: a string_view over a String column is only valid while the block is alive, so a retained key has to be copied into the arena. A key that was never retained (the null view) must not be freed.

The force_counter_map_rebuild flag exists because nth_element reorders the vector, and the hash map stores indices into that vector. After a truncation the indices are wrong, so the map has to be rebuilt from scratch. That is O(k) per truncation, amortised over k inserts — cheap, but it is a real cost of the “map to index, vector of counters” layout.

The `push` helper and a stack-protector detail

cpp
// src/Common/SpaceSaving.h:399
protected:
    /// Fields by value: a `Counter` temporary would escape into this `NO_INLINE` call and give the
    /// per-row `insert` a `-fstack-protector-strong` canary.
    NO_INLINE void push(TKey key, UInt64 count, UInt64 error, size_t hash)
    {
        size_t pos = counter_list.size();
        counter_map.insertIfNotPresent(key, hash, pos);
        counter_list.push_back(Counter{key, count, error, hash});
        truncateIfNeeded(false);
    }

The comment is a compiler-specific micro-optimisation with a surprising side effect. push is NO_INLINE — deliberately, so the per-row insert stays small. But if the Counter temporary were constructed inside push and passed by reference, its address would escape into a non-inlined function, and the compiler would have to protect the stack frame of insert with a canary — on every row. Passing the four fields by value keeps the temporary’s address inside push, so the canary stays where it belongs.

This is the kind of detail that only exists because somebody profiled it.

Getting the answer out

At finalization, the counters are sorted by the same operator> that the truncation used:

cpp
// src/Common/SpaceSaving.h:275
    std::vector<Counter> topK(size_t k) const
    {
        std::vector<Counter> new_list;
        new_list.reserve(counter_list.size());
        for (auto & counter : counter_list)
            new_list.push_back(counter);

        size_t return_size = std::min(new_list.size(), k);
        ::partial_sort(
            new_list.begin(), new_list.begin() + return_size, new_list.end(), [](const auto & l, const auto & r) { return l > r; });

        new_list.resize(return_size);

        return new_list;
    }

partial_sort — O(n log k), and it only sorts the first k. The copy into new_list is because topK is const and the state must not be mutated: insertResultInto may be called more than once in the runningAccumulate / window-function paths, and the state has to stay valid.

The aggregate function then turns the counters into a column, optionally with the counts and the error bounds:

cpp
// src/AggregateFunctions/AggregateFunctionTopK.cpp:260
    void insertResultInto(AggregateDataPtr __restrict place, IColumn & to, Arena *) const override
    {
        ColumnArray & arr_to = assert_cast<ColumnArray &>(to);
        ColumnArray::Offsets & offsets_to = arr_to.getOffsets();

        const typename State::Set & set = this->data(place).value;
        auto result_vec = set.topK(threshold);
        size_t size = result_vec.size();

        offsets_to.push_back(offsets_to.back() + size);

cpp
// src/AggregateFunctions/AggregateFunctionTopK.cpp:273
        if (include_counts)
        {
            auto & column_tuple = assert_cast<ColumnTuple &>(data_to);

            auto & column_key = assert_cast<ColumnVector<T> &>(column_tuple.getColumn(0)).getData();
            auto & column_count = assert_cast<ColumnVector<UInt64> &>(column_tuple.getColumn(1)).getData();
            auto & column_error = assert_cast<ColumnVector<UInt64> &>(column_tuple.getColumn(2)).getData();

The result type with counts is a Tuple(item, count, error) — the error bound is exposed to the user, not just used internally:

sql
SELECT topKWeighted(2, 10, 'counts')(k, w)
FROM VALUES('k Char, w UInt64', ('y', 1), ('y', 1), ('x', 5), ('y', 1), ('z', 10));

text
┌─topKWeighted(2, 10, 'counts')(k, w)─┐
│ [('z',10,0),('x',5,0)]              │
└─────────────────────────────────────┘

The trailing 0 is the error bound — zero, because with only five rows nothing was ever evicted.

The `reserved` parameter: when is it exact?

The user’s k is not the same as the memory the algorithm uses. The parameter reserved is how many candidates the table can hold:

cpp
// src/AggregateFunctions/AggregateFunctionTopK.cpp:556
    UInt64 threshold = 10;  /// default values
    UInt64 load_factor = 3;
    bool include_counts = is_approx_top_k;
    UInt64 reserved = threshold * load_factor;

reserved defaults to k * 3. The parameter is validated against a hard ceiling:

cpp
// src/AggregateFunctions/AggregateFunctionTopK.cpp:605
        if (reserved > DB::TOP_K_MAX_SIZE || load_factor > DB::TOP_K_MAX_SIZE || threshold > DB::TOP_K_MAX_SIZE)
            throw Exception(ErrorCodes::ARGUMENT_OUT_OF_BOUND,
                            "Too large parameter(s) for aggregate function '{}' (maximum is {})", name, toString(TOP_K_MAX_SIZE));

with

cpp
// src/AggregateFunctions/AggregateFunctionTopK.cpp:43
inline constexpr UInt64 TOP_K_MAX_SIZE = 0xFFFFFF;

16 777 215 — a bit over 16 million candidates.

The semantics follow from the insertion logic. The table holds up to reserved counters. Eviction only starts once counter_list.size() >= capacity(), and capacity() is requested_capacity — which is set from reserved:

cpp
// src/Common/SpaceSaving.h:163
    size_t capacity() const { return requested_capacity; }

So:

If the number of distinct values is less than reserved, nothing is ever evicted, every error is zero, and the counts are exact.
If it exceeds reserved, eviction begins and the counts become over-estimates with a bounded error.

That is exactly what the documentation says:

cpp
// src/AggregateFunctions/AggregateFunctionTopK.cpp:750
    FunctionDocumentation::Parameters parameters_approx_top_k = {
        {"N", "The number of elements to return. Default value: `10`. Maximum value of `N = 65536`.", {"UInt64"}},
        {"reserved", "Optional. Defines how many cells reserved for values. If `uniq(column) > reserved`, the result will be approximate. Default value: `N * 3`.", {"UInt64"}},
    };

If uniq(column) > reserved, the result will be approximate. One line, and it tells the user exactly when they can trust the answer.

The topK function has the same knob, but named load_factor:

cpp
// src/AggregateFunctions/AggregateFunctionTopK.cpp:581
                load_factor = applyVisitor(FieldVisitorConvertToNumber<UInt64>(), params[1]);

                if (load_factor < 1)
                    throw Exception(ErrorCodes::ARGUMENT_OUT_OF_BOUND,
                                    "Too small parameter 'load_factor' for aggregate function '{}' (got {}, minimum is 1)", name, load_factor);

and it is a multiplier on N, not an absolute cell count:

cpp
// src/AggregateFunctions/AggregateFunctionTopK.cpp:695
    FunctionDocumentation::Parameters parameters_topKWeighted = {
        {"N", "The number of elements to return. Default value: 10.", {"UInt64"}},
        {"load_factor", "Optional. Defines, how many cells reserved for values. If `uniq(column) > N * load_factor`, result of topK function will be approximate. Default value: 3.", {"UInt64"}},
        {"counts", "Optional. Defines whether the result should contain an approximate count and error value.", {"Bool"}}
    };

So topK(10, 100)(x) means “give me 10, but keep 10 × 100 = 1000 candidates around” — a hundredfold memory blow-up relative to k, and a correspondingly tighter error bound, because evictions only start once 1000 distinct values have been seen.

Merging: the Parallel Space-Saving reduce-and-combine

The hard part of any top-k algorithm is merging two partial results, because a value that was in the top-k of one shard may not be in the top-k of the other. Plain Space-Saving is not mergeable: the error bounds of the two sides are not comparable.

The Parallel Space-Saving paper’s trick is to make the merge account for the fact that a counter from the other side suffers from the first side’s lack of precision. ClickHouse implements it as a two-sweep in-place update:

cpp
// src/Common/SpaceSaving.h:207
    /*
     * Parallel Space Saving reduction and combine step from:
     *  https://arxiv.org/pdf/1401.0702.pdf
     */
    void merge(const Self & rhs)
    {
        if (rhs.empty())
            return;

        if (empty())
        {
            *this = rhs;
            return;
        }

        UInt64 m1 = 0;
        UInt64 m2 = 0;

        if (size() >= capacity())
        {
            m1 = *std::ranges::max_element(alpha_map);
        }

        if (rhs.counter_list.size() >= rhs.capacity())
        {
            m2 = *std::ranges::max_element(rhs.alpha_map);
        }

m1 and m2 are the maximum alpha values of the two sides — that is, the approximate minimum counts of the two tables, if both were full. They are the “resolution” of the two sides.

Then:

cpp
// src/Common/SpaceSaving.h:235
        /*
         * Updated algorithm to mutate current table in place
         * without mutating rhs table or creating new one
         * in the first step we expect that no elements overlap
         * and in the second sweep we correct the error if they do.
         */
        if (m2 > 0)
        {
            for (auto & counter : counter_list)
            {
                counter.count += m2;
                counter.error += m2;
            }
        }

        for (const auto & counter : rhs.counter_list)
        {
            size_t hash = counter.hash;
            if (auto * current = findCounter(counter.key, hash))
            {
                // Subtract m2 previously added, guaranteed not negative
                current->count += (counter.count - m2);
                current->error += (counter.error - m2);
            }
            else
            {
                // Counters not monitored in S1
                counter_list.push_back(Counter{arena.emplace(counter.key), counter.count + m1, counter.error + m1, hash});
            }
        }

Sweep 1. Every counter of the left table gets += m2 on both count and error. Since count and error both grow by m2, count - error — the lower bound — is unchanged. The upper bound grows, because the right side’s counters may have been inflated by evictions we did not see. So the left table’s counters now carry the right table’s uncertainty.

Sweep 2. The right table’s counters are folded in. For a key that already exists on the left, the m2 added in sweep 1 is subtracted back (the comment says Subtract m2 previously added, guaranteed not negative), and the right side’s own count and error are added. For a key that does not exist on the left, it is admitted with count + m1 and error + m1 — the left side’s uncertainty is charged against it.

The alpha maps are then merged element-wise:

cpp
// src/Common/SpaceSaving.h:266
        if (alpha_map.size() == rhs.alpha_map.size())
        {
            for (size_t i = 0; i < alpha_map.size(); i++)
                alpha_map[i] = std::min(alpha_map[i] + rhs.alpha_map[i], MAX_ALPHA_VALUE);
        }

        truncateIfNeeded(true);

Note the size check: the two alpha maps are only merged if they are the same size, which they are if both were resized with the same capacity. The MAX_ALPHA_VALUE clamp is the same “degrade precision, never overflow” rule as before.

The final truncateIfNeeded(true) brings the merged table back down to capacity. The true forces the counter map rebuild, because the merge pushed new counters into the vector.

What the aggregate function adds

AggregateFunctionTopK itself is thin. The state is the SpaceSaving set, and the function is a template over the key type:

cpp
// src/AggregateFunctions/AggregateFunctionTopK.cpp:45
template <typename T>
struct AggregateFunctionTopKData
{
    using Set = SpaceSaving<T, HashCRC32<T>>;

    Set value;
};

The addBatchSinglePlace override is the interesting part — it is where the per-row insert loop lives, and it handles the -If condition column:

cpp
// src/AggregateFunctions/AggregateFunctionTopK.cpp:138
    void addBatchSinglePlace(
        size_t row_begin, size_t row_end, AggregateDataPtr __restrict place, const IColumn ** columns, Arena *, ssize_t if_argument_pos)
        const override
    {
        auto & set = this->data(place).value;
        ensureCapacity(set);

        auto & data = assert_cast<const ColumnVector<T> &>(*columns[0]).getData();

        if (if_argument_pos >= 0)
        {
            const auto & flags = assert_cast<const ColumnUInt8 &>(*columns[if_argument_pos]).getData();
            for (size_t i = row_begin; i < row_end; ++i)
            {
                if (flags[i])
                {
                    if constexpr (is_weighted)
                        set.insert(data[i], columns[1]->getUInt(i));
                    else
                        set.insert(data[i]);
                }
            }
        }

and the capacity has to be re-established on every block, because the state may have been deserialized:

cpp
// src/AggregateFunctions/AggregateFunctionTopK.cpp:132
    void ensureCapacity(AggregateFunctionTopKData<T>::Set & set) const
    {
        if (unlikely(set.capacity() != reserved))
            set.resize(reserved);
    }

resize asserts that the set is empty, so this only fires for a fresh state. The unlikely branch is the deserialization path.

The trade-offs

What this buys you.

Constant memory over an unbounded stream. The state size is bounded by reserved counters regardless of how many distinct values arrive.
A real guarantee, not a vibe. Every count is an over-estimate with a known bound, and the bound is exposed to the user as the third element of the 'counts' tuple.
Exactness when it is affordable. If uniq(column) <= reserved, every error is zero and the answer is exactly right. The approximation degrades gracefully as the cardinality grows past the reservation.
Mergeable. The Parallel Space-Saving reduce-and-combine step means topK can be computed per-shard and merged, which is what makes it usable in a distributed query and in AggregatingMergeTree.
Cheap eviction. O(1) amortised per insert, thanks to the alpha map, instead of the O(n) minimum scan of textbook Space-Saving.

What it costs you.

Over-counting. The reported counts are upper bounds. A value that appears 3 times may be reported as 100 if the table was churning. The ranking is usually right; the magnitudes may not be.
A heuristic minimum. The alpha map buckets by hash, so alpha is a per-bucket estimate, not the global minimum. The error bound is therefore valid but looser than exact Space-Saving would give. The paper’s suggested 6 alpha slots per counter is the knob that trades memory for tightness.
Amortised but real truncation cost. Each truncation is an O(n) nth_element plus an O(k) hash map rebuild, and it happens every ~k inserts. For very small k the max(64, 2k) floor is what keeps this from dominating.
Order dependence. The result depends on the order in which values arrive, which is why the function is registered as order-dependent:

cpp
// src/AggregateFunctions/AggregateFunctionTopK.cpp:630
    AggregateFunctionProperties properties = { .returns_default_when_only_null = false, .is_order_dependent = true };

The same input in a different order can give a different answer. This is inherent to streaming sketches, and it is the price of not storing everything.

The string-key copy. A String key must be copied into the arena when retained, so topK over strings is not free.

The essential idea is that the error bound is not metadata added after the fact — it is a first-class part of the counter, maintained through every insertion, every eviction, and every merge. That is what turns “we approximate” into “we approximate, and here is by how much”.