COUNT(DISTINCT) Does Not Scale. HyperLogLog Does.

Counting things is easy. Counting distinct things is the one that wakes you up.

A total is a single integer you increment. A distinct count requires knowing whether you have seen each item before, which naively means remembering every item you have ever seen. One billion distinct visitor identifiers at 16 bytes each is roughly 16 GB, before hash table overhead, before doing it per day, and before doing it per page and per country.

The exact answer scales linearly with the thing you are trying to measure. That is the wrong shape, and it is why COUNT(DISTINCT ...) is the query that gets killed.

HyperLogLog estimates the same number in memory that does not grow with cardinality at all. Redis uses 12 KB per counter with a standard error of 0.81%, whether the true count is a thousand or ten billion.

Read that exchange rate again, because it is the most lopsided in everyday infrastructure. Counting a billion distinct items exactly: about 16 GB. Estimating it to within roughly one percent: 12 KB. Over a million times less memory, for an error that is invisible in essentially every use case that asks the question.

Why it works#

The mechanism seems implausible until it clicks, and it rests on one property of random bit patterns.

Hash each item to a uniformly random bit string. In random data, half of all values begin with a zero, a quarter begin with two zeros, an eighth with three. Seeing a value that begins with ten zeros is a one in 1,024 event.

So if you have observed many hashed values and the longest run of leading zeros you have seen is ten, that is evidence you have observed roughly 1,024 distinct values. Not proof. Evidence. And it requires storing exactly one number: the longest run seen so far.

Duplicates handle themselves. The same item hashes to the same value every time, so seeing it a million times contributes precisely what seeing it once contributes. Distinctness comes free from the hash, with no deduplication step anywhere.

That single-register version works on average and has enormous variance, since one lucky hash inflates the estimate and nothing corrects it. The fix is to use the first few bits of each hash to select one of m registers and track the longest run separately in each, giving m independent estimators over disjoint subsets. Combine them with a harmonic mean, which damps outliers far better than an arithmetic mean, and the variance comes down to something predictable. That harmonic mean is the specific contribution HyperLogLog made over its predecessors.

The accuracy is a dial you set once#

Standard error is approximately 1.04 / √m:

Registers	Memory at 6 bits each	Standard error
2,048	1.5 KB	2.30%
16,384	12 KB	0.81%
65,536	48 KB	0.41%

Redis defaults to 16,384 registers, which is where the familiar 12 KB and 0.81% come from.

Two things worth noticing. Quadrupling the memory only halves the error, because it improves with the square root, so pushing accuracy well beyond what the use case needs buys very little. And the table contains no column for cardinality, because there is no relationship: memory is a function of register count alone. Redis documents the structure as able to estimate sets of up to 2^64 members in the same 12 KB.

0.81% is a standard error, not a bound#

This trips people up and it matters when you put a number in front of a stakeholder.

A standard error is a distribution parameter, not a guarantee. Roughly two thirds of estimates land within one standard error of the truth and roughly 95% within two. So at 12 KB, on a true count of ten million:

  within ±0.81%   (~68% of the time)    9,919,000  to  10,081,000
  within ±1.62%   (~95% of the time)    9,838,000  to  10,162,000
  outside that    (~5% of the time)     further out than either

About one estimate in twenty is outside that second band. If you are reporting daily uniques, that is roughly one day a month where the number is further off than your stated accuracy, and nothing in the output distinguishes that day from any other.

For a dashboard this is completely fine. For a number somebody will be held to, it is the detail that turns "accurate to within one percent" into an awkward meeting, and the honest phrasing is "typically within one percent" rather than "within one percent".

The other consequence is that you cannot detect small changes. A genuine 0.5% week on week movement in unique users is well inside the noise. Trend lines over longer windows survive; sensitive week on week comparisons do not, and if someone intends to alert on a small delta then this structure is the wrong input for that alert.

Verify it on your own data before trusting it#

The reassuring thing about this trade is that it is cheap to check, and almost nobody does.

Run both for one period. Keep the exact distinct count the expensive way you already use, add a HyperLogLog alongside it, and compare daily for a couple of weeks. You get an error distribution measured on your real key space and your real hash collisions rather than a figure from a blog post, including this one.

Two things that show up when people do this. Error is relative, so your smallest dimensions have the largest absolute wobble, which is usually where the complaints come from. And if you are counting something with low cardinality in some slices, you will see the sparse to dense encoding transition in the memory profile and can decide the threshold below which you keep using an exact set.

Mergeability is the underrated half#

The property that makes this operationally interesting is not the memory. It is that two HyperLogLogs merge into one over the union by taking the elementwise maximum of their registers.

