マージ結合の「本質」と、その甘美な罠
PostgreSQLのクエリプランナーと向き合っていると、時折、彼が「Merge Join」を提示してくる瞬間がある。Nested Loopの泥沼から抜け出したいとき、あるいはHash Joinのメモリ枯渇に怯えるとき、このマージ結合は実に頼もしい相棒に見えるものだ。
しかし、多くのエンジニアが「ソート済みなら速い」という教科書的な理解で止まっている。なぜPostgreSQLはあえてこのアルゴリズムを選択するのか、そしてなぜそれが時に「性能の地雷」と化すのか。今日はその深淵を覗いてみよう。
—
マージ結合が「理にかなう」瞬間
マージ結合（Merge Join）の基本は、整列済みの2つのデータセットを、まるでジッパーを閉じるように端から順に突き合わせていくことだ。計算量は $O(N \log N + M \log M)$ のソートコストと、線形結合の $O(N+M)$ で済む。
これが真価を発揮するのは、以下のようなケースだ。
- 大規模な結合: ハッシュテーブルをメモリ（`work_mem`）に収めきれないとき、Hash Joinはディスクへのスピル（一時ファイル出力）を余儀なくされる。マージ結合は、ソートさえ済んでいれば、メモリ消費を最小限に抑えつつ安定したストリーミング処理が可能だ。
- インデックスの恩恵: 結合キーにB-treeインデックスが貼られている場合、PostgreSQLはソートコストを「ゼロ」とみなす。これは強力だ。順序を維持したままレコードを取り出せるため、実行計画上のコスト評価は劇的に下がる。
—
「ソート」という名の代償
一方で、マージ結合を「悪」に変える最大の要因は、プランナーが「事前のソートが必要だ」と判断した時のコストだ。
もし結合キーにインデックスがなく、かつデータセットが膨大であれば、PostgreSQLは外部ソートを実行する。ここで `work_mem` を超えるソートが発生すれば、一時ファイルへのI/Oが爆発する。
ここで熟練のエンジニアとして見ておきたいのが、`EXPLAIN ANALYZE` の結果に含まれる `Sort Method` だ。
- Quicksort: メモリ内で完結している。理想的だ。
- External Merge: ディスクを使っている。ここでクエリのレスポンスタイムは一気に奈落へ落ちる。
もし本番環境で `External Merge` が見えたなら、インデックスの追加を検討するか、結合条件を見直すべきだ。マージ結合のコスト計算においては、この「ソートコスト」が結合コスト全体を覆い隠すほど大きくなっているケースが非常に多い。
—
トラブルシューティング：なぜ「それ」が選ばれたのか
現場でよくあるのは、「インデックスがあるのにマージ結合が選ばれない」あるいは「全く関係ないところでマージ結合が爆死している」という相談だ。
まず疑うべきは「統計情報の不整合」と「相関性」だ。
1. 統計情報の鮮度: `ANALYZE` が古ければ、プランナーは行数を過小評価する。結果、Nested Loopで十分なはずのクエリにマージ結合が選ばれ、無駄なソートが発生する。
2. 多列インデックスの罠: 結合条件が複数ある場合、単一カラムのインデックスだけではマージ結合のメリットを活かせないことがある。複合インデックスを貼る際、結合順序やフィルタ条件との相性を再確認してほしい。
3. 等価演算子ではない場合: マージ結合は原則として等価結合（`=`）で輝く。不等価条件（`<`, `>`）が混ざった複雑なクエリでは、マージ結合はそもそも選択肢から外れるか、期待した性能が出ない。
—
プロフェッショナルとしての「読み方」
最後のアドバイスとして、実行計画を見る際は「データの流れ」を想像してほしい。
マージ結合の行の下に `Sort` ノードがぶら下がっている場合、それはシステムが「無理やり整列させている」ことを意味する。もしそれが数百万行のデータに対するものなら、インデックスの欠如を疑うサインだ。逆に、`Index Scan` から直接 `Merge Join` に繋がっているなら、それはPostgreSQLが用意した「最適解」である可能性が高い。
マージ結合は、単なるアルゴリズムの選択肢ではない。それは、データベースが物理メモリとディスクI/O、そしてインデックスというリソースをどう配置するかの「戦略」そのものだ。
この戦略を理解し、クエリプランナーと対話できるようになれば、PostgreSQLは単なるデータストアから、あなたの意図を完璧に汲み取る洗練されたツールへと進化するはずだ。
さて、次はどのアルゴリズムの深淵を覗こうか。現場のクエリチューニングは、いつだって技術者の矜持を試してくるものだ。
コメント