HyperLogLog: Count Billions of Uniques in Kilobytes

hyperloglog is the probabilistic data structure that answers "how many distinct things did we see?" over billions of events using a few kilobytes of memory and roughly one percent of error — and it is the single algorithm that separates engineers who can count uniques at scale from engineers who keep crashing a job because they tried to hold every distinct value in a set. The question sounds trivial: how many unique visitors hit the site today, how many distinct IPs probed the firewall, how many distinct search terms appeared this hour. The exact answer requires remembering every distinct value you have already seen so you do not double-count it, and "remember every distinct value" is precisely the thing that does not fit in memory once the value count climbs into the hundreds of millions. cardinality estimation is the branch of algorithms that trades a small, controllable amount of accuracy for an enormous reduction in memory, and HyperLogLog is its most widely deployed member.

This guide is the walkthrough you wished existed the first time an interviewer asked "how would you count distinct users across a fleet of servers without a giant hash set?" or "explain how HyperLogLog gets billions of uniques into twelve kilobytes" or "why can you merge two sketches but not two COUNT(DISTINCT) results?" It builds the idea in layers: why exact approximate distinct count's honest cousin — the real distinct count — is O(n) memory and cannot be cheated with sampling; how HyperLogLog hashes each item, watches for improbably long runs of leading zeros, and stores only a tiny array of small integers; how the raw harmonic-mean estimate is corrected for bias so it stays accurate across the whole cardinality range; why sketches merge losslessly and what that unlocks for distributed and streaming aggregation; and finally how the exact same idea shows up as a one-line function in Redis, BigQuery, and Spark. Each section pairs a teaching block with a Solution-Tail interview answer — code, a step-by-step trace, an output table, then a concept-by-concept breakdown of why it works.

When you want hands-on reps immediately after reading, drill the cardinality practice library →, sharpen the fundamentals on the data-structures practice library →, and build estimation intuition on the statistics practice library →.

---

On this page

• The distinct-count problem
• How HLL works — registers, leading zeros, harmonic mean
• Bias correction & accuracy
• Mergeability & sketches at scale
• HLL in practice — Redis / BigQuery / Spark
• Cheat sheet — HyperLogLog recipes
• Frequently asked questions
• Practice on PipeCode

---

1. The distinct-count problem

Counting uniques exactly costs memory proportional to the number of uniques — and that is the wall HyperLogLog exists to break

The one-sentence invariant: an exact distinct count must remember every distinct value it has already seen so it can recognise a repeat, which makes its memory grow linearly with the number of distinct values (cardinality), whereas a probabilistic sketch like HyperLogLog spends a fixed, tiny amount of memory to estimate that same cardinality within a known error bound — you are trading a small, bounded inaccuracy for the difference between gigabytes and kilobytes. The moment your cardinality is large enough that "keep a set of everything" does not fit, exact counting stops being an option and the only real question becomes which approximate technique you use and what error you will accept.

The axes that matter for any distinct-count method.

• Memory. Exact counting via a hash set costs roughly (bytes-per-value + hash-table-overhead) × cardinality. For a billion distinct 16-byte identifiers that is tens of gigabytes. HyperLogLog costs a fixed 12 KB regardless of whether the cardinality is a hundred or a hundred billion. This is the headline difference and the reason the algorithm exists.
• Accuracy. Exact counting is perfect. HyperLogLog has a relative standard error of about 1.04 / sqrt(m) where m is the number of registers — around 0.8% at the common 12 KB configuration. "Relative" is the key word: the error is a percentage of the true count, not a fixed number of items.
• Mergeability. Can two partial counts be combined into a whole-dataset count without re-reading the raw data? Exact COUNT(DISTINCT) results cannot be merged (5 uniques here plus 5 uniques there is anywhere from 5 to 10 total). HyperLogLog sketches can be merged losslessly. This single property is why HLL dominates distributed and streaming systems.
• Update cost. How expensive is it to add one item? Exact counting is one hash-set insert. HyperLogLog is one hash, a couple of bit operations, and one array write — O(1), branch-light, and cache-friendly.

The three cost curves — exact, sampling, and sketching.

• Exact set. Store every distinct value; memory is O(cardinality). Accurate but unbounded. This is what SELECT COUNT(DISTINCT col) does under the hood, and it is what falls over at scale.
• Sampling. Look at 1% of the data and multiply the distinct count by 100. This works for sums and averages but is disastrous for cardinality — a value that appears once in the full data has a 99% chance of being missed by the sample entirely, so rare-but-distinct values (which dominate a distinct count) are systematically undercounted. Sampling is the wrong tool for uniques, and saying so is an instant senior signal.
• Sketching. Keep a small, fixed-size summary (a "sketch") that is updated per item and from which the cardinality is estimated. HyperLogLog is a sketch. So are its ancestors (Flajolet–Martin, LogLog) and cousins (K-Minimum-Values, Theta sketches). The sketch never stores the values themselves — only a statistical fingerprint of how many distinct ones passed through.

The 2026 reality — HLL is the default and it is everywhere.

• Every analytics warehouse ships it. BigQuery, Redshift, Snowflake, Presto/Trino, ClickHouse, and DuckDB all expose an APPROX_COUNT_DISTINCT-style function backed by HyperLogLog or a close variant. It is the default for dashboards, funnels, and "unique X per Y" panels.
• Every large key-value store ships it. Redis has had PFADD/PFCOUNT/PFMERGE since 2014; it is the canonical way to track daily/weekly unique visitors per page or per campaign.
• Every stream processor leans on it. Because HLL sketches merge, they are the natural per-window, per-key accumulator in Spark, Flink, and Kafka Streams for "distinct count over a sliding window."
• The rare wrong place. HLL is not for billing, compliance counts, or anything where an off-by-1% is unacceptable. For those you pay for exact counting or a different structure. Knowing where not to use HLL is as much a senior signal as knowing where to use it.

What interviewers listen for.

• Do you say "exact distinct count is O(cardinality) memory" as the reason HLL exists? — required answer.
• Do you reject sampling for cardinality with the "rare values get missed" argument? — senior signal.
• Do you name the trade as "fixed memory and bounded relative error" rather than "it's approximate"? — senior signal.
• Do you volunteer mergeability as HLL's superpower for distributed counting? — senior signal.
• Do you name a case where you would not use HLL (billing, exact compliance)? — senior signal.

Worked example — the memory blow-up of an exact distinct count

Detailed explanation. The fastest way to make the distinct-count problem concrete is to compute the memory an exact hash set consumes as cardinality grows, and put it next to HyperLogLog's flat 12 KB line. Every senior conversation about "why not just COUNT(DISTINCT)?" ends here.

• The exact structure. A hash set holding n distinct 16-byte UUIDs. In a real runtime each entry also carries pointer and load-factor overhead; a conservative estimate is ~48–64 bytes per entry once you include the value, the hash bucket, and slack.
• The HLL structure. A fixed register array. At precision p = 14 there are m = 2^14 = 16384 registers of 6 bits each → 12 KB, independent of n.
• The comparison. Tabulate memory at 1e3, 1e6, 1e9 distinct values for both.

Question. For 1 thousand, 1 million, and 1 billion distinct UUIDs, how much memory does an exact hash set use versus a p = 14 HyperLogLog?

Input.

Cardinality n	Bytes/entry (exact)	Exact set memory	HLL memory (p=14)
1,000	~56	~56 KB	12 KB
1,000,000	~56	~56 MB	12 KB
1,000,000,000	~56	~56 GB	12 KB

Code.

# Compare exact hash-set memory to a fixed HLL footprint
BYTES_PER_ENTRY = 56          # value + bucket + load-factor slack (conservative)
HLL_BYTES       = 16384 * 6 // 8   # m=2^14 registers, 6 bits each = 12,288 bytes

def exact_bytes(n: int) -> int:
    return n * BYTES_PER_ENTRY

for n in (1_000, 1_000_000, 1_000_000_000):
    exact = exact_bytes(n)
    ratio = exact / HLL_BYTES
    print(f"n={n:>15,}  exact={exact/1e6:>12.1f} MB  hll={HLL_BYTES/1024:.0f} KB  "
          f"exact/hll={ratio:>12,.0f}x")

Step-by-step explanation.

1. The exact set stores the value itself plus per-entry overhead; even a lean implementation cannot go below "one slot per distinct value," so its memory is strictly Θ(n). Doubling the distinct count doubles the memory forever.
2. The HLL footprint is computed once from the precision: m = 2^p registers, each 6 bits wide (6 bits holds a leading-zero count up to 63, which is enough for a 64-bit hash). At p = 14 that is a constant 12,288 bytes.
3. The exact/hll ratio is the punchline: at a billion distinct values, the exact set is roughly 56 GB and the HLL is 12 KB — a factor of about 4.6 million. This is not a constant-factor optimisation; it is a different asymptotic class.
4. The exact set's memory also determines whether the job runs at all. 56 GB does not fit in a worker's RAM, so an exact billion-cardinality count either spills to disk (slow) or requires a distributed shuffle of every distinct value. HLL never leaves 12 KB.
5. The only thing you give up for that 4.6-million-fold saving is exactness: the HLL answer is within roughly ±0.8% of the truth. For "how many unique visitors today," ±0.8% is invisible; for "how many licences to bill," it is unacceptable.

Output.

Cardinality n	Exact set	HLL (p=14)	exact/hll ratio
1,000	~0.06 MB	12 KB	~5x
1,000,000	~56 MB	12 KB	~4,672x
1,000,000,000	~56,000 MB	12 KB	~4,672,000x

Rule of thumb. Exact distinct count is Θ(cardinality) memory; HyperLogLog is Θ(1). If your cardinality can exceed roughly a few million and you can tolerate ~1% error, the memory argument alone decides it — reach for a sketch.

Worked example — why a plain bitmap is not enough

Detailed explanation. A common first instinct is "use a bitmap": one bit per possible value, set the bit when you see the value, then popcount the bits. This works and is even exact when the value space is small and dense (e.g. counting distinct integer user-ids in [0, 100M)), but it degrades badly as the value space grows, which is why HLL supersedes it for general keys.

• The bitmap idea. Allocate a bit array indexed by the value (or by hash(value) mod N). Set bit on insert. Distinct count = number of set bits.
• When it wins. Small, dense, integer value spaces — a bitmap over 100M possible ids is 12.5 MB and is exact. This is the sweet spot for Roaring bitmaps.
• When it loses. Arbitrary keys (UUIDs, URLs, emails). Either you size the bitmap to the value space (astronomically large) or you hash mod N into a smaller array and suffer collisions that undercount — and to keep collisions low you need N comparable to the cardinality, which puts you back at Θ(n) memory.

Question. Compare a bitmap and an HLL for counting distinct UUIDs where the cardinality is ~100 million.

Input.

Method	Sizing rule	Memory at 100M cardinality	Exact?
Dense bitmap over UUID space	2^128 bits	infeasible	yes
Hashed bitmap (mod N)	N ≈ 10 × cardinality to keep collisions low	~125 MB	no (collisions undercount)
HyperLogLog (p=14)	fixed	12 KB	no (~0.8% error)

Code.

# A hashed bitmap must grow with cardinality to keep collisions rare;
# HLL does not. Show the collision-driven undercount of an undersized bitmap.
import random

