結合アルゴリズム


RDBMSでの代表的な結合アルゴリズムは以下の通り。



・NESTED LOOP (ネステッドループ結合)


最もシンプルな結合方式。
2つのテーブルの一方を基準とし(外部表)、もう一方のテーブルを単純にループして結合する結合方式。



・MERGE JOIN (マージ結合)


2つのテーブルを結合キーでソートし、その結果で突き合わせを行う結合方式。
一般的にはネステッドループ結合より高速となる。


ただ、結合条件が等価の場合はハッシュ結合が行われることが多いのであまり適用されない。
範囲結合条件(>、<,Between 等)に適している。



・HASH JOIN (ハッシュ結合)


2つのテーブルのレコード数の少ない方の結合条件列をハッシュ関数ハッシュ値を求めてメモリ上のハッシュテーブルに格納し、
もう一方のテーブルの値をハッシュ化し、そのテーブルへの問い合わせを行う結合方式。
ハッシュ値で比較を行うため結合条件が=(等価条件)である必要がある。


マージ結合に比べてソート処理が不要な分、高速となる。




ただし、ハッシュ結合が常に高速というわけではない。
索引を使用でき、検索条件による絞り込で対象となるデータが少量となる場合は
ネステッドループ結合の方が高速となることがある。


また、ハッシュ結合はメモリ上にハッシュテーブルを保持するため
リソースが不足している場合は遅くなることがある。