いろいろなBitmap Indexの紹介

プレイドが提供するKARTEでは、エンドユーザの行動データを活用するためにさまざまな分析機能を提供しています。

データベースの裏側を支えるデータ構造にもさまざまなものがあり、それらを正しく理解し活用していくことは分析のサービスを提供する上で非常に重要です。

この記事ではBitmap Indexにフォーカスし、ナイーブなBitmap IndexとRoaring BitmapやBit-Sliced Indexについて解説します。

弊社の記事で手前味噌ですが、OLAPの技術全般については以下の記事も非常に参考になるのでオススメです。
OLAP DBの技術要素の基礎

ナイーブなBitmap Index

最も基本的なBitmap Indexは、カラム内の特定の値ごとに一つのビットマップを持つ構造です。このビットマップでは、各ビットがテーブル内の一つの行（行番号）に対応します。その値を持つ行であればビットを1、持たなければ0とします。

例えば商品テーブルに「商品カテゴリ」というカラムがあり、以下のデータが入っているとします。

この商品カテゴリカラムに対してBitmap Indexを作成すると、以下のようになります。

• トップス: 11100 (0, 1, 2番目の行がトップス)
• ボトムス: 00011 (3, 4番目の行がボトムス)

最大の利点はANDやORをBit演算で高速に計算できることです。

例えば、「トップスまたはボトムスの商品を抽出する」場合、11100 OR 00011 = 11111
となり、全ての行が該当することが分かります。

また、該当するエントリ数の算出はpopcntでできてしまいます。

主な弱点は以下です。

• サイズが大きくなりやすい
  • カーディナリティ(カラム内のユニークな値の数)の分ビットマップを持たなければならず、特にカーディナリティが高い時に大きくなります。
  • 値がスパースな時に非効率です。例えば100万行の商品テーブルで「虹色」の商品が1つだけある場合、「虹色」のビットマップは「00...010...00」のようにほとんどが0で占められます。これなら、単に対応する行番号のリスト（例：[2500]）で持つ方がはるかにコンパクトです。
  • (基本的にはカーディナリティが高いカラムはスパースな値が多いです。多値型の場合はその限りではありませんが)
• 範囲検索が非効率
  • 例えば商品価格のような値に対してBitmap Indexをそのまま使って「1000円以上の商品」を検索する場合、1000円、1001円、1002円… といった個別の価格に対応する全てのビットマップを取得し、ORを取らなければなりません。

Roaring Bitmap

Bitmapの良さを活かしつつ弱点を克服するためのフォーマットがいくつかあります。有名なものがWAH (Word Aligned Hybrid), Concise Bitmap, そしてRoaring Bitmapです。
雑にまとめるとどの手法も、決まった方針でBitmapを分割して、1と0が満遍なく混在するパーツは純粋なBitmapとして扱いつつ、スパースなパーツは行IDのリストやRun-Length Encodingで保持する、という仕組みです。

OLAP分野だとRoaring Bitmapが特に人気なようで、IndexにはRoaring Bitmapが優先されることが多いと思います。以下はRoaring Bitmapについて説明します。

Roaring Bitmapの仕組み

Roaring Bitmapでは、Bitmapを最大65,536(2^16)個の要素で構成されるコンテナに分けます。コンテナはBitmap / Arrayのどちらかで表現します。

• Bitmap: スパースではない場合、65,536ビット（8KB）のビットマップとして格納します。
• Array: スパースな場合(デフォルトでは1が4096個以下)、要素の値を整数のソート済み配列としてそのまま格納します。

(進化版ではRun-Length Encodingという3種類目のコンテナもありますが、今回は割愛します。)

AND/ORなどの論理演算はコンテナ単位で行われ、コンテナの組み合わせごとにアルゴリズムがあります。例えばAND演算は以下です。

• Bitmap vs Bitmap: 通常のビットワイズAND演算。
• Bitmap vs Array: Array内の各要素について、Bitmapの対応するビットを確認。
• Array vs Array: ソート済み配列同士のマージ処理に似た方法で共通要素を探索。

(int32を扱うとして、実際にはcontainerの要素には下位16bitを入れ、上位16bitはコンテナ毎に持ちます。足し合わせることで元のint32に復元できます。)

Arrayコンテナが関わる演算はBitmapコンテナ同士の演算と比べると非効率ですが、そもそも要素数が少ないため大して問題にならない、というのが良くできているところだと思います。また、WAHやConcise Bitmapではワード単位でBitmapかRun-lengthかを区別しますが、Roaring Bitmapでは大きい括りで決まったサイズで分けたことで、オーバヘッドが少なくなったことがポイントだと思います。

余談ですが、OSSのOLAP DBであるApache Druidでは、デフォルトで文字列型の全カラムに対してRoaring Bitmap Indexが作られます。大胆ですね。実際KARTEで扱うような行動データをDruidにロードして試したことがありますが、Bitmap Indexのサイズはカラムナ部分と同程度に収まり、フィルタリングもかなり早くなりました。

また、数値型に対して作らない理由は以下だと思います。

• カーディナリティが高いことが多い(年齢や会員ランクなど、反例も多そうですが)
• 固定長で値が小さいためカラムナフォーマットだけでも十分早い(SIMD / CPUキャッシュ / CPUレベルでの並列化が効きやすい)

Bit-Sliced Index

