ClickHouse Estimates Distinct Counts by Thinning a Hash Table

TL;DR: uniq() is a hash table that deliberately throws data away. When it fills up, it halves its sample rate, keeps the survivors, and multiplies the count back up by the thinning factor. The state stays at a few hundred KiB no matter how many distinct values you feed it.

uniq() is one of the most-used aggregate functions in ClickHouse, and one of the most surprising. It is not exact. It is not a HyperLogLog. It is a hash table that throws data away on purpose, thinning itself as it fills up, and then multiplies back up by the thinning factor to estimate the cardinality.

The algorithm behind it is BJKST (Bretag, Karp, Kutz, Schlossmann — “near-optimal algorithms for estimating the number of distinct elements in a stream of data”). The implementation lives in src/AggregateFunctions/UniquesHashSet.h, and it is one of the more elegant pieces of code in the aggregation framework: a fixed-size table, a single integer of state, and a mathematically exact estimator of what the sample means.

The scheme

The header states the general recipe for approximate aggregation:

cpp
// src/AggregateFunctions/UniquesHashSet.h:27
/** Approximate calculation of anything, as usual, is constructed according to the following scheme:
  * - some data structure is used to calculate the value of X;
  * - Not all values are added to the data structure, but only selected ones (according to some selectivity criteria);
  * - after processing all elements, the data structure is in some state S;
  * - as an approximate value of X, the value calculated according to the maximum likelihood principle is returned:
  *   at what real value X, the probability of finding the data structure in the obtained state S is maximal.
  */

And then the specific recipe:

cpp
// src/AggregateFunctions/UniquesHashSet.h:38
/** Very simple hash-set for approximate number of unique values.
  * Works like this:
  * - you can insert UInt64;
  * - before insertion, first the hash function UInt64 -> UInt32 is calculated;
  * - the original value is not saved (lost);
  * - further all operations are made with these hashes;
  * - hash table is constructed according to the scheme:
  * -  open addressing (one buffer, position in buffer is calculated by taking remainder of division by its size);
  * -  linear probing (if the cell already has a value, then the cell following it is taken, etc.);
  * -  the missing value is zero-encoded; to remember presence of zero in set, separate variable of type bool is used;
  * -  buffer growth by 2 times when filling more than 50%;
  * - if the set has more than UNIQUES_HASH_MAX_SIZE elements, then all the elements are removed from the set,
  *   not divisible by 2, and then all elements that do not divide by 2 are not inserted into the set;
  * - if the situation repeats, then only elements dividing by 4, etc., are taken.
  * - the size() method returns an approximate number of elements that have been inserted into the set;
  * - there are methods for quick reading and writing in binary and text form.
  *
  * A 32-bit hash cannot distinguish more than a few billion elements: the estimate degrades quickly
  * beyond a billion, and above ~30 billion the correction formula even resulted in undefined behavior
  * (issue #6078). To keep the estimate accurate up to trillions, in addition to the main set a small
  * "wide" set of full 64-bit hashes (XOR-ed with a constant, see `wideHash`) is maintained (state version 1).
  * It is thinned out aggressively from the very beginning - only values with UNIQUES_HASH_SET_WIDE_INITIAL_SKIP_DEGREE
  * zero low-order bits enter it - so it stays empty or tiny for the states where the main set is accurate
  * (about 4 values per million distinct elements), and it is bounded by UNIQUES_HASH_SET_WIDE_MAX_SIZE
  * values thinned out further. Once the wide set has enough values for its own estimate to be reliable
  * (which happens at about two billion elements), size() switches to it.
  *
  * The wide set has to be maintained from the first insertion: the high bits of the hashes
  * of the already consumed elements cannot be recovered later. In particular, a state written
  * in the legacy format (state version 0) carries no wide set, and its elements were never
  * offered to one. Such a state is marked as having an incomplete wide sample: it drops its own
  * wide set, never starts a new one, and propagates the mark through merges, so that size()
  * of anything it is merged into falls back to the legacy 32-bit estimator. Estimating from
  * a wide set that covers only a part of the elements would undercount the rest entirely,
  * which is much worse than the degrading precision of the 32-bit estimate.
  */

