HyperLogLog
Probabilistic data structure that counts distinct elements in a stream using constant memory — Flajolet et al. (2007). 12 KB suffices to count billions of unique items with ~2 % error.
The trick: hash keys → count leading zeros in binary hash → the longest run says something about how many unique values you've seen (more uniques → more likely to find a long zero run). Median across m "bins" reduces variance.
Powers Redis PFCOUNT, Presto/Trino approximate distinct counts, BigQuery, Druid. Win over exact count(distinct): from MB of memory per query to KB, and mergeable across partitions.