マージ結合の真実：なぜオプティマイザは「ソート」を嫌うのか
PostgreSQLの実行計画を見ていて、`Merge Join`の文字に胸を躍らせることはありますか？
多くのエンジニアは、`Hash Join`の爆速なハッシュテーブル構築や、`Nested Loop`のインデックス・ルックアップに目を奪われがちです。しかし、大規模なデータセットを扱うとき、あるいはメモリリソースが限られた環境で安定したスループットを維持したいとき、マージ結合こそが真の「職人芸」を発揮する場面があります。
今日は、このマージ結合を究極まで使いこなすための、少し深い話をしましょう。
マージ結合の「期待値」と「現実」
マージ結合は、基本的に「双方がソートされている」ことを前提に動作します。左右の入力をポインタでなぞりながら、一致するキーを拾い上げていく。このアルゴリズムの計算量は $O(M + N)$ であり、非常に効率的です。
しかし、現実は厳しい。PostgreSQLのオプティマイザがマージ結合を選択した際、もし入力データがソートされていなければ、裏側で何が起きるか。そう、「クエリの実行時間を劇的に削る『Sort』ノード」の登場です。
この`Sort`ノードこそが、パフォーマンストラブルの主犯格です。データ量が`work_mem`を超過すれば、ディスクへのスピル（一時ファイルへの書き出し）が発生し、I/O待ちがシステム全体を窒息させます。マージ結合を選んだはずが、ソートのオーバーヘッドで全体が遅延する。皮肉な話ですよね。
インデックスによるソート回避：最適化の定石
マージ結合のポテンシャルを最大化する唯一の方法は、「結合対象のデータを、インデックスによって最初からソートされた状態で提供すること」です。
B-treeインデックスは、データが論理的にソートされた順序を保持しています。PostgreSQLはこれを知っている。もし`JOIN`キーに適切なインデックスが存在すれば、オプティマイザは`Sort`ノードをスキップし、インデックススキャンから直接マージ結合へデータを流し込めます。
ここで重要なのは、「単にインデックスがある」ことと「インデックスがスキャン順序として最適か」は別問題だということです。
- 複合インデックスの順序: 結合条件だけでなく、`ORDER BY`句との整合性も考慮していますか？
- カバリングインデックス: 結合キーだけでなく、SELECTリストに含まれるカラムまで含めることで、`Index Only Scan`を狙えていますか？
これらが噛み合ったとき、PostgreSQLは物理的なソートを一切行うことなく、結合を開始します。この瞬間、クエリのレスポンスは劇的に改善し、CPU負荷も最小限に抑えられます。
トラブルシューティング：なぜ「ソート」が発生し続けるのか
もし、インデックスを張ったはずなのに実行計画から`Sort`ノードが消えないなら、以下の点を確認してみてください。
1. データ型の不一致: 結合キーの型が微妙に異なると（例えば `int` と `bigint`）、暗黙のキャストが発生し、インデックスが使われないケースがあります。
2. アクセスの順序: 統計情報が古いと、オプティマイザが誤ったパスを選択することがあります。`ANALYZE`は打っていますか？
3. セレクトivity（選択率）の誤認: 結合される行数が少ないと予測されているのに、実際は膨大な場合、PostgreSQLはメモリ内ソートを試みて失敗し、結果としてパフォーマンスが劣化します。
エンジニアとしての美学
マージ結合のチューニングは、単なる「速くする作業」ではありません。それは、データベースが持つ「データが並んでいる」という特性を、アルゴリズムのレベルで活かすための対話です。
「とりあえずインデックスを足す」のではなく、「この結合処理がどのような順序でデータを求めているのか」を想像し、ディスクI/Oを極限まで減らす。そうした積み重ねが、何千万行ものレコードを扱うシステムの安定性を支えています。
次に`EXPLAIN ANALYZE`を叩くとき、`Merge Join`の上に`Sort`が鎮座していたら、ぜひ一度インデックスの設計を見直してみてください。ソートという「無駄な計算」が消え去ったときの、クエリの軽快な挙動を一度体感すれば、きっとあなたもマージ結合の虜になるはずです。
データベースの内部動作を理解し、それを操る喜び。これこそが、エンジニアであることの醍醐味ではないでしょうか。
コメント