That comment is the whole algorithm. Read it twice: the key insight is that the set does not grow without bound — it changes what it accepts.

The constants

cpp
// src/AggregateFunctions/UniquesHashSet.h:75
/// The maximum degree of buffer size before the values are discarded
#define UNIQUES_HASH_MAX_SIZE_DEGREE 17

/// The maximum number of elements before the values are discarded
#define UNIQUES_HASH_MAX_SIZE (1ULL << (UNIQUES_HASH_MAX_SIZE_DEGREE - 1))

/** The number of least significant bits used for thinning. The remaining high-order bits are used to determine the position in the hash table.
  * (high-order bits are taken because the younger bits will be constant after dropping some of the values)
  */
#define UNIQUES_HASH_BITS_FOR_SKIP (32 - UNIQUES_HASH_MAX_SIZE_DEGREE)

/// Initial buffer size degree
#define UNIQUES_HASH_SET_INITIAL_SIZE_DEGREE 4

So the main set holds at most 2^16 = 65 536 hashes in a buffer of 2^17 slots, and 15 low bits of the hash are reserved for the thinning mask. The remaining 17 high bits select the cell:

cpp
// src/AggregateFunctions/UniquesHashSet.h:195
    size_t place(HashValue x) const { return (x >> UNIQUES_HASH_BITS_FOR_SKIP) & mask(); }

    /// The value is divided by 2 ^ skip_degree
    bool good(HashValue hash) const { return hash == ((hash >> skip_degree) << skip_degree); }

good() is the thinning test: the low skip_degree bits of the hash must be zero. The high bits pick the position, because the low bits are constant across all surviving elements — using them for the position would pile every element into the same cell.

Thinning

The state is three integers plus a flag:

cpp
// src/AggregateFunctions/UniquesHashSet.h:155
    UInt32 m_size;          /// Number of elements
    UInt8 size_degree{};      /// The size of the table as a power of 2
    UInt8 skip_degree;      /// Skip elements not divisible by 2 ^ skip_degree
    bool has_zero;          /// The hash table contains an element with a hash value of 0.

And the moment of truth is shrinkIfNeed:

cpp
// src/AggregateFunctions/UniquesHashSet.h:346
    /** If the hash table is full enough, then do resize.
      * If there are too many items, then throw half the pieces until they are small enough.
      */
    void shrinkIfNeed()
    {
        if (unlikely(m_size > max_fill()))
        {
            if (m_size > UNIQUES_HASH_MAX_SIZE)
            {
                while (m_size > UNIQUES_HASH_MAX_SIZE)
                {
                    if (unlikely(skip_degree >= max_skip_degree))
                        throw DB::Exception(DB::ErrorCodes::INCORRECT_DATA,
                            "Cannot thin out UniquesHashSet: {} elements remain at the maximum skip degree of {}",
                            static_cast<size_t>(m_size), static_cast<size_t>(max_skip_degree));

                    ++skip_degree;
                    rehash();
                }
            }
            else
                resize();
        }
    }

So: the set grows normally until it holds more than 65 536 elements. Then it does not grow — it thins. skip_degree goes up by one, and every element whose hash is not divisible by 2^skip_degree is deleted:

