Use HLL for approximate count distinct

アプロックスな重複件数のカウントにHLLを使用する

背景

実世界のシナリオでは、データのボリュームが増えるにつれて、データの重複排除の圧力が高まります。データのサイズが一定のレベルに達すると、正確な重複排除のコストは比較的高くなります。この場合、一般的には計算の負荷を軽減するために、近似アルゴリズムを使用します。このセクションでは紹介されるHyperLogLog（HLL）は、優れた空間計算量O(mloglogn)と時間計算量O(n)を持つ近似重複排除アルゴリズムであり、データセットのサイズおよび使用されるハッシュ関数に応じて、計算結果の誤差率を約1%から10%に制御できます。

HyperLogLogとは

HyperLogLogは、非常に少ないストレージスペースを消費する近似的な重複排除アルゴリズムです。HyperLogLogアルゴリズムの実装には、HLL型が使用されます。これは、HyperLogLogの計算の中間結果を保持し、データテーブルの指標列タイプとしてのみ使用できます。

HLLアルゴリズムは、多くの数学的な知識を必要とするため、実例を使用して説明します。まず、試行 A というランダム化された実験を設計します。これは、最初のヘッドが出るまでコインを独立して反復的に投げ、最初のヘッドのコイン投げ回数を確率変数 X として記録するものです。その場合、

X=1, P(X=1)=1/2
X=2, P(X=2)=1/4
...
X=n, P(X=n)=(1/2)n

次に、テスト A からテスト B を構築します。このテストでは、テスト A のデータセット要素に対して N 回独立にテスト A のプロセスを繰り返し、N 個の独立した同一分布の確率変数 X1, X2, X3, ..., XN を生成します。これらの確率変数の最大値を Xmax とします。最尤推定を活用して、N の推定値は 2Xmax です。

次に、ハッシュ関数を使用して与えられたデータセット上で上記の実験をシミュレーションします:

テスト A: データセット要素のハッシュ値を計算し、ハッシュ値を2進数表現に変換します。2進数の最下位ビットからのbit=1の出現を記録します。
テスト B: テスト A のプロセスをテスト B のデータセット要素に対して繰り返します。各テストの最初のビット1の出現の最大位置 "m" を更新します。
データセット内の重複しない要素数を m2 と推定します。

実際には、HLLアルゴリズムでは、要素を下位のkビットに基づいてK=2kのバケットに分割します。k+1ビット目以降での最初のビット1の出現の最大値をm1, m2,..., mkと数え、バケット内の重複しない要素数を2m1, 2m2,..., 2mkと推定します。データセット内の重複しない要素数は、バケットの数とバケット内の重複しない要素数の積の平均を合算します: N = K(K/(2-m1+2-m2,..., 2-mK)).

HLLは、推定結果に補正係数を乗算して結果をより正確にします。

HLLの実装については、以下の記事https://gist.github.com/avibryant/8275649を参照してください。

SELECT floor((0.721 * 1024 * 1024) / (sum(pow(2, m * -1)) + 1024 - count(*))) AS estimate
FROM(select(murmur_hash3_32(c2) & 1023) AS bucket,
     max((31 - CAST(log2(murmur_hash3_32(c2) & 2147483647) AS INT))) AS m
     FROM db0.table0
     GROUP BY bucket) bucket_values

このアルゴリズムは、db0.table0のcol2の重複を排除します。

ハッシュ関数 murmur_hash3_32 を使用してcol2のハッシュ値を計算します（32ビット整数として）。
1024のバケットを使用し、補正係数は0.721で、ハッシュ値の下位10ビットをバケットの添字として使用します。
ハッシュ値の符号ビットを無視し、次に高いビットから最下位ビットまでを調べ、最初のビット1の位置を決定します。
ハッシュ値をバケットでグループ化し、MAX集約関数を使用してバケット内の最初のビット1の位置の最大値を見つけます。
集約結果をサブクエリとして使用し、すべてのバケットの推定値の合計平均をバケットの数と補正係数に乗算します。
空のバケットの数は1とします。

上記のアルゴリズムは、データのボリュームが大きい場合に非常に低い誤差率を持ちます。

これがHLLアルゴリズムの中心的なアイデアです。興味がある場合は、以下のHyperLogLog paperも参照してください。

