Exact answers to queries like COUNT DISTINCT are prohibitively expensive at scale because they require storing every unique value seen. Data sketches — probabilistic data structures from the streaming algorithms field — solve this by trading exactness for speed, producing mathematically bounded approximate answers from a single pass over data in kilobytes of memory. The post covers the core mechanics (hashing, keeping smallest hash values, estimating on demand), the key property of mergeability that enables parallel processing and pre-aggregation, and a taxonomy of sketch families: cardinality sketches (Theta, HyperLogLog, CPC, Tuple), quantiles sketches (Classic, KLL, REQ), frequent items sketches, and reservoir sampling. Trade-offs are addressed honestly: stakeholder resistance, compounding error from stacked set operations, sizing tuning, irreversibility, storage explosion in high-dimensional cubes, and binary format incompatibility between systems. Sketches are inappropriate for financial/compliance reporting, small datasets, or when actual values (not statistics) are needed.