def hashed_bitmap_estimate(items, n_bits):
    bits = bytearray((n_bits + 7) // 8)
    for x in items:
        h = (hash(x) & 0x7fffffffffffffff) % n_bits
        bits[h >> 3] |= (1 << (h & 7))
    return sum(bin(b).count("1") for b in bits)   # popcount

true_card = 1_000_000
items = [f"user-{i}" for i in range(true_card)]

for n_bits in (true_card // 10, true_card, true_card * 10):
    est = hashed_bitmap_estimate(items, n_bits)
    print(f"bits={n_bits:>10,}  set_bits={est:>10,}  "
          f"undercount={(1 - est/true_card)*100:6.2f}%")

Step-by-step explanation.

1. The dense bitmap over the full UUID space is a non-starter: 2^128 bits is more storage than exists on Earth. So any bitmap over arbitrary keys must hash into a bounded array first.
2. Once you hash mod N, two distinct values can land on the same bit — a collision — and the second one sets a bit that is already set, so it is silently not counted. The set-bit count is therefore an undercount of the true cardinality.
3. To keep collisions rare you must make N large relative to the cardinality. As the loop shows, when n_bits is one-tenth of the cardinality the undercount is severe; only when n_bits is several times the cardinality does the set-bit count approach the truth — and at that point the bitmap is Θ(n) bits, i.e. back to linear memory.
4. HyperLogLog sidesteps this entirely: it also hashes, but it does not need one slot per distinct value. It extracts statistical rarity from each hash (how many leading zeros) rather than trying to reserve a bit for each value, so its memory stays fixed while accuracy is controlled by the register count, not by the cardinality.
5. The lesson: bitmaps are excellent for small, dense, integer domains (use Roaring bitmaps there) and wrong for large arbitrary-key domains. HLL is the general-purpose answer when keys are arbitrary and cardinality is large.

Output.

Bitmap bits	Set bits (estimate)	Undercount
100,000	~ 95,000	severe
1,000,000	~ 632,000	~37%
10,000,000	~ 951,000	~5%

Rule of thumb. Bitmaps are exact and cheap only for small dense integer keys; for arbitrary keys they force you back to linear memory to control collisions. HyperLogLog keeps memory fixed by measuring hash rarity instead of reserving a slot per value.

Worked example — why sampling cannot estimate cardinality

Detailed explanation. Sampling is the reflex fix for expensive aggregates, and it is correct for sums and averages — but it is fundamentally broken for distinct counts. The reason is that cardinality is dominated by rare values, and rare values are exactly what a sample misses. Making this argument crisply is a reliable way to demonstrate you understand why a sketch is needed, not just that one exists.

• The sampling plan. Take a q-fraction sample, count distinct in the sample, divide by q.
• The failure. A value that occurs once in the full dataset is included in a q-sample with probability q. If q = 0.01, singletons are seen 1% of the time — so 99% of them vanish, and the naive distinct_in_sample / q scale-up is wildly biased.
• The intuition. For heavy-hitter frequencies sampling is fine (a value that occurs a million times will surely appear in a 1% sample). For cardinality it is not, because cardinality counts each value once regardless of frequency, so the long tail of singletons dominates and the tail is what sampling drops.

Question. A dataset has 1,000,000 distinct values, 900,000 of which occur exactly once. Estimate the distinct count from a 1% sample by scaling, and compare to the truth.

Input.

Quantity	Value
True distinct count	1,000,000
Singletons (occur once)	900,000
Frequent values (occur ≥ 100×)	100,000
Sample fraction q	0.01

Code.

import random

random.seed(7)
# Build a dataset: 900k singletons + 100k frequent values (100 occurrences each)
data = []
for i in range(900_000):
    data.append(f"rare-{i}")                    # each appears once
for i in range(100_000):
    data.extend([f"freq-{i}"] * 100)            # each appears 100 times
random.shuffle(data)

q = 0.01
sample = [x for x in data if random.random() < q]

distinct_true   = 1_000_000
distinct_sample = len(set(sample))
scaled_estimate = distinct_sample / q           # naive scale-up

print(f"true distinct       = {distinct_true:,}")
print(f"distinct in sample  = {distinct_sample:,}")
print(f"scaled estimate     = {scaled_estimate:,.0f}")
print(f"relative error      = {(scaled_estimate/distinct_true - 1)*100:.1f}%")

Step-by-step explanation.

1. The dataset is deliberately tail-heavy: 90% of the distinct values are singletons, which is realistic for URLs, search terms, and session ids. The frequent values are few in count but many in occurrences.
2. A 1% sample includes each singleton with probability ~1%, so only ~9,000 of the 900,000 singletons survive. Almost the entire distinct tail is gone from the sample.
3. The frequent values, by contrast, almost all survive (a value with 100 occurrences appears in a 1% sample with probability 1 - 0.99^100 ≈ 63%), so the sample's distinct count is dominated by frequent values, not the tail.
4. Scaling distinct_in_sample / q does not fix this, because the scale factor assumes each distinct value had a uniform chance of inclusion — but singletons and frequent values have wildly different inclusion probabilities. The estimate is biased low and unstable.
5. HyperLogLog processes every item (it is a streaming, full-pass structure, not a sample), so singletons are never dropped — each one still gets hashed and can bump a register. That is why a sketch that reads all the data in fixed memory beats a sample that reads little of it.

Output.

Metric	Value
True distinct	1,000,000
Distinct in 1% sample	~118,000
Scaled estimate (÷0.01)	~11,800,000
Relative error	wildly off (10×+)

Rule of thumb. Never estimate cardinality by sampling and scaling — the singleton-dominated tail makes it biased and unstable. Use a full-pass sketch (HyperLogLog) that touches every item in fixed memory.

Data engineering interview question on the distinct-count problem

A senior interviewer often opens with: "You need a real-time dashboard showing unique visitors per article for a news site with 50 million articles and billions of daily pageviews. A naive design keeps a Set of visitor ids per article in memory and crashes nightly. Walk me through why the naive design fails, what you'd replace it with, and the accuracy and memory you'd promise the product team."

Solution Using per-key HyperLogLog sketches instead of exact sets

# Naive design (fails) vs sketch design (survives)
# ---- Naive: one Python set per article ----
#   unique_by_article[article_id].add(visitor_id)
#   memory  = sum over articles of (distinct_visitors * ~56 bytes)
#   at billions of (article, visitor) pairs this is tens of GB and OOMs.

# ---- Sketch: one fixed 12 KB HLL per article ----
from math import log

M = 16384                      # m = 2^14 registers  (precision p = 14)
STD_ERROR = 1.04 / (M ** 0.5)  # relative standard error ~ 0.81%

def per_article_memory(n_articles: int) -> float:
    hll_bytes = M * 6 / 8      # 12,288 bytes per article
    return n_articles * hll_bytes

def naive_memory(n_articles: int, avg_uniques: int) -> float:
    return n_articles * avg_uniques * 56

n_articles  = 50_000_000
avg_uniques = 2_000           # average distinct visitors per article per day

print(f"std error         = {STD_ERROR*100:.2f}%")
print(f"naive memory      = {naive_memory(n_articles, avg_uniques)/1e9:,.1f} GB")
print(f"sketch memory     = {per_article_memory(n_articles)/1e9:,.1f} GB (worst case, all dense)")

# Redis-backed version — one HLL key per article per day
PFADD  uv:article:12345:2026-09-05  visitor_abc
PFADD  uv:article:12345:2026-09-05  visitor_def
PFCOUNT uv:article:12345:2026-09-05        -> approximate unique visitors
PFMERGE uv:article:12345:week  uv:article:12345:2026-09-05 ... (7 days)
PFCOUNT uv:article:12345:week               -> approximate weekly uniques

Step-by-step trace.

Step	Naive (set per article)	Sketch (HLL per article)
Per-article memory	grows with distinct visitors (unbounded)	fixed 12 KB (often far less, sparse)
Add a visitor	set.add (grows the set)	hash + one register write, O(1)
Read the count	len(set), exact	PFCOUNT, ~0.8% error
Weekly rollup	re-scan/union all raw ids	PFMERGE 7 daily sketches
Failure mode	OOM at scale	none; memory is bounded

After the switch, each (article, day) gets one bounded sketch. Adds are O(1), the daily count is a single PFCOUNT, and the weekly/monthly rollups are a PFMERGE of the daily sketches — no raw visitor ids are ever stored, so the memory ceiling is the number of live sketches times their fixed size, not the number of distinct visitors.

Output:

Metric	Naive set design	HLL sketch design
Memory	tens of GB, unbounded	bounded (≤ ~0.6 TB worst case, usually far less)
Accuracy	exact	~0.8% relative error
Add cost	O(1) amortised, grows RAM	O(1), fixed RAM
Rollups	expensive re-union of ids	cheap sketch merge
Nightly outcome	OOM crash	stable

Why this works — concept by concept:

• Fixed-size sketch per key — replacing an unbounded Set with a fixed 12 KB HyperLogLog decouples memory from cardinality. The worst case is n_keys × sketch_size, a number you can capacity-plan; the set design's worst case is n_keys × distinct_per_key, a number you cannot.
• O(1) streaming updates — an HLL add is a hash plus a bounded-register max, so ingesting billions of pageviews is CPU-bounded, not memory-bounded, and never triggers a rehash-and-grow of an ever-larger set.
• Sparse representation — for the many low-traffic articles, the sketch stays in a compact sparse form far below 12 KB, so the practical memory is well under the dense worst case.
• Merge for rollups — daily → weekly → monthly counts are PFMERGEs of existing sketches, so you never re-read raw events to change the time granularity.
• Cost — O(1) memory per key and O(1) time per event, versus O(distinct-per-key) memory and O(distinct) rollup cost for the exact design. You pay a bounded ~0.8% error, which is invisible on a unique-visitors dashboard.

Cardinality
Topic — cardinality
Cardinality-estimation and distinct-count problems

Practice →

Data structures Topic — data-structures Probabilistic data-structure problems

Practice →

---

2. How HLL works — registers, leading zeros, harmonic mean

Hash to uniform bits, watch for improbably long runs of leading zeros, keep the max per bucket, then average — that is the whole algorithm

The mental model in one line: HyperLogLog hashes each item to a uniformly random bit string, uses the first p bits to pick one of m = 2^p registers, counts the number of leading zeros (plus one) in the remaining bits, stores the maximum such count ever seen in that register, and finally estimates the cardinality as the harmonic mean of 2^register across all registers times a bias constant — because a long run of leading zeros is improbable, the longest run you have seen is a fingerprint of how many distinct items passed through. No item values are stored; only m small integers.

The core probabilistic intuition.

• A uniform hash makes each bit a fair coin. A good hash spreads any input over the output space uniformly, so each bit of the hash is independently 0 or 1 with probability one-half. The value itself is irrelevant after hashing; only the bit pattern matters.
• Long runs of leading zeros are rare. The probability that a hash begins with exactly k zeros then a one is 2^-(k+1). Seeing a run of 10 leading zeros is a one-in-1024 event — so if you have seen it, you have probably observed on the order of 1024 distinct hashes.
• The maximum run is the fingerprint. Track the longest leading-zero run observed. If the maximum is R, a reasonable guess for the number of distinct items is about 2^R. This is the original Flajolet–Martin insight; everything else is variance reduction.
• One estimator is noisy; many are stable. A single maximum-run counter has enormous variance. HyperLogLog runs m independent estimators (the registers), each seeing a random 1/m slice of the items, and combines them — that averaging is what turns a wild guess into a ~1%-error estimate.

Registers — the fixed-size state.

• What a register holds. A single small integer: the maximum leading-zero-count (rho) seen for hashes routed to that register. Six bits is enough (a 64-bit hash yields rho up to ~50, and 6 bits holds 0–63).
• How many registers. m = 2^p, where p is the precision. p = 14 gives m = 16384 registers and the canonical 12 KB / ~0.8% configuration. More registers → less error and more memory.
• Register routing. The first p bits of the hash select the register index; the remaining bits are scanned for leading zeros. Splitting one hash into "which bucket" plus "how rare" is what lets m estimators run from a single hash function.

The estimator — harmonic mean, not arithmetic mean.

• Why harmonic. Each register's implied estimate is 2^register, an exponential quantity where a single large value can dominate an arithmetic mean and inflate the estimate. The harmonic mean tames those outliers, which is the specific improvement HyperLogLog made over its predecessor LogLog.
• The formula. E = alpha_m × m^2 × ( Σ_j 2^(-M[j]) )^(-1), where M[j] is register j, the sum runs over all m registers, and alpha_m is a bias-correction constant (about 0.7213 for large m). The Σ 2^(-M[j]) term is the reciprocal-sum that makes this a harmonic mean.
• The constant. alpha_m corrects a systematic bias in the raw harmonic-mean formula. It depends on m: 0.673 for m=16, 0.697 for m=32, 0.709 for m=64, and 0.7213 / (1 + 1.079/m) for m ≥ 128.

Common beginner mistakes.

• Using a weak or non-uniform hash — if the bits are not fair coins, the leading-zero statistics are wrong and the estimate is biased.
• Averaging 2^register with the arithmetic mean instead of the harmonic mean — reintroduces the outlier sensitivity HLL was designed to remove.
• Forgetting the alpha_m constant — the raw estimator is biased without it.
• Under-sizing the register width — 4 or 5 bits truncates rho for 64-bit hashes at high cardinality.

Worked example — hash one item into bucket and rho

Detailed explanation. The atomic operation of HyperLogLog is turning one item into a (register_index, rho) pair. Everything else is repeating this and taking a max. Walk through it for a single item at precision p = 4 (small, so the bits are readable).

• Precision. p = 4 → m = 16 registers, register index is the first 4 bits.
• The split. First 4 bits = register index; remaining bits = the run we scan for leading zeros.
• rho. rho = (number of leading zeros in the remaining bits) + 1 — the position of the leftmost 1-bit.

Question. Given a 32-bit hash, compute the register index and rho at p = 4.

Input.

Field	Value
Precision p	4
Registers m	16
Example hash (32-bit)	0110 1 0001 ... (index bits, then remainder)
Index bits	first 4
Remainder	bits after the index

Code.

def bucket_and_rho(h: int, p: int, hash_bits: int = 32):
    """Return (register_index, rho) for a hash value h."""
    m = 1 << p
    # First p bits = register index (top bits of the hash)
    idx = h >> (hash_bits - p)
    # Remaining bits = the tail we scan for the leftmost 1-bit
    remainder = h & ((1 << (hash_bits - p)) - 1)
    w_bits = hash_bits - p
    # rho = position of the leftmost 1-bit in the remainder (1-based)
    if remainder == 0:
        rho = w_bits + 1                      # no 1-bit at all in w_bits
    else:
        rho = w_bits - remainder.bit_length() + 1
    return idx, rho

# Example: hash whose top 4 bits are 0110 (=6), then a 1 immediately after
h = 0b0110_1_0001010101010101010101010  # 32 bits
idx, rho = bucket_and_rho(h, p=4)
print(f"register index = {idx}")   # 6
print(f"rho            = {rho}")   # 1  (leftmost remainder bit is a 1)

Step-by-step explanation.

1. The hash is treated as a fixed-width bit string. Shifting right by hash_bits - p keeps only the top p bits — that integer, 0110 = 6, is the register index. This routes the item to register 6 of 16.
2. Masking with (1 << (hash_bits - p)) - 1 keeps the low w_bits = 28 bits — the remainder we inspect for leading zeros.
3. rho is the 1-based position of the leftmost 1-bit in the remainder. Here the first remainder bit is a 1, so there are zero leading zeros and rho = 1.
4. If the remainder had been 0001..., there would be three leading zeros and rho = 4. Bigger rho means a rarer bit pattern, which is evidence of higher cardinality feeding this register.
5. The remainder == 0 guard handles the vanishingly rare case where the whole tail is zeros; rho is then w_bits + 1. Using a 64-bit hash makes this and hash-collision effects negligible.

Output.

Item hash top bits	Register index	Leading zeros in remainder	rho
0110 1...	6	0	1
0110 0001...	6	3	4
1010 001...	10	2	3

Rule of thumb. One hash → split into p index bits and a remainder → rho is the position of the leftmost 1-bit in the remainder. Register idx keeps max(current, rho). That single step, repeated, is the entire ingest path.

Worked example — build a tiny HLL and update registers

Detailed explanation. Now repeat the atomic step over a stream and keep the per-register maximum. This is the whole "add" side of HyperLogLog; the registers array is the sketch. Build a minimal, correct HLL in a few lines.

• State. An array of m registers initialised to 0.
• Add. Hash the item, compute (idx, rho), set M[idx] = max(M[idx], rho).
• Only the max matters. Re-adding the same item is idempotent (same hash → same idx, rho ≤ stored), which is exactly why the structure counts distinct items.

Question. Implement add for a minimal HyperLogLog and show the register array after ingesting a few items.

Input.

Field	Value
Precision p	4 (m = 16)
Hash	64-bit (blake2b truncated)
Items	"alice", "bob", "carol", "alice" (dup)

Code.

import hashlib

class TinyHLL:
    def __init__(self, p: int = 4):
        self.p = p
        self.m = 1 << p
        self.regs = [0] * self.m
        self.hash_bits = 64

    def _hash(self, item: str) -> int:
        d = hashlib.blake2b(item.encode(), digest_size=8).digest()
        return int.from_bytes(d, "big")          # 64-bit uniform-ish hash

    def add(self, item: str) -> None:
        h = self._hash(item)
        idx = h >> (self.hash_bits - self.p)     # top p bits
        w = h & ((1 << (self.hash_bits - self.p)) - 1)
        w_bits = self.hash_bits - self.p
        rho = (w_bits + 1) if w == 0 else (w_bits - w.bit_length() + 1)
        if rho > self.regs[idx]:                  # keep the maximum
            self.regs[idx] = rho

hll = TinyHLL(p=4)
for item in ["alice", "bob", "carol", "alice"]:  # "alice" twice
    hll.add(item)
print(hll.regs)          # dup "alice" does not change anything the 2nd time
print("non-zero regs:", sum(1 for r in hll.regs if r > 0))

Step-by-step explanation.

1. The register array starts all-zero — a fresh sketch that estimates cardinality 0. Each entry will hold the largest rho routed to it.
2. add hashes the item once, derives (idx, rho), and writes M[idx] = max(M[idx], rho). The max is the crux: only an item that produces a rarer pattern than anything seen before for that bucket changes the state.
3. Adding "alice" the second time hashes to the identical idx and rho, so the rho > regs[idx] test fails and nothing changes. Duplicates are free and invisible — that is why HLL counts distinct elements, not occurrences.
4. Different items scatter across registers because their hash prefixes differ; with only 16 registers and 3 distinct items you will typically see a few non-zero registers, each holding a small rho.
5. The sketch's entire memory is self.regs — 16 integers here, m in general. No item strings are retained, so the structure is privacy-friendly and size-bounded.

Output.

Action	Effect on registers
add("alice")	one register set to its rho
add("bob")	another register set
add("carol")	another register set
add("alice") again	no change (idempotent)
Non-zero registers	~3 (one per distinct item, modulo collisions)

Rule of thumb. The add path is: hash → (idx, rho) → M[idx] = max(M[idx], rho). Because it only ever takes a max, adding a duplicate is a no-op — the reason a max-of-rho array counts distinct items rather than total items.

Worked example — the raw harmonic-mean estimate

Detailed explanation. With registers populated, the estimate is a closed-form formula over the array. Implement the raw HyperLogLog estimator and run it on a synthetic stream to see it land near the true cardinality.

• The reciprocal sum. Z = Σ_j 2^(-M[j]) — small when registers are large (high cardinality).
• The formula. E = alpha_m × m^2 / Z.
• The constant. alpha_m = 0.7213 / (1 + 1.079/m) for m ≥ 128.

Question. Estimate the cardinality of a stream of 100,000 distinct items with a p = 14 HLL using the raw estimator.

Input.

Field	Value
Precision p	14 (m = 16384)
True cardinality	100,000
Estimator	raw harmonic mean
alpha_m	0.7213 / (1 + 1.079/m)

Code.

import hashlib

def alpha_m(m: int) -> float:
    if m == 16:  return 0.673
    if m == 32:  return 0.697
    if m == 64:  return 0.709
    return 0.7213 / (1 + 1.079 / m)

class HLL:
    def __init__(self, p=14):
        self.p, self.m = p, 1 << p
        self.regs = [0] * self.m
        self.bits = 64
    def add(self, x: str):
        h = int.from_bytes(hashlib.blake2b(x.encode(), digest_size=8).digest(), "big")
        idx = h >> (self.bits - self.p)
        w = h & ((1 << (self.bits - self.p)) - 1)
        wb = self.bits - self.p
        rho = (wb + 1) if w == 0 else (wb - w.bit_length() + 1)
        if rho > self.regs[idx]:
            self.regs[idx] = rho
    def raw_estimate(self) -> float:
        Z = sum(2.0 ** (-r) for r in self.regs)
        return alpha_m(self.m) * self.m * self.m / Z

hll = HLL(p=14)
true_n = 100_000
for i in range(true_n):
    hll.add(f"item-{i}")

est = hll.raw_estimate()
print(f"true      = {true_n:,}")
print(f"estimate  = {est:,.0f}")
print(f"error     = {(est/true_n - 1)*100:+.2f}%")

Step-by-step explanation.

1. Every one of the 100,000 distinct items is hashed and routed; because m = 16384, each register sees about 100000 / 16384 ≈ 6 items on average and stores the largest rho among them.
2. raw_estimate computes Z = Σ 2^(-M[j]). A register at value 6 contributes 2^-6; larger registers contribute exponentially less. Z is therefore small when cardinality is high.
3. E = alpha_m × m^2 / Z inverts that relationship: small Z → large E. The m^2 factor scales the harmonic mean of the per-register estimates up to a whole-sketch cardinality.
4. alpha_m ≈ 0.7213 for m = 16384 corrects the systematic bias that the un-normalised harmonic mean carries. Without it the estimate is consistently a few percent high.
5. The result lands within roughly ±0.8% of 100,000 — the ~1% accuracy from 12 KB of registers, no item values stored. At very low or very high cardinality the raw estimate drifts, which is exactly the bias the next section corrects.

Output.

Metric	Value
True cardinality	100,000
Raw HLL estimate	~99,200–100,800
Relative error	within ~±0.8%
Registers used	16,384 (12 KB)
Item values stored	0

Rule of thumb. The estimate is alpha_m × m^2 / Σ 2^(-register) — a harmonic mean of the per-register guesses. It is accurate in the mid-range and biased at the extremes, which is why production HLLs bolt on the corrections in the next section.

Data engineering interview question on the HLL mechanism

A senior interviewer might ask: "Implement the core of HyperLogLog from scratch — the add path and the raw estimator — and explain, as you go, why you use the maximum leading-zero count per register and the harmonic mean across registers rather than the arithmetic mean. Then tell me what breaks if the hash function is not uniform."

Solution Using a from-scratch register array with max-rho updates and a harmonic-mean estimator

import hashlib

def alpha_m(m: int) -> float:
    return {16: 0.673, 32: 0.697, 64: 0.709}.get(m, 0.7213 / (1 + 1.079 / m))

class HyperLogLog:
    def __init__(self, p: int = 14):
        assert 4 <= p <= 18
        self.p, self.m, self.bits = p, 1 << p, 64
        self.regs = bytearray(self.m)              # 1 byte per register (>=6 bits)

    def _hp(self, x: str):
        h = int.from_bytes(hashlib.blake2b(x.encode(), digest_size=8).digest(), "big")
        idx = h >> (self.bits - self.p)
        w = h & ((1 << (self.bits - self.p)) - 1)
        wb = self.bits - self.p
        rho = (wb + 1) if w == 0 else (wb - w.bit_length() + 1)
        return idx, rho

    def add(self, x: str) -> None:
        idx, rho = self._hp(x)
        if rho > self.regs[idx]:                    # MAX, not sum
            self.regs[idx] = rho

    def count(self) -> float:
        Z = sum(2.0 ** (-r) for r in self.regs)
        return alpha_m(self.m) * self.m * self.m / Z

hll = HyperLogLog(p=14)
for i in range(250_000):
    hll.add(f"user-{i}")
print(f"estimate = {hll.count():,.0f}   (true = 250,000)")

Step-by-step trace.

Concern	Choice	Reasoning
Per-register value	max(rho)	duplicates and smaller runs are no-ops → counts distinct
Combine registers	harmonic mean	tames the exponential 2^rho outliers LogLog suffered
Bias constant	alpha_m	removes systematic over-estimate of the raw formula
Hash width	64-bit	avoids collisions / large-range issues near billions
Register width	1 byte (≥6 bits)	holds rho up to 63 for a 64-bit hash

Adding an item takes one hash and a single conditional register write; the estimate is a linear scan over m registers computing alpha_m × m^2 / Σ 2^(-register). The maximum-per-register rule makes re-adding an item free, so the array measures how many distinct items were needed to produce the observed rarest patterns, and the harmonic mean keeps a single lucky long run from blowing up the estimate.

Output:

Metric	Value
True cardinality	250,000
Estimate	~248,000–252,000
Memory	16,384 bytes (register array)
Add complexity	O(1)
Count complexity	O(m)

Why this works — concept by concept:

• Maximum-per-register — storing max(rho) makes the structure a set fingerprint: adding a duplicate can never raise the max, so it is idempotent, and the array reflects distinct elements rather than event volume.
• Leading-zero rarity — the longest leading-zero run is an unbiased signal of how many distinct hashes were drawn, because a run of k zeros occurs with probability 2^-k; the longest run seen scales like log2(cardinality).
• Harmonic mean over registers — averaging 2^register harmonically (a reciprocal sum) suppresses the outlier registers that made the earlier LogLog estimator noisy, cutting the standard error to 1.04/sqrt(m).
• alpha_m bias constant — the raw harmonic-mean formula over-estimates by a fixed factor; alpha_m normalises it. A non-uniform hash breaks the whole chain, because leading-zero probabilities are no longer 2^-k and every downstream constant is wrong.
• Cost — O(1) time and O(1) memory per add, O(m) to read the count, m × 6 bits total. Accuracy is set by m (standard error 1.04/sqrt(m)), completely independent of the cardinality — the property that makes billions-in-kilobytes possible.

Data structures
Topic — data-structures
Implement-the-structure problems (HLL, bloom, sketches)

Practice →

Cardinality Topic — cardinality Cardinality-estimation mechanics problems

Practice →

---

3. Bias correction & accuracy

The raw estimator drifts at small and large cardinalities — corrections and HLL++ pin it to ~1% across the whole range

The mental model in one line: the raw harmonic-mean estimator is accurate in the middle of the cardinality range but biased at the extremes — at low cardinality many registers are still zero and the formula over-counts, at very high cardinality (with a 32-bit hash) it saturates — so production HyperLogLog swaps in linear counting at the low end, a large-range correction at the top of a 32-bit space, and, in Google's HLL++, a 64-bit hash plus an empirically-measured bias table and a sparse encoding to be accurate and compact across the entire range. The accuracy you can promise is the relative standard error 1.04/sqrt(m), and it is set entirely by the register count.

Where the raw estimator goes wrong.

• Small range (low cardinality). When the true count is below about 2.5 × m, many registers are still zero. The harmonic-mean formula systematically over-estimates here, and the fix is to switch to linear counting, which is very accurate when there are empty registers.
• Large range (32-bit hash only). As the estimate approaches 2^32, hash collisions make the raw estimator under-count; the original paper adds a correction E = -2^32 × ln(1 - E/2^32). With a 64-bit hash this range is effectively unreachable and the correction is unnecessary.
• Mid range. The raw estimator is already good; no correction is applied.
• The seam. The original algorithm chooses which branch to use by comparing the raw estimate to thresholds, which creates a small discontinuity at the boundaries — one of the specific things HLL++ smooths out.

Linear counting — the low-cardinality rescue.

• The idea. If V of the m registers are still zero, the cardinality is well estimated by E = m × ln(m / V). This is the classic "balls in bins, count empty bins" estimator and it is far more accurate than harmonic mean when the sketch is sparsely populated.
• The switch. Use linear counting when the raw estimate is ≤ 2.5m and V > 0. Otherwise use the harmonic-mean estimate (with any large-range correction).
• Why it matters. Without it, counting a few hundred distinct items in a 16384-register sketch can be off by several percent — embarrassing on a low-traffic dashboard.

HLL++ — Google's production upgrade (2013).

• 64-bit hash. Eliminates the large-range correction and pushes collision effects out past any realistic cardinality (~1.8e19). This alone removes a whole class of high-end error.
• Empirical bias correction. Instead of the analytic thresholds, HLL++ ships a measured bias table for the intermediate range and interpolates, removing the discontinuities of the original branch-select.
• Sparse representation. At low cardinality it stores an explicit, compressed list of (index, rho) pairs instead of the full dense register array — often kilobytes down to bytes — and only converts to dense when the sparse form grows past a threshold. This makes low-cardinality sketches both smaller and more accurate.

The accuracy contract.

• Standard error. Relative standard error ≈ 1.04 / sqrt(m). This is a standard deviation, so ~68% of estimates fall within ±1 SE and ~95% within ±2 SE of the truth.
• Precision knob. p sets m = 2^p sets both memory (m × 6 bits) and error. Double m (one more bit of p) and the error shrinks by sqrt(2) ≈ 1.41× while memory doubles — diminishing returns, so most systems settle at p = 14.
• It is relative. The error is a percentage of the true count, so absolute error grows with cardinality but the percentage stays fixed — the opposite of a fixed-width counter.

Worked example — precision, memory, and standard error

Detailed explanation. The single most useful table for an HLL interview maps precision p to register count, memory, and standard error. Memorising the shape of it lets you answer "how accurate / how big?" instantly. Build it from the two formulas.

• Memory. m × 6 bits = 2^p × 6 / 8 bytes.
• Error. 1.04 / sqrt(m) = 1.04 / sqrt(2^p).
• The sweet spot. p = 14 → 12 KB, ~0.81% — the Redis / common default.

Question. Tabulate memory and standard error for p from 10 to 16.

Input.

Precision p	Registers m	Formula for memory	Formula for error
10	1,024	2^10 × 6 / 8	1.04 / sqrt(2^10)
12	4,096	2^12 × 6 / 8	1.04 / sqrt(2^12)
14	16,384	2^14 × 6 / 8	1.04 / sqrt(2^14)
16	65,536	2^16 × 6 / 8	1.04 / sqrt(2^16)

Code.

import math

def hll_profile(p: int):
    m = 1 << p
    mem_bytes = m * 6 / 8
    std_err   = 1.04 / math.sqrt(m)
    return m, mem_bytes, std_err

print(f"{'p':>3} {'m':>8} {'memory':>10} {'std error':>10}")
for p in (10, 11, 12, 13, 14, 15, 16):
    m, mem, err = hll_profile(p)
    mem_str = f"{mem/1024:.1f} KB"
    print(f"{p:>3} {m:>8,} {mem_str:>10} {err*100:>9.2f}%")

Step-by-step explanation.

1. m = 2^p is the number of registers; each is 6 bits, so memory is m × 6 / 8 bytes. Every increment of p doubles both m and the memory.
2. Standard error is 1.04 / sqrt(m). Because it depends on sqrt(m), doubling m only improves error by 1.41× — you pay double memory for a ~29% error reduction. That diminishing return is why nobody uses p = 20.
3. p = 14 is the industry default: 16,384 registers, 12 KB, 0.81% error. Redis hard-codes this; BigQuery's default precision (15) is one step finer.
4. At p = 10 you get a 768-byte sketch at ~3.25% error — useful when you have millions of low-cardinality keys and can tolerate coarser counts (e.g. per-user distinct actions).
5. At p = 16 you get 48 KB at ~0.4% error — for a small number of high-value aggregate counters where accuracy matters more than footprint.

Output.

p	m (registers)	Memory	Standard error
10	1,024	0.75 KB	~3.25%
12	4,096	3.0 KB	~1.63%
14	16,384	12.0 KB	~0.81%
16	65,536	48.0 KB	~0.41%

Rule of thumb. Error is 1.04/sqrt(m) and memory is m × 6 bits, so accuracy improves only with the square root of memory. p = 14 (12 KB, ~0.8%) is the default; go coarser for many keys, finer for a few high-stakes counters.

Worked example — linear counting at low cardinality

Detailed explanation. Show the raw estimator drifting at low cardinality and the linear-counting correction fixing it. This is the correction that matters most in practice, because most real keys (per-user, per-page) have low cardinality.

• The symptom. With m = 16384 and only 500 distinct items, the raw harmonic-mean estimate reads noticeably high.
• The fix. Count zero registers V; if the raw estimate ≤ 2.5m and V > 0, use E = m × ln(m/V).
• The result. Linear counting lands within a fraction of a percent where the raw formula was several percent off.

Question. Estimate a 500-distinct stream with a p = 14 sketch using both the raw and the linear-counting estimators.

Input.

Field	Value
Precision p	14 (m = 16384)
True cardinality	500
Raw threshold	E ≤ 2.5m → use linear counting
Linear formula	m × ln(m / V), V = zero registers

Code.

import hashlib, math

class HLL:
    def __init__(self, p=14):
        self.p, self.m, self.bits = p, 1 << p, 64
        self.regs = bytearray(self.m)
    def add(self, x):
        h = int.from_bytes(hashlib.blake2b(x.encode(), digest_size=8).digest(), "big")
        idx = h >> (self.bits - self.p)
        w = h & ((1 << (self.bits - self.p)) - 1)
        wb = self.bits - self.p
        rho = (wb + 1) if w == 0 else (wb - w.bit_length() + 1)
        if rho > self.regs[idx]:
            self.regs[idx] = rho
    def raw(self):
        Z = sum(2.0 ** (-r) for r in self.regs)
        a = 0.7213 / (1 + 1.079 / self.m)
        return a * self.m * self.m / Z
    def count(self):
        E = self.raw()
        if E <= 2.5 * self.m:
            V = self.regs.count(0)                 # empty registers
            if V > 0:
                return self.m * math.log(self.m / V)   # linear counting
        return E

hll = HLL(p=14)
for i in range(500):
    hll.add(f"key-{i}")

print(f"true            = 500")
print(f"raw estimate    = {hll.raw():,.0f}")
print(f"corrected count = {hll.count():,.0f}")

Step-by-step explanation.

1. With only 500 distinct items spread over 16,384 registers, the vast majority of registers are still zero. The harmonic-mean formula was derived assuming most registers are populated, so in this regime it over-estimates.
2. count() first computes the raw estimate and checks it against the 2.5m threshold. Since 500 is far below 2.5 × 16384, it enters the linear-counting branch.
3. Linear counting counts the empty registers V and applies E = m × ln(m/V). This is the "how many balls did it take to leave V of m bins empty" estimator, which is extremely accurate when many bins are empty.
4. The corrected count lands within a fraction of a percent of 500, whereas the raw estimate reads meaningfully higher. On a low-traffic page's unique-visitor counter, that is the difference between a trustworthy and an embarrassing number.
5. As cardinality climbs and registers fill up (V → 0), the linear branch stops firing and the harmonic-mean estimate takes over seamlessly — the two estimators agree in the crossover region around 2.5m.

Output.

Estimator	Value	Error vs 500
Raw harmonic mean	~525–560	+5% to +12%
Linear counting	~499–502	< ±0.6%
Chosen (count())	linear counting	best available

Rule of thumb. Below ~2.5m distinct items, switch to linear counting (m × ln(m/V)); it is far more accurate than the harmonic-mean formula when registers are mostly empty. This is the correction that keeps low-cardinality keys honest.

Worked example — reading the standard error as a confidence band

Detailed explanation. The standard error is a standard deviation, so it defines a confidence band, not a hard bound. Interviewers love the follow-up "so a single HLL count could be off by more than 0.8%?" — the honest answer is yes, with a known probability. Turn the SE into a band.

• The band. Relative SE σ = 1.04/sqrt(m). ~68% of estimates fall within ±σ, ~95% within ±2σ, ~99.7% within ±3σ.
• Absolute band. Multiply by the true count: at 10,000,000 uniques and p=14, σ ≈ 0.81% → ±81,000 (1σ), ±162,000 (2σ).
• The implication. For dashboards this is fine; for anything with a hard threshold ("alert if uniques > X") you must account for the band.

Question. For a p = 14 sketch and a true count of 10,000,000, give the 1σ, 2σ, and 3σ absolute error bands.

Input.

Field	Value
Precision p	14 (m = 16384)
True cardinality	10,000,000
Relative σ	1.04 / sqrt(16384)
Bands	±1σ (68%), ±2σ (95%), ±3σ (99.7%)

Code.

import math

m = 1 << 14
sigma_rel = 1.04 / math.sqrt(m)          # ~0.0081
true_n = 10_000_000

for k in (1, 2, 3):
    band = k * sigma_rel * true_n
    pct  = k * sigma_rel * 100
    coverage = {1: "68%", 2: "95%", 3: "99.7%"}[k]
    print(f"±{k}σ ({coverage}): ±{band:,.0f} uniques  (±{pct:.2f}%)  "
          f"range [{true_n-band:,.0f} .. {true_n+band:,.0f}]")

Step-by-step explanation.

1. The relative standard error at p = 14 is 1.04/sqrt(16384) ≈ 0.81%. This is one standard deviation of the estimator's error distribution, which is approximately Gaussian for large m.
2. At a true count of 10,000,000, one relative sigma is 0.81% × 10,000,000 ≈ 81,000 uniques. So a single estimate is typically within ±81,000 but not guaranteed to be.
3. Two sigma (±162,000, ±1.6%) covers ~95% of estimates; three sigma (±243,000, ±2.4%) covers ~99.7%. The tail beyond that is rare but not impossible.
4. This is why HLL is right for dashboards and funnels (nobody notices ±0.8% on a visitor count) and wrong for billing or hard-threshold alerts (a 2σ excursion could trip or miss a threshold spuriously).
5. If a tighter band is required, the only lever is more registers: going to p = 16 shrinks σ to ~0.41%, halving every band at 4× the memory. There is no free accuracy — it is always paid in registers.

Output.

Band	Relative	Absolute (at 10M)	Range
±1σ (68%)	±0.81%	±81,000	9,919,000 .. 10,081,000
±2σ (95%)	±1.63%	±163,000	9,837,000 .. 10,163,000
±3σ (99.7%)	±2.44%	±244,000	9,756,000 .. 10,244,000

Rule of thumb. Treat the HLL count as true ± 1.04/sqrt(m) at one sigma — a band, not a point. Fine for dashboards; if a hard threshold depends on the number, widen your margins by 2–3σ or raise precision.

Statistics interview question on HLL accuracy

A senior interviewer might ask: "Your product team wants unique-user counts accurate to within 1% for a metric that ranges from a few hundred to tens of millions of uniques per key. Pick a precision, justify the memory, explain how you keep the low end accurate, and tell me the probability that any single reported number is off by more than 2%."

Solution Using p=14 with linear counting at the low end and a stated 2σ confidence contract

import hashlib, math

class ProdHLL:
    """p=14 HLL with linear-counting low-range correction (HLL++-style hash width)."""
    def __init__(self, p=14):
        self.p, self.m, self.bits = p, 1 << p, 64
        self.regs = bytearray(self.m)
        self.alpha = 0.7213 / (1 + 1.079 / self.m)

    def add(self, x: str):
        h = int.from_bytes(hashlib.blake2b(x.encode(), digest_size=8).digest(), "big")
        idx = h >> (self.bits - self.p)
        w = h & ((1 << (self.bits - self.p)) - 1)
        wb = self.bits - self.p
        rho = (wb + 1) if w == 0 else (wb - w.bit_length() + 1)
        if rho > self.regs[idx]:
            self.regs[idx] = rho

    def count(self) -> float:
        Z = sum(2.0 ** (-r) for r in self.regs)
        E = self.alpha * self.m * self.m / Z
        if E <= 2.5 * self.m:                       # low range
            V = self.regs.count(0)
            if V > 0:
                return self.m * math.log(self.m / V)   # linear counting
        return E

    @property
    def std_error(self) -> float:
        return 1.04 / math.sqrt(self.m)

hll = ProdHLL(p=14)
print(f"chosen precision  : p=14  (m={hll.m:,}, memory=12 KB)")
print(f"1σ relative error : {hll.std_error*100:.2f}%")
print(f"2σ relative error : {2*hll.std_error*100:.2f}%  <- ~95% of reads within this")
print(f"P(|error| > 2%)   : ~5% (2% ≈ 2.47σ) -> under 1.5%")

Step-by-step trace.

Requirement	Design choice	Result
~1% accuracy	p = 14 → σ = 0.81%	1σ inside the 1% ask
Memory budget	12 KB per key	capacity-plannable
Low-end (hundreds) accurate	linear counting below 2.5m	< ~0.6% at low cardinality
High end (tens of millions)	64-bit hash, no large-range issue	unbiased across range
"off by > 2%?"	2% ≈ 2.47σ	probability ~1.4%

The design fixes p = 14, so the standard error is 0.81% — comfortably inside the 1% target at one sigma. Linear counting handles the low end where the metric starts (a few hundred uniques), and the 64-bit hash keeps the top end (tens of millions) unbiased. Because 2% is about 2.47 standard errors, the probability that any single reported number is off by more than 2% is roughly 1.4% — small, quantified, and stated up front to the product team.

Output:

Metric	Value
Precision	p = 14
Memory per key	12 KB (dense; less when sparse)
1σ error	0.81%
2σ error	1.63%
P(error > 2%)	~1.4%

Why this works — concept by concept:

• Precision picks the error — since σ = 1.04/sqrt(m) is independent of cardinality, choosing p = 14 fixes the accuracy at 0.81% for every key from hundreds to tens of millions of uniques, which is exactly the range the product team named.
• Linear counting at the low end — below 2.5m the harmonic-mean estimator is biased high; m × ln(m/V) on the empty-register count is accurate to a fraction of a percent, keeping small counts honest.
• 64-bit hash — removes the original 32-bit large-range correction and pushes hash-collision bias past any real cardinality, so the top of the range is unbiased without special-casing.
• Confidence stated as a band — reporting "±0.81% at 1σ, ~1.4% chance of exceeding 2%" turns a vague "it's approximate" into a contract the product team can reason about and sign off on.
• Cost — 12 KB per key, O(1) add, O(m) count. Halving the error to 0.41% would cost 4× memory (p = 16), so p = 14 is the memory-optimal choice for a 1% target.

Statistics
Topic — statistics
Standard-error and estimator-bias problems

Practice →

Cardinality Topic — cardinality Accuracy-tuning and precision-selection problems

Practice →

---

4. Mergeability & sketches at scale

The union of two HyperLogLogs is the element-wise max of their registers — lossless, order-independent, and the reason HLL owns distributed counting

The mental model in one line: because each HyperLogLog register stores the maximum leading-zero count for its bucket, the union of two sketches (built at the same precision) is simply the element-wise maximum of their register arrays — this merge is exact, commutative, associative, and idempotent, so you can compute sketches independently per partition, per shard, or per time-window and combine them with zero loss, which is precisely why HyperLogLog is the default distinct-count primitive in every distributed and streaming system. COUNT(DISTINCT) results cannot be combined this way; HLL sketches can, and that single property is worth more than the memory saving in most large systems.

Why max-per-register is a correct union.

• A register is a max already. Register j in sketch A holds the largest rho among items routed to bucket j in A's stream. Register j in B holds the same for B's stream. The largest rho in the combined stream is just the larger of the two — max(A[j], B[j]).
• No double counting. If an item is in both A and B, it produced the same (idx, rho) in each, so max of two equal values is unchanged. Overlap is handled automatically; the merged sketch reflects the true union cardinality, not the sum.
• Order-independent. max is commutative and associative, so merging in any order — A then B, B then A, or a tree of thousands of partial sketches — gives the identical result. There is no "merge order" bug to worry about.
• Idempotent. Merging a sketch with itself changes nothing. Re-processing a partition (e.g. after a retry) cannot corrupt the union.

What mergeability unlocks.

• Map-reduce distinct count. Each mapper builds a sketch over its shard; the reducer maxes them together and reads one count. No shuffle of raw values, no giant distributed set.
• Streaming windows. Keep one sketch per minute; a "distinct over the last hour" query merges 60 minute-sketches on the fly. Sliding windows become sketch arithmetic.
• Rollups. Store daily sketches; weekly = merge 7, monthly = merge ~30, quarterly = merge the months. You compute the finest granularity once and derive every coarser one by merging — never re-reading raw events.
• Multi-dimensional counts. Store a sketch per (country, day); "distinct users in Europe this week" merges the relevant cells. This is how warehouses answer arbitrary-slice unique counts fast.

The one hard rule and the intersection caveat.

• Same precision to merge. Two sketches can only be merged if they share the same p (same m). A p=12 and a p=14 sketch are not directly mergeable — you can down-sample the finer one to the coarser precision, but you cannot up-sample. Standardise p across a system.
• Intersections are inclusion-exclusion. HLL has no direct intersection. You estimate |A ∩ B| = |A| + |B| - |A ∪ B|. The union is exact-ish; the individual counts each carry error, and subtracting two noisy numbers adds their errors — so intersections of similar-sized, small-overlap sets can be very noisy.
• Jaccard / set difference. Derived the same inclusion-exclusion way, with the same error-amplification caveat. For accurate set operations, Theta sketches or MinHash are the better tools.

Common interview probes on mergeability.

• "Why can you merge HLLs but not COUNT(DISTINCT) results?" — because a register is a max, and max-of-max handles overlap; two distinct counts have no overlap information.
• "Does merge order matter?" — no; max is commutative and associative.
• "Can you merge different precisions?" — no directly; down-sample the finer to the coarser.
• "How do you intersect?" — inclusion-exclusion, and beware error amplification.

Worked example — merge two sketches by element-wise max

Detailed explanation. Implement the merge and verify it equals a fresh sketch built over the concatenated streams. This equivalence — "merge of parts == sketch of whole" — is the property everything else relies on.

• Merge. merged[j] = max(A[j], B[j]) for all j.
• The check. Build A over stream 1, B over stream 2, merge; separately build C over stream 1 + stream 2; the register arrays must be identical.
• The payoff. Distributed counting is provably lossless, not approximately so.

Question. Merge two p = 14 sketches and confirm the merged registers equal a sketch built over both streams together.

Input.

Field	Value
Sketch A stream	users 0..599,999
Sketch B stream	users 400,000..999,999 (200k overlap)
True union cardinality	1,000,000
Merge rule	element-wise max

Code.

import hashlib

class HLL:
    def __init__(self, p=14):
        self.p, self.m, self.bits = p, 1 << p, 64
        self.regs = bytearray(self.m)
        self.alpha = 0.7213 / (1 + 1.079 / self.m)
    def add(self, x):
        h = int.from_bytes(hashlib.blake2b(x.encode(), digest_size=8).digest(), "big")
        idx = h >> (self.bits - self.p)
        w = h & ((1 << (self.bits - self.p)) - 1)
        wb = self.bits - self.p
        rho = (wb + 1) if w == 0 else (wb - w.bit_length() + 1)
        if rho > self.regs[idx]:
            self.regs[idx] = rho
    def merge(self, other):
        assert self.p == other.p, "precisions must match"
        for j in range(self.m):
            if other.regs[j] > self.regs[j]:
                self.regs[j] = other.regs[j]
    def count(self):
        Z = sum(2.0 ** (-r) for r in self.regs)
        return self.alpha * self.m * self.m / Z

A, B, C = HLL(), HLL(), HLL()
for i in range(0, 600_000):        A.add(f"user-{i}")
for i in range(400_000, 1_000_000): B.add(f"user-{i}")
for i in range(0, 1_000_000):      C.add(f"user-{i}")   # whole stream directly

A.merge(B)
print("merged == whole:", A.regs == C.regs)      # True — lossless
print(f"union estimate = {A.count():,.0f}  (true = 1,000,000)")

Step-by-step explanation.

1. Sketch A covers users 0–599,999 and B covers 400,000–999,999, so they overlap on 200,000 users. The true union is 1,000,000 distinct users, not 1,200,000.
2. merge walks the register arrays and keeps the larger value at each index. Because each register is already a per-bucket max, the merged register is the max over the combined stream for that bucket.
3. The assertion A.regs == C.regs passes: the merge of two partial sketches is byte-for-byte identical to a sketch built over the whole stream at once. This is the lossless property, demonstrated rather than asserted.
4. The overlapping 200,000 users contribute the same (idx, rho) in both A and B, so max collapses them automatically — the union estimate is ~1,000,000, not ~1,200,000. No dedup logic was needed; the structure dedups by construction.
5. Because A.regs == C.regs, the estimate is exactly what you would have gotten from the monolithic sketch — merging costs nothing in accuracy, only the O(m) pass over registers.

Output.

Quantity	Value
Sketch A distinct	~600,000
Sketch B distinct	~600,000
Naive A + B (wrong)	~1,200,000
Merged union estimate	~1,000,000
merged registers == whole-stream registers	True

Rule of thumb. Merge is element-wise max, and "merge of parts" is byte-identical to "sketch of the whole." Overlap is handled for free — never add two HLL counts, always merge the sketches then count once.

Worked example — map-reduce distinct count across partitions

Detailed explanation. Scale the merge to the distributed setting: many workers each sketch their shard, a reducer merges all partials, one count comes out. This is the canonical big-data distinct-count job and it moves sketches (12 KB each) across the network, not raw values.

• Map. Each of k workers builds a sketch over its shard.
• Reduce. Max all k sketches together (a tree-reduce works because merge is associative).
• Shuffle cost. k × 12 KB, independent of the number of rows — often megabytes total where the raw data is terabytes.

Question. Sketch 8 partitions independently and reduce them into a single distinct-count.

Input.

Field	Value
Partitions	8
Rows per partition	~2,000,000 (overlapping keyspace)
True global distinct	5,000,000
Shuffle payload	8 × 12 KB = 96 KB

Code.

import hashlib
from functools import reduce

# (HLL class as before: add(), merge(), count(), p=14)
def make_partition_sketch(key_range):
    h = HLL(p=14)
    for i in key_range:
        h.add(f"user-{i}")
    return h

# 8 partitions drawn from a 5,000,000-key universe (with overlap)
import random
random.seed(1)
partitions = []
for _ in range(8):
    start = random.randint(0, 3_000_000)
    partitions.append(make_partition_sketch(range(start, start + 2_000_000)))

# Reduce: merge all partial sketches (associativity makes this safe in any order)
def merge_two(a, b):
    a.merge(b)
    return a

global_sketch = reduce(merge_two, partitions)
print(f"partitions          : {len(partitions)}")
print(f"shuffle payload      : {len(partitions) * 12} KB (sketches, not rows)")
print(f"global distinct est.: {global_sketch.count():,.0f}")

Step-by-step explanation.

1. Each partition builds its own 12 KB sketch over ~2,000,000 rows. No cross-partition communication happens during the map phase — the workers are fully independent, which is what makes the job embarrassingly parallel.
2. The partitions' key ranges overlap (drawn from a shared 5,000,000-key universe), so naively summing their eight individual counts would massively over-count. The merge handles the overlap.
3. reduce(merge_two, partitions) maxes the eight sketches together. Because merge is associative and commutative, a driver-side linear fold and a distributed tree-reduce yield the identical result — you can reduce in whatever topology is cheapest.
4. The only data crossing the network is eight 12 KB sketches — 96 KB total — no matter that the underlying data is ~16,000,000 rows. Contrast an exact distinct count, which must shuffle every distinct key to a common reducer.
5. The final count() on the merged sketch estimates the global distinct at ~5,000,000 within the usual ~0.8% band. One O(m) pass produces the answer for the entire dataset.

Output.

Metric	Value
Partitions sketched	8
Rows processed	~16,000,000
Shuffle payload	96 KB (8 sketches)
Global distinct estimate	~5,000,000
Exact-count shuffle (for contrast)	all distinct keys → one reducer

Rule of thumb. Distributed distinct count = "sketch per partition, merge the sketches." You move kilobytes of sketch instead of terabytes of keys, and associativity lets you reduce in any tree shape.

Worked example — daily → weekly rollups and the intersection caveat

Detailed explanation. Two everyday operations: rolling daily sketches up to weekly (a merge), and estimating an intersection (inclusion-exclusion, with its error caveat). Both come up constantly and the intersection one is a classic trap.

• Rollup. Weekly distinct = merge of 7 daily sketches; monthly = merge of ~30. Compute daily once, derive the rest.
• Intersection. |A ∩ B| = |A| + |B| - |A ∪ B|. Correct in expectation but noisy, because it subtracts two error-bearing estimates.
• The trap. Reporting an intersection of two large, barely-overlapping sets as if it were as accurate as a union.

Question. Roll up 7 daily sketches to a weekly count, and estimate the overlap between two of the days via inclusion-exclusion.

Input.

Field	Value
Daily sketches	7 (one per day)
Weekly count	merge all 7, then count
Day-A distinct	~1,000,000
Day-B distinct	~1,000,000
True A∩B	~300,000

Code.

import hashlib
from functools import reduce
# (HLL class as before, p=14)

def day_sketch(users):
    h = HLL(p=14)
    for u in users:
        h.add(f"user-{u}")
    return h

# 7 days, each ~1,000,000 users, heavily overlapping population
days = [day_sketch(range(d * 100_000, d * 100_000 + 1_000_000)) for d in range(7)]

# Weekly rollup = merge of the 7 daily sketches
weekly = reduce(lambda a, b: (a.merge(b) or a), days, HLL(p=14))
print(f"weekly distinct  = {weekly.count():,.0f}")

# Intersection of day 0 and day 1 via inclusion-exclusion
A, B = days[0], days[1]
union = HLL(p=14); union.merge(A); union.merge(B)
inter = A.count() + B.count() - union.count()      # |A| + |B| - |A ∪ B|
print(f"|A|={A.count():,.0f}  |B|={B.count():,.0f}  |A∪B|={union.count():,.0f}")
print(f"estimated |A∩B| = {inter:,.0f}   (true ≈ 900,000 overlap here)")

Step-by-step explanation.

1. Each day gets its own sketch during ingestion. The weekly rollup is a single merge of the seven daily register arrays — no raw events are touched, so changing the reporting granularity is nearly free.
2. Because the daily populations overlap heavily, the weekly distinct is far less than the sum of the seven daily counts; the merge's automatic dedup produces the correct union.
3. The intersection uses inclusion-exclusion: |A ∩ B| = |A| + |B| - |A ∪ B|. Each of the three terms is an HLL estimate with its own ~0.8% error.
4. The subtraction is where accuracy degrades: if A and B are each ~1,000,000 with 0.8% error (~±8,000 each) and the union is ~1,100,000, the intersection is a difference of large numbers, so the absolute errors of all three terms pile onto a comparatively small result. For small true overlaps the relative error can be enormous.
5. The rule that follows: merges and unions are safe and accurate; intersections and set-differences derived from them are only as good as the gap between the numbers being subtracted. For accurate intersections, reach for Theta sketches or MinHash instead of HLL inclusion-exclusion.

Output.

Operation	Result	Reliability
Weekly rollup (merge 7)	~1.6M distinct	high (union)
|A|	~1,000,000	~0.8% error
|B|	~1,000,000	~0.8% error
|A ∪ B|	~1,100,000	~0.8% error
|A ∩ B| (incl-excl)	~900,000	noisy (errors add)

Rule of thumb. Rollups are merges and are accurate; intersections are inclusion-exclusion and amplify error. Trust HLL unions and rollups freely; treat HLL intersections as rough, and switch to Theta/MinHash when set overlap must be precise.

Data engineering interview question on mergeable sketches

A senior interviewer might ask: "Design a system that reports distinct active users at daily, weekly, monthly, and per-country granularity over billions of daily events, and lets analysts ask arbitrary date-range and country-combination questions without re-scanning raw logs. Explain what you store, how a query is answered, and the one rule that makes it all work."

Solution Using per-(country, day) HLL sketches merged on demand

import hashlib
from functools import reduce
# (HLL class as before, p=14; add(), merge(), count())

# Storage: one sketch per (country, day). Built once during ingest.
#   sketch_store[(country, day)] -> 12 KB HLL
def ingest_event(store, country, day, user_id):
    key = (country, day)
    if key not in store:
        store[key] = HLL(p=14)
    store[key].add(user_id)

def distinct_users(store, countries, days):
    """Answer any (set of countries) x (date range) distinct-user query by merging."""
    acc = HLL(p=14)
    for c in countries:
        for d in days:
            s = store.get((c, d))
            if s is not None:
                acc.merge(s)
    return acc.count()

# --- usage ---
store = {}
# ... ingest_event(store, country, day, user_id) for every event ...

# Queries are all merges of the stored cells:
# weekly_global   = distinct_users(store, ALL_COUNTRIES, last_7_days)
# monthly_europe  = distinct_users(store, EU_COUNTRIES,  last_30_days)
# custom_range    = distinct_users(store, ["US","CA"],   ["2026-09-01","2026-09-02"])

-- The same design in a warehouse: store a sketch column per (country, day),
-- then MERGE the relevant cells at query time (BigQuery HLL_COUNT.* shown).
CREATE TABLE uv_sketch AS
SELECT country, event_date,
       HLL_COUNT.INIT(user_id, 14) AS sketch      -- one 12 KB-ish sketch per cell
FROM   events
GROUP  BY country, event_date;

-- Arbitrary date-range + country-set distinct users: merge, don't re-scan
SELECT HLL_COUNT.MERGE(sketch) AS distinct_users
FROM   uv_sketch
WHERE  country IN ('US','CA')
  AND  event_date BETWEEN '2026-09-01' AND '2026-09-07';

Step-by-step trace.

Layer	What is stored / done	Why
Ingest	one HLL per (country, day)	finest granularity, computed once
Storage	~12 KB per cell	bounded; cells × 12 KB
Weekly query	merge 7 days' cells	no raw re-scan
Per-country query	merge that country's cells	slice by dimension
Arbitrary combo	merge the matching cells	any slice = a merge
Hard rule	all sketches share p = 14	mergeability requires equal precision

The system stores exactly one sketch per finest-grain cell (country, day). Every analyst question — any date range, any set of countries — is answered by merging the matching cells and reading one count. Raw logs are never re-scanned to change granularity or slice; the whole query surface reduces to "select the cells, merge, count."

Output:

Query	How answered	Cost
Global daily	one cell-group merge per day	O(cells) merge
Global weekly	merge 7 days × all countries	O(cells) merge
Europe monthly	merge EU countries × 30 days	O(cells) merge
Custom country+range	merge matching cells	O(cells) merge
Storage	cells × 12 KB	bounded, plannable

Why this works — concept by concept:

• Finest-grain sketch cells — storing one sketch per (country, day) and deriving every coarser view by merging means you compute the expensive part once and answer all granularities from it.
• Any slice is a merge — because merge is associative and commutative, an arbitrary set of cells combines to the correct union regardless of order, so any date-range × country-set query is just "merge the matching cells."
• No raw re-scan — changing granularity (day → week → month) or dimension (country → region) never touches the event logs; it merges 12 KB sketches, turning terabyte scans into kilobyte merges.
• Equal precision is the one rule — every sketch is built at p = 14; sketches of different precision cannot be merged, so standardising p system-wide is what makes the whole design compose.
• Cost — O(number of cells) to merge and O(m) to count per query, with storage of cells × 12 KB — independent of event volume. An exact design would re-aggregate raw events per query, an O(rows) cost every time.

Cardinality
Topic — cardinality
Mergeable-sketch and rollup problems

Practice →

Data structures Topic — data-structures Set-operation and union/intersection problems

Practice →

---

5. HLL in practice — Redis / BigQuery / Spark

The same hash-registers-estimate idea ships as a one-line function in Redis, BigQuery, and Spark — learn the API once, use it everywhere

The mental model in one line: every major data platform exposes HyperLogLog as a small, high-level API — Redis via PFADD/PFCOUNT/PFMERGE, BigQuery via APPROX_COUNT_DISTINCT and the composable HLL_COUNT.* family, Spark via approx_count_distinct(col, rsd) — and although the surface syntax differs, they all implement the identical hash → registers → harmonic-mean estimate you now understand, so the skill transfers directly: pick precision/error, add items, and (in Redis and BigQuery) store and merge portable sketches for rollups. Knowing which knob controls accuracy and which operation is a merge lets you use any of them correctly on day one.

Redis — PFADD / PFCOUNT / PFMERGE.

• The commands. PFADD key element [element ...] adds items; PFCOUNT key [key ...] returns the estimate (of one key, or the union of several); PFMERGE dest src [src ...] writes the merged sketch to a new key. The PF prefix honours Philippe Flajolet.
• The footprint. A dense Redis HLL is capped at 12 KB (p = 14, ~0.81% error); low-cardinality keys use a sparse encoding that can be a few dozen bytes and auto-upgrades to dense as they grow.
• The idiom. One key per (entity, time-bucket) — uv:page:42:2026-09-05. Daily uniques are PFCOUNT; weekly uniques are PFCOUNT over 7 daily keys (implicit union) or a materialised PFMERGE.
• The gotcha. PFCOUNT of multiple keys computes their union on the fly; it is not the sum of their individual counts. That is a feature (correct overlap handling) that surprises people expecting addition.

BigQuery — APPROX_COUNT_DISTINCT and HLL_COUNT.*.

• The one-liner. APPROX_COUNT_DISTINCT(col) returns an approximate distinct count directly — the everyday tool for dashboards.
• The composable family. HLL_COUNT.INIT(col, precision) builds a sketch (a storable BYTES value); HLL_COUNT.MERGE(sketch) unions sketches and returns the count; HLL_COUNT.MERGE_PARTIAL(sketch) unions sketches and returns a new sketch (for staged rollups); HLL_COUNT.EXTRACT(sketch) reads the count from one sketch without merging.
• Precision. INIT's precision runs 10–24 (default 15). Higher precision → less error, bigger sketch — the same 1.04/sqrt(m) trade.
• The pattern. Materialise HLL_COUNT.INIT sketches per finest-grain cell; answer any slice with HLL_COUNT.MERGE. Portable sketches also cross engines (BigQuery, Dataflow, and Java/Go libraries share a compatible format).

Spark — approx_count_distinct(col, rsd).

• The function. approx_count_distinct(col, rsd) where rsd is the target relative standard deviation (default 0.05 = 5%). Smaller rsd → more registers → more memory and time.
• The mapping. rsd is the accuracy knob that indirectly picks p: rsd = 1.04/sqrt(m), so rsd = 0.02 implies m ≈ 2704 → p ≈ 12. Set rsd to the error you can tolerate; do not over-tighten it.
• The distributed win. Spark builds per-partition sketches and merges them in the aggregation — the mergeability from section 4 is exactly what lets it run distributed with a tiny shuffle.
• Cousins. Presto/Trino: approx_distinct(col, e) and a first-class HyperLogLog type with merge(). Postgres: the postgresql-hll extension with an hll column type and hll_union_agg. ClickHouse: uniqHLL12 and the default uniq.

Common interview probes on HLL in practice.

• "What does PFCOUNT key1 key2 return?" — the union estimate, not the sum.
• "How do you do rollups in BigQuery?" — store HLL_COUNT.INIT sketches; HLL_COUNT.MERGE on query.
• "What is Spark's rsd?" — target relative standard error; it picks the register count.
• "Can sketches from different systems merge?" — only if the format and precision match (BigQuery/Dataflow do; Redis's format is its own).

Worked example — Redis daily unique-visitor rollup

Detailed explanation. The most common production HLL job: track unique visitors per page per day in Redis, then roll up to weekly. Show the commands and the Python client calls.

• Keys. uv:page:{id}:{date} — one HLL per page per day.
• Add. PFADD on each pageview.
• Read. PFCOUNT for the day; multi-key PFCOUNT or PFMERGE for the week.

Question. Track daily unique visitors for a page and produce the weekly unique count.

Input.

Field	Value
Daily key	uv:page:42:2026-09-05
Weekly key	uv:page:42:2026-W36
Add	PFADD per pageview
Weekly	PFMERGE 7 daily keys

Code.

# Redis CLI — one HLL key per page per day
PFADD uv:page:42:2026-09-05 visitor_a visitor_b visitor_c
PFADD uv:page:42:2026-09-05 visitor_a            # duplicate: no effect
PFCOUNT uv:page:42:2026-09-05                     # -> ~3 (approx daily uniques)

# Weekly rollup: merge 7 daily keys into a weekly key
PFMERGE uv:page:42:2026-W36 \
        uv:page:42:2026-09-01 uv:page:42:2026-09-02 uv:page:42:2026-09-03 \
        uv:page:42:2026-09-04 uv:page:42:2026-09-05 uv:page:42:2026-09-06 \
        uv:page:42:2026-09-07
PFCOUNT uv:page:42:2026-W36                        # -> approx weekly uniques (union)

# Union on the fly without materialising (multi-key PFCOUNT):
PFCOUNT uv:page:42:2026-09-01 uv:page:42:2026-09-02 uv:page:42:2026-09-03

import redis

r = redis.Redis()

def record_view(page_id: int, date: str, visitor_id: str) -> None:
    r.pfadd(f"uv:page:{page_id}:{date}", visitor_id)

def daily_uniques(page_id: int, date: str) -> int:
    return r.pfcount(f"uv:page:{page_id}:{date}")

def weekly_uniques(page_id: int, dates: list[str]) -> int:
    keys = [f"uv:page:{page_id}:{d}" for d in dates]
    return r.pfcount(*keys)                 # multi-key PFCOUNT = union estimate

record_view(42, "2026-09-05", "visitor_a")
record_view(42, "2026-09-05", "visitor_a")   # dup — free, no effect
record_view(42, "2026-09-05", "visitor_b")
print("daily :", daily_uniques(42, "2026-09-05"))
print("weekly:", weekly_uniques(42, [f"2026-09-0{d}" for d in range(1, 8)]))

Step-by-step explanation.

1. PFADD on each pageview routes the visitor id into the day's sketch. Re-adding the same visitor is idempotent, so refreshes and repeat visits do not inflate the count — the "distinct" semantics are built in.
2. PFCOUNT on the daily key returns the approximate distinct visitors for that day, at ~0.81% error, from a ≤ 12 KB structure regardless of how popular the page is.
3. The weekly rollup uses PFMERGE to union the seven daily sketches into a weekly key, then PFCOUNT reads it. Because merge dedups, a visitor who came every day is counted once in the week.
4. The multi-key PFCOUNT variant computes the union without materialising a merged key — handy for ad-hoc ranges. Crucially it returns the union, not the sum of the daily counts; expecting addition is the classic mistake.
5. Storage scales with the number of live (page, day) keys, not with visitor volume. Low-traffic pages stay in the sparse encoding (tens of bytes); only busy pages reach the 12 KB dense cap.

Output.

Command	Result
PFADD (new visitor)	1 (register changed)
PFADD (duplicate)	0 (no change)
PFCOUNT daily	~ distinct visitors that day
PFMERGE + PFCOUNT weekly	~ distinct visitors that week (union)
Memory per key	≤ 12 KB (sparse when small)

Rule of thumb. In Redis, one HLL key per (entity, time-bucket): PFADD on write, PFCOUNT to read, PFMERGE (or multi-key PFCOUNT) to roll up. Remember multi-key PFCOUNT is a union, never a sum.

Worked example — BigQuery APPROX_COUNT_DISTINCT and staged HLL_COUNT rollups

Detailed explanation. In a warehouse the everyday tool is APPROX_COUNT_DISTINCT, but the real power is the HLL_COUNT.* family that lets you store sketches and merge them later — the same "sketch per cell, merge on query" design from section 4, expressed in SQL.

• Everyday. APPROX_COUNT_DISTINCT(user_id) in any SELECT.
• Store. HLL_COUNT.INIT(user_id, 15) materialises a sketch per group.
• Merge. HLL_COUNT.MERGE(sketch) for the count; HLL_COUNT.MERGE_PARTIAL(sketch) for staged rollups that emit a new sketch.

Question. Show the one-liner, then a two-stage rollup that stores daily sketches and merges them to weekly.

Input.

Field	Value
Fact table	events(user_id, event_date, country)
One-liner	APPROX_COUNT_DISTINCT(user_id)
Daily sketch	HLL_COUNT.INIT(user_id, 15)
Weekly merge	HLL_COUNT.MERGE(sketch)

Code.

-- 1. Everyday one-liner: approximate distinct users per day
SELECT event_date,
       APPROX_COUNT_DISTINCT(user_id) AS approx_dau
FROM   events
GROUP  BY event_date;

-- 2. Stage 1 — materialise one sketch per (country, day)
CREATE OR REPLACE TABLE uv_daily_sketch AS
SELECT country,
       event_date,
       HLL_COUNT.INIT(user_id, 15) AS sketch      -- precision 15
FROM   events
GROUP  BY country, event_date;

-- 3. Stage 2 — weekly uniques per country by MERGING daily sketches (no re-scan)
SELECT country,
       DATE_TRUNC(event_date, WEEK)      AS wk,
       HLL_COUNT.MERGE(sketch)           AS weekly_uniques
FROM   uv_daily_sketch
GROUP  BY country, wk;

-- 4. Staged rollup that emits a NEW sketch (weekly sketch kept for monthly merge)
CREATE OR REPLACE TABLE uv_weekly_sketch AS
SELECT country,
       DATE_TRUNC(event_date, WEEK)          AS wk,
       HLL_COUNT.MERGE_PARTIAL(sketch)       AS sketch   -- returns a sketch, not a count
FROM   uv_daily_sketch
GROUP  BY country, wk;

-- 5. Global distinct across any slice: merge the matching cells
SELECT HLL_COUNT.MERGE(sketch) AS distinct_users
FROM   uv_daily_sketch
WHERE  country IN ('US','CA')
  AND  event_date BETWEEN '2026-09-01' AND '2026-09-07';

Step-by-step explanation.

1. APPROX_COUNT_DISTINCT(user_id) is the drop-in replacement for COUNT(DISTINCT user_id) — same query shape, but backed by HLL so it stays fast and cheap on huge tables. Use it for any dashboard where ~1% error is fine.
2. HLL_COUNT.INIT(user_id, 15) builds and stores one sketch per group as a BYTES value. Precision 15 (BigQuery's default) gives ~0.65% error; you can pass 10–24 to trade accuracy for size.
3. HLL_COUNT.MERGE(sketch) unions the sketches in a group and returns the distinct count in one step — this is how the weekly-per-country query derives weekly uniques from stored daily sketches without re-reading events.
4. HLL_COUNT.MERGE_PARTIAL(sketch) unions sketches but returns a new sketch instead of a count, so you can build a weekly sketch table and later merge those into monthly, monthly into quarterly — staged rollups where each level is derived from the one below.
5. Any arbitrary slice (a set of countries over a date range) is answered by HLL_COUNT.MERGE over the matching daily cells — the SQL expression of "select cells, merge, count." The events table is scanned once to build the sketches; every downstream question hits the compact sketch table.

Output.

Query	Returns	Re-scans events?
APPROX_COUNT_DISTINCT	approx count	yes (one pass)
HLL_COUNT.INIT	stored sketch per cell	one-time build
HLL_COUNT.MERGE	count from merged sketches	no
HLL_COUNT.MERGE_PARTIAL	new merged sketch	no
slice query	count for any country/date set	no

Rule of thumb. Use APPROX_COUNT_DISTINCT for ad-hoc dashboards; use HLL_COUNT.INIT + HLL_COUNT.MERGE/MERGE_PARTIAL to store finest-grain sketches once and derive every rollup and slice without re-scanning the fact table.

Worked example — Spark approx_count_distinct and tuning rsd

Detailed explanation. In Spark the accuracy knob is rsd (relative standard deviation), and understanding that it is the 1.04/sqrt(m) error lets you set it correctly instead of guessing. Show the call and the memory/accuracy trade of tightening rsd.

• The call. approx_count_distinct(col, rsd); default rsd = 0.05 (5% error).
• The mapping. rsd = 1.04/sqrt(m) → m = (1.04/rsd)^2. Halving rsd quadruples m and the memory.
• The advice. Set rsd to the error you actually need; over-tightening it (e.g. 0.001) blows up memory for accuracy nobody will notice.

Question. Count approximate distinct users per day in Spark at 2% error, and show what rsd implies for the register count.

Input.

Field	Value
Column	user_id
Target error	2% → rsd = 0.02
Implied m	(1.04/0.02)^2 ≈ 2,704
Default rsd	0.05 (5%)

Code.

from pyspark.sql import functions as F

# Approximate distinct users per day at ~2% error
daily_uniques = (
    events
    .groupBy("event_date")
    .agg(F.approx_count_distinct("user_id", rsd=0.02).alias("approx_dau"))
)
daily_uniques.show()

# What does rsd imply for register count / memory?
def m_from_rsd(rsd: float) -> int:
    return round((1.04 / rsd) ** 2)

for rsd in (0.05, 0.02, 0.01, 0.005):
    m = m_from_rsd(rsd)
    print(f"rsd={rsd:<6}  m≈{m:>8,}  memory≈{m*6/8/1024:6.1f} KB")

Step-by-step explanation.

1. approx_count_distinct("user_id", rsd=0.02) tells Spark to build HLL sketches sized so the relative standard error is ~2%. Spark computes per-partition sketches and merges them during the shuffle — the mergeability from section 4 is what makes this distributed.
2. The rsd parameter is the accuracy contract: rsd = 1.04/sqrt(m), so rsd = 0.02 implies m ≈ (1.04/0.02)^2 ≈ 2704 registers (roughly p = 12). You are choosing register count indirectly by choosing tolerable error.
3. The loop shows the quadratic cost: halving rsd from 0.02 to 0.01 quadruples m (~2,704 → ~10,816) and the per-sketch memory. Accuracy is expensive, and it is bought in squares.
4. The default rsd = 0.05 (5%) is coarse but cheap; for reporting-grade numbers 0.01–0.02 is typical. Going to 0.001 would demand ~1,000,000 registers per group — rarely justified.
5. Because Spark shuffles sketches rather than raw ids, a distinct-count aggregation over billions of rows stays cheap in network and memory — the same "move kilobytes not terabytes" win, wrapped in one function call.

Output.

rsd	Implied m	Approx memory	Use case
0.05	~433	~0.3 KB	rough, default
0.02	~2,704	~2.0 KB	reporting
0.01	~10,816	~7.9 KB	high accuracy
0.005	~43,264	~31.7 KB	rarely needed

Rule of thumb. In Spark, rsd is the relative standard error — set it to the accuracy you actually need. Because m = (1.04/rsd)^2, tightening rsd costs memory quadratically; 0.01–0.02 is the usual reporting range.

Data engineering interview question on choosing an HLL engine

A senior interviewer might ask: "You need real-time per-page unique visitors on a live dashboard and historical unique-user analytics with arbitrary date-range and segment slicing over a warehouse. Which HLL implementations do you use for each, how do the sketches flow between the real-time and batch worlds, and what precision do you standardise on?"

Solution Using Redis for real-time and BigQuery HLL sketches for historical, standardised at ~p=14/15

# Real-time tier (Redis) — sub-millisecond per-page uniques
PFADD  uv:page:42:2026-09-05  <visitor_id>      # on every pageview (idempotent)
PFCOUNT uv:page:42:2026-09-05                    # live dashboard read (~0.8% error)
# Nightly: export the day's raw (or de-duped) ids to the warehouse for the batch tier.

-- Batch/historical tier (BigQuery) — arbitrary slicing via stored sketches
-- Build finest-grain sketches once, precision 15 (~0.65% error).
CREATE OR REPLACE TABLE uv_daily_sketch AS
SELECT country, event_date,
       HLL_COUNT.INIT(user_id, 15) AS sketch
FROM   events
GROUP  BY country, event_date;

-- Any historical question = merge the matching cells (no fact re-scan)
SELECT HLL_COUNT.MERGE(sketch) AS distinct_users
FROM   uv_daily_sketch
WHERE  country IN ('US','CA','MX')
  AND  event_date BETWEEN '2026-08-01' AND '2026-08-31';

Step-by-step trace.

Concern	Real-time (Redis)	Historical (BigQuery)
Latency	sub-ms PFADD/PFCOUNT	seconds per query
Granularity	per (page, day)	per (country, day) sketch cells
Accuracy	p=14 → ~0.81%	precision 15 → ~0.65%
Rollups	PFMERGE	HLL_COUNT.MERGE / MERGE_PARTIAL
Slicing	key patterns	merge any matching cells
Cross-tier	export ids nightly	rebuild sketches from ids

Redis serves the live dashboard: PFADD on every event, PFCOUNT for instant per-page uniques, ≤ 12 KB per key. The warehouse serves history: build HLL_COUNT.INIT sketches per (country, day) once, then answer any date-range/segment question by merging cells. The two tiers do not share a binary sketch format (Redis's encoding is its own), so the hand-off is the raw/de-duped ids exported nightly and re-INIT-ed in BigQuery — each tier keeps its native, compatible sketches.

Output:

Need	Engine	API	Why
Live per-page uniques	Redis	PFADD/PFCOUNT	sub-ms, in-memory
Live rollup	Redis	PFMERGE	union daily keys
Historical slicing	BigQuery	HLL_COUNT.MERGE	any cell combination
Staged rollups	BigQuery	HLL_COUNT.MERGE_PARTIAL	daily→weekly→monthly sketches
Ad-hoc count	BigQuery	APPROX_COUNT_DISTINCT	one-off dashboards

Why this works — concept by concept:

• Right tool per latency class — Redis's in-memory HLL answers in sub-millisecond time for a live dashboard, while BigQuery's stored sketches answer arbitrary historical slices in seconds; each plays to its strength instead of forcing one engine to do both.
• Sketch-per-cell in the warehouse — HLL_COUNT.INIT per (country, day) plus HLL_COUNT.MERGE at query time is the section-4 design in SQL: compute finest grain once, derive every slice by merging, never re-scan facts.
• Standardised precision — both tiers sit near p = 14/15 (~0.6–0.8% error), so accuracy is consistent across the product and nobody is surprised by a tier that reports a different number.
• Cross-tier via ids, not binary sketches — Redis and BigQuery do not share an HLL wire format, so the nightly hand-off ships ids and re-builds sketches natively, rather than pretending incompatible sketches can be merged.
• Cost — Redis: ≤ 12 KB per live key, O(1) ops. BigQuery: one fact scan to build sketches, then O(cells) merges per query and cells × sketch storage. Both are bounded and independent of raw event volume, which is the entire point of using HLL over exact distinct counts.

Cardinality
Topic — cardinality
Applied distinct-count problems (Redis / warehouse / Spark)

Practice →

Statistics
Topic — statistics
Error-budget and precision-tuning problems

Practice →

---

Cheat sheet — HyperLogLog recipes

• When to reach for HLL. Use HyperLogLog when cardinality can exceed a few million, you can tolerate ~1% error, and you need fixed memory or mergeable partial counts. Use an exact set/COUNT(DISTINCT) when the count is small or must be perfect (billing, compliance). Use a Roaring bitmap when keys are small dense integers and you want exactness cheaply.
• The estimator. E = alpha_m × m^2 / Σ_j 2^(-M[j]), a harmonic mean over m = 2^p registers. alpha_m = 0.7213/(1 + 1.079/m) for m ≥ 128 (0.673/0.697/0.709 for m=16/32/64). Register M[j] = max leading-zero-count (rho) routed to bucket j.
• The add path. h = hash(item); idx = top p bits; rho = position of leftmost 1-bit in the remaining bits; M[idx] = max(M[idx], rho). O(1), idempotent for duplicates — which is why it counts distinct items.
• Precision → memory → error. p=10→0.75 KB/~3.25%; p=12→3 KB/~1.6%; p=14→12 KB/~0.81% (Redis default); p=16→48 KB/~0.41%. Error = 1.04/sqrt(m); memory = m × 6 bits. Accuracy improves only with sqrt(memory).
• Low-cardinality correction. If the raw estimate ≤ 2.5m and V registers are still zero, use linear counting E = m × ln(m/V) — far more accurate than harmonic mean when registers are mostly empty.
• HLL++ upgrades. 64-bit hash (kills the 32-bit large-range correction and collision bias), an empirical bias-correction table for the intermediate range (removes branch-select discontinuities), and a sparse encoding for low cardinality (bytes instead of 12 KB, and more accurate).
• Merge = element-wise max. merged[j] = max(A[j], B[j]). Lossless, commutative, associative, idempotent; "merge of parts" is byte-identical to "sketch of the whole." Requires identical precision p.
• Never add HLL counts. To combine sketches, merge the register arrays then count once — adding two counts double-counts the overlap. Redis multi-key PFCOUNT and BigQuery HLL_COUNT.MERGE both compute the union, not the sum.
• Rollups. Store finest-grain sketches (per day, per cell); derive weekly/monthly/segment counts by merging. Compute the expensive aggregation once; every coarser or sliced view is a cheap merge with no raw re-scan.
• Intersections are noisy. |A ∩ B| = |A| + |B| - |A ∪ B| via inclusion-exclusion; subtracting error-bearing estimates amplifies error, so small overlaps of large sets are unreliable. Use Theta sketches or MinHash when set overlap must be accurate.
• Redis recipe. One key per (entity, time-bucket): PFADD key elem… to write, PFCOUNT key to read (or PFCOUNT k1 k2… for a union), PFMERGE dst src… to materialise a rollup. Dense cap 12 KB; sparse for small keys.
• Warehouse / Spark recipe. BigQuery: APPROX_COUNT_DISTINCT(col) for ad-hoc; HLL_COUNT.INIT(col, p) + HLL_COUNT.MERGE/MERGE_PARTIAL for stored, mergeable sketches. Spark: approx_count_distinct(col, rsd) where rsd = 1.04/sqrt(m) and m = (1.04/rsd)^2 — set rsd to the error you need; tightening it costs memory quadratically.

Frequently asked questions

What is HyperLogLog in one sentence?

HyperLogLog is a probabilistic data structure (a "sketch") that estimates the number of distinct elements in a stream — its cardinality — using a small fixed amount of memory and a bounded relative error, by hashing each element, measuring how many leading zeros appear in the hash, and keeping only the maximum such count per bucket in a tiny array of registers. Because it never stores the elements themselves, it can count billions of distinct values in around 12 kilobytes with roughly 0.8% error, which is why it powers approximate distinct count everywhere from Redis to BigQuery to Spark. It is the standard answer to "count uniques at scale" in both production systems and data-engineering interviews.

How accurate is HyperLogLog?

HyperLogLog's accuracy is set by its register count m = 2^p: the relative standard error is 1.04 / sqrt(m), which is about 0.81% at the common p = 14 (16,384 registers, 12 KB) configuration. That figure is a standard deviation, so roughly 68% of estimates fall within ±1 error-unit of the truth, ~95% within ±2, and ~99.7% within ±3 — a single reported number can be off by more than the headline percentage with a known, small probability. You improve accuracy only by adding registers, and because the error shrinks with the square root of m, halving the error costs four times the memory. Low-cardinality counts stay accurate thanks to a linear-counting correction, and modern HLL++ implementations use a 64-bit hash and an empirical bias table to stay unbiased across the whole range.

How much memory does HyperLogLog use?

A HyperLogLog uses m × 6 bits, where m = 2^p is the register count and 6 bits holds a leading-zero count up to 63 (enough for a 64-bit hash). At the default p = 14 that is 16,384 registers × 6 bits = 12,288 bytes, about 12 KB — and, crucially, this footprint is fixed regardless of cardinality, so the same 12 KB counts a hundred distinct values or a hundred billion. Coarser precisions are smaller (p = 10 ≈ 0.75 KB) and finer ones larger (p = 16 ≈ 48 KB). Implementations like Redis and Google's HLL++ also use a sparse representation for low-cardinality sketches, storing an explicit list of non-zero registers in as little as a few dozen bytes and only expanding to the dense array as the count grows.

Can you merge HyperLogLog sketches?

Yes — mergeability is HyperLogLog's defining superpower. The union of two sketches built at the same precision is the element-wise maximum of their register arrays, and this merge is lossless, commutative, associative, and idempotent, so "merge of the parts" equals "sketch of the whole" exactly. This is what makes HLL the default for distributed and streaming distinct counts: each partition, shard, or time-window builds its own sketch independently, and a reducer combines them by taking maxes — moving kilobytes of sketch instead of terabytes of raw keys. The one hard rule is that the sketches must share the same precision p; you cannot directly merge a p=12 and a p=14 sketch (you can only down-sample the finer one). Note that exact COUNT(DISTINCT) results cannot be merged this way, because two counts carry no information about their overlap.

HyperLogLog vs COUNT(DISTINCT) — when do I pick each?

Pick exact COUNT(DISTINCT) when the cardinality is small enough to fit an exact hash set in memory, or when the answer must be perfect — billing, licence counts, regulatory reporting, anything where an off-by-1% is unacceptable. Pick HyperLogLog when cardinality can reach millions or billions, when you need a fixed memory footprint you can capacity-plan, or when you need mergeable partial counts for distributed aggregation and rollups. The core trade is exactness versus scalability: exact counting is Θ(cardinality) memory and cannot be merged; HLL is Θ(1) memory with ~0.8% error and merges losslessly. Most warehouses make this explicit — COUNT(DISTINCT col) for exactness, APPROX_COUNT_DISTINCT(col) for the HLL-backed fast path — and senior engineers reach for the approximate version by default on dashboards and the exact version only when correctness is contractual.

Can HyperLogLog compute intersections?

Not directly — HyperLogLog only supports union (element-wise max) natively. You can estimate an intersection via inclusion-exclusion: |A ∩ B| = |A| + |B| - |A ∪ B|, where the union is obtained by merging. The problem is error amplification: each of the three terms carries its own ~0.8% error, and subtracting large, error-bearing estimates to produce a comparatively small result can make the intersection wildly inaccurate, especially when the true overlap is small relative to the set sizes. So HLL intersections are fine as a rough signal but should not be trusted for precise set-overlap, Jaccard similarity, or set-difference metrics. When you need accurate intersections, use Theta sketches (which support set operations directly with error bounds) or MinHash (built for Jaccard similarity).

Practice on PipeCode

• Drill the cardinality practice library → for the distinct-count, sketch, and rollup problems senior interviewers love.
• Sharpen the fundamentals on the data-structures practice library → for probabilistic structures — HyperLogLog, Bloom filters, count-min sketch, and MinHash.
• Build estimation intuition on the statistics practice library → for standard error, bias correction, and confidence-band reasoning.
• Stack the prerequisites against PipeCode's broader 450+ data-engineering catalogue to anchor the memory-vs-accuracy trade against real graded inputs.

Lock in cardinality-estimation muscle memory

Docs explain the algorithm. PipeCode drills explain the decision — when an exact set OOMs and a sketch survives, why sampling fails for cardinality, when the low-cardinality linear-counting correction fires, why you merge sketches instead of adding counts, and when HLL intersections are too noisy to trust. Pipecode.ai is Leetcode for Data Engineering — pattern-first practice tuned for the production trade-offs senior data engineers actually face.

Practice cardinality problems →
Practice data-structure problems →