Counting Distinct Values Without Storing Every Record

Questions about log streams are frequently questions about distinct counts: how many users hit the failing endpoint, how many distinct error templates appeared in the last hour, how many hosts reported the condition. Answering them by keeping a set of every identifier is the natural approach and it fails at scale for a reason that has nothing to do with memory efficiency: the set must be merged across shards, retained for the query window, and rebuilt for every different field. A sketch answers the same question with a fixed-size state that merges by a cheap operation, and the price is a known, bounded relative error.

The set is the wrong data structure

An exact distinct count requires storing every distinct value, or a hash of it. The space is proportional to the cardinality, which is exactly the quantity being measured, so the cost of the answer is proportional to the answer. For a field with a million distinct values and a 16-byte hash per value, the state is 16 megabytes per field per window, and merging two shards means a set union that is linear in the smaller set.

The distribution of distinct counts in a log stream is also awkward. A request_id field has a cardinality equal to the request count, which makes the exact answer expensive and useless: nobody needs to know that there were 4,271,933 distinct request identifiers, they need to know that there were about 4.27 million. A host field has a cardinality of a few hundred, where an exact set is trivially cheap. The decision is per field, and it follows the same dimension-versus-payload distinction as Structured Fields Versus Formatted Message Strings.

The observation that makes estimation possible

Uniform hashing maps every distinct value to a random bit string of fixed length. The number of distinct values determines the distribution of those strings in a way that can be observed without storing them.

Take the hash of a value and count the number of leading zero bits before the first one. If the hashes are uniform, the probability of seeing at least k leading zeros is 2^−k, so in a set of n distinct values the maximum observed leading-zero count is about log₂ n. A single register holding that maximum is therefore a very rough estimate: it has a resolution of powers of two and a variance that makes it nearly useless on its own.

The fix is averaging over many independent hash functions, or, equivalently and much more cheaply, splitting the hash into two parts: the first p bits select one of m = 2^p registers, and the remaining bits supply the leading-zero count recorded in that register. Each register observes roughly n/m values, and the maximum over a register estimates log₂(n/m). Averaging the m register values recovers n with a variance that falls as m grows.

The estimator is a harmonic mean of 2^register_value, with corrections for the small-range and large-range regimes where the raw estimator is biased. The correction terms are part of the algorithm and cannot be omitted: the raw harmonic mean overestimates at low cardinality, where many registers are still zero, and the bias is large enough to matter below a few times m.

Error is a formula, not a measurement

The standard error of the register-based estimator is approximately 1.04/√m, where m is the register count. This is an analytic result, and it makes sizing a direct calculation.

Registers (m)	State size at 6 bits/register	Relative standard error
256	192 bytes	about 6.5%
4,096	3 KB	about 1.6%
16,384	12 KB	about 0.8%
65,536	48 KB	about 0.4%

The state size assumes six bits per register, which is the width used in the compact representation because register values above the low 60s are unreachable for any cardinality a system will encounter. Packing six-bit fields into bytes is fiddly but halves the memory relative to one byte per register.

The error is a standard error, meaning that a single estimate falls within roughly one standard error of the truth about 68 percent of the time and within two about 95 percent. Two consequences follow for interpreting a dashboard. First, an estimate of 10,000 with 0.8 percent error has a plausible range of about 9,920 to 10,080, so a change of fifty is not distinguishable from noise. Second, comparing two estimates compounds the error: the difference of two independent estimates has a standard error of √2 times the individual error, so a 0.8 percent sketch cannot resolve a one percent change between two windows.

The second consequence is the one that surprises people. A sketch sized for a single count is not automatically sized for a ratio or a difference, and the required size is set by the smallest effect that must be detected, not by the largest count that must be reported.

Merging, and why the merge is exact

The register array has the property that the merge of two sketches is a per-register maximum. This is a lattice operation: it is associative, commutative, and idempotent, so sketches can be merged in any order and any number of times without changing the result.

