Join-Algorithmen

Join-Algorithmen sind die physischen Methoden – Nested-Loop, Sort-Merge und Hash Join –, die Tupel aus zwei oder mehr Relationen auf einer Join-Bedingung kombinieren, und sie sind in der Regel die performancerelevantesten Operatoren in einem Abfrageplan.

Definition

Ein Join-Algorithmus ist ein physischer Operator, der den Join zweier Relationen auf einem Prädikat berechnet, indem er systematisch Tupel paart, die die Bedingung erfüllen, wobei er verschachtelte Iteration, sortiertes Merging oder Hashing verwendet, um übereinstimmende Tupel effizient zu finden.

Scope

Dieses Thema behandelt die wichtigsten Algorithmen zur Auswertung von Joins: einfache, Block- und Index-Nested-Loop-Joins; Sort-Merge-Join und seine Synergie mit bereits sortierten Eingaben; und Hash Join, einschließlich der Grace- und Hybrid-Varianten, die Eingaben verarbeiten, die größer als der Speicher sind. Es analysiert deren I/O-Kosten und Speicheranforderungen sowie die Bedingungen, unter denen jeder bevorzugt wird. Es schließt die Enumeration der Join-Reihenfolgen durch den Optimierer aus, die unter kostenbasierter Abfrageoptimierung behandelt wird.

Core questions

• Wie unterscheiden sich Nested-Loop, Sort-Merge und Hash Join in Ansatz und Kosten?
• Wann übertrifft ein Index-Nested-Loop-Join die Alternativen?
• Wie verarbeiten Grace- und Hybrid-Hash-Joins Eingaben, die größer als der Speicher sind?
• Wie werden die I/O-Kosten jeder Join-Methode in Bezug auf Seiten und Durchläufe analysiert?
• Welche Join-Bedingung (Gleichheit versus Ungleichheit) erfordert jeder Algorithmus?

Key concepts

• Nested-Loop-Join
• Block-Nested-Loop-Join
• Index-Nested-Loop-Join
• Sort-Merge-Join
• Hash Join
• Grace- und Hybrid-Hash-Join
• Equijoin versus Theta Join
• I/O-Kostenanalyse

Key theories

Nested-Loop-Joins

Für jedes Tupel einer Relation durchsucht der Algorithmus die andere nach Übereinstimmungen; Block-Nested-Loop reduziert I/O durch Pufferung von Seiten, und Index-Nested-Loop ersetzt den inneren Scan durch eine Indexsuche, wenn eine verfügbar ist, was ihn für selektive Joins effizient macht.

Sort-Merge-Join

Beide Eingaben werden nach dem Join-Attribut sortiert und dann in einem einzigen koordinierten Durchlauf zusammengeführt; er ist besonders attraktiv, wenn die Eingaben bereits sortiert sind oder wenn die Ausgabe sortiert sein muss, und er verarbeitet Gleichheits-Joins effizient.

Hash Join

Ein Gleichheits-Join wird berechnet, indem eine In-Memory-Hash-Tabelle auf der kleineren Relation erstellt und diese mit der größeren abgefragt wird; die Grace- und Hybrid-Varianten partitionieren beide Eingaben auf die Festplatte, wenn sie den Speicher überschreiten, was eine starke Leistung für große Equijoins bietet.

Clinical relevance

Joins dominieren die Kosten von Analyse- und Berichtsabfragen, die mehrere Tabellen kombinieren, daher bestimmt die Wahl des Join-Algorithmus – oft die wichtigste Einzelentscheidung in einem Plan –, ob solche Abfragen interaktiv sind oder Stunden dauern, was diese Algorithmen für die Datenbankleistung zentral macht.

History

Sort-Merge- und Nested-Loop-Joins stammen aus den frühesten relationalen Systemen. Hash Join und seine Grace- und Hybrid-Varianten wurden in den 1980er Jahren entwickelt, insbesondere in der Forschung zu parallelen Datenbanken, und es wurde gezeigt, dass sie Sort-Merge bei vielen großen Equijoins übertreffen. Graefes Übersicht von 1993 konsolidierte die Analyse dieser Algorithmen, der Datenbanktexte immer noch folgen.

Key figures

• Goetz Graefe
• David DeWitt

Seminal works

• graefe1993
• garciamolina2008

Frequently asked questions

Welcher Join-Algorithmus ist der schnellste?

Das hängt von den Eingaben ab. Hash Join ist in der Regel am besten für große Equijoins, wenn keine der Eingaben sortiert ist; Sort-Merge gewinnt, wenn die Eingaben bereits sortiert sind oder die Ausgabe geordnet sein muss; und Index-Nested-Loop ist am besten, wenn eine Eingabe klein ist und die andere einen selektiven Index auf der Join-Spalte hat. Der Optimierer wählt basierend auf geschätzten Kosten.

Warum kann Hash Join keine Ungleichheitsbedingungen verarbeiten?

Hash Join gruppiert Tupel nach dem Hash des Join-Schlüssels, sodass nur Tupel mit gleichen Schlüsseln im selben Bucket landen. Das funktioniert für Gleichheitsbedingungen (Equijoin), aber nicht für Ungleichheiten wie 'kleiner als', die den Vergleich von Tupeln über Buckets hinweg erfordern – diese werden stattdessen mit Nested-Loop- oder Sort-Merge-ähnlichen Methoden behandelt.