無駄と文化

実用的ブログ

BigQueryのAPPROX_COUNT_DISTINCTの誤差・コストを実測する

BigQuery データサイエンス

BigQuery には 近似集計関数 (Approximate aggregate functions) と呼ばれる集計関数があります。「厳密な結果を返す保証はないものの、メモリ使用量・集計時間が現実的な範囲に収まるように近似集計を実行してくれる関数」とのことです。

関数名 概要
APPROX_COUNT_DISTINCT(expr) 重複無しカウント COUNT(DISTINCT expr) の近似値
APPROX_QUANTILES(expr, num) 分位数の近似値
APPROX_TOP_COUNT(expr, num) 出現数ランキング上位N位までの近似値
APPROX_TOP_SUM(expr, weight, num) ランキング(重み指定あり)の上位N位までの近似値

公式ドキュメント: https://docs.cloud.google.com/bigquery/docs/reference/standard-sql/approximate_aggregate_functions

 

近似値になってしまうのは仕方ないとして、誤差やコストはどうでしょうか？公式ドキュメントには記載がありません。今回は APPROX_COUNT_DISTINCT で実測して評価します。

 

目次

 

集計誤差の比較

Google は bigquery-public-data というデータセット群を公開しています。下記データセットを使います。

テーブル 概要
github_repos.sample_commits GitHub コミット履歴
google_analytics_sample.ga_sessions_* Google Analytics のセッションログ
stackoverflow.posts_questions Stack Overflow の質問投稿

公式ドキュメント: https://docs.cloud.google.com/bigquery/public-data

 

ユニーク数が少ない場合の誤差

WITH

base AS (
  SELECT
    DATE_TRUNC(DATE(author.date), YEAR) AS year,
    author.email                        AS email
  FROM `bigquery-public-data.github_repos.sample_commits`
)

SELECT
  year,
  COUNT(*)                     AS rows_count,
  COUNT(DISTINCT email)        AS exact,
  APPROX_COUNT_DISTINCT(email) AS approx,
  SAFE_DIVIDE(
    APPROX_COUNT_DISTINCT(email) - COUNT(DISTINCT email),
    COUNT(DISTINCT email)
  )                            AS rel_error
FROM base
GROUP BY year
year rows_count exact approx rel_error
2005-01-01 16,696 1,464 1,463 -0.068%
2006-01-01 29,255 2,163 2,163 0.000%
2007-01-01 33,759 2,320 2,322 0.086%
2008-01-01 48,847 2,746 2,747 0.036%
2009-01-01 52,572 3,020 3,018 -0.066%
2010-01-01 50,028 3,117 3,118 0.032%
2011-01-01 58,008 3,301 3,301 0.000%
2012-01-01 70,378 3,568 3,569 0.028%
2013-01-01 83,056 4,041 4,044 0.074%
2014-01-01 90,113 4,494 4,494 0.000%
2015-01-01 91,334 5,153 5,152 -0.019%
2016-01-01 48,227 3,324 3,322 -0.060%

exact < 10,000 の規模では誤差±2程度のようです。

 

ユニーク数が多い場合の誤差

WITH

base AS (
  SELECT
    DATE_TRUNC(PARSE_DATE('%Y%m%d', date), MONTH) AS month,
    fullVisitorId
  FROM `bigquery-public-data.google_analytics_sample.ga_sessions_*`
  WHERE _TABLE_SUFFIX BETWEEN '20160801' AND '20170730'
)

SELECT
  month,
  COUNT(DISTINCT fullVisitorId)        AS exact,
  APPROX_COUNT_DISTINCT(fullVisitorId) AS approx,
  SAFE_DIVIDE(
    APPROX_COUNT_DISTINCT(fullVisitorId) - COUNT(DISTINCT fullVisitorId),
    COUNT(DISTINCT fullVisitorId)
  )                                    AS rel_error
