imported>Dexxor: /* Nested Loop Join */ Nested Loop leitet hierher weiter

2024-08-11T13:25:36Z

Nested Loop Join: Nested Loop leitet hierher weiter

Neue Seite

Ein '''Join-Algorithmus''' ist eine Strategie ([[Algorithmus]]) zur [[Implementierung]] von [[Relationale Algebra#Join|Joins]] in [[Relationale Datenbank|relationalen Datenbanken]].

Die optimale Strategie hängt von Größe und Struktur der am Join beteiligten [[Relation (Datenbank)|Relationen]], verwendeten oder verwendbaren [[Datenbankindex|Indizes]], der Größe des [[Arbeitsspeicher|Hauptspeichers]] als auch der Join-Art (Natural Join, θ-Join oder Equi-Join) ab.

== Nested Loop Join ==
Es werden nacheinander alle [[Tupel (Informatik)|Tupel]] aus der Relation <math>\mathit{R}</math> ausgewählt und mit jedem Tupel aus der Relation <math>\mathit{S}</math> verglichen.

Der Algorithmus eignet sich für jeden Join und ist auf mehrere Relationen erweiterbar.

=== Pseudocode ===
Umsetzung von <math>R \bowtie_{R.a \theta S.b} S</math> mit <math>\mathit{R}</math> als ''äußerer'' Relation und <math>\mathit{S}</math> als ''innerer'' Relation mithilfe zweier geschachtelter [[Schleife (Programmierung)|Schleifen]] (''{{lang|en|nested loops}}'') in [[Pseudocode]]:
<syntaxhighlight lang="pascal">
foreach r in R do
foreach s in S do
if r.a θ s.b do
⇒ Ausgabe von (r,s)
endif
end foreach
end foreach
</syntaxhighlight>

=== Bewertung ===
Da alle Tupel im [[Kartesisches Produkt|Kreuzprodukt]] miteinander verknüpft werden, ergibt sich ein Rechenaufwand von <math>\mathcal{O}(|R| \cdot |S|)</math>.

Die Anzahl der zu lesenden Blöcke ist im [[Worst Case]] <math>|R| \cdot b_s + b_r</math>, da für jedes Tupel in R alle Blöcke von S erneut geladen werden. Passen beide Relationen in den Speicher, dann müssen für diesen [[Best Case]] <math>b_s + b_r</math> Blöcke gelesen werden.
Passt eine der Relationen komplett in den Speicher, so wird sie als innere Relation ausgewählt, ansonsten ist es sinnvoller, die kleinere Relation als äußere Relation zu wählen.

=== Varianten ===
Beim '''Index Nested Loop Join''' werden vorhandene oder erstellte Indizes abgeglichen. Die Anzahl der Blockzugriffe hängt dann von Größe und Aufbau der Indexstrukturen ab.

== Block Nested Loop Join ==
Im Fall, dass beide Relationen <math>\mathit{R}</math> und <math>\mathit{S}</math> nicht in den Hauptspeicher passen, verbessert ein blockweiser Vergleich den Nested Loop Join.

Der Algorithmus eignet sich für jeden Join.

=== Pseudocode ===
Umsetzung von <math>R \bowtie_{R.a \theta S.a} S</math> in [[Pseudocode]]:
<syntaxhighlight lang="pascal">
foreach Block_r in R do
foreach Block_s in S do
foreach r in Block_r do
foreach s in Block_s do
if r.a θ s.a do
⇒ Ausgabe von (r,s)
endif
end foreach
end foreach
end foreach
end foreach
</syntaxhighlight>

=== Bewertung ===
Wie für den Nested Loop Join ist die Komplexität <math>\mathcal{O}(|R| \cdot |S|)</math>.

Die Anzahl der zu lesenden Blöcke ist im Worst Case <math>b_r \cdot b_s + b_r</math>, im Best Case <math>b_s + b_r</math>.

=== Varianten ===
Passen beide Relationen nicht in den Hauptspeicher, so werden aus der äußeren Relation jeweils so viele Blöcke wie möglich in den Hauptspeicher geladen. Dies reduziert die Anzahl der Blockzugriffe auf die innere Relation.

== Sort-Merge Join ==
Beide Relationen werden nach ihren Join-Attributen sortiert. Das Ergebnis kann dann mit einmaligem Scan durch beide sortierte Relationen berechnet werden.

Der Algorithmus eignet sich nur für Natural Join und Equi-Join.

=== Pseudocode ===
Umsetzung von <math>R \bowtie_{R.a = S.a} S</math> in [[Pseudocode]]:

pr := erstes Tupel in R
ps := erstes Tupel in S
while pr ≠ endofR and ps ≠ endofS do
// Sammeln aller Tupel mit gleichen Joinattributen aus S
Ms := Menge mit Inhalt ps
foreach ts in S > ps
if ts.a = ps.a
Ms += Menge mit Inhalt ts
elseif
ps := ts
break foreach
endif
end foreach
// suche passendes Anfangstupel in R
foreach tr in R > pr
pr = tr
if tr.a ≥ ts.a
break foreach
endif
end foreach
// Tupel ausgeben
foreach tr in R > pr
if tr.a > ts.a
break foreach
endif
foreach ts in Ms
⇒ Ausgabe von (tr,ts)
end foreach
pr = tr
end foreach
end while

=== Bewertung ===
Die Anzahl der Blockzugriffe für die Sortierung von <math>\mathit{S}</math> ist im schlechtesten Fall (Worst Case) <math>b_s \cdot \left(2 \cdot \log \left(\frac{b_s}{b_{free}}\right) \right) + b_s</math>, analog für <math>\mathit{R}</math>.

=== Varianten ===
Falls Indizes existieren, können diese für das Abrufen der sortierten Join-Attribute verwendet werden. Beim Auslesen der Tupel kann die Zufallsverteilung im Worst Case zu <math>|S| + |R|</math> Blockzugriffen führen.

Beim '''Hybrid Merge-Join''' wird deshalb eine Relation <math>\mathit{S}</math> sortiert. Danach wird diese über den Index mit den Tupeladressen der anderen Relation <math>\mathit{R}</math> gemergt. Die Ergebnismenge wird nach den Tupeladressen sortiert und die Tupel aus <math>\mathit{R}</math> damit mit möglichst wenigen Blockzugriffen dazugelesen.

== Hash-Join (Simple-Hash) ==

Die erste Relation erzeugt mit den Join-Attributen eine Hashtabelle.
Die Join-Attribute der zweiten Relation werden ebenfalls gehasht. Zeigt der Wert auf ein nicht leeres Bucket in der Hashtabelle, wird das Bucket mit dem aktuellen Tupel verglichen.

Die Hashtabelle wird im Allgemeinen für die kleinere Relation angelegt. Der Hash Join ist nur für Equi-Joins geeignet.

=== Pseudocode ===

<math>R \bowtie_{R.a = S.b} S</math>
'''Für alle''' Elemente s aus S '''wiederhole'''
Hashe über den Join Attributen s(b);
Trage Tupel entsprechend den Werten in Hashtabelle ein
'''end'''
'''Für alle''' Elemente r aus R '''wiederhole'''
Hashe über den Join Attributen r(a);
'''if''' r auf nicht-leeres Bucket hashed
'''if''' r <math>\theta</math> s
speichere r <math>\bullet</math> s in Ergebnismenge
'''end'''
'''end'''
'''end'''

=== Bewertung ===

Die [[Average Case|durchschnittliche Laufzeit]] des Hash-Joins beträgt: <math>\mathcal{O}(n + m)</math>

=== Varianten ===

==== Hash-Partioned-Join ====
Die Relationen <math>\mathit{R}</math> und <math>\mathit{S}</math> werden mit einer gleich- und zufällig verteilenden [[Hashfunktion]] in <math>n_h</math> disjunkte Partitionen <math>H_{s_0}</math> bis <math>H_{s_{n_h}}</math> (analog für R) zerlegt. Dabei fallen die Tupel der beiden Relationen in die gleichen Buckets, wenn die Wertebereiche ähnlich sind.

Es müssen dadurch nur die Partitionen <math>H_{s_i}</math> und <math>H_{r_i}</math> verglichen werden, da sie die Tupel mit den gleichen Join-Attributen enthalten. Der Algorithmus eignet sich nur für Natural Join und Equi-Join.

==== Implementierungen des Hash-Partioned-Join ====
* [[GRACE Hash Join]]
* [[Hybrid Hash Join]]
* [[Hashed Loops Join]]

== Parallel-Join ==
Parallelisierte Algorithmen verteilen die Arbeit an einem Join auf mehrere Prozessoren oder Rechner. Sie werden in [[Paralleldatenbanken]] oder in arbeitsverteilenden Frameworks wie [[MapReduce]], [[Dryad]] und [[Hadoop]] angewandt.

Auf den einzelnen Prozessoren kann ein beliebiger Join-Algorithmus laufen.

=== Fragment-and-Replicate Join ===
Eine Erweiterung des Partitioned Join für θ-Joins: die Elemente des Kreuzprodukt der Partitionspaare <math>H_{r_i}</math> und <math>H_{s_i}</math> wird an jeweils einen Prozessor übergeben. Durch die Replikation steigt der Datentransfer stark an.

[[Kategorie:Datenbanktheorie]]

Join-Algorithmus - Versionsgeschichte

imported>Dexxor: /* Nested Loop Join */ Nested Loop leitet hierher weiter