Mergeable Summaries for High Scale, High Cardinality Analytics
summary
Describes a practical system that turns commutative associative merge operators into mergeable summaries used at Microsoft, Sisu, and in Apache Druid to answer top-K, quantiles, and distinct queries without storing raw events. Implements a top-K fixed-size hash map (100 entries ≈ 1% error, 1000 ≈ 0.1%), a moment-based estimator (min, max, count, sum, sumsq, sumcubed) to reconstruct distributions, and reservoir sampling for arbitrary UDFs; production workloads merge hundreds to thousands of sketches per query and see ~5x speedup in merged-heavy queries.
AI-written summary · about
chapters (8)
- 0:00High cardinality analytics intro
- 2:53CRDTs to mergeable summaries
- 7:45Mergeable summaries for cubes
- 12:35Top K summaries accuracy
- 15:01Percentile and quantile estimation
- 18:53Handling arbitrary user-defined functions
- 21:19Production deployment lessons
- 23:44Summary and future
related talks
42mMergeable Summaries and the Data Sketches Library
38mAdd ALL the things: abstract algebra meets analytics
31mAnswering Multi-dimensional Queries on Massive Datasets
39mUsing Monoids for Large Scale Business Stats
16mA Compiler for Fused Relational Operations on Multisets
25mHigh on Cardinality, Low on Memory
01h 04mQuery Optimization and Acceleration at Dremio
31mSummingbird: A Streaming Map-Reduce API for Storm, Hadoop, & More