HyperLogLog：BigQuery が 1 兆件のユニーク数を 16KB で数えるアルゴリズム

import hashlibimport math
class HLL:    def __init__(self, b=12):        """b=12 → m=4096 レジスタ → 誤差 約 1.6%"""        self.b = b        self.m = 1 << b   # レジスタ数 (2^b)        self.registers = [0] * self.m
    def add(self, item):        # 64 bit ハッシュ        h = int(hashlib.sha256(str(item).encode()).hexdigest(), 16)        # 先頭 b bit でレジスタ index、残り bits で ρ (末尾 0 の連続数+1)        idx = h & (self.m - 1)        w = h >> self.b        rho = (w & -w).bit_length() if w else 64        # 各レジスタは観測した最大 ρ を保持        self.registers[idx] = max(self.registers[idx], rho)
    def count(self):        # 調和平均で推定        alpha = 0.7213 / (1 + 1.079 / self.m)        z = sum(2 ** -r for r in self.registers)        e = alpha * self.m * self.m / z        # 小規模補正 (linear counting)        if e <= 2.5 * self.m:            zeros = self.registers.count(0)            if zeros:                e = self.m * math.log(self.m / zeros)        return int(e)
    def merge(self, other):        """2 つの HLL を結合 (UNION の正確な実装)"""        assert self.m == other.m        self.registers = [max(a, b) for a, b in zip(self.registers, other.registers)]
# 動作確認hll = HLL(b=12)true_unique = 100_000for i in range(true_unique):    hll.add(f"user_{i}")
estimated = hll.count()print(f"True: {true_unique}, Estimated: {estimated}")print(f"Error: {abs(estimated - true_unique) / true_unique * 100:.2f}%")print(f"Memory: {hll.m * 4 / 1024:.1f} KB")
# 実機実行結果:# True: 100000, Estimated: 98985# Error: 1.01%# Memory: 16.0 KB

# pip install datasketchfrom datasketch import HyperLogLog
hll = HyperLogLog(p=12)for i in range(100_000):    hll.update(f"user_{i}".encode("utf-8"))
print(f"Estimated: {int(hll.count())}")
# 結合 (異なるサーバの集計を統合)hll1 = HyperLogLog(p=12)hll2 = HyperLogLog(p=12)for i in range(50_000):     hll1.update(f"u{i}".encode())for i in range(30_000, 80_000):  hll2.update(f"u{i}".encode())
merged = HyperLogLog(p=12)merged.merge(hll1)merged.merge(hll2)# True unique = 80,000 (重複部分を考慮)print(f"Merged estimate: {int(merged.count())}")

-- BigQuery: APPROX_COUNT_DISTINCTSELECT  date,  APPROX_COUNT_DISTINCT(user_id) AS unique_usersFROM eventsWHERE date >= DATE_SUB(CURRENT_DATE(), INTERVAL 30 DAY)GROUP BY date;
-- Snowflake / Redshift も同様の関数-- 通常の COUNT(DISTINCT) の 10-100 倍速い
-- HLL_SKETCH を使った高度な集計 (BigQuery)WITH daily AS (  SELECT    date,    HLL_COUNT.INIT(user_id) AS sketch  FROM events  GROUP BY date)SELECT HLL_COUNT.MERGE(sketch) AS unique_30daysFROM daily;