HyperLogLog: Counting a Billion Uniques in 1.5 KB of Memory

Posted on

Every analytics dashboard has one question that looks trivial and isn’t: how many unique users did this? You can run COUNT(DISTINCT user_id) on a small table and get an exact answer in milliseconds. Run the same query on a few billion rows and you’ll discover that exact distinct counting is one of the most expensive things a database can do — it needs to remember every distinct value it has seen, which means memory proportional to cardinality. A billion distinct users means tracking something on the order of a billion values, whether that’s a hash set in RAM or a temp file on disk.

HyperLogLog (HLL) is the reason this question is answerable at scale. It estimates cardinalities beyond a billion with a typical standard error of about 2% using roughly 1.5 KB of memory. Not gigabytes — kilobytes. The trade-off is that the answer is approximate: ask “how many uniques?” and you get 48,391,226 when the true answer is 48,412,003. For a dashboard tile, that’s fine. For a billing reconciliation, it isn’t — and knowing which side of that line your query falls on is the entire skill of using HLL well.

This post walks through how the algorithm actually works (it’s simpler than the name suggests), where it lives in the tools you already use, and the operational details — mergeability, set operations, and error behavior — that determine whether it’s the right estimator for your workload.

The Impossibility It Sidesteps

Exact distinct counting requires memory that grows linearly with the number of distinct values. There’s no clever data structure around this in the general case: if the stream can contain n distinct elements, an exact counter must be able to distinguish all of them, and the information-theoretic floor is roughly log₂ of the number of possible sets. For real-world cardinalities, that floor is far above the memory budget of a typical aggregation node.

HyperLogLog trades exactness for a fixed memory bound. A sketch has a constant size — a few kilobytes — no matter whether it has seen a thousand elements or a trillion. The estimate comes with a well-defined error profile: for a sketch with m registers, the standard error is approximately 1.04 / sqrt(m). With the common m = 16384 (2^14 registers, about 12 bits of hashing per element for register selection), that’s roughly 0.81%. With m = 1024, it’s about 3.25%. You choose the register count as an accuracy/memory dial, and the dial is set once — the error does not grow as cardinality grows. That last property is what makes it fundamentally different from sampling, where the absolute error scales with the population.

How the Estimate Emerges From Coin Flips

The core intuition is a hash used as a source of randomness. Feed every element through a good hash function and look at the binary representation of the result. If the hash behaves like random bits, then the probability of seeing a hash that starts with k zeros is 2^(-k). If you’ve observed a run of k leading zeros somewhere in your stream, it’s likely you’ve seen something on the order of 2^k distinct elements — because with fewer, that pattern would probably not have occurred yet.

A single “maximum run of leading zeros” statistic is a terrible estimator on its own — one unlucky element with a long zero prefix throws it off by a huge factor. HyperLogLog fixes this with two ideas:

  • Stochastic averaging. Split the hash into two parts: the first b bits index into an array of m = 2^b registers, and the remaining bits are used for the leading-zero count. Each register independently tracks the longest run of zeros seen among elements hashing to its bucket. Now the estimate is an average over m independent experiments instead of a single fragile one.
  • Harmonic mean aggregation. The registers are combined with a harmonic mean rather than an arithmetic one, weighted by a bias-correction constant. The harmonic mean is dominated by the small values, which keeps outliers — those unlucky long-zero-prefix elements — from dragging the estimate upward. The constant 0.539 in the original formulation comes from correcting the residual bias of the estimator.

In pseudocode, the update looks like this:

import hashlib
from math import log

def hll_add(sketch, p, value: bytes):
    h = int.from_bytes(hashlib.sha256(value).digest(), "big")
    idx = h >> (256 - p)            # first p bits pick the register
    suffix = h & ((1 << (256 - p)) - 1)
    rank = (256 - p) - suffix.bit_length() + 1  # leading zeros + 1
    sketch[idx] = max(sketch[idx], rank)

def hll_count(sketch, p):
    m = 1 << p
    alpha = 0.5199  # bias constant for this range; others exist for small m
    z = sum(2.0 ** -r for r in sketch)
    raw = alpha * m * m / z
    v = sketch.count(0)
    if raw <= 2.5 * m and v > 0:    # small-range correction
        raw = m * log(m / v)
    return int(raw)

Two details in that snippet are worth pausing on because they explain most real-world surprises. The small-range correction handles the case where the estimate is near the number of registers and many registers are still zero — the raw formula systematically undershoots there, so the estimator switches to linear counting. And the bias constant differs by register count; production implementations (notably Google’s HLL++ engineering paper) add empirical bias-correction tables on top of the raw estimator for medium ranges, which is why two “correct” HLL implementations can disagree slightly on the same input.

Where You Already Have HyperLogLog

