Nested Loop Join?

[flashray]

Hallo,

in einem Übungsblatt für eine Datenbankvorlesung geht es unter anderem um das "Nested Loop Join".

Könnte mir vielleicht jemand grob erklären, was der Nested Loop Join ist! Wir haben zwar viele andere Joins wie Natural Join oder Semi Join oder Theta Join gelernt. Den Nested Loop Join kann ich aber leider nirgends einordnen.


Vg Erdal

 

[hpvw]

Nach dem, was Google dazu sagt, ist das eine bestimmte Form der Optimierung des Natural-Join.

Darf ich fragen, in welchem Rahmen diese Datenbankvorlesung statt findet? Das klingt nämlich sehr theoretisch, wenn nicht gar esoterisch ...

Gruß hpvw

 

[flashray]

Hallo hpvw,

das ist eine Einführungsveranstaltung zu Datenbanksystemen.

Hier der Link zur Vorlesung:
Datenbanksysteme I - Forschungsgruppe Datenbanken - Universität Mannheim

Hier das Übungsblatt:
http://pi3.informatik.uni-mannheim.de/downloads/hauptstudium/dbs1/ss06/blatt10.pdf


Konnte leider mit den Funden aus google nix anfangen. Könntest du das bitte etwas näher erläutern! Ist das etwa sowas wie ein Alghoritmuss nach welchem der Natural Join intern im Datenbanksystem verarbeitet wird?
Auch irritiert mich der Aufgabentext da von seitenorientiertem Nested Loop Join und Seitenzugriffen die Rede ist. Wodoch in der Vorlesung bisher immer die Rede von Relation bzw. Tabellen und Tupeln bzw. Zeilen und Attributen bzw. Spalten war.


Vg Erdal

 

[hpvw]

Konnte leider mit den Funden aus google nix anfangen. Könntest du das bitte etwas näher erläutern! Ist das etwa sowas wie ein Alghoritmuss nach welchem der Natural Join intern im Datenbanksystem verarbeitet wird?

So habe ich es beim ASA SQL-Benutzerhandbuch und bei Kreissl verstanden.

Auch irritiert mich der Aufgabentext da von seitenorientiertem Nested Loop Join und Seitenzugriffen die Rede ist. Wodoch in der Vorlesung bisher immer die Rede von Relation bzw. Tabellen und Tupeln bzw. Zeilen und Attributen bzw. Spalten war.

Bei der Aufgabe kann ich Dir auch nicht helfen. Ich würde aber vermuten, dass sich irgendwo in Deinen Unterlagen eine Formel für Aufgabe 2 findet.

Gruß hpvw

 

[Exceptionfault]

Also, ein Nested Loop Join beschreibt die Vorgehensweise bzw. den Algorithmus der Datenbank beim
Joinen. Eine andere Art wäre zum Beispiel der Hash Join.

Einen Nested Loop (verschachtelte Schleife) sollte die Datenbank immer dann nutzen, wenn zwei Tabellen
gejoint werden, bei denen sich die Treffermengen stark unterscheiden. Man spricht beim Nested Loop
dann von der inneren und äußeren Tabelle.

Das DBMS macht im Grunde folgendes:

Es sucht sich die Tabelle mit der kleineren Treffermenge und wählt sie als äußere Tabelle.
Für jeden gefundenen Treffer sucht sie in der größeren inneren Tabelle die passenden Ergebnisse.
Die Performance ist also davon abhängig wieviel Treffer in der äußeren Tabelle existieren und
wie schnell die Ergebnisse in der inneren Tabelle gefunden werden (Index?!)

Sind beide Tabellen bzw. Treffermengen gleich groß, also würde die Äußere Tabelle zu groß werden,
wird sich das DBMS für einen Hash Join entscheiden. Dabei werden beide Ergebnismengen nach dem
Joinkriterium sortiert und jeweils die obersten Zeilen miteinander verglichen.

Das ganze hat also weniger etwas mit der Art (inner, outer, left, right...) des Joins, sondern viel
mehr mit dem Algorithmus in der Datenbank was zu tun.