HyperLogLog
Probabilistisk datastruktur som räknar distinkta element i en stream med konstant minne — Flajolet et al. (2007). 12 KB räcker för att räkna miljarder unika items med ~2 % fel.
Magin: hash nycklar → räkna antal initiala nollor i binär hash → längsta sekvensen säger något om hur många unika du sett (ju mer unika, desto mer sannolikt att hitta en lång nollsekvens). Median över m "bins" minskar varians.
Driver Redis PFCOUNT, Presto/Trino approximate distinct counts, BigQuery, Druid. Vinst mot exakt count(distinct): går från MB:s minne per query till KB:s, och mergeable mellan partitioner.