Nested Loop Join

Nested Loop Join

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.


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Nested loop join — A nested loop join is a naive algorithm that joins two relations R and S by making two nested loops: For each tuple r in R do For each tuple s in S do If r and s satisfy the join condition Then output the tuple <r,s> This algorithm will… …   Wikipedia

  • 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… …   Deutsch Wikipedia

  • Block nested loop — A block nested loop is an algorithm used to join two relations in a relational database.This algorithm is a variation on the simple nested loop join used to join two relations R and S (the outer and inner join operands, respectively). Suppose |R| …   Wikipedia

  • Join (SQL) — An SQL join clause combines records from two or more tables in a database.[1] It creates a set that can be saved as a table or used as is. A JOIN is a means for combining fields from two tables by using values common to each. ANSI standard SQL… …   Wikipedia

  • Hash join — The Hash join is an example of a join algorithm and is used in the implementation of a relational database management system.The task of a join algorithm is to find, for each distinct value of the join attribute, the set of tuples in each… …   Wikipedia

  • Joinalgorithmen — sind mögliche Strategien (Algorithmen) zur Implementierung von Joins. Die optimale Strategie hängt von Größe und Struktur der am Join beteiligten Relationen, verwendeten oder verwendbaren Indizes, der Größe des Hauptspeichers als auch der Join… …   Deutsch Wikipedia

  • Query optimizer — The query optimizer is the component of a database management system that attempts to determine the most efficient way to execute a query. The optimizer considers the possible query plans for a given input query, and attempts to determine which… …   Wikipedia

  • Oxygene (programming language) — Oxygene Developer RemObjects Software Stable release 3.0.21 (August 29, 2009; 2 years ago (2009 08 29)) Influenced by Object Pas …   Wikipedia

  • JavaScript syntax — This article is part of the JavaScript series. JavaScript JavaScript syntax JavaScript topics This box: view · …   Wikipedia

  • D (programming language) — For other programming languages named D, see D (disambiguation)#Computing. D programming language Paradigm(s) multi paradigm: imperative, object oriented, functional, meta Appeared in 1999 (1999) Designed by …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”