ビットマップインデックスの仕組み

ビットマップインデックスの仕組みについて調査してまとめたメモです。

そもそもインデックスとは

ビットマップインデックスの前にそもそもインデックスとは何かについて簡単に説明。
インデックスはざっくりいえばテーブルに対してのSQL（SELECT文）の処理速度を高速化するための仕組み。
日本語でいうと索引。専門書や辞書で後ろの方についている索引と同じイメージ。
辞書の場合、調べたい用語があるときに、1ページから順番に探していくよりも、先に索引で該当の用語が何ページにあるかを確認し、そのページを調べにいくほうが確実に時短。
その仕組みをDBMSで実現しているのがインデックス。

インデックスの種類

インデックスにはいくつかの種類がある。

・Bツリーインデックス
・ビットマップインデックス
・ハッシュインデックス

などなど。
DBMSにおいて単にインデックスというと、大抵の場合Bツリーインデックスのことを指す。
本の索引のイメージに近いのがBツリーインデックス。
名前の通り木構造になっていて、検索値を元に該当レコードが格納されているブロックのアドレスを取得する仕組み。
Bツリーインデックスについては詳しくは解説しているサイトや記事がたくさんあるので他を参照ください。

ビットマップインデックスとは

ビットマップインデックスは、検索に用いられるカラムに対して、その値とレコードとのビットマップを使ってレコードを検索するインデックス。
このインデックスが有効なのは検索するカラムのカーディナリティが低い（取りうる値の種類が少ない）場合。

例えば、「名前」「性別」「血液型」という情報を持つユーザーテーブルがあって、10万件のレコードがあったとする。
この場合、名前はほとんどの場合被らないので、レコード毎にほぼ違った値になる。
つまりカーディナリティが高い。
一方、性別は男と女の2種類の値しか取らないし、血液型はA、B、O、ABの4種類しかない。
つまりカーディナリティが低い。

この場合、名前で検索を行った際にはBツリーインデックスによる検索の方が明らかに効率が良いが、
性別や血液型で検索を行う場合、ビットマップインデックスの方が効率が良くなる可能性が高い。

サンプル

言葉だけの説明だと分かりにくいのでサンプルで。

名前、血液型、性別というカラムを持ったユーザーテーブルを考える。
以下の6件のレコードが登録されているとする。

ユーザー

ID	名前	血液型	性別
1	佐藤	A	男
2	鈴木	B	女
3	田中	O	男
4	高橋	A	女
5	伊藤	O	男
6	山本	AB	女

この時、血液型と性別に対するビットマップインデックスは以下のようになる。

血液型のビットマップ

レコード番号	1	2	3	4	5	6
A	1	0	0	1	0	0
B	0	1	0	0	0	0
O	0	0	1	0	1	0
AB	0	0	0	0	0	1

性別のビットマップ

レコード番号	1	2	3	4	5	6
男	1	0	1	0	1	0
女	0	1	0	1	0	1

レコード番号というのは、レコードを特定するための値だと思ってください。
Oracleでいうrowid、PostgreSQLでいうTIDみたいなもの。
ここではわかりやすくするためIDと一致するようにしています。

ここで例えば

select * from ユーザー where 血液型 = 'A';

というSQLを実行したとする。
ビットマップインデックスが使用される場合、血液型のビットマップのAのビット列を見る。
「100100」
ビット列はこうなっているので、1つ目のレコードと4つ目のレコードが該当する。
結果的に佐藤、高橋のレコードがヒットする。

このように、条件に合致するビット列を見て、値が1になっているレコードを取得するのが
ビットマップインデクスの仕組み。

ビットマップインデックスのもう一つのメリット

ビットマップインデックスにはもう一つ、OR検索でもインデックスが使用されるという特徴がある。
Bツリーインデックスの場合、性質上OR演算子があるとほとんどの場合インデックスは使用されないので、
その点がBツリーインデックスと異なる点。

例えば

select * from ユーザー where 血液型 = 'O' or 性別 = '女';

というSQLを実行したとする。

血液型Oに該当するビット列は
「001010」
性別が女に該当するビット列は
「010101」

それぞれのビット列の論理和を取ると
「011111」となる。
この結果、鈴木さんから山本さんまでの5レコードがヒットする。

同じ理屈でAND条件(論理積)も使えるが、AND条件の場合はBツリーインデックス有効なのでメリットというほどでもないかと。

DBMS毎のビットマップインデックスの仕様

Oracle

Oracleの場合、create index するときに「bitmap」のオプションを付けるとビットマップインデックスになる。

PostgreSQL

インデックス作成時には指定することはできないが、実行計画では「Bitmap Scan」が確認できる。
どうやらSQL実行時にワーキングメモリ内にビットマップを作成して検索速度を上げているらしい。

SQL Server

私が調べた限りサポートしてないっぽい。

他のDBMS製品

すみませんが未調査です。知る機会があれば、もしくは情報いただければ更新します。