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

その「Bitmap Heap Scan」、本当に効率的と言い切れますか？

PostgreSQLの実行計画を見ていると、ふと目に飛び込んでくる `Bitmap Heap Scan`。普段何気なく眺めているこのスキャン手法ですが、なぜオプティマイザがわざわざこのステップを選択するのか、その「真意」を深く考えたことはありますか？

今回は、単なる教科書的な定義を超えて、PostgreSQLのストレージエンジンがこの手法で何を成し遂げようとしているのか、そして現場のエンジニアがどこで躓きやすいのかについて、少し深掘りしてみたいと思います。

—

なぜインデックススキャンではなく「ビットマップ」なのか

通常、`Index Scan` はインデックスで見つけたポインタ（TID）に従って、一つひとつテーブルのページをフェッチします。しかし、これが何万件ものレコードを対象にする場合、問題が起きます。インデックス上の順序と、物理的なテーブル上の順序がバラバラであれば、OSレベルで激しい「ランダムI/O」が発生し、ディスクヘッド（あるいはSSDのコントローラ）をいたずらに消耗させることになるからです。

ここで登場するのが `Bitmap Heap Scan` です。この手法のキモは、「一度ビットマップに焼き直してから、物理配置の順序で読む」という点にあります。

1. Bitmap Index Scan: インデックスからヒットしたTIDをメモリ上のビットマップに変換する。
2. Bitmap Heap Scan: そのビットマップを走査し、物理的にページ番号が若い順にテーブルをアクセスする。

これにより、同じページへのアクセスを一度にまとめ（Sequential Accessに近い形にし）、ランダムI/Oのペナルティを劇的に低減させる。これがこの手法の本質です。

内部アーキテクチャの「限界」を知る

しかし、このビットマップは魔法の杖ではありません。ここで意識すべきは、`work_mem` との戦いです。

ビットマップはメモリ上に展開されます。対象行数が膨大になると、このビットマップ自体が巨大化し、メモリを食いつぶします。PostgreSQLはこれに対処するため、ある一定のメモリ量を超えると、ビットマップの解像度を落とします（ページ単位の管理から、より粗い管理へ）。

これを「Lossy（非可逆）」なビットマップと呼びます。

Exact: どの行がヒットしたか明確。
Lossy: そのページの中に「ヒットする行があるかもしれない」ことしか分からない。

Lossyになった場合、PostgreSQLはテーブルページを読み込んだ後に、改めて各行に対して `Recheck Cond`（再判定）を走らせる必要があります。つまり、インデックスで絞り込んだはずなのに、結局テーブルの全行チェックに近いオーバーヘッドが生じるわけです。

トラブルシューティングの勘所

もしあなたのクエリで `Bitmap Heap Scan` が遅いと感じたら、以下のポイントを疑ってみてください。

work_mem の不足:

`EXPLAIN ANALYZE` を見てください。`Lossy pages` や `Removed by index check` が大量に出ていませんか？もしそうなら、`work_mem` を増やすことで、ビットマップを「Exact」に保ち、余計なテーブル走査をスキップできる可能性があります。

物理順序の崩壊:

テーブルの物理配置がインデックスの順序とあまりに乖離していると、結局 `Bitmap Heap Scan` をしてもIO効率が上がりません。あまりに頻繁にこのパスを通るクエリがあるなら、`CLUSTER` コマンドで物理配置をインデックスに合わせて整列させるという、古風ですが強力なチューニングが効くケースもあります。

オプティマイザの誤解:

統計情報が古く、実際には数件しかヒットしないのに「大量ヒットする」と見積もられて `Bitmap Heap Scan` が選ばれている場合もあります。`ANALYZE` の実行はもちろんですが、そもそもインデックスが適切か、あるいは `BRIN` インデックスのような別のアプローチの方が適していないか検討する余地があります。

最後に

`Bitmap Heap Scan` は、ランダムI/Oという「悪」を、メモリという「力」でいなすための洗練された戦略です。しかし、その力もメモリの限界や物理配置という現実の壁に直面すれば、途端に非効率なボトルネックへと変貌します。

チューニングとは、こうしたデータベースエンジンの「思考プロセス」を読み解き、彼らが最も得意とする土俵を用意してあげる作業に他なりません。

あなたのデータベースが今、なぜその計画を選んだのか。実行計画のその先にある「I/Oの風景」を想像してみると、今まで見えなかった改善の糸口が見えてくるはずですよ。

それでは、また次回の深掘りでお会いしましょう。