HyperLogLog関数¶

Prestoは、HyperLogLogデータ構造を使用して、approx_distinct()関数を実装しています。

データ構造¶

Prestoは、HyperLogLogデータスケッチを、*最大ハッシュ*を格納する32ビットバケットのセットとして実装します。これらは、疎な表現（バケットIDからバケットへのマップとして）または密な表現（連続したメモリブロックとして）で格納できます。 HyperLogLogデータ構造は、疎な表現として開始され、より効率的になると密な表現に切り替わります。 P4HyperLogLog構造は密に初期化され、その存続期間中は密なままです。

HyperLogLogは暗黙的にP4HyperLogLogにキャストされますが、HyperLogLogをP4HyperLogLogに明示的にキャストすることもできます。

cast(hll AS P4HyperLogLog)

シリアライゼーション¶

データスケッチは、varbinaryにシリアル化したり、varbinaryからデシリアライズしたりできます。これにより、後で使用するために格納できます。複数のスケッチをマージする機能と組み合わせることで、クエリのパーティションの要素の:func:!approx_distinct`を計算し、その後、非常に少ないコストでクエリ全体を計算できます。

たとえば、毎日のユニークユーザーのHyperLogLogを計算することで、毎日のデータを組み合わせることで、週間または毎月のユニークユーザーを段階的に計算できます。これは、日次収益を合計して週間収益を計算するのと似ています。approx_distinct()とGROUPING SETSを一緒に使用すると、HyperLogLogを使用するように変換できます。例

CREATE TABLE visit_summaries (
  visit_date date,
  hll varbinary
);

INSERT INTO visit_summaries
SELECT visit_date, cast(approx_set(user_id) AS varbinary)
FROM user_visits
GROUP BY visit_date;

SELECT cardinality(merge(cast(hll AS HyperLogLog))) AS weekly_unique_users
FROM visit_summaries
WHERE visit_date >= current_date - interval '7' day;

関数¶

approx_set(x) -> HyperLogLog()¶: 入力データセットxのHyperLogLogスケッチを返します。最大標準誤差の値は、デフォルトで0.01625です。このデータスケッチはapprox_distinct()の基礎となっており、cardinality()を呼び出すことで格納して後で使用できます。

approx_set(x, e) -> HyperLogLog()¶: 最大標準誤差eで、入力データセットxのHyperLogLogスケッチを返します。この関数の現在の実装では、eが[0.0040625, 0.26000]の範囲内である必要があります。このデータスケッチはapprox_distinct()の基礎となっており、cardinality()を呼び出すことで格納して後で使用できます。

cardinality(hll) -> bigint(): これは、hll HyperLogLogデータスケッチによって集計されたデータに対してapprox_distinct()を実行します。

empty_approx_set() -> HyperLogLog()¶: 空のHyperLogLogを返します。最大標準誤差の値は、デフォルトで0.01625です。

empty_approx_set(e) -> HyperLogLog()¶: 最大標準誤差eの空のHyperLogLogを返します。この関数の現在の実装では、eが[0.0040625, 0.26000]の範囲内である必要があります。

merge(HyperLogLog) -> HyperLogLog()¶: 個々のhll HyperLogLog構造の集合和のHyperLogLogを返します。

merge_hll(array(HyperLogLog)) -> HyperLogLog()¶: hll HyperLogLog構造の配列の和集合のHyperLogLogを返します。