B-treeの「正体」を再考する：PostgreSQLにおけるインデックス最適化の深淵
PostgreSQLを触り始めて数年、あるいは数十年経つと、誰もが一度は「なぜこのクエリはインデックスを使わないのか？」という壁にぶつかります。B-treeインデックスはあまりに身近すぎて、まるで空気のように扱われがちですが、その内部構造を理解し尽くしているエンジニアは意外と少ないものです。
今日は、教科書的な説明は一旦脇に置いて、PostgreSQLのB-treeが裏側で何をしていて、どうすればそのポテンシャルを極限まで引き出せるのか、現場の視点から紐解いていこうと思います。
—
B-treeは「静的なリスト」ではない
まず大前提として、PostgreSQLのB-treeは「バランスのとれた検索木」という単純な定義を超えています。インデックスページ（リーフノード）は双方向にリンクされており、これがスキャン性能の要です。
等価検索（`=`)だけでなく、範囲検索（`<`, `>`, `BETWEEN`)がこれほど高速なのは、条件に合致した先頭のリーフを見つけた後、PostgreSQLが単に木を辿るのを止めるのではなく、リーフのチェーンを横にスライドしてデータを拾い集めるからです。
ここでよくあるミスが、インデックスの「カーディナリティ」だけを気にして、「インデックスの順序」を軽視することです。複合インデックスを設計する際は、`WHERE`句の絞り込み条件（Equality）を左側に寄せ、範囲検索（Range）を右側に配置する。これは鉄則ですが、なぜそうなるかといえば、B-treeの構造上、範囲検索が始まるとその後のカラムのソート順序が検索効率に寄与しなくなるからです。
「インデックスオンリースキャン」という理想郷
性能チューニングの銀の弾丸として語られる「インデックスオンリースキャン（IOS）」。これは、ヒープ（実テーブル）へのアクセスを完全に回避し、インデックスページだけでクエリを完結させる手法です。
しかし、ここで多くのエンジニアが躓くのが Visibility Map（VM） の存在です。
PostgreSQLは「このインデックスデータが最新で、かつ全てのトランザクションから見て可視である」ことを保証するために、VMを参照します。もし、頻繁な`UPDATE`によってヒープの各行の可視性がコロコロ変わっている場合、いくらインデックスにデータが含まれていても、PostgreSQLは結局ヒープへアクセス（Heap Fetch）しに行きます。
- 教訓： インデックスオンリースキャンが効かないときは、クエリの書き方ではなく、`VACUUM`の頻度やテーブルの更新頻度を疑ってください。インデックスに不要なカラムを詰め込みすぎる（Include句の乱用など）と、インデックスの肥大化を招き、キャッシュ効率が落ちるというトレードオフも忘れてはいけません。
パフォーマンストラブルシューティングの勘所
もしあなたが「インデックスを貼っているのに遅い」という事象に直面したら、まずは以下のステップを疑います。
1. インデックスの肥大化（Bloat）を確認せよ
頻繁な`UPDATE`や`DELETE`はインデックスに「死んだエントリ」を残します。`pgstattuple`拡張を使って、インデックスの物理的な占有率と実データの比率を見てください。無駄に巨大なインデックスは、I/O負荷を増大させる最大の要因です。
2. データ型の不一致は「インデックス殺し」
`WHERE column_a = ‘123’` のように、数値型カラムに対して文字列で比較してはいけません。暗黙の型変換が発生すると、オプティマイザはインデックスを無視してシーケンシャルスキャンを選択せざるを得なくなります。`EXPLAIN ANALYZE`の計画を見て、型変換が起きていないか目を光らせるのです。
3. ソートの回避を意識する
`ORDER BY`句がインデックスの順序と一致しているか。これだけでCPUコストが劇的に変わります。高度なチューニングでは、あえてインデックスを「ソート順を合わせるためだけ」に作成することもあります。
最後に：インデックスは「投資」である
インデックスは読み取りを高速化する魔法の杖ですが、書き込みには必ずコストが伴います。テーブルにインデックスを一つ追加するということは、`INSERT`や`UPDATE`のたびにそのコストを支払うという「投資」です。
「とりあえず貼っておこう」という安易な設計は、数年後に必ず技術的負債となって跳ね返ってきます。
PostgreSQLのエンジンは非常に賢いですが、その賢さを活かすのも殺すのも、インデックスという名の地図をどう設計するかにかかっています。皆さんのデータベースが、今日も軽快にクエリを捌いていることを願っています。
それでは、また次回の深掘りでお会いしましょう。
コメント