頻繁な値の推定¶

概要¶

Snowflakeは、メトワリー、アグラワル、およびアッバディによる データストリーム内の最も頻繁なk要素の効率的な計算（）で提示された省スペースアルゴリズムの実装を提供します。 APPROX_TOP_K ファミリーの関数を介して実装されます。

さらに、 APPROX_TOP_K_COMBINE 関数は、カファロ、プリメノ、およびテンペスタによって概説された 並列省スペースアルゴリズム を利用します。

アルゴリズムのエラーの割合は、データの歪み具合とアルゴリズムで使用されるカウンター数に大きく依存します。データの歪みが大きくなるか、使用されるカウンターが増えると、出力はより正確になります。

SQL 関数¶

次の 集計関数 は、省スペースを使用して頻繁な値を推定するために提供されています。

• APPROX_TOP_K: 入力の頻繁な値の近似値を返します。

• APPROX_TOP_K_ACCUMULATE: 最後の推定ステップをスキップし、集約の終了時に省スペース状態を返します。

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

• APPROX_TOP_K_ESTIMATE: APPROX_TOP_K_ACCUMULATE および APPROX_TOP_K_COMBINE によって生成された省スペース状態のカーディナリティ推定値を計算します。

実装の詳細¶

実装の各カウンタは、アイテムとその頻度を追跡します。特に、この実装はカウンターのイプシロン値を追跡しません。これらは、アルゴリズムの出力に関する保証を与えるためにのみ有用であり、アルゴリズム自体には使用されないためです。

カウンターの最大数は10万に設定されています。この場合、メモリには10万のカウンターが格納されますが、エクスポートされた状態で格納されるのはこれらのほんの一部です。

k の最大数は10万です。すべての値が出力に収まらない場合、この値は自動的に減少します。

ほとんどの場合、実装の実行時間はカウンター数に依存しません。実装では、カウンター数がアルゴリズムのランタイムに顕著な影響を与えないことが保証されます。

各集約状態の各カウンターは、約100バイトの一定量のメモリオーバーヘッドを使用します。したがって、集計が c カウンターを使用し、 g の集計グループがある場合、集計は c * g * 100B のメモリと値を格納するメモリを使用します。このメモリが合計メモリバジェットを超えると、メモリがディスクにスピルします。これは、特に多数の一意の値がある場合に、正確なバージョンが使用するよりもはるかに少ないメモリです。