That merge is exact. Not approximate, not lossy, not accumulating error with each merge. The merged counter is bit for bit the counter you would have built by feeding both datasets into one from the start.

Which turns distributed counting from hard into trivial. Each server keeps a local counter, a coordinator merges them, and no node ever sees another node's items. Per hour counters merge into per day, per day into per month, all from stored counters rather than by reprocessing raw events.

Compare the exact version. Distinct counting across servers means shipping the identifiers themselves or shuffling them by hash, and that shuffle is the expensive part of the distributed problem. HyperLogLog deletes it.

If the "merge by taking the max, order does not matter, merging twice is harmless" shape feels familiar, it should. That is a grow-only CRDT, and the convergence properties are the same ones.

The thing it cannot do#

Unions, yes. Intersections and differences, no.

There is no way to compute the distinct count of items appearing in both of two counters, because the structure retains no information about which items contributed to it. That is the whole point of the structure and it is also the limitation.

You can in principle use inclusion-exclusion with the union estimate:

  |A ∩ B| = |A| + |B| − |A ∪ B|

In practice this is unusable, and it is worth understanding why rather than just being told. Each term carries roughly 0.8% relative error, but the errors are relative to the inputs, not to the answer. If A and B each have 100 million members and their intersection is 1 million, your error terms are on the order of 800,000 each while the quantity you are estimating is 1,000,000. The error can comfortably exceed the answer, and it can go negative.

The failure here is not that the estimate is slightly off. It is that the estimate is meaningless and does not announce itself as meaningless. If you need intersections, HyperLogLog is the wrong tool, and no amount of increasing register count rescues it.

The same reasoning applies to drill-down. A counter tells you there were 4.2 million distinct users. It can never tell you which users, or let you filter to a subset after the fact. Any dimension you might want to slice by has to be decided in advance and given its own counter. That is cheap, at 12 KB each, but it is a design decision made before the data arrives rather than a question you can ask afterwards.

You probably already have it#

This is not exotic infrastructure you need to adopt. It is sitting in things you run:

  Redis             PFADD, PFCOUNT, PFMERGE
  ClickHouse        uniqCombined, uniqHLL12
  Presto / Trino    approx_distinct
  BigQuery          APPROX_COUNT_DISTINCT
  Postgres          via the postgresql-hll extension

In Redis the API deliberately mirrors sets, so the migration from the exact version is close to mechanical:

> PFADD bikes Hyperion Deimos Phoebe Quaoar
(integer) 1
> PFCOUNT bikes
(integer) 4
> PFADD commuter_bikes Salacia Mimas Quaoar
(integer) 1
> PFMERGE all_bikes bikes commuter_bikes
OK
> PFCOUNT all_bikes
(integer) 6

PFADD and PFCOUNT are O(1); PFMERGE is O(n) in the number of sketches being merged. Redis encodes the structure as a string, so GET and SET serialise and restore it, which makes shipping counters between systems unremarkable.

When to reach for it, and when not to#

Use it when	Because
Unique visitors, viewers, players per period	Nobody acts differently on 4.21M versus 4.23M
Distinct counts across many dimensions	12 KB per counter makes breadth affordable
Counting across servers or time buckets	Merge is exact and needs no shuffle
The exact query already gets killed	An approximate answer beats no answer

Avoid it when	Because
The number is billed, audited or reported	Approximate is not a defensible basis
You need the intersection of two sets	Inclusion-exclusion error can exceed the answer
You need to know which items	The structure keeps no membership information
Cardinality is small	A plain set is exact, simpler and smaller

That last row matters more than it looks. At a few thousand distinct items a SET is exact and costs less than 12 KB, so the probabilistic structure is pure overhead. The threshold where it starts paying is higher than people assume, and good implementations know this: they use a sparse encoding at low cardinality and only switch to the dense register array once it is actually cheaper.

The general lesson#

The useful question when you hit a scaling wall is not "how do I make this computation faster" but "what precision am I actually buying, and am I using it?"

A distinct count feeding a dashboard, a capacity model, or a trend line is consumed by a human who reads it to one or two significant figures. Paying 16 GB and a query timeout to produce digits nobody reads is a straightforward bad trade, and it is a very common one, because exactness is the default and nobody is asked to justify it.

Probabilistic structures are what you get when someone asks.

---

Related reading: Prometheus Cardinality Explosion for what happens when you store every distinct combination instead of estimating it, and Self-Hosting Langfuse on Kubernetes for cardinality as a capacity constraint in a trace store. Bloom and Cuckoo filters, Count-Min Sketch, MinHash, skip lists and Merkle trees, alongside the architectural patterns they support, are Architecture and Scale.