💽

ビットマップスキャンを初めて知った。例えて説明してみる

に公開
PostgreSQL
SQL
index
tech

前提

  • Btree インデックスの仕組みは把握していること

概要

DB のインデックスにはさまざまな種類があり、Btree、hash、GIN や GiST などがある。
ビットマップインデックスもまたインデックスに関わる技術であるには変わらないが、上記とは立ち位置が異なる。

上記で述べたのはインデックスの物理的な構造であり、インデックススキャン、ビットマップインデックスはそれらの活用方法といえる。

現実世界のシチュエーションについて

ある図書倉庫は、下記のような構造になっているとする

  • 本がバインダーにしまわれている
  • バインダーごとに #xxxx の通し番号がついている
  • 手元には、「本のタイトルごとに整理された案内図」（＝本のタイトルで作成したインデックス）がある

タイトル バインダー番号
Alice in Wonderland #200F
Animal Farm #F331
Anna Karenina #1352
A Tale of Two Cities #CD23
Atomic Habits #982A
... ...
Hamlet #76A7
Harry Potter and the Sorcerer's Stone #777A
Heart of Darkness #001C
...

ここで目的は、

  • 条件に沿った書籍をいかに高速に集めてくるか

となる.

この現実世界を念頭に置きながら、ビットマップスキャンの仕組みを追っていく。

現実世界で2つの手法をそれぞれどう例えられるか

インデックススキャン

目的：『Harry Potter and the Sorcerer's Stone』をとってきたい

  1. 手元の表から、目的の本が存在するバインダーの番号を見つける
    • -> 『#777A』
  2. 『#777A』がある棚までダッシュする 🏃💨
  3. 棚から『#777A』の中身をとる
  4. 元の地点までダッシュで戻ってくる 🏃💨

となる。
ここで、とってくるべき本が複数、10000冊くらいあったらどうだろう。

10000冊に対して上記のアルゴリズムを繰り返し行えば目的は達成できるが、

  • 😟 LOOP 10000 times
    1. 本が存在するバインダーを確認する
    2. バインダーがある棚までダッシュする 🏃💨
    3. バインダーの中身をとる
    4. 元の地点までダッシュで戻ってくる 🏃📗💨

と、途方もない.

ビットマップスキャン

目的：『H』から始まる本をとってきたい

インデックススキャンのやりかたじゃなくて、

  1. 先に該当するバインダーにチェックをしたメモを作る
  2. バインダーのおおよその位置はわかってるので、A Block, B Block, ... とグループ化しておく.
  3. 😄 LOOP i in Range(棚の数)
    1. 荷台を持って i 番目の棚までダッシュする 🏃📦💨
    2. i 番目の棚から必要な本をごっそり持ってくる
    3. 元の地点までダッシュで戻って本を置く 🏃📦📚💨

の方が賢くね？

の発想がビットマップスキャン

ビットマップスキャンのやり方だとさらに嬉しいのが、条件が増えた時。

目的：『H』から始まる【科学】の本をとってきたい

となったとする。
必要な事前準備として、科学に属するバインダーはどれであるか、の表は作っておく必要がある（＝【ジャンル】カラムでインデックスを作成する）

手元にある２つの表をそれぞれ総なめして、下記に該当するバインダーの番号を事前に控えておく

  • 『H』から始まるもの
  • 【科学】ジャンルの本のもの

とってくるべき番号がわかったので、あとはさっきと同様、

  1. バインダーのおおよその位置はわかってるので、A Block, B Block, ... とグループ化しておく.
  2. 😄 LOOP i in Range(棚の数)
    1. 荷台を持って i 番目の棚までダッシュする 🏃📦💨
    2. i 番目の棚から必要な本をごっそり持ってくる
    3. 元の地点までダッシュで戻って本を置く 🏃📦📚💨

で効率よくとれる。

これをインデックススキャンで例えると、

  1. 😓 LOOP 'H'で始まる本
    1. 索引を見て、該当するバインダーの場所へダッシュする 🏃💨
    2. バインダーを開く
    3. 「これは科学の本か？」といちいち中身を目視確認する（フィルタリング）
    4. 科学ならカゴへ、違えば棚に戻す
    5. 元の地点までダッシュで戻る 🏃💨

となるので、往復の回数が多くなる程ビットマップスキャンに遅れをとる。

2つのスキャンの比較

一般に下記のように語られる

比較項目 インデックススキャン ビットマップスキャン
主な用途 ごく少数のデータ抽出 中規模なデータ抽出
I/O 方式 ランダム I/O (インデックス → テーブルを往復) シーケンシャル I/O 寄り (物理順にまとめて読込)
データの順序 インデックスの順序で取得可能 順序は保証されない (物理順になるため)
開始コスト 低い (すぐに見つかった行から返し始める) 高い (最初にビットマップを作成する必要がある)
複数索引の併用 基本的に不可 可能 (複数の索引を AND/OR で結合可能)
メモリ使用量 少ない 必要 (work_mem 内にビットマップを保持)

これらを順に、現実世界を交えながら記事内で解説していく

主な用途

インデックススキャンは言わずもがな、高速に該当するデータを見つけるために用いられる。
高速に該当のバインダーをみつけ、必要な数だけ往復する。
ただし、見つけるのが早いとはいえ、とってくるべき本の数が多くなると往復時間のオーバーヘッドが大きくなってしまう。

ビットマップスキャンは、事前にメモを作成するオーバーヘッドがある。
ただし、とってくるべき本の数が多いほど、そのメモが役立つ。
特に、複合条件の場合はこのメモがとても役立つ。

I/O 方式

インデックススキャン：ランダム I/O (あっちこっち飛び回る)

