Sampling vs Sketch Based Techniques

Two Families of Approximation: AQP splits into two main approaches: sampling based and sketch based techniques. Understanding which to use and when is critical for system design interviews. Sampling Based AQP: Sampling maintains subsets of your data at different rates. You might create a 1% uniform sample where every row has a 1 in 100 chance of being included. The system runs normal Structured Query Language (SQL) style queries on these smaller tables and scales results appropriately. For example, a COUNT on a 1% sample gets multiplied by 100. The advantage is generality. Any SQL query that works on the full table works on the sample. Joins work. Filters work. You just accept some statistical variance in the results. Companies typically maintain multiple sample rates: 0.1%, 1%, and 10% samples of the same base table, then the query optimizer picks the smallest sample that meets accuracy requirements. The disadvantage is storage overhead. A 1% sample of a 5 PB table is still 50 TB. You also need batch jobs to keep samples fresh, which adds operational complexity. Sketch Based AQP: Sketches are specialized probabilistic data structures that track aggregate statistics in sublinear space. The most common is HyperLogLog (HLL), which estimates distinct counts using only 1 to 2 KB per group regardless of cardinality. A sketch tracking 100 million unique users takes the same space as a sketch tracking 100 unique users. Sketches have magical properties for distributed systems: they are mergeable. You can compute sketches per partition, per hour, per region, then merge them at query time with simple union operations. This makes them perfect for streaming systems where data arrives continuously. The tradeoff is specificity. Each sketch type supports exactly one operation. HyperLogLog does distinct counts. Quantile sketches do percentiles. Count Min Sketch does frequency estimation. You cannot run arbitrary SQL on a sketch. Real World Hybrid Approach: Production systems combine both. Google BigQuery offers approximate aggregation functions that transparently use HLL sketches for distinct counts, making cardinality linear in number of groups rather than number of rows. For a query grouping by 1,000 values across billions of rows, this changes I/O from terabytes to megabytes. Apache Druid and Pinot use sketches for known heavy queries like cardinality and quantiles, then fall back to sampling or exact computation for arbitrary aggregations. Uber runs approximate latency percentiles from sketch based structures updated in real time, while exploratory queries from data scientists run on sampled tables refreshed nightly.