異なる値の数の推定

Snowflakeは HyperLogLog を使用して、データセット内にある異なる値のおおよその数を推定します。HyperLogLog は、数パーセントの平均相対誤差で数兆行の異なるカーディナリティを推定できる最新のカーディナリティ推定アルゴリズムです。

カーディナリティの推定が許容される状況では、 COUNT(DISTINCT ...) の代わりに HyperLogLog を使用できます。

このトピックの内容:

概要

Snowflakeは、 HyperLogLog で提示された HyperLogLog アルゴリズムのバイアス修正実装を提供します。これは、フラジョレらによるほぼ最適なカーディナリティ推定アルゴリズムの分析()です。

入力が潜在的に大きく、おおよその結果が許容できる場合は常に HyperLogLog を使用することをお勧めします。HyperLogLog 実装の平均相対誤差は1.62338%です(対応する COUNT(DISTINCT ...) 結果との平均相対差)。

SQL 関数

次の 集計関数 は、HyperLogLog を使用してカーディナリティを推定するために提供されています。

  • HLL: 入力の異なるカーディナリティの近似値を返します。

  • HLL_ACCUMULATE: 最後の推定ステップをスキップし、集計の終了時に HyperLogLog 状態を返します。

  • HLL_COMBINE: 入力状態を単一の出力状態に結合(つまり、マージ)します。

  • HLL_ESTIMATE: HLL_ACCUMULATE および HLL_COMBINE によって生成された HyperLogLog 状態のカーディナリティ推定値を計算します。

  • HLL_EXPORT: HyperLogLog 状態を BINARY 形式から OBJECT に変換します(その後、印刷したり、 JSON としてエクスポートしたりできます)。

  • HLL_IMPORT: HyperLogLog 状態を OBJECT 形式から BINARY 形式に変換します。

実装の詳細

Snowflakeの実装では、入力行を64ビット値にハッシュします。これについて、上位12ビットまたは「精度」(HyperLogLog アルゴリズムの論文で説明されています。詳細については、上記のドキュメントリンクをご参照ください)を使用して入力値をいわゆるサブストリームに分割します。これにより、次の平均相対誤差が得られます。

sqrt(3*ln(2)-1)/sqrt(2^precision) = 0.0162338 = 1.62338%

つまり、 COUNT(DISTINCT ...)1,000,000 の結果を返すクエリの場合、 HyperLogLog は通常、 983,767 から 1,016,234 の範囲の結果を返します。

各サブストリームについて、 HyperLogLog は最大先行ゼロカウント(精度= 12の64ビット値の0と52の間)を維持します。この状態の最も簡単な表現は、 2^12 = 4096 サブストリームごとに1バイトの単純なバイト配列です。実装には、集計グループごとに最大4096バイト(2^precision = 2^12 = 4096)のメモリが必要です。技術的には、サブストリームごとに(8ビットではなく)6ビットのみが必要ですが、スペース効率と計算効率の両方がある程度犠牲になります。

入力カーディナリティが小さい場合、ほとんどのサブストリームはヒットしません。したがって、実装では、集約グループごとに4096バイトのブロック全体を事前に割り当てるのではなく、有益な場合は常に、この状態のスペース最適化された「スパース」表現を使用します。その結果、HyperLogLog のメモリコストは集約グループごとに4096バイトより大幅に低くなる可能性があります(集約グループごとに約32バイトまで)。これにより、(クエリの GROUP BY または OVER 句で決定される数百万または数十億の)多くの集約グループでのカーディナリティ推定を、対応する COUNT(DISTINCT ...) クエリよりも桁違いに少ないメモリと CPU 時間を使用して実行できます。

非常に大きな入力テーブルと多くの集計グループが HyperLogLog の合計メモリバジェットを超える(まれな)ケースでは、Snowflakeは他の集計関数と同様に、引き続き一時領域にスピルして再帰的な集計を実行できます。

エクスポートされた状態形式

HyperLogLog アルゴリズムの状態は、それぞれ HLL_EXPORT および HLL_IMPORT 関数を使用してエクスポートおよびインポート(または再インポート)できます。エクスポートされた状態は OBJECT タイプで、次のフィールドが含まれています。

デンス形式

version:

HyperLogLog 実装のバージョン番号。

precision:

サブストリームの選択に使用するハッシュ値ビットの数。現在、12に固定されています。

dense:

整数の配列。各整数には、対応するサブストリームの最大先行ゼロカウント+ 1が含まれます。0は、対応するサブストリームがまだヒットしていないことを示します。有効な値は0から53の範囲です。対応するサブストリームインデックスは、配列内の要素の位置によって指定されます。

例:

{
  "version" : 3,
  "precision" : 12,
  "dense" : [3,3,3,3,5,3,4,3,5,6,2,4,4,7,5,6,6,3,2,2,3,2,4,5,5,5,2,5,5,3,6,1,4,2,2,4,4,5,2,5,...,4,6,3]
}
Copy

