Use Bitmap for exact count distinct

ビットマップを使用した正確な重複カウントのための使用方法

このトピックでは、StarRocksでビットマップを使用して一意の値の数を計算する方法について説明します。

ビットマップは、配列内の一意の値の数を計算するための便利なツールです。この方法は、従来の重複カウントと比較して、より少ないストレージスペースを使用し、計算を高速化することができます。[0、n)の値範囲を持つ配列Aがあると仮定します。 (n+7)/8バイトのビットマップを使用すると、配列内の一意の要素の数を計算できます。これには、すべてのビットを0に初期化し、要素の値をビットの添字として設定し、すべてのビットを1に設定します。ビットマップ内の1の数は、配列内の一意の要素の数です。

従来の重複カウント

StarRocksは、重複カウントを使用する際に詳細なデータを保持することができるMPPアーキテクチャを使用しています。ただし、重複カウント機能はクエリ処理中に複数のデータシャッフルが必要であり、データの量が増加するにつれてパフォーマンスが線形に低下します。

以下のシナリオでは、テーブル(dt、page、user_id)内の詳細データに基づいてUV（Unique Visitors）を計算します。

dt	page	user_id
20191206	game	101
20191206	shopping	102
20191206	game	101
20191206	shopping	101
20191206	game	101
20191206	shopping	101

StarRocksは、次の図に示すようにデータを計算します。まず、データをpageとuser_idの列でグループ化し、その後に処理結果をカウントします。

注: この図は、2つのBEノードで計算された6行のデータの概略図です。

複数のシャッフル操作を必要とする大量のデータを処理する場合、必要な計算リソースが大幅に増加することがあります。これにより、クエリが遅くなります。ただし、ビットマップテクノロジーを使用すると、この問題を解決し、このようなシナリオでクエリのパフォーマンスを向上させることができます。

pageごとにUV（Unique Visitors）をカウントする場合:

select page, count(distinct user_id) as uv from table group by page;

|  page   |   uv  |
| :---: | :---: |
|   game  |  1   |
|   shopping  |   2  |

ビットマップを使用した重複カウントの利点

以下の点で、COUNT(DISTINCT expr)に比べてビットマップを使用することで利点が得られます:

ストレージスペースの削減: INT32データの一意の値の数をビットマップを使用して計算する場合、必要なストレージスペースはCOUNT(DISTINCT expr)の1/32のみです。StarRocksでは、圧縮されたローリングビットマップを使用して計算を実行するため、従来のビットマップと比較してストレージスペースの使用量がさらに減少します。
高速な計算: ビットマップはビット演算を使用しており、COUNT(DISTINCT expr)と比較して計算が高速化されます。StarRocksでは、一意の値の数の計算を並列で処理することができ、クエリのパフォーマンスがさらに向上します。

ローリングビットマップの実装については、specific paper and implementationを参照してください。

使用上の注意点

ビットマップインデックスとビットマップの重複カウントの両方が、ビットマップ技術を使用しています。ただし、これらを導入する目的と解決する問題は完全に異なります。前者は、基数が低い固定列をフィルタリングするために使用されます。後者は、データ行の値列における一意の要素の数を計算するために使用されます。
StarRocksの2.3以降のバージョンでは、集約テーブル、Duplicate Keyテーブル、Primary Keyテーブル、Unique Keyテーブルのいずれのタイプでも、値列をBITMAPとして定義することがサポートされています。ただし、テーブルのソートキーはBITMAPタイプにすることはできません。
テーブルを作成する際、値列をBITMAPと定義し、集約関数をBITMAP_UNIONにすることができます。
次のデータ型のデータに対してのみ、ローリングビットマップを使用して重複する値の数を計算できます：TINYINT、SMALLINT、INT、BIGINT。他のデータ型のデータの場合、グローバルディクショナリを構築する必要があります。

ビットマップを使用した重複カウント

ページのUV（Unique Visitors）の計算を例にとります。

ビットマップ関数BITMAP_UNIONを使用したBITMAP列visit_usersを持つ集約テーブルを作成します。

CREATE TABLE `page_uv` (
  `page_id` INT NOT NULL COMMENT 'page ID',
  `visit_date` datetime NOT NULL COMMENT 'access time',
  `visit_users` BITMAP BITMAP_UNION NOT NULL COMMENT 'user ID'
) ENGINE=OLAP
AGGREGATE KEY(`page_id`, `visit_date`)
DISTRIBUTED BY HASH(`page_id`)
PROPERTIES (
  "replication_num" = "3",
  "storage_format" = "DEFAULT"
);

