ApsaraDB for SelectDB の HLL 機能を使用した重複排除 - ApsaraDB for SelectDB

HyperLogLog (HLL) は、ApsaraDB for SelectDB に組み込まれた近似重複排除アルゴリズムです。正確な個別カウントが不要な場合、HLL は COUNT DISTINCT よりも高速に実行され、使用するメモリもはるかに少なくなります。そのため、日次のユニークビジター (UV) 数やページビュー統計などの大規模な分析ワークロードに適しています。

HLL は、空間計算量 O(log(logn)) と時間計算量 O(n) を実現します。一般的な誤差率は約 1% です。実際の誤差率は、データセットのサイズと使用されるハッシュ関数に依存します。

HLL を使用する場合

次の両方の条件が当てはまる場合に HLL を使用してください。

データセットが大規模で、正確な重複排除のコストが高くなる規模にデータ量が達している。
概算結果が許容される。例えば、日次の UV 数やページビュー統計など。

正確な重複排除が必要な場合は、代わりに COUNT DISTINCT を使用してください。

HLL の仕組み

HLL は、LogLog アルゴリズムの改良版です。その数学的基礎はベルヌーイ試行です。

数学的基礎

ベルヌーイ試行は、コイン投げの実験です。表が出るまでコインを繰り返し投げ、投げた回数を k として記録します。この実験を n 回繰り返します。すべての試行における投げた回数の最大値は k_max です。

最尤推定 (MLE) を使用すると、推定されるカーディナリティ (個別値の総数) は次のようになります。

n = 2^k_max

k_max のみを記録すれば、カーディナリティを推定するのに十分です。生の値を保存する必要はありません。

推定誤差

n が小さい場合、1 回の推定ラウンドでは誤差率が高くなります。例えば、k_max = 6 の 3 回の試行後、式で計算すると 2^6 = 64 となりますが、これは実際の n = 3 とは大きく異なります。試行回数が増えるにつれて、誤差は減少します。

SelectDB における HLL の実装

SelectDB の HLL 機能は、HLL アルゴリズムのエンジニアリング実装です。HLL 列は、生の値ではなく中間計算状態を保存します。SelectDB は、この状態を継続的に集約してデータ量を削減し、クエリを高速化します。HLL 機能を使用して得られる推定結果の誤差率は約 1% です。

HLL は、値列としてのみ使用でき (キー列としては使用できません)、HLL_UNION 集約タイプを使用します。システムは、集約の程度に基づいて列の長さを自動的に決定します。長さやデフォルト値を指定する必要はありません。

HLL は、COUNT DISTINCT を置き換えるために一般的に使用され、ROLLUP 機能と連携して時間範囲全体で効率的に UV 数を計算します。

HLL 関数

関数	説明
`HLL_UNION_AGG(hll)`	集約関数。クエリ条件に一致するすべての行の推定カーディナリティを計算します。
`HLL_CARDINALITY(hll)`	単一の HLL 列値の推定カーディナリティを計算します。
`hll_hash(column_name)`	指定されたソース列から HLL 列値を生成します。データの挿入またはインポート時にこの関数を使用します。

説明

HLL 列をクエリするには、HLL_UNION を使用してください。HLL 列の生の値を直接選択することはできません。

日付別の UV 数のカウント

この例では、集計テーブルを作成し、サンプルデータをロードし、HLL を使用して UV 数をクエリします。

ステップ 1：HLL 列を持つテーブルの作成

CREATE TABLE test_hll(
    dt date,
    id int,
    name char(10),
    province char(10),
    os char(10),
    pv hll hll_union
)
Aggregate KEY (dt,id,name,province,os)
distributed by hash(id) buckets 10
PROPERTIES(
    "replication_num" = "1",
    "in_memory"="false"
);

重要

HLL 列を定義する際は、次の点に注意してください。

列タイプを hll に、集約タイプを hll_union に設定します。
HLL 列をキー列として設定しないでください。
長さやデフォルト値を指定しないでください。システムが自動的に長さを設定します。

ステップ 2：データのインポート

次の内容を含む CSV ファイル (test_hll.csv) を準備します。

2022-05-05,10001,Test 01,Beijing,windows
2022-05-05,10002,Test 01,Beijing,linux
2022-05-05,10003,Test 01,Beijing,macos
2022-05-05,10004,Test 01,Hebei,windows
2022-05-06,10001,Test 01,Shanghai,windows
2022-05-06,10002,Test 01,Shanghai,linux
2022-05-06,10003,Test 01,Jiangsu,macos
2022-05-06,10004,Test 01,Shaanxi,windows

以下のインポート方法では、hll_hash(id) を使用して、id 列から pv HLL 列にデータを入力します。

Stream Load

curl --location-trusted -u root: \
  -H "label:label_test_hll_load" \
  -H "column_separator:," \
  -H "columns:dt,id,name,province,os,pv=hll_hash(id)" \
  -T test_hll.csv \
  http://127.0.0.1:8030/api/demo/test_hll/_stream_load

ロードが成功すると、次のような結果が返されます。

{
    "TxnId": 693,
    "Label": "label_test_hll_load",
    "TwoPhaseCommit": "false",
    "Status": "Success",
    "Message": "OK",
    "NumberTotalRows": 8,
    "NumberLoadedRows": 8,
    "NumberFilteredRows": 0,
    "NumberUnselectedRows": 0,
    "LoadBytes": 320,
    "LoadTimeMs": 23,
    "BeginTxnTimeMs": 0,
    "StreamLoadPutTimeMs": 1,
    "ReadDataTimeMs": 0,
    "WriteDataTimeMs": 9,
    "CommitAndPublishTimeMs": 11
}

Broker Load

LOAD LABEL demo.test_hlllabel
(
    DATA INFILE("hdfs://hdfs_host:hdfs_port/user/doris_test_hll/data/input/file")
    INTO TABLE `test_hll`
    COLUMNS TERMINATED BY ","
    (dt,id,name,province,os)
    SET (
        pv = HLL_HASH(id)
    )
);

ステップ 3：UV 数のクエリ

全期間の合計 UV

SELECT HLL_UNION_AGG(pv) FROM test_hll;

+---------------------+
| hll_union_agg(`pv`) |
+---------------------+
|                   4 |
+---------------------+
1 row in set (0.00 sec)

この結果は COUNT(DISTINCT pv) に相当します:

SELECT COUNT(DISTINCT id) FROM test_hll;

+----------------------+
| count(DISTINCT `id`) |
+----------------------+
|                    4 |
+----------------------+
1 row in set (0.01 sec)

日付別の UV

SELECT HLL_UNION_AGG(pv) FROM test_hll GROUP BY dt;

+---------------------+
| hll_union_agg(`pv`) |
+---------------------+
|                   4 |
|                   4 |
+---------------------+
2 rows in set (0.01 sec)