GoSuda

活気あふれるビットマップ

By snowmerak views ...

ビットマップとは?

ここでのビットマップはインデックスの一種です。グラフィックスを想定して来られた方は、戻るボタンを押していただければ結構です。

基本概念

ビットマップは、データベースのインデキシング技術の一形態です。特定のカラムの値をビット配列またはベクトルの一つの要素や形式で表現し、各ビットが該当カラムの特定の値が存在するかどうかを示します。したがって、最も基本的な形式は、各 row に対してビットインデックスを割り当て、存在の有無を 0 と 1 で表現することです。

例えば、性別カラムを持つテーブルがあると仮定しましょう。このテーブルには 5 つの row があり、性別カラムの値は次のとおりであるとします:

  1. 男性
  2. 女性
  3. 男性
  4. 女性
  5. その他

この場合、性別カラムに対するビットマップインデックスは次のように表現できます:

  • 男性: 10100
  • 女性: 01010
  • その他: 00001

では実際にどこで使うのか

単にこれを表現するためのものではないと、皆さんは考えるでしょう。ビットマップインデックスを適切に活用するために、次のケースを考えてみましょう。

1CREATE TABLE IF NOT EXISTS Users (
2    id INT PRIMARY KEY,
3    name VARCHAR(100),
4    active BOOLEAN,
5    sex BOOLEAN,
6    age INT
7);

このテーブルに 1,000,000 個の row があると仮定しましょう。そして、次のようなクエリを実行するとします。

1SELECT * FROM Users WHERE active = TRUE AND SEX = TRUE;

このクエリは、active と sex カラムの両方が TRUE である row を検索します。この場合、二つのカラムが共に TRUE である条件を満たす row を最も速く見つける方法として、bit and 演算を活用することができるでしょう。

  • active カラムに対するビットマップインデックスが 1100110011... (1,000,000 個のビット配列)として事前にインデックシングされており、
  • sex カラムに対するビットマップインデックスが 1010101010... (1,000,000 個のビット配列)として事前にインデックシングされているとします。

すると、二つのビットマップインデックスに対して bit and 演算を実行することで、両方のカラムが TRUE である row を迅速に見つけることができます。単純なビット演算であるため、他のインデックススキャンよりもはるかに速く結果を得られるでしょう。

トレードオフ

ビットマップインデックスは非常に効率的になり得ますが、いくつかのトレードオフがあります。他にも多くの欠点がありますが、今回は一つだけ取り上げて先に進みます。

それは、ビットマップインデックスは低いカーディナリティ(すなわち、カラムに取りうる値の数が少ない場合)により適しているということです。高いカーディナリティのカラムにビットマップインデックスを用いると、ビットマップが非常に大きくなる可能性があります。

高いカーディナリティのカラムにビットマップインデックスを用いると、各固有値ごとに別々のビットマップを生成する必要があるため、多くの保存領域が必要になり得ます。例えば、カラムに 1,000,000 個の固有値があるならば、1,000,000 個のビットマップを生成しなければならず、これは非常に非効率的になり得ます。

では、私たちは

高いカーディナリティによって生じるビットマップの問題を代替するために、Roaring Bitmap と呼ばれるものを使用することができます。Roaring Bitmap にはさまざまな特性がありますが、最も大きな基本理念と特性は、データの密度に応じて最も適した保存方式を動的に選択し、圧縮率と演算速度の両方を最大化することです。

Roaring Bitmap の基本概念

2 段階インデックシング

Roaring Bitmap は、一つの整数を保存するために、まず次の 2 段階を経ます。2 段階インデックシングという言葉ではありますが、単に二次元配列だと考えていただければ十分です。

  • 上位 16 ビットの抽出: 整数の上位 16 ビットを抽出し、それをインデックスとして使用します。総計 65536 の長さを持つ二次元配列のうち、外側の配列のインデックスとなるのです。この配列は後述するコンテナのアドレスを保存します。
  • 下位 16 ビットの抽出: 整数の下位 16 ビットを抽出し、それをコンテナ内での位置として使用します。

コンテナ

このコンテナは、先ほど例えたとおり、二次元配列のうち内側の配列に該当します。ただし、上位 16 ビットの配列とは異なり、このコンテナは内部データの量に応じて内部構造が変わります。Roaring Bitmap は次の 3 種類のコンテナをサポートします。

  • Array Container: このコンテナは、内部に保存されるデータが少ない場合に使用されます。具体的には、4096 個以下の要素を保存する際に使用されます。このコンテナは単純にソートされた整数配列として実装されています。二分探索によって要素を見つけることができます。
  • Bitmap Container: このコンテナは、内部に保存されるデータが多い場合に使用されます。具体的には、4096 個を超える要素を保存する際に使用されます。このコンテナは 65536 ビット(8192 バイト)のビットマップとして実装されています。各ビットは該当位置の整数が存在するかどうかを示します。
  • Run Container: このコンテナは、連続する整数の範囲を保存する際に使用されます。例えば、1, 2, 3, 4, 5 のような連続した整数を保存する際に効率的です。このコンテナは (開始値, 長さ) のペアのリストとして実装されています。もしすべてが存在するならどうなるでしょうか? それは最初から最後まで全てが存在するという意味なので、(0, 65536) を一つだけ保存すればよいのです。

