ApsaraDB for SelectDB の HLL 機能を使用して重複を削除する - ApsaraDB for SelectDB

このトピックでは、ApsaraDB for SelectDB が提供する HyperLogLog（HLL）機能を使用して重複を削除し、クエリを高速化する方法について説明します。

概要

実際のビジネスシナリオでは、ビジネスデータの量が増加するにつれて、データ重複削除の負荷が増加します。データ量が特定の規模に達すると、正確な重複削除のコストも増加します。許容できる場合は、近似重複削除アルゴリズムを使用して重複をすばやく削除し、計算の負荷を軽減できます。

ApsaraDB for SelectDB は、近似重複削除を実装するための HLL アルゴリズムを提供します。HLL は、O(log(logn)) 形式で表される優れた空間計算量と、O(n) 形式で表される時間計算量をサポートしています。計算結果の誤差率は、データセットのサイズと使用されるハッシュ関数に応じて、約 1% ～ 2% に制御できます。

HLL のしくみ

HLL アルゴリズムは、LogLog アルゴリズムのアップグレードバージョンであり、近似重複削除をサポートしています。その数学的根拠はベルヌーイ試行です。

数学的根拠

コインには 2 つの面があります。コインを投げた後、コインの表または裏が出る確率は 50% です。コインの表が出るまでコインを投げ続け、これを完全なベルヌーイ試行として記録します。このように、n 回のベルヌーイ試行を実行すると、コインの表が n 回出ます。

たとえば、1 回のベルヌーイ試行でコインを k 回投げたとします。最初のベルヌーイ試行でコインを投げた回数は k1 です。n 番目のベルヌーイ試行では、コインを投げた回数は kn です。n の値はベルヌーイ試行の回数とともに増加します。ベルヌーイ試行の中で、コインを投げた回数の最大値は k になり、これはコインを k 回投げた後に表が出たことを示します。コインを投げた回数の最大値は k_max と呼ばれます。ベルヌーイ試行に基づいて、次の結論を導き出すことができます。

kn は k_max より大きくありません。
kn は少なくとも 1 つのベルヌーイ試行で k_max と等しくなります。

最尤推定（MLE）法と組み合わせると、n と k_max の間には次の推定相関関係があります。n = 2^k_max k_max だけを記録すれば、データレコードの総数、つまりカーディナリティを推定できます。

推定誤差

次の結果が得られたとします。

最初の試行では、表が出るまでコインを 3 回投げました。この場合、k = 3、n = 1 です。
2 番目の試行では、表が出るまでコインを 2 回投げました。この場合、k = 2、n = 2 です。
3 番目の試行では、表が出るまでコインを 6 回投げました。この場合、k = 6、n = 3 です。
...
n 番目の試行では、表が出るまでコインを 12 回投げました。この場合、n = 2^12 です。

最初の 3 つの試行に基づくと、k_max = 6、n = 3 です。これらの値を推定式に適用すると、計算値 2^6 は 3 と等しくありません。これは、試行回数が少ない場合、この推定方法の誤差率が高いことを示しています。

3 つの試行は 1 ラウンドの推定を構成します。1 ラウンドの推定のみを実行し、n が大きい場合、推定誤差率は比較的減少しますが、それでも低くはありません。

HLL 関数

HLL 機能は、HLL アルゴリズムに基づくエンジニアリング実装です。HLL 関数は、HLL ベースの計算プロセス中に中間結果を保存するために使用されます。HLL は、データを集約することでデータ量を継続的に削減するために、テーブル内の値列の型としてのみ使用できます。これにより、クエリが高速化されます。HLL 機能を使用して得られる推定結果の誤差率は約 1% に達します。HLL 列は、他の列またはインポートされたデータを使用して生成されます。データをインポートする際には、hll_hash 関数を使用して、データ内の HLL 列の生成に使用する列を指定します。HLL 関数は、多くの場合、COUNT DISTINCT 関数の代わりに使用され、ROLLUP 関数とともに使用して、ユニークビジター数（UV）をすばやく計算します。

次の HLL 関数が提供されています。

HLL_UNION_AGG(hll)
この関数は集計関数であり、条件を満たすすべてのデータの推定カーディナリティを計算するために使用されます。
HLL_CARDINALITY(hll)
この関数は、単一の HLL 列の推定カーディナリティを計算するために使用されます。
HLL_HASH(column_name)
この関数は、データの挿入またはインポート時に HLL 列を生成するために使用されます。この関数の使用方法の詳細については、このトピックの例セクションを参照してください。

例

HLL 列を含むテーブルを作成します。
```
CREATE TABLE test_hll(
    dt date,
    id int,
    name char(10),
    province char(10),
    os char(10),
    pv hll hll_union  /* PV を格納するための HLL 列 */
)
Aggregate KEY (dt,id,name,province,os)
distributed by hash(id) buckets 10
PROPERTIES(
    "replication_num" = "1",
    "in_memory"="false"
);
```
重要
HLL 関数を使用する場合は、次の項目に注意してください。
- HLL 関数を使用して列から重複を削除する場合は、CREATE TABLE ステートメントで列の型を HLL に、列の集計型を HLL_UNION に設定する必要があります。
- HLL 列をキー列として使用することはできません。
- HLL 列の長さまたはデフォルト値を指定する必要はありません。長さは、データの集計度に基づいてシステムによって指定されます。

データをインポートします。

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

次のいずれかの方法でデータをインポートします。

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
/* id 列に基づいて HLL 列を生成 */

{
    "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 /* Broker Load のラベル */
 (
    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) /* id 列に基づいて HLL 列を生成 */
    )
 );

データをクエリします。

HLL 列の元の値を直接クエリすることはできません。HLL_UNION_AGG 関数を使用することによってのみ、HLL 列の元の値をクエリできます。

ページビュー（PV）の総数を計算します。サンプルコード：

SELECT HLL_UNION_AGG(pv) FROM test_hll;
+---------------------+
| hll_union_agg(`pv`) |
+---------------------+
|                   4 |
+---------------------+
1 row in set (0.00 sec)

返される結果は、(DISTINCT pv) 関数によって返される結果と同じです。

SELECT COUNT(DISTINCT pv) FROM test_hll;
+----------------------+
| count(DISTINCT `pv`) |
+----------------------+
|                    4 |
+----------------------+
1 row in set (0.01 sec)

1 日の PV を計算します。サンプルコード：

SELECT HLL_UNION_AGG(pv) FROM test_hll GROUP BY dt;
+---------------------+
| hll_union_agg(`pv`) |
+---------------------+
|                   4 |
|                   4 |
+---------------------+
2 rows in set (0.01 sec)