All posts

Counting the Uncountable: How a Few Kilobytes Stand In for a Billion Things

Every ‘unique visitors’ number on your dashboard is a confident approximation. HyperLogLog and its cousins distill billions of events into a few kilobytes with a provable error bound — and there’s a live one in the sandbox you can stream a firehose through.

Abstract visualization of a colorful particle data stream funneling through a narrow point into a compact glowing grid of registers, on a dark background with teal, blue, and pink accents.

Count distinct visitors within a known margin.

The tile reads 2.47M unique visitors this month. It is wrong, and the person who built it knows exactly how wrong: about ±0.81%, roughly twenty thousand either way. The exact figure would have cost a terabyte of shuffle and twenty minutes of cluster time; the wrong one fit in 12 kilobytes and landed before the page finished painting. That trade — a provably-bounded approximation in exchange for a thousandfold less memory — is the most underrated idea in data engineering, and almost nobody outside the warehouse team knows it's quietly running under their dashboards.

The most defensible number is the one that admits it's guessing

Ask a database for COUNT(DISTINCT user_id) over a billion-row events table and you are asking it to do something expensive. To count distinct things exactly, you have to remember every distinct thing you've already seen — a hash set that grows with the data, a sort that spills to disk, a shuffle that drags every row across the network so identical keys land on the same machine. For a few thousand rows, who cares. For a billion rows a day across a sharded cluster, exact distinctness is the query that pages the on-call engineer at 2 a.m.

So the warehouse cheats, and the cheat is the interesting part. Instead of remembering the values, it remembers a shape. It keeps a tiny, fixed-size summary that captures just enough statistical structure to estimate how many distinct things went by — and it tells you the answer with a known error bound. Not a vague "this might be off." A number: this estimate is within 0.81% of the truth, 65% of the time, by construction.wiki

I've built enough Looker and BigQuery dashboards to have strong feelings about this, and the strongest one is this: a number with an error bar is more honest than a number without one. The exact-looking COUNT(DISTINCT) that took twenty minutes implies a precision the underlying data rarely deserves — bot traffic, double-fired events, session-stitching guesses, the user who cleared cookies. The approximate count that admits ±0.81% is the one I'd defend in a review, because it states its own uncertainty out loud. Distilling billions of raw events into a single tile on a slide is an act of lossy compression. The craft is being explicit about what you threw away.

The structures that make this trade are called probabilistic data sketches, and the most famous of them is HyperLogLog.

How HyperLogLog counts without remembering

Here is the whole idea in one image: flip a coin until it comes up tails, and record the longest run of heads you saw. One person's longest streak tells you almost nothing. But say a thousand people each play, and the longest streak anyone hit was nine heads in a row. You can reasonably guess that a lot of people played. A nine-head run is a 1-in-512 event, and you don't see 1-in-512 events in a small crowd. Rare patterns are evidence of large populations. That single intuition, made rigorous, is HyperLogLog.flajolet

The mechanics are almost insultingly simple. Each incoming key is hashed into a random-looking bit string. The first few bits choose one of m registers — think of them as m separate coin-flipping games running in parallel. The remaining bits are the "coin flips": the algorithm counts the leading zeros and keeps, in that register, only the longest run it has ever seen. Duplicates change nothing, because the same key hashes to the same bits and the same already-recorded run. At the end, it takes a bias-corrected harmonic mean across all m registers and turns "the longest runs we saw" back into "how many distinct keys must have flowed through."

Figure 1: One pass of HyperLogLog — hash each key, split the bits, keep only the longest zero-run per register, then take a bias-corrected harmonic mean.

The payoff is that the memory never grows with the data. The registers are the whole state. Feed HyperLogLog ten items or ten billion, and it occupies the same fixed array — you are only ever paying for m small numbers. The accuracy is governed entirely by how many registers you keep: the standard error is 1.04 / √m. Double the registers, and the error shrinks by √2. The canonical configuration reaches a typical 2% error on cardinalities above a billion using about 1.5 kB.wiki

The implementations you've actually used are tuned variants of exactly this:

  • Redis popularized it for application developers with three commands — PFADD, PFCOUNT, PFMERGE — backed by a sketch capped at 12 kB that holds a 0.81% standard error across billions of elements.wiki
  • ClickHouse ships uniqHLL12, roughly 2.5 kB of state per group at about 1.6% error, the workhorse behind daily-active-user and unique-visitor metrics.clickhouse
  • Meta rebuilt cardinality estimation in Presto on HyperLogLog to make distinct counts tractable across their warehouse, and contributed the storage format back.presto
  • BigQuery exposes it as HLL_COUNT.* and APPROX_COUNT_DISTINCT — the function I reach for first whenever a dashboard query starts timing out.bq

That last one matters because of the word approximate sitting right there in the function name. The honesty is built into the API:

-- Exact: correct, slow, memory-hungry, pages you at 2 a.m.
SELECT COUNT(DISTINCT user_id) FROM events;

-- Approximate: ~0.8% error, constant memory, returns before you blink
SELECT APPROX_COUNT_DISTINCT(user_id) FROM events;

I built a live version so you can watch the trade happen instead of taking my word for it: the HyperLogLog sandbox. Stream synthetic events through it, watch the register heatmap light up, and watch the estimate chase the true distinct count while the memory figure stays frozen. The instructive button is +1M duplicates — the event counter rockets by a million while the estimate barely twitches, because duplicates carry no new information. Slide the precision down and watch the error band widen into noise; slide it up and watch it tighten. It's the most direct way I know to feel why this works — and the whole thing is open source, with a GitHub link tucked into the sandbox if you want to clone it and point it at your own firehose.

One sketch per question

