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

データ構造

Trinoは、HyperLogLogデータスケッチを32ビットのバケットのセットとして実装しています。これらのバケットは最大ハッシュ値を格納します。これらは、疎に格納される場合（バケットIDからバケットへのマップとして）、または密に格納される場合（連続したメモリブロックとして）があります。HyperLogLogデータ構造は、効率的な場合には密な表現に切り替わるように、最初は疎な表現として始まります。P4HyperLogLog構造は、密に初期化され、その寿命全体で密に保たれます。

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

cast(hll AS P4HyperLogLog)

シリアル化

データスケッチは、varbinaryにシリアル化およびデシリアル化することができます。これにより、後で使用するために保存することができます。複数のスケッチをマージする能力と組み合わせると、クエリのパーティションの要素のapprox_distinctを計算し、後でクエリ全体で非常に少ないコストで計算することができます。

例えば、日別のユニークユーザーのHyperLogLogを計算することで、週次または月次のユニークユーザーを、日次を組み合わせることで逐次的に計算することができます。これは、日次収益を合計することで週次収益を計算するのと似ています。GROUPING SETSを使用したapprox_distinctの使用法は、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()

approx_set(x) → HyperLogLog

入力データセットxのHyperLogLogスケッチを返します。このデータスケッチはapprox_distinctの基礎となり、後でcardinality()を呼び出すことで保存および後で使用することができます。

cardinality()

cardinality(hll) → bigint

これは、hll HyperLogLogデータスケッチによって要約されたデータに対してapprox_distinctを実行します。

empty_hll()

empty_hll() → HyperLogLog

空のHyperLogLogを返します。