ネストループ結合

ネストループ結合は、 2つのネストされたループを使用して2つのリレーションを結合する単純なアルゴリズムです。^{[1]結合操作は}データベース管理にとって重要です。

2 つの関係と は次のように結合されます。 ${\displaystyle R}$${\displaystyle S}$

アルゴリズムnested_loop_joinは、
    R内の各タプルrに対して、S内の各タプルsに対して、rとs が結合条件を満たす場合はタプル < r、s >
を生成します。 
         
             
                

_{このアルゴリズムには、n r} *b _s + b _{r の}ブロック転送と n _r +b _{r の}シークが含まれます。ここで、b _rと b _{s は}それぞれリレーション R と S のブロック数であり、n _{r は}リレーション R のタプル数です。

アルゴリズムはI/O で実行されます。ここで、 はそれぞれとに含まれるタプルの数であり、任意の数の関係を結合するように簡単に一般化できます... ${\displaystyle O(|R||S|)}$${\displaystyle |R|}$${\displaystyle |S|}$${\displaystyle R}$${\displaystyle S}$

ブロックネストループ結合アルゴリズム^[2]は、単純なネストループアルゴリズムを一般化したものであって、追加のメモリを利用してリレーションのスキャン回数を減らします。このアルゴリズムは、リレーション R の大きなチャンクをメインメモリにロードします。各チャンクについて、S をスキャンし、現在メモリ内にあるすべてのタプルペアの結合条件を評価します。これにより、S のスキャン回数がチャンクごとに 1 回に減ります。 ${\displaystyle S}$

内部リレーションに結合で使用される属性のインデックスがある場合は、単純なネスト ループ結合をインデックス結合に置き換えることができます。

アルゴリズムindex_joinは、
    R内の各タプルrに対して、インデックス検索でS内の各タプルsに対してタプル< r、s >
を生成する。 
        
            

このバリエーションの時間計算量は、${\displaystyle O(|R||S|){\text{ から }}O(|R|\log |S|)}$

• ハッシュ結合
• ソートマージ結合