How does APPROX_COUNT_DISTINCT differ from COUNT(DISTINCT) in an analytical engine?
answer
- one returns an estimate, the other the truth
- memory grows with distinct values, not rows
- a fixed-size summary replaces the full value set
- hashing plus registers instead of a hash table
- typical error is a low single-digit percentage
basics
~20 sAPPROX_COUNT_DISTINCT returns an estimated number of distinct values computed from a small fixed-size sketch, rather than the exact number computed by tracking every value seen. It uses far less memory and time, at a few percent typical error.
solid answer
~50 s`COUNT(DISTINCT col)` has to remember every distinct value it has seen, so its memory grows with the cardinality of the column and, in a distributed engine, all copies of a value must be brought together before they can be deduplicated. `APPROX_COUNT_DISTINCT` (most analytical engines expose it under that name or a close variant) instead hashes each value into a small fixed-size probabilistic sketch — usually HyperLogLog — and estimates the cardinality from the shape of that sketch. The sketch is a few kilobytes regardless of whether the column holds a thousand or a billion distinct values, so the query needs no large hash table and no reshuffling of the data. The price is that the answer is an estimate, typically within a low single-digit percentage of the truth. Use it for dashboards, trends and exploration; use the exact function when the number is billed, audited or reconciled.
code
sql · 9 lines-- exact: memory grows with the number of distinct user_ids
SELECT event_date, COUNT(DISTINCT user_id) AS dau
FROM events
GROUP BY event_date;
-- approximate: fixed-size sketch per group, a few percent error
SELECT event_date, APPROX_COUNT_DISTINCT(user_id) AS dau_est
FROM events
GROUP BY event_date;go deeper
Be ready to say plainly that one function is exact and the other is an estimate from a compact sketch, and that the estimate is normally within a few percent. Naming HyperLogLog as the usual mechanism is a bonus.
Explain why the exact version is expensive — it must remember every distinct value, so memory tracks cardinality — and why the sketch is a fixed size no matter how many distinct values arrive.
Show judgment about which reported metrics may be approximate. Interviewers want to hear you separate indicator numbers from billed or audited numbers, and hear you name the consistency oddities estimates introduce.
Own this as a platform policy rather than a per-query choice: which metrics in the semantic layer are declared approximate, how the error bound is published to consumers, and why a metric must never silently switch implementations.
## The two functions side by side `COUNT(DISTINCT user_id)` is defined to return the exact number of different non-null values in the column. To honour that definition, an engine must be able to answer "have I seen this value already?" for every row, which means it must keep the set of values it has already seen. The natural implementation is a hash table keyed by the value. Its size is driven by the **cardinality** of the column — the number of distinct values — not by the number of rows. Ten billion rows over fifty distinct countries costs almost nothing; ten billion rows over five hundred million user ids costs a large hash table. `APPROX_COUNT_DISTINCT(user_id)` answers a deliberately weaker question: roughly how many distinct values are there? It replaces the exact set with a **sketch** — a small, fixed-size summary that supports the operation you actually need (an estimate of cardinality) while throwing away the ability to answer membership. The near-universal choice is HyperLogLog. ## What the sketch actually stores HyperLogLog hashes each input value to a uniformly distributed bit string. A fixed number of leading bits selects one of `m` registers; the remainder is inspected for its run of leading zeros, and the register keeps the maximum run length it has ever seen. A long run of zeros is rare, so seeing one is evidence that many distinct values were hashed. Averaging that evidence across all `m` registers (with a harmonic mean and a bias correction) yields the estimate. Two consequences follow directly from this design. First, the state is **fixed size**: `m` small registers, typically a few to a few tens of kilobytes, no matter how many distinct values arrive. Second, feeding the same value in twice changes nothing, because the register only ever takes a maximum — the sketch is naturally idempotent, which is exactly what deduplication needs. ## The cost difference in practice In a single-node engine the difference shows up as memory: the exact hash table for hundreds of millions of ids can exceed the operator's memory budget and spill to disk, turning a scan-bound query into an I/O-bound one. In a distributed engine the difference is larger still, because exactness forces data movement — every occurrence of a given value has to reach the same worker before duplicates can be collapsed. The approximate version builds one small sketch per worker locally, and the workers exchange only the sketches. ## The accuracy you can expect HyperLogLog's relative standard error is about `1.04 / sqrt(m)`. With 16384 registers that is roughly 0.8%: on a true value of 50,000,000 you would typically land within a few hundred thousand, and occasionally further. Most engines expose a precision or accuracy parameter that increases `m` — the error shrinks with the square root of the sketch size, so halving the error costs four times the memory. Note that this is a *relative* error: the absolute miss grows with the number you are estimating. Many implementations also switch to an exact or sparse representation at low cardinality, so small groups often come back exactly right. That is an implementation convenience, not a guarantee you should build on. ## Where it belongs and where it does not Approximate distinct counts are right whenever the decision the number feeds is insensitive to a percent or two: daily and monthly active users on a trend chart, unique visitors per page, distinct error codes in a monitoring view, cardinality checks while exploring a new dataset, funnel steps. They are wrong whenever the number is the product rather than an indicator: anything invoiced, anything reported to a regulator, anything reconciled against an upstream system of record, and any threshold decision where the boundary sits inside the error band. One subtle trap: because each estimate carries its own independent error, two separately estimated results need not be consistent with each other. A filtered subset can come back with a slightly larger estimate than the unfiltered table, which looks like a data bug and is not. ## The rest of the family The same trade appears for other aggregates that are expensive because they need to remember detail. Approximate percentile functions replace a full sort with a quantile summary. Approximate top-K functions replace a full frequency table with a heavy-hitters sketch. In every case the question to ask is the same one: is this number a decision input where a small, bounded error is invisible, or is it the answer itself?
- Does the approximate function get slower as the number of distinct values grows?Barely. The per-row work is a hash plus a register update regardless of cardinality, and the sketch stays the same size, so runtime tracks the number of rows scanned rather than the number of distinct values. The exact version is the one that degrades with cardinality, because its hash table grows and eventually spills.
- If a group only has a few hundred distinct values, is the approximate function still worth using?Not really — at low cardinality the exact count is cheap, and many implementations fall back to an exact or sparse representation anyway, so you gain nothing and give up a guarantee. The approximation earns its keep at high cardinality: millions or billions of distinct values, especially when many groups are computed at once.
- Can you make the approximate answer more accurate?Yes, by raising the precision or accuracy parameter, which increases the number of registers in the sketch. Error falls with the square root of the register count, so cutting the error in half costs roughly four times the sketch memory. Beyond a point, computing exactly is cheaper than chasing accuracy.
Counting distinct values exactly is like keeping a guest list at the door; the approximate version is like glancing at the crowd and estimating attendance — far cheaper, close enough to plan for, useless for billing each guest.
saying these in an interview costs you the question
- Claims the approximate function samples rows instead of hashing all of them
- Says the error is unbounded or unpredictable rather than a known relative error
- Thinks approximate memory grows with the number of distinct values
- Uses the approximate count for invoiced or audited numbers
- Believes the two functions differ only in speed, not in the answer