異なる値の数の推定¶

概要¶

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 タイプで、次のフィールドが含まれています。

例¶

環境設定：

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に短縮されます。