なぜ今さら「マージ結合」の話をするのか？
やあ。今日はPostgreSQLの実行計画でよく見かける「Merge Join（マージ結合）」について話そうと思う。
現場で「クエリが遅い！」と駆け込まれるとき、たいてい実行計画を見ると `Hash Join` が暴れていたり、最悪の場合 `Nested Loop` が死ぬほど回っていたりする。そんな時、ベテランはふと「あ、ここはマージ結合がハマるかもな」と直感的に考えるものなんだ。
教科書的な定義は「ソート済みの入力をマージする」というものだけど、実務では「なぜオプティマイザがその選択をしたのか」「あえてマージ結合を狙いに行くにはどうすればいいか」という視点がめちゃくちゃ大事なんだよね。
—
マージ結合の「直感的な」仕組み
マージ結合は、例えるなら「2つの名簿を突き合わせて、同じ名前の人をチェックする作業」だ。
それぞれの名簿が「あいうえお順」に並んでいれば、上から順に見ていって、一致したら取り出し、違ったら小さい方の名簿を下にずらす。これだけで全件チェックが終わる。ソートさえ済んでいれば、非常に効率的で、メモリへの負荷もハッシュ結合ほど大きくない。
PostgreSQL内部では、以下の手順で動いている。
1. 入力のソート: 結合キーがインデックスなどでソート済みならそのまま使う。そうでなければ、その場で `Sort` ノードが走り、メモリ（`work_mem`）を使って並び替える。
2. マージ処理: 2つの入力をポインタで追いかけながら、等価なキーを見つけて結合していく。
具体的にどんな時に選ばれるのか？
オプティマイザがマージ結合を選ぶのは、主にこんなケースだ。
- 結合キーにインデックスがある: `B-tree` インデックスのおかげで、並び替えのコストがゼロになるから、最強に速い。
- 結果セットが巨大: ハッシュテーブルを作るためのメモリ（`work_mem`）が足りず、ディスクに溢れてしまうような巨大なデータの場合、マージ結合の方が安定して動作することが多い。
- 不等号結合: `t1.id > t2.id` のような結合条件の場合、ハッシュ結合は使えない。ここでマージ結合が輝く。
—
実践的なチューニング：どうやってマージ結合を「狙う」か
もし君のクエリで「ハッシュ結合が使われているけれど、メモリが足りずに遅くなっている」なら、マージ結合への誘導を検討してみてほしい。
例えば、こんなクエリがあったとする。
SELECT
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.order_date > ‘2023-01-01’;
もし `orders.customer_id` にインデックスが貼られていなくて、`c.id` が主キー（つまりインデックスあり）だとする。このとき、PostgreSQLは `orders` をフルスキャンしてハッシュテーブルを作る道を選ぶかもしれない。
ここで、`orders` にも `customer_id` のインデックスを追加してやるとどうなるか。
CREATE INDEX idx_orders_customer_id ON orders(customer_id);
こうすることで、実行計画は「両方の入力がソートされている」と判断し、コストの低いマージ結合へ切り替わる可能性が高まるんだ。
—
現場からのアドバイス：注意点
ただし、盲信は禁物だよ。マージ結合には「ソート」という高い壁がある。
もしクエリのたびに膨大なデータを `ORDER BY` しているなら、それは結合以前の問題だ。`work_mem` が小さい環境だと、ソート処理がディスク（`temp_files`）に書き込まれて、逆に悲惨な遅延を生むこともある。
チェックリスト:
- `EXPLAIN ANALYZE` を見て、`Sort` ノードで「Disk: …kB」となっていないか？
- `work_mem` は適切か？（セッションごとに消費されるから、むやみに大きくしすぎないように注意）
- 結合キーにインデックスがあるか？（特に外部キー制約には必ずインデックスを貼るという基本、守れている？）
最後に
マージ結合は、PostgreSQLが持つ「いぶし銀」なアルゴリズムだ。派手さはないけれど、大規模なテーブルを扱うときや、インデックスを適切に設計したときには、驚くほどの安定感を見せてくれる。
まずは今のクエリの実行計画を `EXPLAIN (ANALYZE, BUFFERS)` で見てみてほしい。そこには、データベースが君に伝えようとしている「最適化のヒント」が全部書かれているはずだから。
何か詰まったら、またいつでも聞きに来てくれ。エンジニア同士、一緒に手を動かしていこう。
コメント