You probably don’t need to implement this — most analytical infrastructure ships it. The API shapes differ, and those differences matter operationally:

  • Redis exposes the sketch as a first-class data type: PFADD to insert, PFCOUNT to estimate, PFMERGE to union sketches. Each key holds a fixed 12 KB sketch with ~0.81% standard error. The catch is that PFCOUNT on a single key is fast, but counting across many keys is O(n) over the keys and may mutate a cached value — the docs are explicit that you shouldn’t call it in a hot loop.
  • PostgreSQL has no native HLL in core; the common route is the postgresql-hll extension (originally from Citus), which adds an hll type with tunable log2m parameters and full sketch serialization, so sketches can be stored in tables and aggregated later.
  • BigQuery has the HLL_COUNT family: HLL_COUNT.INIT builds sketches you can store in a column, HLL_COUNT.MERGE combines them, and HLL_COUNT.EXTRACT produces the number. The init/merge split is the interesting part — it means you can precompute daily sketches and answer “monthly uniques” by merging 30 small sketches instead of rescanning a month of events.
  • ClickHouse offers uniq() (its own variant), uniqCombined() (which adaptively switches representations as cardinality grows), and uniqHLL12(), the classic 12-bit HLL. ClickHouse’s defaults are tuned for speed and the estimates are noticeably rougher than a full HLL.
  • Spark‘s approx_count_distinct is HLL under the hood, with an optional rsd (relative standard deviation) parameter that maps back to the register count.
  • DuckDB and Elasticsearch (the cardinality aggregation) round out the list — same algorithm, same knobs.

The unifying pattern across all of these: the sketch is a value. It can be computed incrementally, stored, transmitted, and combined. That’s the property exact counting can never have.

Mergeability Is the Superpower

The single most useful property of an HLL sketch is that unions are exact on the sketch level: merging two sketches means taking the per-register maximum, and the result is precisely the sketch you would have built by feeding the union of both element sets into one sketch. Merge a million sketches and the merged sketch is still ~12 KB with the same error bound.

This reshapes how you build aggregation pipelines. Instead of storing event rows and recomputing uniques per query, store sketches:

-- BigQuery: materialize daily HLL sketches, merge on demand
CREATE OR REPLACE TABLE analytics.daily_unique_sketches AS
SELECT
  event_date,
  country,
  HLL_COUNT.INIT(user_id) AS user_sketch
FROM analytics.events
GROUP BY event_date, country;

-- Monthly uniques = merge 30 tiny sketches, not scan 30 days of events
SELECT
  country,
  HLL_COUNT.EXTRACT(HLL_COUNT.MERGE(user_sketch)) AS monthly_uniques
FROM analytics.daily_unique_sketches
WHERE event_date BETWEEN '2026-09-01' AND '2026-09-30'
GROUP BY country;

The same pattern works with Redis PFMERGE for real-time dashboards and with postgresql-hll‘s hll_add_agg/hll_union_agg in materialized views. The sketch becomes a precomputed, composable summary that answers a whole family of questions — daily, weekly, monthly, per-country, per-platform — from the same few kilobytes.

Set Operations: Where the Sharp Edges Are

Unions are free, but the operations people actually ask for — intersections and differences — are where HLL bites. Neither is directly supported, because the sketch is a lossy summary: you cannot determine which elements two sketches share. The standard workaround is the inclusion–exclusion principle:

|A ∩ B| ≈ |A| + |B| − |A ∪ B|       -- all three from sketches
|A − B| ≈ |A| − |A ∩ B|

The problem is error amplification. Each sketch carries an independent error, and intersection errors compound. If A and B overlap heavily — say |A ∩ B| is 5% of |A| — then a 1% error in each of the three terms can easily produce an intersection estimate with 20–40% relative error, or even a negative number. The errors don’t average out; they add in the worst direction. Practical rules:

  • Use sketch-based intersections only when the intersection is a substantial fraction of the union. If two segments barely overlap, the estimate is noise.
  • If intersection accuracy matters, consider a different sketch family entirely — theta sketches (Apache DataSketches) support intersections natively with bounded relative error on the result.
  • Watch for negative results from inclusion–exclusion in production queries; clamp to zero and log, because a negative unique count in a dashboard is a support ticket.

Practical Failure Modes

A few things go wrong repeatedly in production HLL deployments:

  • Weak hash functions. The estimator assumes hash outputs are uniformly random. A hash with clustering (or worse, an identity function on sequential IDs) biases the leading-zero distribution and the estimate drifts. If you control the hashing, use something like xxHash or SHA-derived bits; if the database handles it, leave it alone.
  • Register-count mismatch on merge. Sketches built with different precision parameters can’t be merged meaningfully — Redis will error, some libraries silently truncate. Standardize the precision per pipeline and treat a mismatch as a data incident.
  • Treating the estimate as exact in joins or filters. An HLL result is fine for display and alerting, wrong as an input to another exact computation. Don’t join on it, don’t sum HLL outputs across groups and expect the total to equal the uniques of the whole (they answer different questions — sum of estimates over counts a shared user once per group; the union counts them once).
  • Wrong tool for small cardinalities. Below roughly 10–100K distinct values, exact counting is cheap and HLL just adds error. The estimator earns its keep in the millions-to-trillions range.

When to Reach for It

The decision is genuinely simple. If you need the exact number — billing, reconciliation, anything contractually binding — spend the memory and compute on exact counting, possibly with pre-aggregation. If you need the shape of the number — dashboards, anomaly detection, A/B test guardrails, capacity planning — a sketch with a known error bound is the only approach that scales, and it scales absurdly well: constant memory, mergeable, incremental.

Start by checking what your database already ships. If you’re on BigQuery, the HLL_COUNT functions with materialized sketch tables will likely cut both cost and latency on every unique-count query you have. If you’re on Postgres, add the postgresql-hll extension to your materialized views. If you’re on Redis, a PFADD on the write path and a 12 KB key replaces an entire class of expensive queries. The algorithm is forty years old, the implementations are mature, and the only real cost is making peace with the word “approximately.”

Leave a Reply

Your email address will not be published. Required fields are marked *