Abstract

Approximate query processing (AQP) has long promised interactive analytics over petabyte-scale datasets by trading a small, bounded error margin for dramatic latency reductions. Sketch data structures sit at the heart of practical AQP implementations, encoding statistical summaries of entire datasets into fixed-memory footprints. In late 2025, mainstream warehouse engines have moved well beyond simple HyperLogLog cardinality estimation toward richer sketch families that answer a wider class of analytical queries with sub-second response times and rigorous error guarantees.

Beyond HyperLogLog - Sketch Families in Production

HyperLogLog remains the industry standard for COUNT DISTINCT estimation, and implementations in BigQuery, Snowflake, and Trino expose it directly via APPROX_COUNT_DISTINCT. But HyperLogLog answers exactly one question. The Count-Min sketch extends the concept to frequency queries: given a high-cardinality dimension, it returns approximate counts per distinct value using a two-dimensional hash array. Practical deployments tune the width and depth parameters (typically 2^14 width, depth 7) to hold error below 0.1% with 99% confidence, fitting in under 1 MB of memory per sketch.

For quantile queries, the t-digest and KLL (Karnin-Lang-Liberty) sketches have both landed in production-grade libraries. Apache DataSketches, maintained by Yahoo, ships KLL as its primary quantile sketch. Trino exposes approx_percentile through it. The sketch merges correctly across partitions, enabling distributed computation without centralizing raw data.

Integration Patterns in Warehouse Engines

Modern warehouse planners treat sketches as first-class aggregation intermediates. Snowflake’s APPROX_PERCENTILE persists sketch state across incremental materialized view refreshes, updating only affected partitions. BigQuery’s BI Engine pre-computes HLL++ sketches at ingestion time for INFORMATION_SCHEMA tables, making cardinality lookups microsecond-fast.

Composability is the key integration challenge. Sketch bytes must be serializable, merge-able, and version-stable. Apache DataSketches defines a versioned binary format adopted by several engines as a common interchange - a sketch computed in Spark can merge with one in Trino without re-reading source data.

Error Budgeting and Limitations

Deploying AQP effectively requires matching query class to acceptable error tolerance. Operational dashboards tolerate 2-3% relative error for trend lines; billing-critical aggregations do not. A routing layer - query annotation or a planner hint - directs exploratory queries to sketch-backed paths and exact queries through full scans.

Sketches have real limits. Joins across sketches do not compose correctly in general: a sketch of table_A UNION table_B is not the union of their individual sketches unless the family explicitly supports set operations (as HLL does for union, not intersection). Median estimation via t-digest has known tail bias under extreme skew. Correctness guarantees require users to understand what error bounds mean - still an underserved UX problem in most warehouse consoles.