このテーブルにデータをロードします。INSERT INTOを使用してデータをロードします:

INSERT INTO page_uv VALUES
(1, '2020-06-23 01:30:30', to_bitmap(13)),
(1, '2020-06-23 01:30:30', to_bitmap(23)),
(1, '2020-06-23 01:30:30', to_bitmap(33)),
(1, '2020-06-23 02:30:30', to_bitmap(13)),
(2, '2020-06-23 01:30:30', to_bitmap(23));

データがロードされた後:ローカルファイルからデータをロードします:

echo -e '1,2020-06-23 01:30:30,130\n1,2020-06-23 01:30:30,230\n1,2020-06-23 01:30:30,120\n1,2020-06-23 02:30:30,133\n2,2020-06-23 01:30:30,234' > tmp.csv | 
curl --location-trusted -u <username>:<password> -H "label:label_1600960288798" \
    -H "column_separator:," \
    -H "columns:page_id,visit_date,visit_users, visit_users=to_bitmap(visit_users)" -T tmp.csv \
    http://StarRocks_be0:8040/api/db0/page_uv/_stream_load

行page_id = 1, visit_date = '2020-06-23 01:30:30'には、visit_usersフィールドに3つのビットマップ要素（13, 23, 33）が含まれています。
行page_id = 1, visit_date = '2020-06-23 02:30:30'には、visit_usersフィールドに1つのビットマップ要素（13）が含まれています。
行page_id = 2, visit_date = '2020-06-23 01:30:30'には、visit_usersフィールドに1つのビットマップ要素（23）が含まれています。

ページのUV（Unique Visitors）を計算します。

SELECT page_id, count(distinct visit_users) FROM page_uv GROUP BY page_id;
+-----------+------------------------------+
|  page_id  | count(DISTINCT `visit_users`)|
+-----------+------------------------------+
|         1 |                            3 |
|         2 |                            1 |
+-----------+------------------------------+
2 rows in set (0.00 sec)

グローバルディクショナリ

現在、ビットマップベースの重複カウント機構は、入力が整数であることを必要とします。ビットマップに他のデータ型を使用する必要がある場合は、他のタイプのデータ（文字列型など）を整数型にマッピングするために独自のグローバルディクショナリを構築する必要があります。グローバルディクショナリを構築するためのいくつかのアイデアがあります。

Hiveテーブルベースのグローバルディクショナリ

この方式では、グローバルディクショナリ自体がHiveテーブルであり、生の値とエンコードされたInt値の2つの列を持っています。グローバルディクショナリを生成するための手順は次のとおりです。

ファクトテーブルのディクショナリ列を重複排除して、一時テーブルを生成します。
一時テーブルとグローバルディクショナリを左結合し、new valueを一時テーブルに追加します。
new valueをエンコードしてグローバルディクショナリに挿入します。
ファクトテーブルと更新されたグローバルディクショナリを左結合し、IDで辞書の項目を置換します。

この方法により、グローバルディクショナリを更新することができ、値列をSparkまたはMRを使用して置換することができます。トライ木ベースのグローバルディクショナリと比較して、このアプローチは分散可能であり、グローバルディクショナリを再利用することができます。

ただし、いくつかの注意点があります：元のファクトテーブルが複数回読み込まれ、グローバルディクショナリの計算中に多くの余分なリソースを消費する2つの結合があることに注意してください。

トライツリーベースのグローバルディクショナリを構築する

ユーザーは、トライツリー（プレフィックスツリーまたはディクショナリツリーとも呼ばれる）を使用して独自のグローバルディクショナリを構築することもできます。トライツリーは、ノードの子孫に共通の接頭辞があり、クエリ時間を短縮し、文字列の比較を最小限に抑えることができるため、ディクショナリエンコーディングの実装に適しています。ただし、トライツリーの実装は分散化が難しく、データボリュームが比較的大きい場合にパフォーマンスのボトルネックを引き起こす可能性があります。

グローバルディクショナリを構築し、他のタイプのデータを整数データに変換することで、ビットマップを使用して非整数データ列の正確な重複カウント分析を実行することができます。

ビットマップを使用した正確な重複カウントのための使用方法

従来の重複カウント​

ビットマップを使用した重複カウントの利点​

使用上の注意点​

ビットマップを使用した重複カウント​

グローバルディクショナリ​

Hiveテーブルベースのグローバルディクショナリ​

トライツリーベースのグローバルディクショナリを構築する​