Sketches, heavy hitters and floating-point sums

Why is even a SUM not deterministic?

Approximate aggregation: what a sketch actually does

The usual story, "sketches trade accuracy for speed", understates the mechanism and so misses when sketches are worth using. The sharper statement is:

A sketch is a small summary structure of fixed size that can be updated one row at a time and merged with other sketches. HyperLogLog (HLL) gives COUNT DISTINCT a fixed-size, mergeable accumulator of about 12 KB. KLL and t-digest do the same for quantiles. As soon as the accumulator is bounded and mergeable, every optimization in this article comes back:

partial aggregation,
two-phase aggregation with one shuffle,
spilling partial results instead of raw rows,
immunity to group skew,
incremental maintenance.

One change in the function's algebra unlocks several structural advantages at once. That is why sketches matter a great deal in distributed engines and hardly at all on a single node with everything in memory, where an exact hash set was already fine.

Precision, mergeability, sampling

The fee is small and grows fast: HLL's error falls as one over the square root of its register count, so 12 KB gives about 0.8% and 0.1% costs about 800 KB. Precision costs quadratically in memory, the same square-root law (error ∝ 1/√n) that governs sampling. Two properties matter for an operator. Mergeability is not uniform: HLL merges bit-identically in any order, while t-digest re-compresses and gives answers that depend on the merge tree, so a published metric should check which sketch it uses (HyperLogLog, quantile sketches). And a sample cannot estimate a distinct count: the rare values that dominate the answer are the ones a sample misses (why NDV cannot be sampled). Sampling works for SUM and AVG; it fails for COUNT DISTINCT, MIN and MAX.

A fourth strategy: bound the output

There is a fourth approximate strategy. It is not a sketch of the value but a bound on the output. Heavy-hitters structures (Space-Saving, Count-Min) track the top-k groups accurately and drop the tail, turning O(G) state into O(k). If the query needs only the top 20 products, holding ten million groups was never necessary.

Floating-point summation: even the easy case is not exact

SUM over floating-point numbers (doubles) is not associative: (a + b) + c can differ from a + (b + c) in the last bits, because each addition rounds. Different partition counts, different task completion orders and different merge trees give different low bits. So the most plainly distributive aggregate in SQL is already non-deterministic across runs in a distributed engine, before any sketch is involved.

This matters for the same reason lossy sketch merges matter. A reported figure that changes when the cluster is resized is a reconciliation problem, even when both values are "right". The fixes are ordinary:

Kahan or Neumaier compensated summation (carry a small correction term for the bits lost in each addition),
fixed-point or decimal types for money,
sorting before summing.

The lesson: exactness and determinism are different properties. A distributed SUM is exact only in the sense that each partial is computed correctly.

Case, resolvedConstructed case · Omar and Tarini at Shopsy

The COUNT(DISTINCT) that ran out of memory

COUNT(DISTINCT user_id) over 50 billion events ran one executor out of memory, and turning on partial aggregation made a SUM by customer slower. Where it started: Aggregation algorithms →

Tarini explains Omar's two symptoms in one picture.

The distinct count. COUNT(DISTINCT user_id) is holistic. There is no small partial result to build on each executor, so every raw row of the home page (5 billion rows, 40 GB) was sent to one executor with 16 GB of memory. She rewrites it with the two-shuffle plan (deduplicate (page, user_id) pairs first, then count). For the monthly dashboard, where 0.8% error is fine, she uses HLL: 12 KB per page, mergeable, one shuffle, immune to the skewed page. Omar's one worry is that the dashboard number moves slightly between runs. She tells him to check which sketch it is: HLL merges are exactly reproducible, a t-digest's are not.

The slower partial aggregation. With 10 million rows per executor spread over 40 million customers, the local table has about 8.85 million entries and reduces the data by only 1.13x. Partial aggregation was a tax. She asks the platform team to switch on the engine's adaptive mode, which samples the first rows and drops the partial step when the hit rate is low. Omar writes a note on his monitor: "rows per group per partition, and which kind of function."