HyperLogLog answers exactly one question — how many distinct? — and answers nothing else. That narrowness is the point. The sketch family is a set of specialized instruments, each trading a different slice of exactness for a different constant-size summary. Pick the wrong one and you get nonsense; pick the right one and you get a hard question answered in kilobytes.

SketchQuestion it answersMemoryError profileWhere you've met it
HyperLogLogHow many distinct items?~1.5–12 kB~0.8–2% std. errorAPPROX_COUNT_DISTINCT, Redis PFCOUNT, ClickHouse uniq
Count-Min SketchHow frequent is this item? (heavy hitters)KBs, tunableOne-sided overcountNetwork telemetry, trending-topic counts, rate limitingcms
Bloom filterHave I seen this item before?~bits per itemFalse positives, never false negativesCache admission, "is this URL malicious," dedup pre-checkscms
t-digest / KLLWhat's the p50 / p99? (quantiles)KBs, constantAccurate at the tailsLatency dashboards, SLO percentilesbq

Table 1: The working set of probabilistic sketches. Each answers one question in sublinear space; none of them store the underlying values.

The mental model that keeps me out of trouble: a Bloom filter is a bouncer with a bad memory who never wrongly turns away a regular but occasionally waves through a stranger. A Count-Min Sketch is a tally that might overcount but never undercounts, which is why it's the de facto standard inside programmable network switches where you have nanoseconds and no RAM.cms A t-digest is the one to reach for when somebody asks for p99 latency and you refuse to either store every request or lie with an average. And HyperLogLog is the distinct-counter. Four questions, four instruments, all of them sublinear.

The superpower is that sketches merge

Constant memory is the headline, but mergeability is what makes sketches the backbone of real pipelines, and it's the property most people miss.

Two HyperLogLog sketches can be combined into one by taking the register-wise maximum — and the merged sketch is exactly what you'd have gotten by feeding both streams into a single sketch from the start. No re-reading of rows. No re-shuffle. This is the difference between a parlor trick and infrastructure.

Figure 2: Mergeability — combine per-shard sketches by taking register-wise maxima, then estimate once. The expensive pass over raw rows happens only at ingest.

Mergeability is why this scales the way warehouses need it to. You compute one sketch per shard, per hour, per partition — wherever the data already lives — and store the little binary blobs. "Distinct users today" is a merge of 24 hourly sketches. "Distinct users this quarter" is a merge of 90 daily ones. The expensive pass over raw events happens once, at ingest; every rollup after that is cheap arithmetic over kilobyte summaries. Additive metrics like SUM always composed this way; sketches drag the non-additive ones — distinct counts, quantiles, heavy hitters — into the same world.

This is exactly the bet Apache DataSketches institutionalized: a library of mergeable sketches with mathematically proven, user-tunable error bounds, designed so a sketch built in one engine can be read in another.datasketches On May 22, 2025, BigQuery shipped DataSketches support: C++ compiled to WebAssembly, running inside JavaScript UDFs. Sketches range from about 50 bytes to 2 MB, depending on the accuracy you dial in. The binary format is interpretable across Java, C++, and Python.bq A Spark job can build a sketch at ingest and a BigQuery query can merge it at read time. Databricks wired the same library into Spark for sketch-based distinct counting.spark The sketches have become a lingua franca for approximate aggregates moving between systems.

The timing is not an accident. Single-node analytics is having a genuine moment — DuckDB crossed a million weekly PyPI downloads as the embedded, zero-config warehouse-in-your-app, while ClickHouse hardened into the high-scale real-time engine, with teams reporting steep cost drops migrating off cloud warehouses.olap PostHog runs product analytics — funnels, retention, paths — over billions of events on ClickHouse, after starting on Postgres until, in their words, analytical queries "were frying it alive."posthog You do not serve a real-time funnel over billions of events by exact-counting on every page load. You serve it with uniq, and you accept the error bar.

Knowing the error budget is the actual skill

The storytelling lives in that distinction, and it's not a soft point — it's what separates a defensible dashboard from a misleading one.

Every number you put in front of a decision-maker has an error budget, whether or not you've measured it. Sketches force you to make that budget explicit, which is a feature disguised as a constraint. The real skill in data storytelling isn't picking the right chart type. It's knowing, for every figure on the slide, how wrong it's allowed to be — and matching the tool to that tolerance.

A 0.8% error on monthly active users is invisible; nobody steers the company differently because the number was 2.47M instead of 2.49M. Approximate it, ship it, move on. The same 0.8% error on a billing reconciliation, a financial close, a fraud case count, or a regulatory filing is malpractice. Those are the places where you eat the terabyte shuffle and count every row exactly. The error budget is zero, and "close enough" is a lawsuit. Reaching for APPROX_COUNT_DISTINCT on revenue is the kind of shortcut that ends up in a postmortem.

The discipline is choosing deliberately, and labeling the choice. A dashboard tile that quietly shows an approximate count looks identical to one showing an exact count — same font, same confidence, same authority — which is precisely the design failure. If a number is a 0.8%-error estimate, the interface should be willing to say so, the same way a good loading state is willing to say what it's waiting on. The estimate isn't the problem. The estimate pretending to be exact is the problem.

The research underneath all this is still moving, incidentally — newer cardinality sketches like UltraLogLog squeeze the same accuracy into less space than classic HyperLogLog, so the constants in that 1.04/√m bargain keep improving.ultraloglog But the core idea is decades old and quietly load-bearing: most of the "exact" numbers you trust every day are confident approximations wearing a precise-looking outfit.primer

So the next time a dashboard tells you there were exactly 2,473,918 unique visitors, treat that last digit with the skepticism it has earned. The honest version of that number is a range, computed in kilobytes, that knows its own margin of error — and is willing to tell you. Go push a few million events through the sandbox and watch a 12-kilobyte array refuse to be impressed by a firehose. Then go put an error bar on something.