インデックス（案内図）は「タイトル順」に綺麗に並んでいるが、実際のバインダー（実データ）は「倉庫に入荷した順」などでバラバラの棚に置かれていることが多い。 そのため、インデックス順に忠実に本を取りに行こうとすると……

  1. 案内図の1番目：「Alice」を取りに、東の A 棚へダッシュ 🏃💨
  2. 案内図の2番目：「Zoo」を取りに、西の Z 棚へダッシュ 🏃💨
  3. 案内図の3番目：「Apple」を取りに、また東の A 棚へ戻る 🏃💨

といった具合に、倉庫の東と西を反復横跳びするような動きになる。 これが ランダム I/O。 HDD で言えば、ディスクのヘッドがガチャガチャと激しく動いている状態。
😟 1冊だけなら気にならないが、数が多いと移動（シーク）だけでヘトヘトになってしまう。

ビットマップスキャン：シーケンシャル I/O 寄り (一筆書き)

対してビットマップスキャンは、事前に「どこの棚に行くべきか」をすべてリストアップし、「倉庫の入り口から近い順（物理的な配置順）」 に並べ替えてから出発する。

  • 「A 棚には『Alice』と『Apple』があるな。まとめて取ろう」 📦
  • 「その足で奥の Z 棚に向かって『Zoo』を取ろう」 📦

と、動きに無駄がなく、一筆書きのようにスムーズに回収できる。 これが シーケンシャル I/O（に近い動き）。
😄 物理的に近いデータをまとめて読み込むため、大量の本を集める際には、個別に走り回るよりも圧倒的に効率が良くなる。

データの順序

インデックススキャン：並び順が保証される (整列済み)

インデックス（案内図）は、「タイトルのアルファベット順」 に綺麗に整理されている。
インデックススキャンはこの案内図の順番通りに棚へ向かうため、集めてきた本も自然と 「アルファベット順」 に並んでいる。
😄 もし利用者が「タイトル順に並べて渡してくれ（ORDER BY title）」と要望している場合、この手法なら改めて並べ替え（ソート）をする手間が省けるので非常に効率が良い。

ビットマップスキャン：順序は保証されない (バラバラ)

対してビットマップスキャンは、「どの棚に行くか」を決めた後、「棚の物理的な位置順」 に回収ルートを再構築してしまう。
「A棚の『Alice』を取って、隣のB棚にある『Harry Potter ...』を取って...」と回収するため、元々の案内図にあった「アルファベット順」は無視される。
結果として、荷台に積まれた本はタイトル順ではなく、「倉庫の配置順」 という人間にはあまり意味のない順番で返ってくる。
😟 もし利用者が「タイトル順」を求めている場合、回収し終わった後で改めて並べ替え（ソート処理）を行うコストが発生する。

開始コスト

インデックススキャン：低い (ロケットスタート)

「1冊目」を見つけるだけなら、これが最速。
準備運動もなしに、いきなり案内図の先頭を見てダッシュを開始できる 🏃💨。
😄 「最初の数件だけ欲しい（LIMIT）」場合や、Web画面のページネーションなど、レスポンスの速さが求められる場面で強い。

ビットマップスキャン：高い (作戦会議が必要)

走り出す前に 「作戦会議（ビットマップ作成）」 の時間が必要になる。 倉庫全体の地図を広げ、該当するすべての箇所にチェックを入れ、効率的なルートを計算してからようやく「よし、行くか」と腰を上げる。
😟 もし「1冊だけ欲しい」という状況でこれを行うと、「作戦会議している時間で走って取ってこれただろ！」となってしまう。
😄 逆に、1万冊集めるような大仕事なら、最初の数ミリ秒の作戦会議は誤差であり、トータルの効率で逆転する。

複数索引の併用

インデックススキャン：基本的に不可 (二兎を追えない)

人間は走りながら2つの地図を同時に見ることはできない。
😟「Hから始まる」地図と「科学ジャンル」の地図を持っていても、インデックススキャンでは 「どちらか絞り込めそうな方の地図」を1つだけ選んで走る ことになる。
選ばれなかった方の条件（例：科学ジャンル）は、棚に到着してから実物を目視確認（フィルタリング）することで解決するしかない。

ビットマップスキャン：可能 (地図の重ね合わせ)

ビットマップスキャンなら、走り出す前の「机上の作戦会議」でこれを解決できる。

  1. 「Hから始まる」場所をマークした透明なシートを作る 📝
  2. 「科学ジャンル」の場所をマークした透明なシートを作る 📝
  3. 2枚のシートを重ね合わせる（ビット演算 AND）

「両方にマークがついている場所」 だけを書き写した「最強の地図」を作る ✨

この「最強の地図」を持って出発すれば、無駄な棚には一切行かずに済む。これがビットマップスキャンの真骨頂（Bitmap And / Or）である。

メモリ使用量

インデックススキャン：少ない (メモ帳でOK)

現在追いかけている「1冊分の場所」さえ覚えておけばいいので、メモリ（脳の記憶容量）はほとんど使わない。

ビットマップスキャン：必要 (巨大な地図を広げる場所)

「倉庫のどこに目的の本があるか」という全域マップ（ビットマップ）を作成するため、ある程度のメモリ領域（work_mem）が必要になる。

さいごに

ビットマップスキャンの発想を知ったので、アウトプットをして定着を試みた。
本の倉庫の世界観の設定は何気に結構悩まされるところがあった。

B-tree という物理的なデータは同じでも参照方法が複数戦略あるの、おもろすぎる

個人的TODO

  • PostgreSQL を対象に、よりマシン寄りの仕組みを追う

Discussion