スパース形式

version:

HyperLogLog 実装のバージョン番号。

precision:

サブストリームの選択に使用するハッシュ値ビットの数。現在、12に固定されています。

sparse:

indices: それぞれがサブストリームインデックス(ベース0)を含む整数の配列。有効な値は0から4095の範囲です。

maxLzCounts: 整数の配列。各整数には、対応するサブストリームの最大先行ゼロカウント+ 1が含まれます。0は、対応するサブストリームがまだヒットしていないことを示します。

有効な値は0から53の範囲です。指定された先行ゼロカウントのサブストリームは、 indices 配列の対応する要素によって指定されます。

indices および maxLzCounts 配列は、同じ長さでなければなりません。 HLL_IMPORT 関数は、サブストリームインデックスが有効な範囲内にあり、重複するサブストリームインデックスがないことも確認します。 indices 配列を並べ替える必要はありません。先行ゼロカウントは検証されません。無効な値はクエリの失敗を引き起こすことはありませんが、 HLL_ESTIMATE の未定義の結果につながります。

例:

{
  "version" : 3,
  "precision" : 12,
  "sparse" : {
    "indices": [1131,1241,1256,1864,2579,2699,3730],
    "maxLzCounts":[2,4,2,1,3,2,1]
  }
}
Copy

環境設定:

USE WAREHOUSE dontdrop;
USE DATABASE stressdb;
USE SCHEMA bdb_5nodes;

SELECT COUNT(*) FROM uservisits;

-----------+
 COUNT(*)  |
-----------+
 751754869 |
-----------+
Copy

ステップ1:

カレンダーの日付(年/月/日)と HLL 構造を含むテーブルを作成します。 HLL_EXPORT を使用して、バイナリ構造をテキストオブジェクトとして格納します。

CREATE OR REPLACE TABLE daily_uniques
AS
SELECT
 visitdate,
 hll_export(hll_accumulate(sourceip)) AS hll_sourceip
FROM uservisits
GROUP BY visitdate;
Copy

ステップ2:

ステップ1の各日の HLL 構造を集約することで、月ごとに一意の IPs を計算できます。 HLL_IMPORT を使用してテキストをバイナリ構造に変換し、次に HLL_COMBINE を使用して複数の HLL 構造を単一の構造に結合した上で、 HLL_ESTIMATE を使用して異なる値の数を計算します。

SELECT
  EXTRACT(year FROM visitdate) AS visit_year,
  EXTRACT(month FROM visitdate) AS visit_month,
  hll_estimate(hll_combine(hll_import(hll_sourceip))) AS distinct_ips
FROM daily_uniques
WHERE visitdate BETWEEN '2000-01-01' AND '2000-12-31'
GROUP BY 1,2
ORDER BY 1,2;

------------+-------------+--------------+
 VISIT_YEAR | VISIT_MONTH | DISTINCT_IPS |
------------+-------------+--------------+
       2000 |           1 |      1515168 |
       2000 |           2 |      1410289 |
       2000 |           3 |      1491997 |
       2000 |           4 |      1460837 |
       2000 |           5 |      1546647 |
       2000 |           6 |      1485599 |
       2000 |           7 |      1522643 |
       2000 |           8 |      1492831 |
       2000 |           9 |      1488507 |
       2000 |          10 |      1553201 |
       2000 |          11 |      1461140 |
       2000 |          12 |      1515772 |
------------+-------------+--------------+

Elapsed 1.3s
Copy

比較:

詳細レベルのデータで、 HLL 関数を使用した集計の使用を HLL と比較します。この場合、 HLL() はステップ2の HLL_ESTIMATE(HLL_COMBINE(HLL_IMPORT())) と同等です。

SELECT
  EXTRACT(year FROM visitdate) AS visit_year,
  EXTRACT(month FROM visitdate) AS visit_month,
  hll(sourceip) AS distinct_ips
FROM uservisits
WHERE visitdate BETWEEN '2000-01-01' AND '2000-12-31'
GROUP BY 1,2
ORDER BY 1,2;

------------+-------------+--------------+
 VISIT_YEAR | VISIT_MONTH | DISTINCT_IPS |
------------+-------------+--------------+
       2000 |           1 |      1515168 |
       2000 |           2 |      1410289 |
       2000 |           3 |      1491997 |
       2000 |           4 |      1460837 |
       2000 |           5 |      1546647 |
       2000 |           6 |      1485599 |
       2000 |           7 |      1522643 |
       2000 |           8 |      1492831 |
       2000 |           9 |      1488507 |
       2000 |          10 |      1553201 |
       2000 |          11 |      1461140 |
       2000 |          12 |      1515772 |
------------+-------------+--------------+

Elapsed 2m 29s
Copy

ここで見るように、 HLL 構造の集約はベースデータの集約よりも大幅に高速化します。たとえば、この小さな例では1.3秒と149秒であり、クエリ時間は100分の1に短縮されます。