【実務・中級編】結合アルゴリズム：マージ結合 – PostgreSQL

やあ。データベースの運用やクエリのチューニング、順調に進んでるかな？

PostgreSQLを使っていて、実行計画（`EXPLAIN ANALYZE`）を見たときに、「Nested Loop」や「Hash Join」はよく見かけるよね。でも、たまにふと顔を出す「Merge Join（マージ結合）」について、深く考えたことはあるだろうか？

今日は、この「マージ結合」という、一見地味だけど実はめちゃくちゃ頼りになるアルゴリズムについて、現場の視点から解説するよ。

マージ結合を一言で言うと、「あらかじめ整列されたデータ同士を、先頭からペラペラとめくりながら突き合わせる手法」だ。

トランプの神経衰弱を想像してみてほしい。バラバラに散らばったカードから同じ数字を探すのは大変だよね（これがHash Joinに近い）。でも、もし最初から数字順に並んでいたら？お互いのカードを左から順番に見ていけば、最小限の労力でペアが見つかるはずだ。これがマージ結合の基本概念だよ。

マージ結合の最大の弱点であり、同時に強みでもあるのが「ソート済みであること」という前提条件だ。

PostgreSQLがマージ結合を選択する場合、内部ではこんなことが起きている。

1. 入力Aと入力Bを結合キーでソートする（インデックスが効いていれば、このコストは0になる！）
2. 両者を先頭から順にスキャンして一致するものを取り出す

つまり、もし結合キーにインデックスが張られていれば、ソートコストがスキップされて、驚異的な速さで結合が終わるんだ。逆に、インデックスがなくて毎回ソートが発生するなら、PostgreSQLのオプティマイザは「それならHash Joinの方が速いな」と判断して、そっちを選びがちだね。

実務で「マージ結合が最適解」になるのは、主にこんなケースだ。

Hash Joinはメモリ（`work_mem`）にハッシュテーブルを展開するから、メモリが足りないとディスクに溢れて（スパルタ）激遅になる。一方、マージ結合はストリーミング処理に近いから、メモリ消費が安定しているんだ。

これは意外な盲点なんだけど、結合の結果がすでにソートされているなら、その後のソート処理を省略できる。クエリ全体で見ると、マージ結合の方がトータルコストが下がるケースがあるんだ。

例えば、売上データ（`orders`）と顧客データ（`customers`）を結合するとしよう。

— よくある結合クエリ
SELECT o.order_id, c.name
FROM orders o
JOIN customers c ON o.customer_id = c.id
ORDER BY o.customer_id;

もし`orders.customer_id`と`customers.id`にインデックスがあれば、PostgreSQLは喜んでマージ結合を選んでくれる。

もし「インデックスがあるのになぜかHash Joinになってしまう」という場合は、`SET enable_hashjoin = off;` を一時的に試して、マージ結合の実行計画を確認してみるのも手だ（※本番環境でやる時は要注意！）。

現場でクエリが遅いとき、すぐにインデックスを追加しがちだけど、ちょっと待ってほしい。

「Nested Loopでいいのか？」「Hash Joinでメモリが溢れていないか？」「マージ結合のために、インデックスを少し調整（包含インデックスなど）すれば、ソートコストをゼロにできるんじゃないか？」

こうやって、「データベースがどうやってデータを突き合わせようとしているか」をイメージできると、チューニングの解像度がグッと上がるよ。

マージ結合は、決して万能じゃない。でも、ソートとインデックスの仕組みを理解しているエンジニアにとって、ここぞという時に頼れる最高の武器になるはずだ。

次はぜひ、自分のプロジェクトの `EXPLAIN` を眺めてみてくれ。そこに潜んでいる「マージ結合」のサインを見つけたら、君ももう立派なパフォーマンス・チューナーだ。

それじゃ、また現場で会おう！