このような方式により、Roaring Bitmap はメモリを非常に効率的に使用でき、さまざまなデータ密度に対して最適な性能を提供することが可能になります。

Roaring Bitmap の機能

基本機能

Roaring Bitmap は次のような基本機能を提供します。

  • 挿入: 新しい整数をビットマップに追加します。この過程で適切なコンテナを選択したり、必要に応じてコンテナを変換したりすることがあります。
  • 削除: 既存の整数をビットマップから取り除きます。この過程でも、コンテナの状態に応じた適切な処理が行われます。
  • 検索: 特定の整数がビットマップに存在するかどうかを確認します。この過程は非常に速く実行されます。

集合演算

Roaring Bitmap は、さらに次のような集合演算をサポートします。

  • 和集合 (Union): 二つのビットマップのすべての要素を含む新しいビットマップを生成します。
  • 積集合 (Intersection): 二つのビットマップに共に存在する要素のみを含む新しいビットマップを生成します。
  • 対称差集合 (Symmetric Difference): 二つのビットマップのうち一方にのみ存在する要素を含む新しいビットマップを生成します。

これらの演算は、ビットマップのコンテナ種類に応じて最適化されており、非常に速く実行されます。

Go 言語での利用

Go 言語では github.com/RoaringBitmap/roaring パッケージを使用することで、Roaring Bitmap を容易に活用できます。このパッケージは Roaring Bitmap のすべての機能を提供し、Go 言語の特性に合わせて最適化されています。

インストール

1go get github.com/RoaringBitmap/roaring/v2

使用例

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2"
 7)
 8
 9func main() {
10	b1 := roaring.BitmapOf(1, 2, 3, 4)     // 1, 2, 3, 4で初期化
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // 2, 4, 6, 8, 12で初期化
12
13	b1.Add(5)  // 5を追加
14	b2.Add(10) // 10を追加
15
16	b2.Remove(12) // 12を削除
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// bitmap演算は元の値を変更するため、複製を作成して使用
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

12025/09/08 22:16:27 and result: [2 4]
22025/09/08 22:16:27 or result: [1 2 3 4 5 6 8 10]
32025/09/08 22:16:27 xor result: [1 3 5 6 8 10]

上記の例示コードには含まれていない主要な機能として、次のようなものがあります。

  • Contains(x uint32) bool: 特定の値がビットマップに存在するかを確認
  • GetCardinality() uint64: ビットマップに含まれる要素の数を返す
  • Rank(x uint32) uint64: 特定の値以下の要素の数を返す
  • ToBytes() ([]byte, error): ビットマップをバイトスライスにシリアライズ
  • FromBytes(data []byte) error: バイトスライスからビットマップを復元
  • Clone() *Bitmap: ビットマップの複製を生成
  • Clear(): ビットマップを初期化
  • NextValue(x uint32) int64: x 以上の次の要素を返す
  • PreviousValue(x uint32) int64: x より小さいか等しい
  • Maximum() uint32: ビットマップ内で最大の要素を返す
  • Minimum() uint32: ビットマップ内で最小の要素を返す

このような機能があります。詳細は公式ドキュメントを参照してください。

参考までに、roaring パッケージには uint32 だけでなく uint64 をサポートするパッケージも含まれています。ほぼ同じインターフェースを提供するため、そのまま置き換えて使用できます。

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2/roaring64"
 7)
 8
 9func main() {
10	b1 := roaring64.BitmapOf(1, 2, 3, 4)     // 1, 2, 3, 4で初期化
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // 2, 4, 6, 8, 12で初期化
12
13	b1.Add(5)  // 5を追加
14	b2.Add(10) // 10を追加
15
16	b2.Remove(12) // 12を削除
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// bitmap演算は元の値を変更するため、複製を作成して使用
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

おわりに

Roaring Bitmap は、高いカーディナリティの整数集合を効率的に保存および操作できる強力なツールです。Go 言語で github.com/RoaringBitmap/roaring パッケージを使用すれば、Roaring Bitmap のすべての機能を容易に活用できます。このパッケージは、さまざまなコンテナ種類と最適化された演算を通じて、メモリ使用量と性能を最大化します。データベースインデックシング、ログ分析、統計計算など、さまざまな分野で Roaring Bitmap を活用し、効率的なデータ処理を実現できます。

Roaring Bitmap は特に大規模データセットで高い性能を発揮し、さまざまなアプリケーションで有用に使用されえます。Go 言語の簡潔で効率的な文法と組み合わさることで、Roaring Bitmap は開発者に強力なツールを提供します。今後も Roaring Bitmap の発展とともに、より多くの機能と最適化が行われることが期待されます。

私がなぜこれをしたのかですか? 時系列データベースで各タグごとのインデックシングと高速な和集合演算のためです。