PostgreSQLのB-treeインデックス、その「深さ」と「順序」を理解してクエリを爆速にする話
やあ。データベースのパフォーマンスチューニングの世界へようこそ。
現場でPostgreSQLを触っていると、とりあえず困った時に `CREATE INDEX` を打つことってあるよね。でも、ちょっと待ってほしい。「とりあえず」でインデックスを貼るのと、仕組みを理解して狙い澄ましたインデックスを貼るのとでは、データ量が100万行を超えたあたりから雲泥の差が出てくるんだ。
今日は、PostgreSQLのデフォルトである「B-treeインデックス」について、教科書には載っていない（あるいは読み飛ばされがちな）「実務で効く」話をしようと思う。
—
B-treeは「木」だけど、実はすごく「背が低い」
B-treeインデックスがなぜ優秀なのか。それは、データを探すための「経路」がめちゃくちゃ効率的だからだ。
B-treeは階層構造（ツリー）になっているけれど、実はこの木、「背が低い」のが最大の特徴なんだ。数百万件のデータがあっても、ルートからリーフ（末端のデータ）まで、せいぜい3段か4段程度。つまり、ディスクI/Oの回数は最小限で済むように設計されている。
よく「インデックスを貼りすぎると遅くなる」と言うけれど、それは単にインデックスの更新コストだけの話じゃない。インデックスが巨大になりすぎると、このツリーの「深さ」が増してしまい、検索のたびにディスクへ何度もアクセスしなきゃいけなくなる。だから、「必要な列にだけ、適切なインデックスを」という鉄則が生まれるわけだ。
—
複合インデックスの「列の順序」が命運を分ける
ここからが本題。複数列にインデックスを貼る「複合インデックス」を作るとき、みんななんとなく列を選んでいないかな？
実は、B-treeにおける複合インデックスの列順序は、「左から右へ」というルールが絶対だ。
例えば、ユーザーの「ステータス」と「作成日時」で検索することが多いシステムがあるとしよう。
— よくあるダメな例：これだと「作成日時」だけでの検索が効かない
CREATE INDEX idx_status_created ON users (status, created_at);
このインデックスは、`WHERE status = ‘active’ AND created_at > ‘2023-01-01’` というクエリには最強に効く。でも、`WHERE created_at > ‘2023-01-01’` というクエリを投げると、PostgreSQLはインデックスを無視してフルスキャンを始める可能性が高い。
なぜか？
B-treeは、先頭の列（この場合は`status`）でまず大きくソートされたデータ構造を持っているからだ。先頭の列が決まっていないと、インデックスをどう辿ればいいか迷子になってしまうんだよ。
実践的なアドバイス
複合インデックスを作るときは、以下の優先順位で列を並べるのが定石だ。
1. 等価比較（`=`）される列を左に置く
2. 範囲検索（`>`, `<`, `BETWEEN`）される列をその右に置く
3. カーディナリティ（値の種類の多さ）が高いものを優先する
もし`status`（値の種類が少ない）と`user_id`（値の種類が多い）があるなら、`WHERE`句の構成にもよるけれど、基本的には絞り込み性能が高い（＝検索範囲を小さくできる）列を左に寄せる意識を持っておくといい。
—
範囲検索の落とし穴：B-treeの限界を知る
B-treeは「等価比較」と「範囲検索」には強いけれど、万能じゃない。
例えば、`WHERE created_at > ‘2023-01-01’ ORDER BY created_at` のようなクエリならB-treeは最高に効率的だ。でも、`WHERE email LIKE ‘%gmail.com’` のような、先頭がワイルドカードの検索には太刀打ちできない。これはB-treeが「前方一致」を前提に並んでいるからだ。
もしワイルドカード検索が頻繁に発生するなら、それはB-treeではなく `pg_trgm` (Trigramインデックス) の出番かもしれない。適材適所、道具を選ぼう。
—
最後に：EXPLAIN ANALYZEを愛そう
どんなに綺麗なインデックスを設計しても、プランナ（PostgreSQLの脳みそ）がそれを選んでくれなければ意味がない。
クエリが遅いと感じたら、まずは `EXPLAIN ANALYZE` を叩く癖をつけてほしい。
EXPLAIN ANALYZE SELECT FROM users WHERE status = ‘active’ AND created_at > ‘2023-01-01’;
ここで `Index Scan` が発生しているか、あるいは予想に反して `Seq Scan`（全件検索）になっていないかを確認する。もし `Seq Scan` になっているなら、それはインデックスが使われていない証拠だ。
—
インデックスのチューニングは、いわば「整理整頓」だ。ライブラリの棚をどう並べれば一番早く本が見つかるか、それを考えるのはエンジニアとして一番面白い作業の一つだと思う。
また何か詰まったら聞きに来てくれ。君のクエリが爆速になるのを応援しているよ。
コメント