Articles

Approximate Distinct Counts in Data Interviews: HyperLogLog, Error, and Mergeability

Prepare for approximate distinct count interviews with HyperLogLog error budgets, tested sketch merges, BigQuery patterns, rolling windows, and recovery rules.

Approximate distinct counts in data interviews test whether you can trade exact membership for compact, mergeable cardinality state. HyperLogLog estimates how many different identities appeared; it does not retain a usable list of those identities. A strong answer defines the identity, error budget, merge compatibility, and correction strategy before proposing a sketch.

This guide uses original examples and a locally tested register demonstration, not a claim that any employer expects one particular implementation.

What does HyperLogLog remember?

In conventional HLL, a hash distributes identities across registers. Part of the hash chooses a register; the remaining bits supply a rank based on the first set bit. Each register retains the largest rank it has seen. Repeated identities produce the same update, so duplicates do not keep increasing the state. An estimator combines the registers into a cardinality estimate. The original paper develops this construction and its accuracy analysis. Flajolet and colleagues: HyperLogLog

The sketch answers “approximately how many distinct values?” It cannot return every user, reconstruct an individual journey, or replace an exact membership lookup. It also does not estimate a percentile simply because both problems involve compact summaries. If the requirement changes from unique visitors to purchase latency, choose a summary appropriate to the new query.

HLL++ is an engineered variant, not merely another name for identical bytes. Google's research describes improvements to the basic algorithm. In an interview, separate the statistical idea from a product's representation, correction rules, and supported operations. HyperLogLog in Practice

Does 0.81% error mean the answer is always that close?

No. The conventional large-cardinality approximation for relative standard error is 1.04 / sqrt(m), where m is the number of registers. It describes statistical dispersion under the model, not a hard bound on each estimate. With 4,096 registers, the formula gives about 1.625%; with 16,384, about 0.8125%. Four times as many registers roughly halves this error scale. Original HLL analysis

For a population near one million, 0.8125% corresponds to roughly 8,125 users on that standard-error scale. It does not promise an absolute error below 8,125. Nor does a repeat run with the same identities and hash configuration produce an independent experiment: deterministic input and state normally reproduce the same estimate.

Redis documents a 0.81% standard error for its implementation. BigQuery documents precision-dependent HLL++ confidence intervals. Neither number should be copied into a guarantee for an unrelated library or mixed-precision pipeline. Redis PFCOUNT and BigQuery sketches

Turn accuracy into a decision. If a dashboard distinguishes broad growth trends, a small relative error may be acceptable. If an alert triggers at 1,000,000 users and the estimate is 999,800, the sketch alone may not resolve which side of the threshold the exact count occupies. Use an uncertainty band or an exact fallback near the boundary, with thresholds chosen for the application rather than invented as a universal HLL rule.

Why daily distinct estimates cannot simply be added

Consider two days: day A has users {u1, u2, u3}, and day B has {u3, u4}. The exact daily counts are three and two, but the two-day union contains four users. Adding even perfectly accurate daily counts gives five. Approximation is not the source of this mistake; lost overlap information is.

Compatible HLL states merge by taking the maximum at each register. This produces the state obtained by processing the union under the same configuration. Merge is associative, commutative, and idempotent at this register-state level: grouping, arrival order, and replaying an identical partial sketch do not change the result.

That does not make the resulting count exact. It preserves the estimator's union input without storing the full set. Keep the mergeable state until the last aggregation stage, then extract a number. Redis's multi-key PFCOUNT, for example, estimates a union rather than summing the individual counts. Redis union counting

A runnable probe for register merge behavior

This Python example is deliberately not a production cardinality estimator. It builds tiny 16-register states using a fixed SHA-256 encoding and demonstrates their merge algebra. There is no bias correction, sparse encoding, serialization contract, or estimate function. Do not compare its memory use or precision with a vendor's implementation.

from hashlib import sha256
from math import sqrt

def registers(values, p=4):
    width = 64 - p
    result = [0] * (1 << p)
    for value in values:
        digest = sha256(value.encode("utf-8")).digest()
        h = int.from_bytes(digest[:8], "big")
        bucket = h >> width
        tail = h & ((1 << width) - 1)
        rank = width - tail.bit_length() + 1
        result[bucket] = max(result[bucket], rank)
    return result

def merge(left, right):
    assert len(left) == len(right)
    return [max(a, b) for a, b in zip(left, right)]

a = ["u1", "u2", "u3", "u3"]
b = ["u3", "u4"]
c = ["u5"]
ra, rb, rc = registers(a), registers(b), registers(c)
assert merge(ra, rb) == registers(a + b)
assert merge(ra, ra) == ra
assert merge(ra, rb) == merge(rb, ra)
assert merge(merge(ra, rb), rc) == merge(ra, merge(rb, rc))
assert registers(a) == registers(list(reversed(a)))
assert registers(a) == registers(sorted(set(a)))
print(len(set(a)), len(set(b)), len(set(a + b)))
print(merge([0, 2, 1, 0], [1, 1, 0, 3]))
print([round(100 * 1.04 / sqrt(m), 4)
       for m in (4096, 16384)])

Executed locally, this prints 3 2 4, the illustrative vector [1, 2, 1, 3], and error percentages [1.625, 0.8125]; all assertions pass. The four-register vectors illustrate maximum-by-position only and are not the hashed states for those user sets.