cpp
// src/AggregateFunctions/UniquesHashSet.h:200
    /// Delete all values whose hashes do not divide by 2 ^ skip_degree
    void rehash()
    {
        for (size_t i = 0; i < buf_size(); ++i)
        {
            if (buf[i])
            {
                if (!good(buf[i]))
                {
                    buf[i] = 0;
                    --m_size;
                }
                /** After removing the elements, there may have been room for items,
                  * which were placed further than necessary, due to a collision.
                  * You need to move them.
                  */
                else if (i != place(buf[i]))
                {
                    HashValue x = buf[i];
                    buf[i] = 0;
                    reinsertImpl(x);
                }
            }
        }

The picture is this:

text
  distinct values arriving:  A B C D E F G H ... (millions)

  skip_degree = 0  ->  accept everything, table grows
  table full at 65536 elements, distinct count so far maybe 200 000
  skip_degree = 1  ->  accept only hashes with bit0 == 0   (half of them)
  table full again at 65536, distinct count so far maybe 400 000
  skip_degree = 2  ->  accept only hashes with bits1..0 == 0 (a quarter)
  ...
  skip_degree = k  ->  accept 1 in 2^k elements

Each thinning step halves the sample rate, and the sample size stays roughly constant. The estimate multiplies the surviving count back up by 2^skip_degree.

Here’s the thing: the table does not need to know how many distinct values it has seen. It only needs to know how aggressively it is currently sampling. The count falls out of that at the end.

The estimator

The estimator is not simply m_size * 2^skip_degree — there is a correction for the systematic error of 32-bit hash collisions, and a pseudo-random remainder so that the result does not visibly sit on a power of two:

cpp
// src/AggregateFunctions/UniquesHashSet.h:842
        if (0 == skip_degree)
            return m_size;

        size_t res = m_size * (1ULL << skip_degree);

        /** Pseudo-random remainder - in order to be not visible,
          * that the number is divided by the power of two.
          */
        res += (intHashCRC32(m_size) & ((1ULL << skip_degree) - 1));

        /** Correction of a systematic error due to collisions during hashing in UInt32.
          * `fixed_res(res)` formula
          * - with how many different elements of fixed_res,
          *   when randomly scattered across 2^32 buckets,
          *   filled buckets with average of res is obtained.
          */
        return correctFor32BitCollisions(res);

The pseudo-random remainder is a lovely touch of honesty. Without it, every estimate would be a multiple of a power of two, and users would (correctly!) assume the result was rounded. It only costs one CRC and one mask.

The collision correction is an analytic formula for the birthday problem. If res distinct elements are scattered over 2^32 buckets, the number of occupied buckets is less than res because of collisions; to recover the number of distinct elements from the number of occupied buckets, you invert that relation:

cpp
// src/AggregateFunctions/UniquesHashSet.h:548
    /** With how many different elements, when randomly scattered across 2^32 buckets,
      * the given number of non-empty buckets is obtained on average.
      * This is the correction of the systematic error due to collisions of the 32-bit hashes.
      */
    static size_t correctFor32BitCollisions(size_t res)
    {
        size_t p32 = 1ULL << 32;

        /** When the number of distinct elements is much larger than 2^32, almost all buckets are filled
          * and `res` may reach (or, due to the pseudo-random remainder, exceed) 2^32,
          * where the formula below is not defined (previously this resulted in undefined behavior
          * when casting infinity or NaN to an integer). Saturate the estimate instead:
          * 32 bits of a hash contain no information about larger cardinalities anyway
          * (and the wide set takes over long before this point).
          */
        if (res >= p32)
            res = p32 - 1;

        return static_cast<size_t>(round(static_cast<double>(p32) * (log(static_cast<double>(p32)) - log(static_cast<double>(p32 - res)))));
    }

Read the formula as p32 * (ln p32 - ln(p32 - res)). For small res it is approximately res; for res near p32 it blows up, which is why the saturation guard exists — and that guard is the fix for issue #6078, where the cast of inf to an integer was undefined behaviour.

The wide set: fixing the 32-bit ceiling

The 32-bit hash has a hard ceiling. At a few billion distinct elements the correction formula is already straining, and above ~30 billion it was producing garbage. The fix, added in state version 1, is a second set that stores full 64-bit hashes — but only a tiny, heavily thinned sample of them.

The sample is defined by a skip degree of 18: only hashes with 18 zero low-order bits enter it, i.e. one in 262 144:

cpp
// src/AggregateFunctions/UniquesHashSet.h:89
/** Only hashes with this many zero low-order bits enter the wide set, so that it stays
  * negligibly small while the main set is accurate: one hash in 262144 passes.
  */
#define UNIQUES_HASH_SET_WIDE_INITIAL_SKIP_DEGREE 18

/// The maximum degree of the wide set buffer size before the values are thinned out further.
#define UNIQUES_HASH_SET_WIDE_MAX_SIZE_DEGREE 15

/// The maximum number of elements of the wide set: 16384 values take 256 KiB.
#define UNIQUES_HASH_SET_WIDE_MAX_SIZE (1ULL << (UNIQUES_HASH_SET_WIDE_MAX_SIZE_DEGREE - 1))

/** The estimate is taken from the wide set when it has at least this many values, i.e. starting
  * from about UNIQUES_HASH_SET_WIDE_MIN_SIZE_FOR_ESTIMATE * 2^UNIQUES_HASH_SET_WIDE_INITIAL_SKIP_DEGREE,
  * about two billion elements: at that point the statistical error of the wide estimate (about 1%)
  * meets the degrading precision of the 32-bit one.
  */
#define UNIQUES_HASH_SET_WIDE_MIN_SIZE_FOR_ESTIMATE 8192

So the wide set holds at most 16 384 hashes (256 KiB) and needs 8192 of them before it is trusted. Since only one in 262 144 elements enters it, 8192 elements means about 2.1 billion distinct values have been seen — exactly the point where the 32-bit estimator starts to degrade.

The wide set has one more twist: the hashes are XOR-ed with a constant before being stored.

cpp
// src/AggregateFunctions/UniquesHashSet.h:518
    /** The wide set samples the full hashes XOR-ed with this constant rather than the hashes themselves.
      * The sample stays just as uniform, but the hash of a frequent value never becomes a candidate
      * systematically: the default hash of the integer 0 is 0, and zeros are frequent in real data -
      * without the offset every such row would be a candidate for the wide set and would cost
      * an extra pass over its batch (this doubled the time of `uniq` over such columns).
      * The low bits up to the maximum thinning of the main set are zero, so that every candidate
      * still passes good() of the main set (see `widePrefilterMask`), and the next ones are not,
      * so that the hash 0 is never a candidate.
      */
    static constexpr UInt64 wide_hash_offset = 0x9E3779B97F4A0000ULL;

The constant is the golden-ratio fraction used in many hash mixers (0x9E3779B97F4A0000 is 2^64 / φ). The problem it solves is delightfully concrete: the default hash of the integer 0 is 0, and the wide-set candidate test is “are the low 18 bits zero?”. The hash 0 passes that test — so every zero row in the data would enter the wide set, and the extra work doubled the runtime of uniq over columns full of zeros.

XOR-ing with an offset whose low bits are non-zero removes that pathology while preserving uniformity.

The offset has to satisfy two constraints, and they are checked at compile time:

cpp
// src/AggregateFunctions/UniquesHashSet.h:528
    static_assert((wide_hash_offset & ((1ULL << max_skip_degree) - 1)) == 0);
    static_assert((wide_hash_offset & ((1ULL << UNIQUES_HASH_SET_WIDE_INITIAL_SKIP_DEGREE) - 1)) != 0);

The first says: the offset’s low bits are zero up to the maximum thinning degree of the main set, so that a wide candidate still passes the main set’s good() test — the wide set is a subset of the main sample. The second says: the offset’s low 18 bits are not all zero, so the hash 0 is never a wide candidate.

Two constraints, two static_asserts. This is the good stuff: an invariant expressed as a compile-time proof instead of a comment.

The wide set is allocated lazily, in a single block holding both the header and the table:

cpp
// src/AggregateFunctions/UniquesHashSet.h:373
    static WideSet * allocWideSet(UInt8 new_size_degree)
    {
        /// The header and the table are placed in a single allocation.
        size_t bytes = sizeof(WideSet) + (1ULL << new_size_degree) * sizeof(UInt64);
        WideSet * res = new (HashTableAllocator().alloc(bytes)) WideSet;
        res->size_degree = new_size_degree;
        res->buf = reinterpret_cast<UInt64 *>(reinterpret_cast<char *>(res) + sizeof(WideSet));
        return res;
    }

and it is only allocated when the first candidate shows up — which, for most data, never happens:

cpp
// src/AggregateFunctions/UniquesHashSet.h:469
        if (!wide)
            wide = allocWideSet(UNIQUES_HASH_SET_INITIAL_SIZE_DEGREE);

Which estimator is used

cpp
// src/AggregateFunctions/UniquesHashSet.h:820
    size_t size() const
    {
        /** The wide set gives a reliable estimate once it has enough values;
          * below that the 32-bit main set is more precise. If the wide sample does not cover
          * all the elements (see `wide_incomplete`), it is not there at all and the legacy
          * estimator is used, because a partial wide estimate would silently lose the rest.
          */
        if (wide && wide->m_size >= UNIQUES_HASH_SET_WIDE_MIN_SIZE_FOR_ESTIMATE)
        {
            size_t res = static_cast<size_t>(wide->m_size) * (1ULL << wide->skip_degree);

            /** Pseudo-random remainder - in order to be not visible,
              * that the number is divided by the power of two.
              */
            res += (intHashCRC32(wide->m_size) & ((1ULL << wide->skip_degree) - 1));

            /** Collisions of 64-bit hashes are negligible: their systematic error would reach
              * just 0.003% at 10^15 distinct elements, far below the statistical error of the estimate.
              */
            return res;
        }

Note the last comment: at 10^15 distinct elements, the systematic error of 64-bit hash collisions would be 0.003%, far below the statistical error of the estimate itself. So the wide set is not exact either — it is exact enough.

The hot loop: batching

The insertion path is where the performance lives, because uniq is usually applied to millions of rows. The implementation does not insert one hash at a time; it computes eight hashes and eight target cells first, then inserts them:

cpp
// src/AggregateFunctions/UniquesHashSet.h:749
        size_t i = 0;
        while (i < size)
        {
            /// Check that we have enough capacity and enough values to insert in batch. If not, we will insert values one by one which
            /// allows us to check the shrink condition after each insert and avoid inserting too many values before shrinking.
            if ((max_fill() - m_size) >= insert_many_batch_size && ((size - i) >= insert_many_batch_size))
            {
                /// We read and transform multiple values at once which allows both the compiler and the CPU to better optimize the code.
                /// We calculate place() even for !good() hashes to maximize data independence and enable better out-of-order execution.
                /// The extra work is negligible compared to the instruction level parallelization benefits.
                std::array<HashValue, insert_many_batch_size> hash_value; // NOLINT(cppcoreguidelines-pro-type-member-init,hicpp-member-init) - filled by the loop below before read
                for (size_t j = 0; j < insert_many_batch_size; ++j)
                {
                    hash_value[j] = hash(Transform(data[i + j]));
                }

with the batch size fixed at eight:

cpp
// src/AggregateFunctions/UniquesHashSet.h:665
    /// This value is arbitrary. The optimal value might depend on the CPU pipeline depth, cache line size (64B = 8 UInt64s),
    /// hash function quality, collision rate, instruction parallelism, etc.
    /// We choose a value that is big enough to provide sufficient instruction level parallelism but not too big to bloat the code size.
    static constexpr size_t insert_many_batch_size = 8;

Two details worth noticing. place() is computed even for hashes that will be rejected by good(), on purpose: it keeps the loop free of data-dependent branches and lets the out-of-order engine overlap the work. And the wide-set candidates are collected into a small local buffer during the loop and inserted after it, because inserting them inside would force the compiler to reload the set’s fields from memory on every iteration:

cpp
// src/AggregateFunctions/UniquesHashSet.h:738
        /** The candidates for the wide set (see the comment at `widePrefilterMask`) are detected
          * behind the `good()` test, which every one of them passes and which already rejects all
          * but one value in 2^skip_degree, and they are only collected into a local buffer there.
          * They are inserted after the loop rather than inside it: a call inside would make
          * the compiler cautiously reload the fields of the set from memory all the time.
          * This loop is very sensitive to the code generation: the batch loops below must be
          * fully unrolled as they are without the wide set, otherwise `uniq` gets up to 50% slower.
          */

“otherwise uniq gets up to 50% slower” is a great reminder that in an aggregation hot loop, the code layout is part of the algorithm.

What is hashed

The value that goes into the set is not the value itself but a 64-bit hash of it, of which only the low 32 bits feed the main set:

cpp
// src/AggregateFunctions/UniquesHashSet.h:637
    /// The full 64-bit hash: its low 32 bits feed the main set, and the whole value the wide set (see `wideHash`).
    static UInt64 fullHash(Value key) { return static_cast<UInt64>(Hash()(key)); }
    static HashValue hash(Value key) { return static_cast<HashValue>(fullHash(key)); }

and the per-type hashing is chosen in the aggregate function:

cpp
// src/AggregateFunctions/AggregateFunctionUniq.h:273
template <typename T, typename ColumnType>
struct AggregateFunctionUniqTraits
{
    static ALWAYS_INLINE auto hash(T x)
    {
        if constexpr (std::is_same_v<T, std::string_view>)
        {
            return CityHash_v1_0_2::CityHash64(x.data(), x.size());
        }
        else if constexpr (std::is_same_v<T, IPv6>)
        {
            /// For compatibility reasons IPv6 is hashed as FixedString(16).
            return CityHash_v1_0_2::CityHash64(reinterpret_cast<const char *>(&x), sizeof(x));
        }
        else if constexpr (is_floating_point<T>)
        {
            return bit_cast<UInt64>(x);
        }
        else if constexpr (sizeof(T) <= sizeof(UInt64))
        {
            return x;
        }
        else
        {
            return DefaultHash64<T>(x);
        }
    }

Note that for integers the “hash” is the identity: an integer’s low bits are used directly, which is fine because the thinning test only looks at the low 15..18 bits and the position comes from the high bits. For sequential integers the high bits are nearly constant too — which is precisely why the wide set XORs with an offset, and why the main set’s place() uses the high bits of the 32-bit hash, which is intHash32 and mixes.

Indeed the set’s own hash function is the 32-bit integer hash:

cpp
// src/AggregateFunctions/UniquesHashSet.h:108
/** This hash function is not the most optimal, but UniquesHashSet states counted with it,
  * stored in many places on disks (in many companies), so it continues to be used.
  */
struct UniquesHashSetDefaultHash
{
    size_t operator() (UInt64 x) const
    {
        return intHash32<0>(x);
    }
};

That comment is a nice piece of engineering history: the hash is frozen because the serialized states of uniq are stored on disk in many companies’ systems, and changing the hash would invalidate all of them.

The state format

Because the set is serialised into aggregate-function states that travel between servers, the format is versioned. Version 1 adds a flags byte:

cpp
// src/AggregateFunctions/UniquesHashSet.h:963
    /** Two serialization formats exist.
      * The legacy format (state version 0): skip_degree, then the number of values, then the 32-bit values
      * of the main set.
      * The new format (state version 1): a flags byte (bit 0 - a wide set follows the main set,
      * bit 1 - the wide sample is incomplete, see `wide_incomplete`; the two are mutually exclusive),
      * then the main set in the legacy layout, then, if present, the wide set: its skip_degree,
      * the number of values, and the 64-bit values.
      */

and a legacy state read back is marked as having an incomplete wide sample:

cpp
// src/AggregateFunctions/UniquesHashSet.h:1048
        /** A non-empty state written in the legacy format carries elements that were never offered
          * to a wide set, so no wide estimate of this state (or of anything it is merged into)
          * can be trusted. An empty legacy state contributes nothing and does not spoil a merge.
          */
        if (use_legacy_format && m_size > 0)
            wide_incomplete = true;

That mark is sticky and propagates through merges, because the missing high bits of the already-consumed elements cannot be recovered. The alternative — estimating from a partially-covering wide sample — would silently undercount everything the sample missed, which is far worse than a merely imprecise estimate.

The whole family

uniq is one of several cardinality estimators in ClickHouse, and they make different trade-offs:

function	structure	exact?
`uniqExact`	a full hash set of the values	yes
`uniq`	the thinning set of this article	no, ~1-2% error
`uniqCombined`	small set → hash set → HyperLogLog, switching as it grows	no
`uniqTheta`	a datasketches theta sketch	no, mergeable

uniqCombined is the one that switches representation:

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.

and uniqExact keeps the two-level structure of the previous article in reserve, converting when it grows:

cpp
// src/AggregateFunctions/AggregateFunctionUniq.h:154
    /// When creating, the hash table must be small.
    static constexpr size_t initial_size_degree = 4;
    using SingleLevelSet = HashSetWithStackMemory<Key, HashCRC32<Key>, initial_size_degree>;
    using TwoLevelSet = TwoLevelHashSet<Key, HashCRC32<Key>>;
    using Set = UniqExactSet<SingleLevelSet, TwoLevelSet>;

Note the “hash table must be small”: the initial buffer lives on the stack of the aggregate function state, so a uniqExact state that never grows past 2^4 slots allocates nothing on the heap at all.

A quick sanity check of the behaviour in SQL:

sql
SELECT
    uniqExact(user_id)      AS exact,
    uniq(user_id)           AS approx,
    uniqCombined(user_id)   AS combined
FROM events;

approx will differ from exact by a fraction of a percent on a few million distinct users, and by more on a few hundred million — that is the thinning, and it is the price of a bounded 64 KiB state.

Trade-offs

What the thinning set buys:

A bounded, tiny state. The main set is at most 2^17 × 4 bytes = 512 KiB, and the wide set at most 256 KiB. A uniq state never grows with the cardinality, which matters when the state is merged across a cluster or spilled to disk.
A mergeable state. Merging two uniq states is a union of hash sets plus a max(skip_degree), which is why uniq works with Distributed tables and AggregatingMergeTree.
A principled estimator. The thinning factor is known exactly, so the estimate is a maximum-likelihood estimate rather than a heuristic.
No allocation in the hot loop. The table is a flat array of UInt32, and the batch of eight hashes is computed with instruction-level parallelism.

What it costs:

Precision. The relative error grows with the cardinality, because the sample size stays constant while the multiplier grows. The wide set pushes the useful range from billions to trillions, but the error is still around 1% at the switch-over point.
A hash-quality dependency. The whole scheme assumes the hash is uniform; a bad hash breaks the thinning, because the surviving elements would not be a uniform sample.
Irreversible loss. Once thinned, the dropped hashes are gone. That is why the wide set has to be fed from the first insertion, and why a legacy state can never grow a wide sample.
A 32-bit ceiling without the wide set, which is exactly the bug that issue #6078 was, and why the state format has two versions.

This is a good example of an approximation that is statistically principled rather than ad hoc: the state is small because the algorithm throws away information on purpose, and the estimate is exact given the information that was kept.

Wrapping up

The one thing to remember: uniq() does not estimate by approximating — it estimates by sampling, and it knows the sample rate exactly. That is why the state never grows and why the estimate is a maximum-likelihood one rather than a guess.

The part people get wrong: the state is not just “a hash set”. It is a hash set plus a thinning factor, plus a second sparse 64-bit sample that takes over past ~2 billion distinct values. If you are estimating cardinalities in the trillions, you are living in the wide set’s world.

What to go do about it: compare uniq against uniqExact on your own data before you trust it. If the two agree within a percent, uniq is fine and cheaper. If they do not, and you need exactness, you know now what you are paying.