HyperLogLogの使用方法

HyperLogLogの重複排除を使用するためには、テーブルの作成文でターゲットの指標列タイプをHLL、集約関数をHLL_UNIONに設定する必要があります。
現在、集約モデルのみがHLLを指標列タイプとしてサポートしています。
HLLタイプの列でcount distinctを使用すると、StarRocksは自動的にHLL_UNION_AGGの計算に変換します。

例

まず、以下のようなHLLカラムを持つテーブルを作成します。uvは集約カラムであり、カラムタイプはHLLで、集約関数はHLL_UNIONです。

CREATE TABLE test(
        dt DATE,
        id INT,
        uv HLL HLL_UNION
)
DISTRIBUTED BY HASH(ID);

注意: データのボリュームが大きい場合、高頻度なHLLクエリに対して対応するロールアップテーブルを作成することをお勧めします。

Stream Loadを使用してデータをロードします：

curl --location-trusted -u <username>:<password> -H "label:label_1600997542287" \
    -H "column_separator:," \
    -H "columns:dt,id,user_id, uv=hll_hash(user_id)" -T /root/test.csv http://starrocks_be0:8040/api/db0/test/_stream_load
{
    "TxnId": 2504748,
    "Label": "label_1600997542287",
    "Status": "Success",
    "Message": "OK",
    "NumberTotalRows": 5,
    "NumberLoadedRows": 5,
    "NumberFilteredRows": 0,
    "NumberUnselectedRows": 0,
    "LoadBytes": 120,
    "LoadTimeMs": 46,
    "BeginTxnTimeMs": 0,
    "StreamLoadPutTimeMs": 1,
    "ReadDataTimeMs": 0,
    "WriteDataTimeMs": 29,
    "CommitAndPublishTimeMs": 14
}

ブローカーロードモード：

LOAD LABEL test_db.label
 (
    DATA INFILE("hdfs://<hdfs_host>:<hdfs_port>/user/starrocks/data/input/file")
    INTO TABLE `test`
    COLUMNS TERMINATED BY ","
    (dt, id, user_id)
    SET (
      uv = HLL_HASH(user_id)
    )
 );

データのクエリ

HLL列では、その元の値を直接クエリすることはできません。代わりに、関数HLL_UNION_AGGを使用します。
総uv数を求める場合、

SELECT HLL_UNION_AGG(uv) FROM test;

この文は、以下と等価です

SELECT COUNT(DISTINCT uv) FROM test;

各日のuvをクエリする場合

SELECT COUNT(DISTINCT uv) FROM test GROUP BY ID;

注意事項

BitmapとHLLのどちらを選ぶべきですか？データセットのベースが数百万または数千万であり、数十台のマシンがある場合はcount distinctを使用します。ベースが数億であり、正確な重複排除が必要な場合はBitmapを使用します。近似的な重複排除が許容される場合は、HLL型を使用します。

Bitmapは、TINYINT、SMALLINT、INT、BIGINTのみをサポートしています。ただし、LARGEINTはサポートされていません。他のタイプのデータセットを重複排除する場合、元のタイプを整数タイプにマッピングするための辞書を構築する必要があります。辞書の構築は複雑で、データのボリューム、更新頻度、クエリの効率、ストレージなどの問題のトレードオフが必要です。HLLは辞書を必要とせず、対応するデータ型はハッシュ関数をサポートする必要があります。HLLを内部でサポートしていない解析システムでも、ハッシュ関数とSQLを使用してHLLの重複排除を実装することができます。

一般的なカラムに対しては、NDV関数を使用して近似的な重複排除を行うことができます。この関数は、COUNT(DISTINCT col)の結果の近似集計を返し、内部実装ではデータのストレージタイプをHyperLogLogタイプに変換して計算します。NDV関数は計算に多くのリソースを消費するため、高並行性のシナリオには適していません。

ユーザーの行動分析を行いたい場合は、IntersectCountまたはカスタムのUDAFを検討することができます。

アプロックスな重複件数のカウントにHLLを使用する

背景​

HyperLogLogとは​

HyperLogLogの使用方法​

例​

注意事項​

背景

HyperLogLogとは

HyperLogLogの使用方法

例

注意事項