HyperLogLog (HLL)

HyperLogLog works by hashing each incoming element into a uniformly distributed bit string, then splitting that hash into two parts: a bucket index (the first p bits, selecting one of m = 2^p registers) and a remainder used to compute the position of the leftmost 1-bit. Each register stores only the maximum leftmost-1-bit position observed for hashes routed to it. Because the probability of seeing a run of k leading zeros drops exponentially, the maximum observed run length across many independent buckets is a strong statistical proxy for log2(cardinality). The final estimate is derived from the harmonic mean of all register values, scaled by a bias-correction constant (alpha_m) empirically tuned to counteract small-range and large-range estimation bias.

Two failure regions require correction. For very small cardinalities, hash collisions across the limited register space bias the harmonic mean upward, so implementations fall back to linear counting (based on the fraction of empty registers) below a threshold. For very large cardinalities approaching the hash space limit, a large-range correction adjusts for saturation. Modern implementations (e.g., Google’s HLL++, used in BigQuery and Presto/Trino) also use a sparse representation when the sketch is mostly empty, storing only nonzero register indices, and lazily convert to the dense fixed-size array once occupancy crosses a threshold — this matters operationally because sketch size in transit and on disk is not always the theoretical constant.

The property that makes HLL indispensable in distributed architectures is mergeability: two sketches built independently over disjoint data shards can be combined into a single sketch representing the union simply by taking the element-wise maximum of their registers. This enables cardinality estimation to be computed at ingestion time, per shard, per region, or per time window, and then rolled up without re-scanning raw data — critical for streaming pipelines (Kafka Streams, Flink) and time-series/observability systems where recomputing exact `COUNT(DISTINCT)` over retained raw events is cost-prohibitive. Redis exposes this directly via PFADD, PFCOUNT, and PFMERGE; Elasticsearch’s cardinality aggregation and Apache DataSketches’ HLL sketch follow the same underlying construction.

Standard error scales as approximately 1.04 / sqrt(m), meaning precision is purely a function of register count (memory), not of the underlying dataset size — a 16KB sketch (p=14, 16384 registers) yields roughly 0.8% relative error regardless of whether the true cardinality is one million or one billion. This decoupling of accuracy from data volume is the core architectural tradeoff: engineers must choose p upfront based on acceptable error, since increasing precision later requires re-ingesting raw data, as sketches cannot be “refined” after the fact, only merged with same-or-lower-precision peers.

HyperLogLog is best understood as a deliberate abandonment of exactness in exchange for a fixed, predictable, and horizontally composable cost model, which is precisely what makes it viable for cardinality queries at the scale where exact distinct-counting via hash sets or sort-based deduplication becomes operationally and financially untenable.