Oracle® 非公式 SQL, PL/SQL & DBA's ガイドサイト

ソート・マージ結合 （SORT MERGE JOIN）

ソート・マージ結合、マニュアル上では、ソート／マージ結合と書かれている。英文は Sort Merge Joins である。 これはマージソートと混同するのを嫌ったのだろうか？意図は良くわからない。
（ソート／マージ結合には少し違和感があるので、以下 ソート・マージ結合として書いてしまいます。）

ソート・マージ結合とは

ソート・マージ結合とは、表現するならば、ある 2 つの表を結合キーでソートし 2 つの行セット同士をバッファという会場で 集団お見合いさせて、そこから大量のカップルをごっそりと生み出すようなものであると考えるとわかりやすい。

下の図は「部門一覧表」と「利用者一覧」を「部門 (DEPT_ID)」の等価結合 (=)によってソート・マージ結合させているイメージ図である。 （この例ではマッチングの会場には席がひとつしかない)

▼DEPT_ID をキーにしたソート・マージ結合の動作イメージ（シングルスレッド）

SELECT /*+ USE_MERGE(A B) */... FROM A, B WHERE A.DEPT_ID = B.DEPT_ID

ソート・マージ結合の動作イメージ（javascriptが無効のため表示できません)

この例はシンプルでわかりやすく表現しているため処理の無駄も多い。（フラッシュを手抜きしたいというのもある）
それに以前に、実は等価結合(=)ではソート・マージ結合は、ほとんど選択されない。
一般的な等価結合ではハッシュ結合の方がソート・マージ結合より効率的であるから…

また Oracle ではソート・マージ結合は、よりスマートで効率的に結合処理が行なわれているのは想像に難しくない。
（フラッシュではイメージしやすいように選択ソートもどきで行セットをソートしている）
Oracle 10g からマニュアルのソート・マージのコストの計算式が微妙に変わっているので変更されているかもしれないが、 以前は N×LOG(N) + M×LOG(M) というコストであった。

マニュアルから察することができる内容からイメージ図において注意しておきたい点は 3つ

• ソート処理を完了することなく結合を完了できる
• 等価結合では一般的にハッシュ結合が有利
• ソート・マージ結合のためにソート処理が発生する場合には効率が悪い

ソート処理を完了することなく結合を完了できる

これは、上の例で示すならば、左の行セットにおいて DEPT_ID の値域は 100 〜 102 である。 このとき右の行セットは値域外のレコードまでソートの対象する必要はないし比較する必要もなかった。
ちなみに値域は SQL で指定されていなくても統計情報に存在している総レコード数やヒストグラム、値域なども参考にして効率よく正確な値を取得していると思われる。

等価結合では一般的にハッシュ結合が有利

ソート・マージ結合は、ネステッド・ループ結合 が適さない場合で、かつ、ハッシュ結合が行なうことができない範囲結合(<,>,between など) が主な守備範囲、得意分野である。
なんとなくであるがネステッド・ループ結合やハッシュ結合はスター選手、ソート・マージ結合は控えの選手という感じがする。

ソート・マージ結合のためにソート処理が発生する場合には効率が悪い

これは逆にいうと、「入力する行セット」がすでにソート済みの表(※1) 、索引列だけの操作、ソート処理が必要な SQL(※2) の後続処理に有用といえる。

(※1) 索引構成表、または、ソート済みハッシュクラスタ

(※2) UNION , INTERSECT 他 / DISTINCT / GROUP BY / インラインビュー・分析関数などを使った各種 SQL

関連事項

• SELECT