結合の「静かなる実力者」：PostgreSQLのマージ結合を深掘りする
PostgreSQLのクエリプランナと夜通し対話していると、時折、Nested Loopの無邪気な計算量や、Hash Joinのメモリ枯渇リスクに頭を抱えることがあります。そんな時、私たちの頼もしい相棒となってくれるのが「マージ結合（Merge Join）」です。
一見すると地味で、ソートという重い前処理を必要とするこの結合アルゴリズム。しかし、大規模データセットを扱う現場において、これほど安定感のある選択肢は他にありません。今回は、あえてこの「古き良き」アルゴリズムの深淵に潜り込んでみましょう。
—
マージ結合のメカニズム：本質は「突き合わせ」
マージ結合の核心は、非常にシンプルです。「ソート済みの二つのリストを、片端から順に突き合わせる」。
具体的には以下のステップを踏みます。
1. Sort Phase: 両方の入力データセットを結合キーでソートする（すでにインデックスで順序が保証されている場合はスキップされます）。
2. Merge Phase: 両方のポインタを先頭に置き、値を比較する。
- 値が一致すれば結合し、両方のポインタを進める。
- 一致しなければ、小さい値のポインタを進める。
このプロセスは極めて効率的で、計算量は実質的に `O(N log N + M log M)` に収束します。特筆すべきは、Hash Joinのように巨大なハッシュテーブルをメモリ上に構築する必要がないことです。メモリ消費という「爆弾」を抱えずに済む点は、大規模データ処理における精神衛生上の大きなメリットと言えるでしょう。
なぜ、マージ結合が選ばれないことがあるのか？
優秀なマージ結合ですが、プランナがこれを避けるシーンには明確な理由があります。
- ソートコストの壁: 結合キーに適切なインデックスがない場合、メモリ（`work_mem`）内で収まらないソートが発生し、ディスク（一時ファイル）への書き出しが始まります。この「ディスクI/O」が発生した瞬間に、クエリのレスポンスは崩壊します。
- 等価結合の制約: マージ結合は、基本的に「等価（=）」条件での結合に最適化されています。非等価結合（不等号など）が絡むと、このアルゴリズムは力を発揮できません。
パフォーマンストラブルシューティング：現場からの視点
もし、あなたのクエリがマージ結合を選択しているにもかかわらず遅いのであれば、まずは「なぜソートに時間がかかっているのか」を疑ってください。
1. `work_mem` との闘い
実行計画（`EXPLAIN ANALYZE`）を見て、「Sort Method: external merge」と表示されていませんか？これはメモリが足りず、ディスクにデータが溢れている証拠です。
対策はシンプルですが慎重に。そのクエリのためだけに `SET work_mem = ’64MB’;` のように一時的に引き上げるか、あるいは対象カラムにインデックスを張り、ソート自体を回避するアプローチを検討すべきです。
2. インデックスの有効活用
もし結合キーにインデックスがあっても、フィルタ条件が複雑だとインデックスがスキャンされないことがあります。実行計画で「Index Scan」ではなく「Seq Scan」＋「Sort」になっていないかを確認してください。場合によっては、カバリングインデックスを検討する余地があります。
3. 「多対多」の罠
マージ結合は、結合キーに重複が多い場合、内部的に「Mark/Restore」という処理を行い、ポインタを巻き戻して突き合わせを繰り返します。これが頻発すると、CPU負荷が急上昇します。結合キーのカーディナリティ（値の多様性）が極端に低い場合は、Hash Joinの方が適しているケースも多いのです。
—
最後に：エンジニアとしての嗅覚
PostgreSQLのプランナは非常に賢いですが、時として統計情報の鮮度不足や複雑な相関関係によって「誤った判断」をすることがあります。
マージ結合は、データ量が増えれば増えるほど、その真価を発揮するアルゴリズムです。しかし、そのポテンシャルを引き出すには、「どのカラムに、どのようなインデックスがあり、それがソートコストをどれだけ削減できているか」をイメージできるだけの深い洞察が求められます。
チューニングとは、データベースに魔法をかけることではなく、データベースが本来持っている効率的なパスを、物理設計と統計情報を通して「見つけてあげる作業」です。
皆さんのクエリが、明日もマージ結合で軽快に駆け抜けることを願っています。それでは、また。
コメント