マージ結合の「静かなる実力」— なぜPostgreSQLは時にソートを愛するのか
PostgreSQLのクエリチューニングをしていると、ハッシュ結合（Hash Join）の派手な速度に目が向きがちです。巨大なメモリを確保し、一気にハッシュテーブルを構築して……というアプローチは確かに強力ですが、実戦の現場では「マージ結合（Merge Join）」が最後の砦として、あるいは最強の最適化戦略として君臨する場面が多々あります。
今日は、この「一見地味だが、極めて合理的」なマージ結合の深淵を覗いてみましょう。
—
マージ結合のメカニズム：調和のとれた同期
マージ結合の基本概念は非常にシンプルです。「ソート済みの二つのリストを、端から順に突き合わせる」。
内部的には、PostgreSQLは両方の入力に対して「ポインタ」を一つずつ持ちます。
1. 現在の値を比較する。
2. 一致すれば結合して結果を出す。
3. 一致しなければ、小さい方のポインタを一つ進める。
このロジックが美しいのは、「一度通過した行を二度と見なくていい」という点です。ハッシュ結合のようにハッシュテーブルのメモリ枯渇を心配したり、ネステッドループのように指数関数的なコストに怯える必要はありません。両方の入力がソート済みであれば、計算量は $O(N+M)$ に収束します。
なぜ「ソート済み」がボトルネックになるのか
マージ結合が採用されない最大の理由は、多くの場合「ソートコスト」にあります。
もしクエリ実行時に、インデックスが使えず、明示的に `Sort` ノードが実行されるなら、そのコストはマージ結合の恩恵を容易に吹き飛ばします。しかし、ここでエンジニアの腕の見せ所があります。
- インデックスを活用した「ソート回避」:
テーブルの結合キーにB-treeインデックスが貼られていれば、PostgreSQLは物理的なソートを省略し、インデックススキャンで得られた順序をそのままマージ結合に流し込みます。これが決まったときのクエリプランは、まさに芸術品です。
- メモリの制約:
ハッシュ結合は `work_mem` を食いつぶしてディスクスワップを引き起こすリスクがありますが、マージ結合はストリーミング処理に近い特性を持つため、メモリ負荷が比較的安定しています。
パフォーマンストラブルシューティング：現場の視点
マージ結合が遅いと感じたとき、私たちはどこを見るべきか。
1. 想定外の「再スキャン」
マージ結合は、結合キーに重複がある場合、内部的に「巻き戻し（Rescan）」を行います。例えば、左側のキーが `1, 2, 2, 2, 3` で、右側が `2, 2` の場合、右側のポインタを先頭に戻さなければなりません。この時、もし右側の入力がメモリ上に保持できず、ディスクに溢れていたら……パフォーマンスは目に見えて劣化します。`EXPLAIN ANALYZE` で `Batched` や `Rescan` の動きを追うのは必須です。
2. 統計情報の嘘
オプティマイザがマージ結合を選ぶかどうかは、見積もりの精度に依存します。`ANALYZE` が古い状態で、行数見積もりが大きく外れていると、本来はハッシュ結合が速いケースでマージ結合が選ばれ、無駄なソートコストを支払うことになります。
3. 結合キーの型不一致
これは意外と見落とされます。`JOIN` の左右で型が微妙に異なると、暗黙のキャストが発生し、インデックスが使えなくなる（SARGabilityの喪失）だけでなく、ソート順序が期待通りにならないケースがあります。プランナが「ソート済み」と判断してくれないときは、まず型の一致を確認しましょう。
結びに：愛すべき「堅実な選択」
マージ結合は、決して派手なヒーローではありません。しかし、データ量が膨大になり、ハッシュテーブルがメモリに収まりきらなくなったとき、あるいはデータの統計的特性が特定の順序を保持しているとき、このアルゴリズムは驚くべき安定性を見せます。
「なぜこのクエリはマージ結合を選んだのか？」
そう疑問に思ったとき、それはPostgreSQLがあなたに「ここにはインデックスによる最適化の余地があるよ」と囁いているのかもしれません。インデックス設計とクエリプランの対話。これこそが、データベースエンジニアの醍醐味だと、私は信じています。
皆さんの環境でも、`EXPLAIN` を眺めながら、この「静かなる実力者」との対話を楽しんでみてください。きっと新しい発見があるはずです。
コメント