Bitmap Indexの弱点に対応するフォーマットとして、Bit-Sliced Indexもあります。ざっくり言えば数値型に向いてるIndexです。(Roaring BitmapはBitmap単体のフォーマットですが、Bit-Sliced Indexはindex全体のフォーマットです。組み合わせることもできます。)

Bit-Sliced Indexは、カラムの値を特定の基数で分解（スライス）し、各ビット位置ごとにビットマップを作成します。

以下は商品価格を基数2で表現(=2進数)する例です。B[i]は2進数表現の、i bit目を意味します。

Bit-Sliced Indexでは、物理的には縦方向のBitmapを持ちます。この例では行数が4で桁数が8(bit)なので、長さ4のBitmapが8個作られます。

ナイーブなBitmap Indexでは行番号を指し示すBitmapが値ごとに作られますが、今回は値自体もBitmapでエンコーディングするのでこんがらがりがちです。上記の表を行列と捉えて、横方向のBitmapは値自体の表現であり、縦方向のBitmapは値の特定の桁が一致する行番号を指し示すBitmapと言えます。

価格が最大で255円だとすると、基数2のBlit-Sliced Indexで必要なビットマップは8個です。ナイーブなBitmap Indexなら最大256個のビットマップが必要になることと比べると、大幅にサイズを抑えられることが分かります。

Bit-Sliced Indexによる合計計算（基数2の場合）

応用のアルゴリズムとして、Bit-Sliced Indexでカラムに含まれる値の合計値が計算できます。

元々の目的である索引以外にも使えるのが面白いです。

/**
 * B: 特定カラムCのBit-Sliced Index (B[i]はi番目のビットに対応するビットマップ)
 * Bf: 条件を満たす行を示すビットマップ (Foundset)
 * num_bits: 値を表現するのに必要なビット数(横方向のBitmapのビット数)
**/
int sum = 0;
for (int i = 0; i < num_bits; ++i) {
    // i番目のビットが立っている行だけを対象に、2^i を加算
    sum += 2^i * POPCOUNT(B[i] AND Bf);
}
return sum;

基数

ここまで基数2を例にしてきましたが、他の基数を取ることもできます。例えば基数10とすると、1000未満の整数であれば100,10,1の位の3つの10bitのスライスで表現し、位の値がNならスライスの右からN番目に1を立てます。

例えば230は100の位が2、10の位が3、1の位が0なので、以下のようになります。

0000000100(100の位) 0000001000(10の位) 0000000001(1の位)

基数は単一である必要はなく、位ごとに変えることもできます。

基数の増減に伴うトレードオフはサイズとクエリ効率にあるようです。基数を増やすサイズは増えますが、例えば等価検索の効率が良くなることは明らかです。

Encodingと検索

値のBitmap(横方向)のEncodingのバリエーションとして、Equality EncodingとRange Encodingがあります。

Equality Encodingは値がNならN番目のbitに1を立てるもので、ここまでで説明してきた方法です。
Range Encodingでは、値がNならN番目のbitとその左のbit全てに1を立てます。

例えば基数10で230を表現すると、100の桁が2、10の桁が3、1の桁が0ですから、以下のようになります。
0000000100 0000001000 0000000001(Equality Encoding)
1111111100 1111111000 1111111111(Range Encoding)

その名の通り範囲検索に強いエンコーディングです。

それぞれのエンコーディングで等価検索と範囲検索のアルゴリズムがあります。複雑なので、範囲検索の大雑把な方針のみ説明します。

Equality Encodingの範囲検索

例えば特定の値より大きいデータを取る場合、位だけを見て対象の値より大きいと分かる行を取るステップと、同じ位の中で対象の値より大きい行を取るステップがあります。

例えば基数2で 価格 >= 5 (バイナリ: 00000101) を検索する場合、以下の2つの結果の和集合が結果です。

• 8以上255以下の行
  • B[7]からB[3]までのうちどれか一つでも1が立っている(ORで取得)
• 5以上7以下の行
  • B[2]が立っていて、B[1]かB[0]のうちどちらか一つでも1が立ってる(ANDとORで取得)

Range Encodingの範囲検索

特定の値より大きいデータを取る場合、その値のbitだけをチェックします。例えば基数10で値が200以上のデータを取る場合、100の位のスライスの右から1番目のbitが0である行を取得します。

まとめ・感想

Bitmap Indexと言えばデカいイメージがありますが、対策としていろいろなアイデアが提案されています。こんなにアイデアを凝らすほどAND/ORの効率が重要であり、それが早く処理できるBitmapが魅力的ということですね。

Roaring Bitmapに比べるとBit-Sliced Indexはそこまで流行ってないような気もします。カラムナDBであれば数値型はカラムナだけ十分早いからでしょうか。行指向のDBでは有用な気もしますが、更新が重いからかもしれません。

また、Bit-Sliced Indexの基数とエンコーディングについては、クエリやデータパターンに応じて選ぶのが重要な気がします。それぞれの特性・トレードオフを整理するところまでは今回は辿り着けませんでしたが、興味があれば各種論文を見てみると良いかもしれません。

参考資料

Improved query performance with variant indexes | ACM SIGMOD Record
Bitmap index design and evaluation | ACM SIGMOD Record
[1004.0403] CONCISE: Compressed 'n' Composable Integer Set
Roaring Bitmaps