マージ結合の「静かなる実力」：なぜ今、あえて深掘りするのか
データベースのチューニングにおいて、ネステッドループ結合（Nested Loop）の直感的な挙動や、ハッシュ結合（Hash Join）の爆発的なパフォーマンスに目を奪われがちだ。しかし、PostgreSQLのクエリプランナーが時折提示する「Merge Join（マージ結合）」という選択肢。これに鼻先で笑って「ハッシュの方が速いだろう」と決めつけていないだろうか？
実は、マージ結合は非常にエレガントで、特定の条件下では唯一無二の最適解となる。今回は、この古風でいて現代のワークロードにおいても極めて強力な結合戦略を、内部アーキテクチャの深層から紐解いていこう。
—
1. 内部アーキテクチャ：ソートという名の「事前準備」
マージ結合の核心はシンプルだ。「双方がソートされている」という前提条件さえ揃えば、ポインタを片方ずつ進めるだけで結合が終わる。計算量は $O(N + M)$。ハッシュテーブルを作るメモリのオーバーヘッドも、ネステッドループのような指数関数的な増大も発生しない。
しかし、この「ソート済み」という前提が曲者だ。もし結合対象がインデックスでソートされていない場合、PostgreSQLは `Sort` ノードを挿入する。この「ソートのためのコスト」こそが、プランナーがマージ結合を嫌う最大の理由だ。
- インデックスを活用したマージ結合: 最高のシナリオだ。`B-tree` インデックスが既にソート順を保証していれば、プランナーはソートコストを「ゼロ」とみなす。この時、マージ結合は圧倒的に高速で、かつメモリ効率も最強となる。
- ソートを伴うマージ結合: もしインデックスがない場合、プランナーはメモリ（`work_mem`）を使って外部ソートを行う。ここで `work_mem` が足りなければ、ディスクへ溢れ出し、パフォーマンスは劇的に悪化する。
2. ネステッドループやハッシュ結合との境界線
「いつマージ結合を選ぶべきか？」という問いに対する答えは、実はシンプルではない。
- ハッシュ結合が選ばれる理由: メモリ上に巨大なハッシュテーブルを構築できるなら、非ソートデータに対してもマージ結合のソートコストを上回る効率を見せることがある。
- マージ結合の優位性: 最大の武器は「不等号結合（非等価結合）」への対応だ。ハッシュ結合は等価結合（`=`)でしか使えない。`a.val < b.val` といった範囲条件が必要な場合、PostgreSQLは基本的にネステッドループかマージ結合を選ぶことになる。データ量が多い場合、ネステッドループでは歯が立たない。ここでマージ結合が「救世主」として登場するわけだ。
3. パフォーマンストラブルシューティング：現場で起きる「罠」
マージ結合が遅いと感じたとき、まず疑うべきは以下の3点だ。
① 統計情報の鮮度と「過信」
プランナーは統計情報を見て「このテーブルはソート済みだ」と誤認することがある。特に、ソートキーのデータ分散が激しい場合、見積もりが大きく外れ、本来選ぶべきインデックスが無視されることがある。`EXPLAIN ANALYZE` を見て、`Actual Rows` と `Estimated Rows` に乖離がないかを確認してほしい。
② ソートコストの隠れた重み
`work_mem` の設定値が小さい環境で、巨大なテーブルをマージ結合させようとしていないか？ `Merge Join` が発生しているノードで「Disk:」という表示が見えたら、それはパフォーマンスの致命傷だ。この場合、インデックスを追加してソートを回避するか、`work_mem` を一時的に増やすのが定石だ。
③ インデックスの「効き」を再確認する
単にカラムにインデックスを貼ればいいわけではない。結合キーが複数ある場合、インデックスの順序（複合インデックスの構成）と、SQLの `JOIN` 条件の順序が合致しているか確認してほしい。ここがズレていると、インデックスがあってもマージ結合はソートノードを強制的に発生させる。
—
最後に：職人の勘と統計の融合
マージ結合は、決して「ハッシュ結合の劣化版」ではない。データがソートされているという「構造的な美しさ」を最大限に利用する、極めて論理的な戦略だ。
もし、あなたのデータベースで特定のクエリが `Hash Join` に甘んじているなら、一度 `enable_hashjoin = off` にして、マージ結合の挙動を観察してみてほしい。そこに新しい最適化のヒントが隠されているかもしれない。
データベース設計とは、結局のところ「データの流れをどう整理するか」というパズルなのだ。そのパズルのピースとして、マージ結合という選択肢を常に磨いておいてほしい。現場からは以上だ。
コメント