概要
ユニークユーザ数の集計など、count distinctを実行する場合、BigQueryでも処理時間が膨大になってしまうほどのレコード数を扱いたい時、近似集計が有用である。
BigQueryでは2つの方法があり、その簡単な違いをまとめる。
本編
count distinct集計は、集計対象のユニーク数に依存したメモリを必要とするため、大規模なデータほど大きな計算コストが伴う。
そのため、集計を厳密性を捨てて、高速で集計するアルゴリズムが存在する。
BigQueryでは、以下の近似集計関数が用意されている。
APPROX_COUNT_DISTINCT-
HyperLogLog++関数(HLL_COUNT.INIT → HLL_COUNT.MERGE)
近似計算の仕組み
どちらも仕組みは同様で、条件が同じであれば結果も一致する（後述）
c.f. HyperLogLog sketch in practice -異なり数の集計の悩みはほぼ解決！-
サンプル
公開データセットでの例が以下の通り(データをちゃんと確認おらず意味のある集計かは置いておく)
近似計算例
select
dt,
sum(repository_unique_num) as repository_unique_num,
sum(approx_repository_unique_num) as approx_repository_unique_num,
hll_count.merge(sketch_repository_unique_num) as hll_repository_unique_num,
from (
select
date(created_at) as dt,
count(distinct repository_url) as repository_unique_num,
approx_count_distinct(repository_url) as approx_repository_unique_num,
hll_count.init(repository_url) as sketch_repository_unique_num,
from
`bigquery-public-data.samples.github_timeline`
where
created_at is not null
group by 1
)
group by 1
order by 1
-
APPROX_COUNT_DISTINCT- 通常の集計関数と同様に利用できる
-
HyperLogLog++関数- HLL_COUNT.INITでsketchを集計した後、これをHLL_COUNT.MERGEで参照する
- sketchを保存しておくことで集計時の再利用性が高まる
どちらも精度は厳密集計時に対する相対誤差が1~2%ほどで収まる
（HyperLogLog++関数では精度を指定することができる）
HyperLogLog++関数の違い
HyperLogLog++関数(今後HLLと呼ぶ)を採用するメリットは複数存在する
- (BigQueryの仕様として)オプションで精度を変更することができる
- init時にオプションを設定することで、近似計算の精度を調整できる
- デフォルトは15
- 大きくするほど精度は高くなる一方、sketchの必要サイズが大きくなり、計算コストが上がる
精度オプション
select
dt,
sum(repository_unique_num) as repository_unique_num,
hll_count.merge(sketch_repository_unique_num) as hll_repository_unique_num,
hll_count.merge(sketch20_repository_unique_num) as hll20_repository_unique_num,
from (
select
date(created_at) as dt,
count(distinct repository_url) as repository_unique_num,
hll_count.init(repository_url) as sketch_repository_unique_num,
hll_count.init(repository_url, 20) as sketch20_repository_unique_num,
from
`bigquery-public-data.samples.github_timeline`
where
created_at is not null
group by 1
)
group by 1
order by 1
- sketchを利用して、効率よくユニーク数集計ができる
- sketchデータを中間テーブル化し、それを活用することで効率的に集計ができる
sketch再利用の例
with
sketch_data as (
select
date(created_at) as dt,
hll_count.init(repository_url) as sketch_repository_unique_num,
from
`bigquery-public-data.samples.github_timeline`
where
created_at is not null
group by 1
)
select
'daily' as type,
dt,
hll_count.merge(sketch_repository_unique_num) as repository_unique_num,
from
sketch_data
group by 1, 2
union all
select
'monthly' as type,
date_trunc(dt, month) as dt,
hll_count.merge(sketch_repository_unique_num) as repository_unique_num,
from
sketch_data
group by 1, 2