Idempotence is what makes the structure useful for a stream that may deliver a record twice. Because the merge takes a maximum, a duplicate value has no effect after the first observation, so the estimate is insensitive to duplicates. That is a strong property: an exact set is also insensitive to duplicates, but a count of records is not, and a stream with at-least-once delivery makes the distinction essential. A “distinct count” over a duplicated stream is still correct, while a “count of events” is inflated by the duplication factor.

Merging also composes with time windows. A sketch per minute merges into a sketch per hour and then per day, with no loss beyond the individual sketches’ error, which grows by the √k factor for k merged sketches only if they are disjoint. If the windows overlap, the idempotence means overlapping records are counted once, which is the correct behaviour for a distinct count and the wrong one for a rate.

The register state does not support subtraction, and this is a hard limitation. Removing a value from the set is not possible, because the register only remembers a maximum and there is no record of which value contributed it. A sliding window over a sketch therefore cannot be implemented by subtracting the departing window; it must be computed by merging the windows that remain, or by maintaining sketches at a granularity fine enough that the departing window is discarded whole. Systems that support “distinct count over the last 30 minutes” with a one-minute resolution keep thirty sketches and merge them per query, and the cost of the query is proportional to the number of sketches merged.

Alternatives and their regimes

Exact set with a cardinality cap. Below a threshold of a few thousand, a hash set is exact, cheap, and supports membership queries that a sketch cannot answer. A hybrid keeps the exact set until it exceeds the cap and converts to a sketch at that point, which is the design used by several implementations to get exactness for small cardinalities and bounded memory for large ones. The conversion is one-way, which is acceptable because the exact representation is only abandoned when it becomes expensive.

Sampling-based estimation (theta sketches). These retain a sample of the hash values below a threshold chosen so that the sample fits a target size. The estimate is the sample size divided by the threshold fraction, which is unbiased, and the structure supports set operations including intersection and difference, operations a register sketch cannot perform. The cost is that the retained hashes are stored, so the state is proportional to the sample size rather than fixed, and the error is a function of the sample size. For questions involving overlap between two populations, such as how many users saw both of two errors, this class is the right tool.

Bitmap over a bounded domain. When the domain is known and small (a few thousand possible status codes, a fixed set of host identifiers), a bitmap is exact, fixed-size, and supports union, intersection, and difference with single instructions per word. The domain must be enumerable, which excludes arbitrary identifiers but includes most categorical fields.

The selection criterion is what the question requires, not what the cardinality is. A question that only needs a count is answered by the smallest structure that bounds the error. A question that needs membership, intersection, or difference needs a structure that retains values or an exact representation. Choosing a register sketch for an overlap question and discovering later that the operation is unsupported is a design error that requires reprocessing the raw data, which may no longer exist because of the retention window described in Retention Policy as a Storage Budget.

Aggregating over a stream that is already reduced

A sketch is applied to values extracted from records, so its accuracy depends on the record stream being complete for the values of interest. If the stream has been collapsed by repeat suppression, the values inside the collapsed records are gone: the mechanism described in Repeat Suppression and Template Fingerprints replaces many records with one plus a count, and a distinct count over a field that only appeared in the discarded records cannot be recovered. This is a case where two reductions compose badly, and the ordering matters: suppression must preserve the fields that feed a cardinality estimate, or the estimate must be computed before suppression.

The same reasoning applies to sampling. A sample of records yields a sketch of the sampled values, and scaling the estimate by the inverse sampling rate is valid only for a uniform sample over the whole population. A sample biased toward rare templates, which is what template-aware sampling produces, does not support a simple scaling, because the inclusion probability differs per value. The sketch estimates the cardinality of what it saw, and what it saw was not a uniform sample of the population.

The practical arrangement is to compute cardinality sketches at the point where the full stream exists, in the collector and before any reduction, and to ship the merged sketch as a first-class aggregate alongside the retained records. The sketch is then a summary that survives the loss of the records it summarized, which is the property that makes it worth its fixed cost.