【テクニカル・上級編】ビットマップヒープスキャン – PostgreSQL

インデックス・スキャンの「裏側」：ビットマップヒープスキャンの美学と限界

PostgreSQLのクエリプランナと長く付き合っていると、時折「なぜインデックスを使っているのに、こんなにヒープ（テーブル本体）へのランダムアクセスが暴れるのか？」と頭を抱えたくなる瞬間がありますよね。

そんなとき、プランナが選択肢として提示してくるのが「Bitmap Heap Scan」です。

一見すると、Index Scanの劣化版のように思えるかもしれません。しかし、大規模なデータセットや、インデックスとヒープの物理的な並びが乖離している環境において、このスキャン方式はまさに「救世主」となり得るのです。今日は、このビットマップスキャンの深淵を少し覗いてみましょう。

1. なぜ「ビットマップ」なのか：ランダムアクセスの回避術

単純なIndex Scanは、インデックスで見つけたTID（Tuple Identifier）を使って、その都度ヒープページを読みに行きます。データが小さいときは良いのですが、検索対象が数万件、数十万件となってくると、ストレージのヘッド（SSDならIOPS）は悲鳴を上げ、ランダムアクセスの嵐でクエリは停滞します。

ここでBitmap Heap Scanの出番です。このプロセスは大きく二段階に分かれます。

1. Bitmap Index Scan: インデックスを辿り、条件に合致するTIDを物理的な位置（ページID）へとマッピングし、メモリ上にビットマップを作成します。
2. Bitmap Heap Scan: 作成されたビットマップを元に、物理的に近いページをまとめてヒープから読み込みます。

この手法の最大の賢さは、「物理的なストレージの読み込み順序を最適化できる」という点にあります。メモリ上でページ番号をソートし、ディスク上の位置に近い順に効率よくアクセスすることで、ヘッドの移動を最小限に抑えることができるのです。

2. メモリという名の「諸刃の剣」：work_memとの駆け引き

ここで多くのエンジニアが直面するのが、`work_mem` に関する悩みです。

ビットマップが十分にメモリ（`work_mem`）に収まれば良いのですが、対象データが膨大になると、PostgreSQLはビットマップを「Lossy（非可逆）」な形式へと切り替えます。

Exactモード: ページ内の具体的なタプルまで正確に保持。
Lossyモード: 「このページの中に該当する何かが存在する」という情報までしか保持しない。

Lossyモードになると、ヒープページを読み込んだ後に、改めて各タプルに対して「本当に条件に合致するか」を再チェック（Recheck）する必要があります。この「再チェック」のコストは無視できません。もしクエリが遅いと感じたら、`EXPLAIN ANALYZE` の結果に `Lossy bitmaps` という文字が出ていないか確認してみてください。もし出ていれば、`work_mem` を増やすことで劇的に改善する可能性が高いはずです。

3. パフォーマンストラブルシューティングの勘所

現場でビットマップスキャンがボトルネックになっている場合、私は以下の観点で調査を進めます。

インデックスの有効性: そもそもビットマップスキャンが選択されているということは、プランナが「Index Scanより効率的だ」と判断したからです。もしこのスキャンが重いなら、インデックスの選択基準が甘いか、あるいはテーブルの物理的な順序（Cluster）が乱れすぎている可能性があります。
相関関係（Correlation）の確認: `pg_stats` ビューを見て、列と物理的なデータの相関を見てみてください。相関が極端に低い場合、どのスキャン方式を使ってもIOは跳ね上がります。いっそのこと、`CLUSTER` コマンドで物理順序を再整理するのも、プロとしての「一手」です。
BitmapAnd / BitmapOr: 複数のインデックスを組み合わせる場合、ビットマップはこれ以上ないほど強力です。しかし、複数のインデックスをAND/ORで繋ぐ複雑なクエリは、ビットマップ生成のオーバーヘッドを増大させます。複合インデックス（Covering Index）への作り直しが必要なサインかもしれません。

最後に：データベースは「物理」である

ビットマップヒープスキャンは、論理的なデータ構造を、いかに物理的なストレージの制約に適合させるかという、PostgreSQLの知性が詰まった仕組みです。

「なぜインデックスが効かないのか？」と悩んだとき、インデックスそのものを見るのではなく、その先にある「ディスクがどう動いているか」を想像してみてください。ビットマップという抽象化された仕組みを理解することは、データベースエンジニアとしての解像度を一段階上げてくれるはずです。

皆さんのクエリが、今日も効率よくディスクを叩けますように。