🌟

BigQuery の COUNT DISTINCT を近似集計で高速化する

2022/10/03に公開

BigQuery

tech

クラウドエースの小坂です。
データウェアハウス構築、最近は特に BigQuery/Looker を活用した分析環境構築プロジェクトのプロジェクトマネージャーをよくやっています。

今回は膨大なデータの中からある項目のユニーク数(例えば DAU/MAU など)を集計する際に近似集計を使って集計処理を高速化する方法について紹介します。

検証に利用するデータ

今回は BigQuery 上で無償で提供されている bigquery-public-data のデータセットのデータを利用します。

テーブルは bigquery-public-data.wikipedia.pageviews_2021 を利用します。

テーブルの情報は下記の通りです。

Table info

項目	値
Table ID	bigquery-public-data.wikipedia.pageviews_2021
Table size	2.15 TB
Number of rows	53,288,623,350
Partitioned by	DAY
Partitioned on field	datehour
Clustered by	wiki,title

Schema

Field name	Type
datehour	TIMESTAMP
wiki	STRING
title	STRING
views	INTEGER

テーブルサイズも非常に大きく、レコード数も膨大なので今回の検証にちょうどよさそうなデータです。
今回はこのデータを使って2021年の wikipedia のページ閲覧情報から title のユニーク数の集計を行ってみようと思います。

検証

検証1 普通に COUNT DISTINCT する

まずはこのデータに対してシンプルに COUNT DISTINCT を行い、結果を確認してみます。

SELECT
  COUNT(DISTINCT title)
FROM
  `bigquery-public-data.wikipedia.pageviews_2021`
WHERE
  DATE(datehour) < "2022-09-23" --ここは2021年のデータが全て対象になる条件ならなんでも OK

実行した結果の出力は 236,516,112 となりました。

実行にかかったスキャン量・時間は以下のとおりです。

項目	値
スキャン量	1.51 TB
処理時間	1 min 21 sec

532億レコードからユニーク数を集計していると考えると十分高速な気もしますが、これを更に近似集計を使って高速化してみます。

検証2 近似集計を使って処理を高速化する

BigQuery で使用できる COUNT DISTINCT の近似集計は以下の2つがあります。

APPROX_COUNT_DISTINCT 関数

HyperLogLog++ 関数(HLL++関数)

APPROX_COUNT_DISTINCT 関数 と HLL++関数 はともに近似集計を行う、という点では同様のものですが、以下のような違いもあります。

HyperLogLog++ 関数は再集計が可能だが、APPROX_COUNT_DISTINCT は再集計はできない
APPROX_COUNT_DISTINCT はシンプルに対象のカラムを指定し APPROX_COUNT_DISTINCT(カラム名) で集計が可能だが、HLL++関数ではスケッチを作成してそのスケッチを集計するというステップを踏む必要がある

使い分けとしては

再集計が不要であれば APPROX_COUNT_DISTINCT
再集計がしたければ HLL++

という形で使い分ければよいかと思います。

実際に試しながら詳細について説明していきます。

検証2-1 APPROX_COUNT_DISTINCT でタイトルのユニーク数を集計する

まずは APPROX_COUNT_DISTINCT を使ってタイトルのユニーク数を集計してみます。

SELECT
  approx_count_distinct(title)
FROM
  `bigquery-public-data.wikipedia.pageviews_2021`
WHERE
  DATE(datehour) < "2022-09-23" --ここは2021年のデータが全て対象になる条件ならなんでも OK

実行した結果の出力は 235,922,465 となりました。

COUNT DISTINCT との集計結果の差は 0.251% でした。

実行にかかったスキャン量・時間は以下のとおりです。

項目	値
スキャン量	1.51 TB
処理時間	31 sec

COUNT DISTINCT と比べると約62%処理時間が短縮されています。

シンプルに近似集計で COUNT DISTINCT を行うだけであれば APPROX_COUNT_DISTINCT を使用すれば簡単に可能です。

検証2-2 HLL++ 関数を使ってタイトルのユニーク数を集計する

続いて HLL++ 関数 を使用して近似集計を行ってみます。

SELECT
  hll_count.extract( --② hll_count.extract で①で作成したスケッチを元に近似集計を行う
    hll_count.init(title) --① hll_count.init でスケッチという近似集計のための情報を作成する
) 
FROM
  `bigquery-public-data.wikipedia.pageviews_2021`
WHERE
  DATE(datehour) < "2022-09-23" --ここは2021年のデータが全て対象になる条件ならなんでも OK

基本的に2つのステップが必要となり

hll_count.init() でスケッチという近似集計のための情報を作成する
hll_count.extract() で①で作成したスケッチを元に近似集計を行う

という処理を行います。

実行した結果の出力は 235,922,465 となり APPROX_COUNT_DISTINCT と同じ結果となりました。

実行にかかったスキャン量・時間は以下のとおりです。

項目	値
スキャン量	1.51 TB
処理時間	30 sec

こちらでも APPROX_COUNT_DISTINCT とほぼ同じ結果が出力されますが、APPROX_COUNT_DISTINCT と比べて 2 ステップの関数の記述が必要になるため、少し手間です。

検証2-3 HLL++ 関数を使ってタイトルのユニーク数の再集計を行う

上記の通り、APPROX_COUNT_DISTINCT でも HLL++ でも出力される結果はほぼ同じになります。