FROM base
GROUP BY month
month rows_count exact approx rel_error
2016-08-01 74,759 61,699 61,557 -0.230%
2016-09-01 71,032 59,121 59,243 0.206%
2016-10-01 97,506 84,901 84,521 -0.448%
2016-11-01 113,972 99,734 100,356 0.624%
2016-12-01 79,124 63,839 63,776 -0.099%
2017-01-01 64,694 53,041 53,342 0.567%
2017-02-01 62,192 51,364 51,306 -0.113%
2017-03-01 69,931 57,888 58,001 0.195%
2017-04-01 67,126 55,681 55,665 -0.029%
2017-05-01 65,371 52,233 52,395 0.310%
2017-06-01 63,578 52,067 52,183 0.223%
2017-07-01 69,192 56,599 56,557 -0.074%

exact > 50,000 の規模に対して誤差は0.7%以下の傾向です。

 

規模による傾向

レコード数の規模によって誤差がどのように推移するのか見てみます。

WITH

ranges AS (
  SELECT * FROM UNNEST([
    STRUCT(DATE '2020-01-01' AS since, DATE '2020-01-01' AS until),
    STRUCT(DATE '2020-01-01' AS since, DATE '2020-01-05' AS until),
    STRUCT(DATE '2020-01-01' AS since, DATE '2020-01-31' AS until),
    STRUCT(DATE '2020-01-01' AS since, DATE '2020-03-31' AS until),
    STRUCT(DATE '2020-01-01' AS since, DATE '2020-06-30' AS until),
    STRUCT(DATE '2020-01-01' AS since, DATE '2020-12-31' AS until),
    STRUCT(DATE '2020-01-01' AS since, DATE '2022-12-31' AS until)
  ])
)

SELECT
  DATE(MIN(p.creation_date))             AS since,
  DATE(MAX(p.creation_date))             AS until,
  COUNT(*)                               AS rows_count,
  COUNT(DISTINCT p.owner_user_id)        AS exact,
  APPROX_COUNT_DISTINCT(p.owner_user_id) AS approx,
  SAFE_DIVIDE(
    APPROX_COUNT_DISTINCT(p.owner_user_id) - COUNT(DISTINCT p.owner_user_id),
    COUNT(DISTINCT p.owner_user_id)
  )                                      AS rel_error
FROM ranges AS r
JOIN `bigquery-public-data.stackoverflow.posts_questions` AS p
  ON DATE(p.creation_date) BETWEEN r.since AND r.until
GROUP BY r.since, r.until
since until rows_count exact approx rel_error
2020-01-01 2020-01-01 2,390 2,213 2,214 0.045%
2020-01-01 2020-01-05 17,563 14,936 14,945 0.060%
2020-01-01 2020-01-31 147,805 100,730 101,670 0.933%
2020-01-01 2020-03-31 451,332 255,313 256,775 0.573%
2020-01-01 2020-06-30 997,113 482,766 484,218 0.301%
2020-01-01 2020-12-31 1,871,695 786,442 787,489 0.133%
2020-01-01 2022-09-25 4,770,063 1,689,354 1,680,798 -0.506%

レコード数の増加に対して誤差が線形に 悪化/改善 することはなく、概ね1%以下の誤差に収まっているようです。

 

コスト比較

BigQuery では スキャン量 と スロット時間 に対して課金されるので、それぞれ比べてみます。

レコード数 ユニーク数 COUNT(DISTINCT expr) APPROX_COUNT_DISTINCT
約70万 約4万 40MB / 0.716秒 40MB / 0.717秒
約90万 約70万 27MB / 12.405秒 27MB / 9.658秒
約800万 約300万 348MB / 8.710秒 348MB / 5.039秒

以下の傾向が読み取れます。

  • スロット時間に対してレコード数はほぼ影響せず、ユニーク数の影響が支配的
  • 4万ユニーク数程度ではスキャン量・スロット時間ともにほぼメリット無し
    • APPROX_COUNT_DISTINCT を使うと厳密さが犠牲になるぶんネガティブ
  • ユニーク数70万以上なら明確に差が見える

ここからわかる APPROX_COUNT_DISTINCT の使い所は

  • 🙅‍♀️ 大規模データ
  • 🙆‍♀️ 大規模かつユニーク数が多いデータ (ユニーク数: 数十万~)

のようですね。

 

まとめ

「行数が多いからとりあえず APPROX_COUNT_DISTINCT を使う」ではなく、ユニーク数を試算して使い分けるのが良さそうです。

 

 

私からは以上です。