The probe isolates an important invariant: partitioning and replay do not change compatible register state. It does not prove an implementation's statistical error distribution. A thousand repeats of this one dataset would not supply a meaningful accuracy benchmark.

Store sketches when later queries need a union

In BigQuery, APPROX_COUNT_DISTINCT returns an approximate scalar count; the approximate-aggregate interface does not expose custom precision. It is convenient for a final answer, but saving only that scalar discards the state needed for subsequent union queries. BigQuery approximate aggregate functions

The HLL interface separates stages: INIT creates a sketch, MERGE returns a union estimate, MERGE_PARTIAL retains merged sketch bytes, and EXTRACT estimates one sketch. The following GoogleSQL pattern is documentation-checked, not executed in a cloud project. Its exact reference union is four; do not assume every approximate API must return exactly four. BigQuery HLL++ functions

WITH events AS (
 SELECT DATE '2026-08-01' AS day, 'u1' AS user_id
 UNION ALL SELECT DATE '2026-08-01', 'u2'
 UNION ALL SELECT DATE '2026-08-01', 'u3'
 UNION ALL SELECT DATE '2026-08-01', 'u3'
 UNION ALL SELECT DATE '2026-08-02', 'u3'
 UNION ALL SELECT DATE '2026-08-02', 'u4'
), daily AS (
 SELECT day, HLL_COUNT.INIT(user_id, 15) AS sketch
 FROM events
 GROUP BY day
)
SELECT HLL_COUNT.MERGE(sketch) AS two_day_unique_users
FROM daily;

For a persistent daily table, keep the date, segment keys, identity-definition version, sketch configuration, and completeness watermark alongside the sketch. Otherwise a numerically plausible total can conceal a semantic mismatch between partitions. A missing daily row also needs a status: verified no activity is different from a failed ingestion job.

Which sketches are compatible?

Agree on more than register count. Both producers need the same entity definition, input encoding, hash convention, supported precision conversion, and serialization format. For example, one producer counting account IDs and another counting device IDs cannot form a meaningful user union even if a library accepts their bytes.

BigQuery requires compatible underlying input types; merging string-based and integer-based sketches is an error. Its documented merge behavior downgrades differing precisions to the lowest involved. That is a specific supported conversion, not permission to zip arbitrary arrays from unrelated systems. BigQuery merge requirements

Treat a hash or identity migration as a versioned data migration. Rebuild comparable partitions or maintain separate series until a verified conversion exists. Increasing precision for new days cannot recover information already discarded from old low-precision state. Likewise, changing anonymous-device resolution may change the measured population more than the sketch's statistical error.

How do rolling windows and deletions work?

Ordinary HLL is not invertible: a register maximum does not remember which identities established it or what the runner-up would be after deletion. BigQuery explicitly states that values cannot be deleted from an HLL++ sketch. Subtracting yesterday's extracted estimate from a monthly estimate is not a rolling-distinct algorithm. BigQuery sketch deletion limits

Instead, retain appropriately sized time-bucket sketches. A 30-day query merges exactly the 30 eligible daily buckets. When a day expires, omit it from the next union; do not subtract it from one irreversible all-time sketch. A query starting at noon cannot recover a half-day boundary from daily state alone. Use finer buckets or retained detail for the partial intervals.

Late additive events can update their original bucket under its existing contract. Corrections that remove an identity, change its eligibility, or move it between buckets require rebuilding affected state from authoritative retained data, or another design that preserves enough information. Recompute dependent cached unions too. An idempotent merge protects duplicate delivery, not an incorrect source population.

For exact-window techniques before choosing approximation, see Rolling Distinct Users in SQL. Sketching changes storage and accuracy; it does not settle timezone, late-data, or activity-definition decisions.

Validate accuracy separately from pipeline correctness

Use small deterministic fixtures for empty input, duplicate-heavy streams, full overlap, disjoint partitions, reordered merges, and supported serialization round trips. Compare direct-build state with merged state when the implementation exposes a meaningful state comparison. Test a mismatched configuration explicitly rather than hoping the service rejects it.

Then compare estimates against exact counts across multiple cardinalities and representative identity populations. Record signed relative error, absolute relative error, and behavior near important thresholds. Separate exact reference errors from sketch errors: an exact query with the wrong filter is not ground truth. For a deterministic implementation, vary datasets or supported hash configurations; repeatedly querying one unchanged table adds no independent evidence.

Benchmark scan cost, aggregation memory, merge work, and number of grouped sketches, not just one sketch's size. A compact state per group can still consume substantial memory across millions of groups. If exact counting already meets the latency and resource budget, approximation introduces complexity without a demonstrated benefit.

Practice choosing the right distinct-count design

These questions cover related design decisions, not five interchangeable HLL implementations. The sorted-array prompt deliberately tests an exact alternative; the rolling-average prompt distinguishes daily counts from a window union.

Question	Practice focus
Design a DAU/MAU metrics system	Sketch use.
Design late-tolerant streaming window aggregator	Late events.
Compute DAU and rolling MAU with zero days	Exact baseline.
Compute 7-Day Rolling Average of Unique Post Viewers	Window meaning.
Count Distinct Values in a Huge Sorted Array	Exact choice.

Try Design a DAU/MAU metrics system with three explicit deliverables: a metric contract, a sketch compatibility contract, and a recovery path for corrections. Explain where an exact answer remains necessary before discussing how much memory approximation saves.