はじめに

業務で、データセットを特定のカラムで集約した際にデータのユニーク数が1 or 2以上を判定するフィルタを実装したかった。
単純にcountDistinctを使って実装することもできるが、より高速に動作するapprox_count_distinctが使えないか気になって挙動を調べた。
他にまとまった記事が見つからなかったため、記事として残しておく。誰かの役に立てば嬉しい。

誤り等遠慮なく指摘してください。

前置き

approx_count_distinctとは

Aggregate function: returns the approximate number of distinct items in a group.

spark sqlの集約関数の一つで、グループ中のユニーク数を高速に推定する関数。
膨大なログからユニークユーザ（UU）数を概算したい時などに使用される。

実体はカーディナリティ推定に使用されるHyperLogLog++[2]と呼ばれる乱択アルゴリズムである。

本題

HyperLogLog++とは

元論文：HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm

HyperLogLog++ とは、カーディナリティ（ユニーク数）推定に用いられるHyperLogLogアルゴリズム[1]をgoogleのエンジニアが改良したもの。
乱数の性質を利用して、高精度かつ効率的にカーディナリティを推定することができる。

基本原理

乱数が大量に存在していて、ユニークな乱数が何個あるか考えたいとする。
HyperLogLogでは確率の考え方を逆手に取ったような方法で、「ある乱数が出現した」という事実から、その乱数の出現確率に基づき「乱数の生成個数」を推定している。
これにより、全ての乱数をメモリに保持しておかなくても「ある乱数が出現した」ことだけわかれば、全体の乱数の個数がわかる。

コイン投げによる例え

コイン投げを例にして説明すると、以下のようになる（[3]を参考にした）。

コインを繰り返し投げたとき、表が連続でk回でる確率は (1/2)^kである。
では、「コインを繰り返し投げる」という試行をN回行った際に、連続で表が出た回数の最大値がkだったとする。
この時、(1/2)^kの確率で発生するような事象が発生したので、試行回数NはN=2^kだったと推定する。
（「連続で表が出た回数の最大値がkである」事象の尤度を最大化するNは2^kということ）

つまり、表が連続で出た回数だけわかれば、コイン投げの試行回数が推定できる。

Hash値を乱数として利用

データと乱数を紐づけるために、以下の特徴をもつhash関数を利用する。

同一のデータからは同一のhashが生成される
hash値の分布が一様（乱数に近い）

例）　hash値に基づくユニーク数のカウント

"data1” → 0010010...
"data2" → 0101000...
"data3" → 1101010...
"data4" → 1001100...
"data1" → 0010010...

hash値の各bitをコインの表と裏と考えれば、上述した基本原理を用いてユニークなhash値の数、つまり、ユニークなデータの数を推定できる（hashの衝突は一旦無視）。
例の場合、先頭から0が最大で2個連続している（data1）ケースが存在しており、ユニーク数は2^2=4と推定される。

アルゴリズム

基本的なアルゴリズムとしては以下の通り[1]。

hash値の先頭x bitをバケットのアドレスとして、hashの残りのbitを乱数の代わりとして利用する。
各バケットで、先頭の0が最大何個連続しているか（最初の1が何bit目に出現するか）を記録しておき、最終的なカーディナリティ推定に利用する。

HyperLogLogの問題点

ユニーク数が小さくなると推論精度が下がってしまう。（確率のブレが大きくなる）

ユニーク数が小さい時のHyperLogLog++の挙動

前述したようにユニーク数が小さいときは推論精度が下がるため、ユニーク数が小さい時にはLinearCountingと呼ばれるアルゴリズムを使用して精度を担保している。
アルゴリズムの切り替えは推定ユニーク数を閾値処理して決めている。

LinearCounting

HyperLogLogのアルゴリズムでバケットに値を入れた後、空のバケットの数からカーディナリティを推定する。

例えば、もともとバケットが1000個用意されていたとして、上記の処理後、空のバケットが990個の場合、ユニーク数は10と推定できる。

バケットの数によって衝突する可能性が変わってくるので、その辺も含めた補正がかけられているが、原理としては例の通り。

ユニーク数が1 or 2以上かの判定精度

判定を誤るのは以下の２パターンのみで、これらが生じる確率は実用上十分に小さい。

実際のユニーク数が1であるのに、2以上と推定してしまうケース

LinearCountingでは、ユニーク数が1であれば衝突は絶対に発生せず正確に推定できる。

実際のユニーク数が2以上であるのに、1と推定してしまうケース

ユニークなデータ全てのhashが衝突する確率に近く（バケット数が有限なので多少異なる）、非常に小さい。

結論

ユニーク数が1であるか、2以上であるかを判定するフィルタの実装にapprox_count_distinctを使用しても問題ないと判断できる。

※金融や医療のような絶対に間違いが発生してはいけない領域では使用すべきではない。

参考資料

[1] HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
[2] HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm
[3] Zennの記事: https://zenn.dev/masatana/articles/3140f10708ddcf
[4] BrainPadの資料: https://www.slideshare.net/BrainPad/deltacube