Nested Loop

Der Nested Loop Join ist eine mögliche Strategie in einem Datenbanksystem für Umsetzungen von Joins. Dabei werden nacheinander alle Tupel (Informatik) aus der einen Relation ausgewählt und mit jedem Tupel aus der anderen verglichen.

Beispiel

Für eine Anweisung wie R Join S mit R.a=S.a könnte eine Umsetzung in Pseudocode wie folgt aussehen:

 foreach r in R do
   foreach s in S do 
     if r.a = s.a do
       Ausgabe von (r,s)
     endif
   end foreach
 end foreach      

Bewertung

Da für alle Tupel der Relation R jeweils alle Daten aus B eingelesen werden müßen ergibt sich ein Aufwand von $\mathcal{O}(n^2)$.

Üblicherweise wählen Umsetzungen aus Effizienzgründen die kleinere Relation für die äußere Schleife, weiterhin werden die Tupel aus der inneren meist in Blöcken ausgelesen. Sind die Eingangsmengen gleich groß, wird, je nach Datenbanksystem, eher ein Hash Join eingesetzt werden.

Varianten

Weitere Varianten sind der Block nested Loop Join, bei dem auch bei der Relation R nur Blöcke eingelesen werden, sowie der Index nested Loop Join, bei dem in der inneren Schleife ein Index genutzt wird.