ではなぜ HLL++ 関数 なんてものが用意されているのでしょうか…？
それは HLL++ 関数 を使用すると、COUNT DISTINCT の結果の再集計が行えるためです。

例えば、

日別でタイトルのユニーク数を計算したテーブルを作成する
1 で作成したテーブルから週別でタイトルのユニーク数を計算する

みたいなことが可能です。

APPROX_COUNT_DISTINCT や COUNT DISTINCT を使用している場合には、既に集計された数値のみが情報として保持されるため、
そこから再集計を行おうとしてもユニーク数を数えることができません。

一方 HLL++ では スケッチ という形で集計の基となる情報を保持するため、そのスケッチ同士を集計することにより再集計を実現しています。
(実際どういう処理が内部的に行われているのかは私は全くわかりませんが、わからなくても HLL++ で再集計はできますので安心してください)

実際に wikipedia のページ閲覧情報を使って、

日別のタイトルのユニーク数を計算
1の結果から週別のタイトルのユニーク数を計算

を行ってみます。

そろそろ BigQuery の課金がかかりすぎて会社から怒られるかもしれないので、データのスキャン範囲を1ヶ月程度に絞って実行します。

検証2-3-1 日別のタイトルのユニーク数を計算

まずは日別のタイトルのユニーク数を計算します。
それとともに再集計に必要になるスケッチも作成します。

SELECT
  DATE(datehour) AS DATE, --日別に集計
  hll_count.extract(hll_count.init(title)) AS hll_count, --HLL++ でタイトルのユニーク数を集計
  hll_count.init(title) AS hll_sketch --HLL++ スケッチを作成
FROM
  `bigquery-public-data.wikipedia.pageviews_2021`
WHERE
  DATE(datehour) BETWEEN "2021-01-01" AND "2021-01-31"
GROUP BY
  1
ORDER BY
  1 ASC

出力結果のサンプルは以下のとおりです。

日単位で集計された近似集計結果とともにスケッチが出力されます。

次にこのスケッチを使って週単位に再集計します。

検証2-3-2 週別のタイトルユニーク数を再集計

スケッチを元に再集計を行う際には HLL_COUNT.MERGE 関数を使用します。

SELECT
  DATE_TRUNC(DATE, WEEK) AS week, --週単位に集計
  HLL_COUNT.MERGE(hll_sketch) AS title_cnt--スケッチを元に再集計を行う
FROM
  `検証2-3-1 で作成した一時テーブルを指定`
GROUP BY
  1
ORDER BY
  1 ASC

出力結果は以下のとおりで週単位でのタイトルユニーク数が出力されました。

Row	week	title_cnt
1	2020-12-27	27576010
2	2021-01-03	47219763
3	2021-01-10	47447924
4	2021-01-17	47924684
5	2021-01-24	55828919
6	2021-01-31	23225473

COUNT DISTINCT で同様の結果を計算した際との差分を見てみましょう。

WITH hll AS(
  SELECT
    DATE_TRUNC(DATE, WEEK) AS week,
    HLL_COUNT.
  MERGE
    (hll_sketch) AS title_cnt
  FROM
    `検証2-3-1 で作成した一時テーブルを指定`
  GROUP BY
    1 )

,count_distinct AS (
  SELECT
    DATE(TIMESTAMP_TRUNC(datehour, WEEK)) AS week,
    --週別に集計
    COUNT(DISTINCT title) AS title_cnt
  FROM
    `bigquery-public-data.wikipedia.pageviews_2021`
  WHERE
    DATE(datehour) BETWEEN "2021-01-01"
    AND "2021-01-31"
  GROUP BY
    1 )

SELECT
  hll.week,
  hll.title_cnt AS hll_cnt,
  count_distinct.title_cnt AS cnt_distinct,
  1 - SAFE_DIVIDE(hll.title_cnt, count_distinct.title_cnt) AS ratio
FROM
  hll
LEFT JOIN 
  count_distinct
  ON hll.week = count_distinct.week

出力結果は以下のとおりでした。

Row	week	hll_cnt	cnt_distinct	ratio
1	2020-12-27	27576010	27650140	0.002680999084
2	2021-01-03	47219763	47373449	0.003244137871
3	2021-01-10	47447924	47494299	0.000976432982
4	2021-01-17	47924684	47939426	0.0003075130687
5	2021-01-24	55828919	56229926	0.00713155838
6	2021-01-31	23225473	23300426	0.003216808139

大きいものでも 0.7% 程度のズレとなりました。

まとめ

今回は COUNT DISTINCT を高速化する方法として APPROX_COUNT_DISTINCT と HLL++ を紹介しました。

COUNT DISTINCT の集計が高速化され、かつ再集計も可能で非常に便利な関数である一方、
正確な値ではない(近似集計である)ことに留意してケース・バイ・ケースでどちらを使用すべきかをビジネスユーザーとも相談しつつ使用してみてください。

また便利な BigQuery の関数を見つけたらご紹介したいと思います。

検証に利用するデータ

検証

検証1 普通に COUNT DISTINCT する

検証2 近似集計を使って処理を高速化する

検証2-1 APPROX_COUNT_DISTINCT でタイトルのユニーク数を集計する

検証2-2 HLL++ 関数を使ってタイトルのユニーク数を集計する

検証2-3 HLL++ 関数を使ってタイトルのユニーク数の再集計を行う

検証2-3-1 日別のタイトルのユニーク数を計算

検証2-3-2 週別のタイトルユニーク数を再集計

まとめ

Discussion