GoSuda

活気あるビットマップ

By snowmerak
views ...

ビットマップとは？

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

基本概念

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

例えば、性別カラムを持つテーブルがあると仮定します。このテーブルに5つの行があり、性別カラムの値が以下のようであるとします。

  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個の行があると仮定します。そして、次のクエリを実行するとします。

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

このクエリは、activeとsexカラムが両方ともTRUEである行を検索します。この場合、両方のカラムがTRUEである条件を満たす行を最も迅速に検索する方法として、ビットAND演算を活用できるでしょう。

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

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

トレードオフ

ビットマップインデックスは非常に効率的である可能性がありますが、いくつかのトレードオフが存在します。他にも多くの欠点がありますが、ここでは1つだけ指摘します。

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

高いカーディナリティのカラムにビットマップインデックスを使用すると、各固有値に対して個別のビットマップを生成する必要があるため、多くのストレージスペースが必要になる可能性があります。例えば、カラムに1,000,000個の固有値がある場合、1,000,000個のビットマップを生成する必要があり、これは非常に非効率的である可能性があります。

そこで我々は

高いカーディナリティから生じるビットマップの代替として、Roaring Bitmapを使用できます。Roaring Bitmapにはいくつかの特性がありますが、最も大きな基盤となる哲学と特性は、「データの密度に応じて最適な保存方式を動的に選択し、圧縮率と演算速度の両方を最大化すること」です。

Roaring Bitmapの基本概念

2段階インデックス作成

Roaring Bitmapは、整数を1つ保存するために、まず以下の2段階を経ます。2段階インデックス作成と言っても、単に2次元配列と考えることができます。

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

コンテナ

このコンテナは、先ほど比喩した通り、2次元配列のうち内側の配列に相当します。しかし、上位16ビットのそれとは異なり、このコンテナは内部データの量に応じて内部構造が異なります。Roaring Bitmapは以下の3種類のコンテナをサポートしています。

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

このような方式により、Roaring Bitmapはメモリを非常に効率的に使用し、様々なデータ密度に対して最適なパフォーマンスを提供できます。

Roaring Bitmapの機能

基本機能

Roaring Bitmapは、以下の基本機能を提供します。

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

集合演算

Roaring Bitmapは、以下の集合演算もサポートしています。

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

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

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	// ビットマップ演算は元のオブジェクトを変更するため、複製を作成して使用します
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	// ビットマップ演算は元のオブジェクトを変更するため、複製を作成して使用します
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の発展とともに、さらなる機能と最適化が期待されます。

私はなぜこれを行ったのでしょうか？時系列データベースにおける各タグごとのインデックス作成と高速な和集合演算のためです。