Abstract

Exact computation over billion-row datasets is often neither necessary nor achievable within interactive query latency targets. Probabilistic data structures - HyperLogLog, Count-Min Sketch, Bloom filters, T-Digest, and more recently KLL sketches - trade a bounded, configurable error for orders-of-magnitude reduction in memory and computation. These structures are no longer experimental additions to analytics pipelines; they are first-class citizens in DuckDB, Apache Datasketches, ClickHouse, BigQuery, and Snowflake, with well-characterized error bounds and merge semantics that make them composable across distributed partitions. This post examines the operational behavior of these structures, where the error bounds are misunderstood in practice, and how the sketch-merge property enables precomputed approximate analytics at scale.

HyperLogLog and the Distinct Count Problem

Counting distinct values exactly requires maintaining a hash set whose size grows linearly with cardinality - impractical for cardinalities in the hundreds of millions. HyperLogLog (HLL) estimates cardinality using the leading zeros of hashed values, requiring only a few kilobytes of state regardless of input cardinality. The error bound is deterministic: HLL with precision parameter p=14 guarantees less than 0.81% standard error for cardinalities above a few thousand. ClickHouse’s uniqHLL12 function and BigQuery’s APPROX_COUNT_DISTINCT both use HLL variants with similar precision. The less-understood property is mergeability: HLL sketches computed over disjoint partitions can be merged by union to produce a sketch equivalent to running HLL over the combined input. This makes HLL the natural choice for daily distinct-user counts that are precomputed per partition and merged at query time.

Count-Min Sketch for Frequency Estimation

Count-Min Sketch (CMS) estimates the frequency of any item in a stream using a two-dimensional array of counters and multiple hash functions. It overcounts but never undercounts - the error is one-sided. For heavy-hitter detection (finding the top-k most frequent items in a stream), CMS combined with a heap provides a streaming solution that processes each event in O(1) time with bounded memory. The error guarantee depends on the table dimensions: a CMS with width w and depth d guarantees that any frequency estimate is within (total count / w) of the true value with probability 1 - (1/2)^d. At w=65536 and d=5, memory is under 2.5 MB and error bounds are tight enough for most analytical applications. Flink’s native CMS operator and the Apache Datasketches library both expose configurable CMS implementations suitable for production use.

T-Digest and KLL for Quantile Estimation

Quantile computation over a distributed stream requires either sorting the full dataset or using a quantile sketch. T-Digest builds a compressed representation of the data distribution by merging sorted micro-clusters (centroids), with higher resolution near the tails where quantile error is most damaging. KLL (Karnin-Lang-Liberty) sketches, incorporated into Apache Datasketches and now available in several cloud query engines, provide strong theoretical guarantees on maximum quantile error that T-Digest’s heuristic merge does not. For p99 latency monitoring over tens of billions of events, KLL’s tail accuracy advantage over T-Digest is meaningful; for median computation on moderately skewed data, both produce indistinguishable results. Spark’s Greenwald-Khanna-based approxQuantile function predates KLL’s availability and is less accurate at extreme quantiles.

Composability as a Design Pattern

The defining property that makes these structures useful beyond single-query optimization is composability: sketches computed incrementally or across partitions merge into a sketch equivalent to one built over the full input. This enables a pattern where raw event streams are pre-aggregated into sketch columns in a summary table, and interactive queries run against the summary rather than the raw data. A table with one HLL column per dimension, one CMS per metric, and one KLL sketch per latency field can answer distinct-count, frequency, and quantile queries over arbitrary filter combinations without touching the raw events. The engineering cost is the sketch update logic at ingest time; the operational payoff is sub-second query latency over analytical workloads that would otherwise require full scans.