マージ結合（Merge Join）の「深淵」を覗く ― なぜ、そのアルゴリズムは選ばれるのか
PostgreSQLのクエリプランナと対峙しているとき、`Merge Join`という文字を目にすると、僕は少しだけ背筋が伸びる思いがします。
Nested Loop Joinの「総当たり」とも、Hash Joinの「メモリを食い尽くすリスク」とも違う。マージ結合は、いわば「静かなる実力者」です。ソート済みという前提さえ整えば、これほど計算コスト効率の良い結合アルゴリズムは他にありません。
今日は、教科書的な説明はあえてスキップして、現場でこのアルゴリズムとどう向き合うべきか、その内部構造とチューニングの勘所について少し深く掘り下げてみましょう。
—
1. 内部アーキテクチャの核心：なぜ「順序」がすべてなのか
マージ結合の本質は、二つの入力セットが結合キーでソートされているという前提にあります。
PostgreSQLは、ポインタを両方のセットの先頭に置き、まるで二本の川を同時に下るかのようにデータを読み進めます。
- 片方のキーが小さければ、そのポインタを進める。
- 一致すれば結合を出力する。
- 一致しなければ、小さい方を次に進める。
この「O(N+M)」という線形時間で完結する挙動は、インデックスが完璧に効いている時、あるいは実行計画の中で`Sort`ノードが適切に配置された時に、圧倒的なパフォーマンスを見せます。しかし、ここで一つ重要な注意点があります。それは、「重複キーの取り扱い」です。
結合キーに重複がある場合、PostgreSQLは「マージ・マーク（Merge Mark）」という仕組みを使って、一時的に位置を記憶し、再スキャンを行います。もしデータセットが巨大で、かつ結合キーの重複度が異常に高い場合、この「行ったり来たり」が予期せぬCPU負荷を生むことがあります。統計情報が古いと、このコストを見誤り、プランナが安易にマージ結合を選択して地雷を踏む……というのは、よくある悲劇です。
2. パフォーマンストラブルシューティング：プランナの「幻想」を疑え
現場でマージ結合が遅いと感じたとき、まず確認すべきは「コスト計算の乖離」です。
インデックスの有無とソートコスト
プランナは「インデックススキャンでソート済みデータが手に入る」と判断すれば、マージ結合を優先します。しかし、実際にはインデックスが断片化していたり、`ORDER BY`句が複雑だったりして、期待した効率が出ないことがあります。
隠れた「Materialize」ノード
実行計画の中に `Materialize` ノードが見えたら要注意です。これはマージ結合が「再スキャン」を要求しているサインです。メモリに乗り切らないデータが一時ファイル（ディスク）へ溢れ出すと、一気にパフォーマンスは崩壊します。`work_mem`の設定値が適切かどうか、そしてクエリの結合条件が本当にインデックスを活用できる形になっているか、`EXPLAIN (ANALYZE, BUFFERS)` を見て、バッファヒット率とI/O負荷を追跡してください。
3. マージ結合を味方につけるための「作法」
僕がパフォーマンスチューニングを行う際、マージ結合を意図的に狙うこともあります。特に、以下の条件が揃っている場合は非常に強力です。
- 大量のデータを結合する時: ハッシュ結合のようにメモリ上に巨大なハッシュテーブルを作る必要がないため、メモリ消費を抑えつつ、安定したスループットを出せる。
- 結合条件が不等号（<, >）を含む時: ハッシュ結合は等価結合（=）しか扱えませんが、マージ結合はソート済みであることを活かして、範囲条件でも適用できる可能性があります。
もし、プランナがマージ結合を選んでくれないときは、あえて結合キーに合わせたインデックスを作成し、`set enable_hashjoin = off;` といった一時的な介入を行う前に、まずは統計情報（`ANALYZE`）の更新を疑ってください。多くの場合、解決の糸口はそこにあります。
—
最後に：アルゴリズムとの対話
マージ結合は、派手な最適化テクニックではありません。しかし、データ構造の美しさを最大限に活かす、非常にエンジニアリングらしいアルゴリズムです。
クエリが遅いと嘆く前に、一度 `EXPLAIN` の詳細を眺めてみてください。PostgreSQLがどのポインタを追いかけ、どこで立ち止まっているのか。その挙動を読み解くことができれば、あなたはデータベースの「中の人」の視点に、また一歩近づけるはずです。
データベースは、嘘をつきません。ただ、私たちが正しい問いを投げかけるのを待っているのです。
それでは、また次回の記事で。深い深いクエリの世界でお会いしましょう。
コメント