An exact distinct count per group holds every identifier seen — what does a bounded-size summary change, and what must you agree first?
answer
- constant size instead of every value
- summaries merge like accumulators
- the answer is within a stated error
- never for a billed or audited number
basics
~20 sA fixed-size summary answers distinct-count, quantile or heavy-hitter questions within a stated error and merges the way an accumulator does, so a group costs a constant instead of one entry per distinct value. The price is an error budget somebody must accept.
solid answer
~50 sAn exact distinct count is not foldable in the sense that saves memory: the carried value is a set of identifiers, and it grows with distinct values, so a group's cost tracks its cardinality. A **bounded-size summary** replaces that set with a fixed-size structure that answers the same shape of question within a stated error, and — critically — two of them merge into one summary of both inputs, which is what makes it usable as a per-group accumulator at all. The swap is not a pure win, and the agreement is the interview answer: who accepts that a recount may differ, whether any threshold or alert sits inside the error band, whether the figure is ever reconciled against an exact number, and whether every producer builds its summaries the same way so they can still be merged.
go deeper
Know that some questions can be answered approximately from a fixed-size summary, instead of keeping every value the group has seen.
Explain the mechanism: a constant-size structure that combines the way an accumulator does and answers within a stated error, in exchange for never being exact.
Run the agreement before the swap: who accepts the error, whether any threshold sits inside the error band, and whether anyone will ever reconcile the number against an exact recount.
Set the policy for which figures may be estimates and which may not, and make the error budget a published property of the number rather than a hidden implementation choice.
## What exactness costs on this axis For most aggregates, an open group costs one small carried value. For three families it does not: an exact distinct count must keep the identifiers to recognise a repeat, an exact quantile must keep the values because the middle of a set depends on records not yet seen, and an exact ranking by frequency must keep a count per distinct key. In each case the group's footprint grows with the data's cardinality, and the memory product — what one open group holds times how many are open — becomes unbounded in a factor the author does not control. ## What a bounded-size summary is A **bounded-size summary** is a fixed-size structure built by folding records into it, which answers a cardinality, quantile or membership question within a stated error instead of keeping every record. Its footprint is chosen when the summary is configured, not by the data: a summary of a thousand distinct values and a summary of a billion occupy the same space. The published algorithms behind these have names worth recognising — HyperLogLog for distinct counts, Count-Min Sketch for heavy hitters, t-digest for quantiles, Bloom filter for membership — but the mechanism is what you are being asked about, and the functions a query language exposes them through belong to a different subject. | Question | Exact carried value | Summary carried value | What the error means | |---|---|---|---| | how many distinct | every distinct identifier | fixed-size structure | the count is off by a small relative amount | | which are the heavy ones | a count per identifier | fixed-size counter array | a count may be overstated, rarely understated | | the ninety-fifth percentile | every value | fixed-size ordered summary | the reported value is near the true one | | has this been seen before | every identifier | fixed-size bit structure | a "yes" may be wrong, a "no" is not | ## What the summary gives back: mergeability at constant size The property that makes a summary usable per group is that two of them combine into a summary of both inputs, and the combined one is the same size. That is exactly the accumulator contract, which is why a summary slots into a grouping where an exact set could not: the group costs one constant-size value, partial results from different workers combine, and a longer boundary costs nothing more in memory than a short one. ## What must be agreed before you swap This is the part interviewers are actually probing, because the engineering is easy and the commitment is not: 1. **Who owns the error budget.** Somebody must state the tolerated error and accept that recounting the same input can produce a different number. If the answer is "nobody has been asked", the swap is not ready. 2. **Whether any threshold sits inside the error band.** An alert at a broad threshold tolerates a small relative error. An alert that fires at exactly one hundred distinct sources does not, because the error is comparable to the decision. 3. **Whether the figure is ever reconciled.** A number that somebody will compare against an exact recount, an invoice or an audit must be exact. Estimates and exact figures should not sit in the same column of the same report. 4. **Whether every producer builds summaries the same way.** Combining generally requires matching configuration. Summaries built at different precisions cannot simply be merged, and their error claims do not add in any convenient way. ## Where it is the wrong trade - **Billed or audited quantities.** A charge per distinct active account must reconcile exactly, and an error band is not a defensible answer to a customer. - **Small groups.** Where a group holds a handful of distinct values, the exact set is smaller than the summary and exactness is free. - **Questions the summary cannot answer.** A summary that estimates cardinality cannot list the identifiers, so any downstream need to enumerate rather than count kills the swap. - **Comparisons at the resolution of the error.** Two estimates that differ by less than the error band have not been shown to differ at all, and a dashboard showing that difference as a trend is misleading. ## Where engines of this class differ Whether a summary is available to you as a built-in per-group value, or has to be carried as your own accumulator with your own combine step, varies across runtimes in this family — as does whether a declarative expression is recognised and compiled into one. Do not assume the presence of a built-in: the concept travels, the availability does not. What does travel is the reasoning — the exact answer costs one entry per distinct value, the summary costs a constant, and the difference is paid in an error that somebody has to sign for.
- If the group must also report an exact total, does the summary still help?Yes, and both are carried side by side. The total folds exactly into one number, while the approximate part is carried in the fixed-size summary. The group's cost stays constant, and only the distinct-count column carries an error band — which should be labelled as such wherever it is read.
- Two teams built summaries with different sizes or settings. What happens when you merge them?Generally you cannot, because combining requires matching configuration. The usual remedies are to rebuild the finer-grained side, or to reduce both to the coarser configuration where the algorithm supports it. The error claims of the result are not simply the sum of the two inputs' claims, so restate the budget after any such downgrade.
saying these in an interview costs you the question
- Claims an approximate count converges to the exact answer given enough records.
- Assumes the stated error is a hard cap every group is guaranteed to meet.
- Uses an approximate count for a billed or audited figure.
- Thinks the summary still holds the identifiers and could list them.
- Believes summaries from different configurations can always be merged.