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	// 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の発展とともに、さらなる機能と最適化が実現されることが期待されます。

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