What probabilistic structures forbid

Why store sketches rather than estimates?

The rule that is violated most often: store the sketch, not the estimate

A mergeable sketch does not compound error. Merging 30 daily HyperLogLogs produces exactly the sketch you would have built from the full month, so the error of the monthly figure equals the error of one daily figure. But storing approx_count_distinct(day) as a number and summing across days is not approximately right. It is wrong, by the amount of cross-day overlap (a parcel scanned on Monday and Tuesday is counted twice), and the error grows with the number of days combined. The same applies to quantiles. A rollup table whose columns are sketches is a different kind of object from one whose columns are numbers, and the difference is that the first one composes.

This is also the answer to a question that is easy to miss: how does error behave when sketches feed sketches? Mergeable sketches do not compound error. Estimates do.

What this article forbids

Exact distinct counting in sublinear space.
Exact quantiles in bounded space.
Any estimator with error better than 1/√m from m observations (the Approximation law).
Cardinality estimation from a uniform sample.
Sub-quadratic exact all-pairs similarity.
In general: any question whose answer is not a function of the statistic the sketch kept. HLL cannot intersect, Count-Min cannot see the tail, a sample cannot count distinct values, a filter cannot list its contents.

There is one more, and it has operational teeth: you cannot recover the data from the sketch. Sketching is an early decision about the question. A rollup table of HLL sketches keyed by day and three dimensions has committed you to those dimensions. A fourth dimension means reprocessing the raw data, if you still have it. Sketch-based pre-aggregation trades query cost for the permanent loss of unasked questions, and the bill arrives months later, when someone asks a reasonable question that the pipeline structurally cannot answer.

Escapes and their costs

Escape	Cost
Keep the raw data next to the sketch	the space you were saving (usually still correct)
Choose a sketch with more algebraic closure (Theta instead of HLL)	more space per unit of accuracy; buys intersections
Two tiers: exact structures for the head, sketches for the tail, or a sampled exact store next to a full sketch	two systems to run
Restrict the question, not the answer (exact top-k by a bounded heap, from Ordering structures)	nothing; the best escape when it is available, because it costs no accuracy
Buy more memory	at the square-root exchange rate: 4 times the memory for half the error

Case, resolvedConstructed case · Arjun at Parcelo

40 GB to count about a billion

A unique-parcels report needed 40 GB to hold a billion distinct tracking IDs, and mistyped IDs (8% of lookups) each cost a full index descent and an SSD read just to answer 'not found'. Where it started: Probabilistic structures →

Problem 1 (40 GB of state). The dashboard needs "about 1 billion", not 1,000,000,000 exactly. Arjun replaces the hash set with one HyperLogLog per day: 16,384 registers of 6 bits is about 12 KB, with a standard error of 1.04/√16,384 = 0.81%. The job needs 12 KB instead of 40 GB. Because HLL is idempotent, a replayed Kafka-style batch does not change the answer. And because merge is element-wise max, "unique parcels this week" is a merge of seven stored daily sketches, which is exact under union. He stores the sketches, not the numbers, in the rollup table. He does not use HLL for "parcels seen at both Mumbai and Pune", because that is an intersection; for such questions he uses Theta sketches.

Problem 2 (typos hit the SSD). Parcelo's files are immutable, so he builds an XOR filter per file at write time, about 8 bits per key at 1% false positives. A mistyped ID is now rejected in memory 99% of the time, with no SSD read. Real IDs pay one extra memory probe. He checks the workload first: typos are 8% of lookups, so the filter saves about 7.9% of all reads and costs a small probe on the other 92%. This is a good deal here because the SSD is about 1,000 times slower than the probe. For a table that fits in RAM, it would be pure overhead.

The other questions from the same week. "Which three depots send most scans?" is a heavy-hitter question, so he uses Space-Saving with 1,000 counters and does not present its output as an exact ranking. "Delay percentiles per depot per hour" uses one t-digest per depot per hour, merged upward; he never averages stored p99 values. Lena asks for a sample of 10,000 events for debugging a strange depot: a reservoir sample. He notes that sampling would never have found the 12 broken scans, which is why those are tracked separately with an exact counter.

His rule for the wall: a sketch answers one question; write the question next to it.