Join-Algorithmen: Nested Loop, Hash, Merge

Sie kennen INNER JOIN bereits als Syntax. In einem Vorstellungsgespräch auf Senior-Level fragen Interviewer, wie die Datenbank einen Join physisch ausführt. Es gibt drei Algorithmen:

• Nested Loop Join
• Hash Join
• Merge Join (Sort-Merge)

Der logische Join-Typ (INNER, LEFT) ist unabhängig vom Algorithmus. Der Planer wählt den Algorithmus anhand der Tabellengrößen, Indizes und Sortierreihenfolge. Zu wissen, wann welcher Algorithmus am besten abschneidet, ist der Kern dieser Lektion.

Der Nested Loop ist der einfachste Algorithmus: Für jede Zeile der äußeren Tabelle wird die innere Tabelle nach passenden Zeilen durchsucht. Im Pseudocode sind das zwei Schleifen, eine innerhalb der anderen.

Naiv betrachtet ist das O(outer * inner) und für große Tabellen äußerst schlecht. Der Algorithmus wird jedoch hervorragend, wenn die innere Seite einen Index auf dem Join-Schlüssel besitzt: Für jede äußere Zeile wird dann eine schnelle Indexsuche statt eines vollständigen Scans der inneren Tabelle ausgelöst.

Der Planer bevorzugt ihn, wenn die äußere Tabelle klein und die Join-Spalte der inneren Tabelle indiziert ist.

Das eindeutige Merkmal eines Nested Loop ist loops am inneren Knoten. Das Beispiel zeigt loops=3, weil die äußere Seite 3 Zeilen geliefert hat und der innere Index-Scan daher 3-mal ausgeführt wurde.

Gefährlich wird es, wenn die äußere Seite groß ist. Liefert sie 2 Millionen Zeilen, wird die innere Seite 2 Millionen Mal ausgeführt. Selbst eine schnelle Suche von 0,01 ms dauert dann 20 Sekunden.

Markieren Sie im Vorstellungsgespräch jeden Nested Loop, bei dem loops an einer inneren Tabelle ohne guten Index groß ist: Das ist die langsame Abfrage.

Der Hash Join eignet sich gut für große, unsortierte Tabellen. Er läuft in zwei Phasen ab:

• Build: Die kleinere Tabelle wird gelesen und in eine speicherinterne Hash-Tabelle geladen, deren Schlüssel die Join-Spalte ist.
• Probe: Die größere Tabelle wird durchsucht; für jede Zeile wird der Join-Schlüssel gehasht und in der Hash-Tabelle nachgeschlagen.

Jede Tabelle wird nur einmal gelesen, sodass sich ungefähr O(outer + inner) ergibt. Es werden weder Indizes noch sortierte Eingaben benötigt. Deshalb dominiert dieser Algorithmus große analytische Joins mit Gleichheitsbedingungen.

Zu Hash Joins müssen Sie zwei Punkte erwähnen:

• Sie funktionieren nur bei Join-Bedingungen auf Gleichheit (a.id = b.id). Eine Bereichsbedingung wie a.x < b.y kann keinen Hash Join verwenden.
• Die Build-Seite muss in work_mem passen. Falls das nicht möglich ist, lagert Postgres Batches auf die Festplatte aus (Sie sehen dann Batches: > 1 und Festplattennutzung), wodurch der Join stark verlangsamt wird.

Ein Hash Join mit einer riesigen Build-Seite und zu kleinem work_mem ist daher ein echter Performancefehler, auf den Sie in der Praxis hinweisen sollten.

Der Merge Join (Sort-Merge) erfordert, dass beide Eingaben nach dem Join-Schlüssel sortiert sind. Anschließend werden beide Eingaben im Gleichschritt durchlaufen, ähnlich wie beim Zusammenführen zweier sortierter Listen. Dabei wird jeweils der Zeiger weiterbewegt, der zurückliegt.

Er ist effizient, wenn die Eingaben bereits sortiert sind, etwa weil sie direkt aus einem Index in Schlüsselreihenfolge kommen. Dann ist kein Sortierschritt erforderlich. Anders als ein Hash Join unterstützt er außerdem Bereichs- und Ungleichheits-Joins.

Sind die Eingaben nicht vorsortiert, fügt der Planer explizite Sort-Knoten hinzu. Die Kosten dieser Sortierung können dazu führen, dass ein Hash Join stattdessen günstiger ist.

Merken Sie sich, wann welcher Algorithmus gewinnt:

• Nested Loop: kleine äußere Tabelle und ein indizierter innerer Join-Schlüssel; außerdem die einzige Option für Nicht-Gleichheits-Joins ohne sortierte Eingabe.
• Hash Join: große, unsortierte Tabellen mit Gleichheitsbedingung; keine Indizes erforderlich.
• Merge Join: beide Eingaben sind bereits nach dem Schlüssel sortiert (oft über Indizes), oder es handelt sich um Bereichs-Joins; hervorragend für sehr große vorsortierte Datenmengen.

Der Planer schätzt die Kosten jedes Algorithmus und wählt anhand seiner Zeilenschätzungen den günstigsten aus.

Der Ressourcenverbrauch unterscheidet sich deutlich, und Interviewer prüfen genau diesen Punkt:

• Nested Loop: minimaler Speicherbedarf; die Kosten werden von den wiederholten Suchen auf der inneren Seite bestimmt.
• Hash Join: benötigt Speicher für die Hash-Tabelle; lagert sie auf die Festplatte aus, wenn sie zu groß ist.
• Merge Join: Zusammenführen ist günstig, aber eine vorherige Sortierung ist teuer; Sortierungen verwenden ebenfalls work_mem und können auf die Festplatte ausgelagert werden.

Wenn Sie work_mem erhöhen, kann sich ein langsamer Hash oder eine langsame Sortierung, die auf die Festplatte ausgelagert wird, in eine speicherinterne Variante verwandeln. Das ist eine konkrete Optimierungsantwort.

Ein klassisches Szenario: Eine Abfrage war in der Entwicklung schnell, aber in der Produktion langsam. Der Plan zeigt einen Nested Loop mit loops=3000000.

Der Planer hat die Anzahl der Zeilen auf der äußeren Seite unterschätzt (veraltete Statistiken meldeten 3 Zeilen, tatsächlich sind es 3 Millionen) und deshalb einen Nested Loop gewählt. Mit korrekten Statistiken hätte er einen Hash Join ausgewählt.

Ihre Antwort im Vorstellungsgespräch: Führen Sie ANALYZE aus, damit die Schätzung stimmt; der Planer wechselt dann zu einem Hash Join und die Abfrage wird deutlich schneller.

Normalerweise sollten Sie Algorithmen nicht erzwingen, aber zum Vergleichen können Sie dies in Tests tun. Postgres stellt für jede Methode eigene Schalter bereit:

SET enable_nestloop = off; und entsprechend für enable_hashjoin und enable_mergejoin. Schalten Sie einen Schalter aus, führen Sie EXPLAIN ANALYZE erneut aus und beobachten Sie, ob die Alternative tatsächlich schneller ist.

Die richtigen Lösungen bleiben: aktuelle Statistiken, die passenden Indizes, ausreichendes work_mem und selektive Prädikate. Das Erzwingen dient ausschließlich der Diagnose.

Wenden Sie das Gelernte auf eine analytische Arbeitslast an, bei der zwei große Fakten- und Dimensionstabellen über eine id verknüpft werden:

• Wenn die Dimension in den Speicher passt, erwarten Sie einen Hash Join, der oft die beste Wahl ist.
• Wenn beide Tabellen über Indizes bereits sortiert eintreffen, kann ein Merge Join den Aufbau der Hash-Tabelle vermeiden.
• Ein Nested Loop wäre hier ein Warnsignal und wird meistens durch eine falsche Schätzung verursacht.

Zu erkennen, welchen Algorithmus der Planer gewählt hat, und zu beurteilen, ob er den richtigen hätte wählen müssen, ist genau das Senior-Level-Signal, das diese Fragen prüfen.

Sie verknüpfen zwei große, unsortierte Tabellen über eine Gleichheitsbedingung a.id = b.id. Keine der Tabellen besitzt einen nützlichen Index und die Statistiken sind korrekt. Welchen Join-Algorithmus wird der Planer höchstwahrscheinlich auswählen?

Die drei Join-Algorithmen:

• Nested Loop: äußere Zeilenanzahl mal innerer Lookup; hervorragend bei einer kleinen äußeren Tabelle und einem indizierten inneren Schlüssel, gefährlich bei sehr großem loops-Wert.
• Hash Join: Build-and-Probe-Verfahren; am besten für große, unsortierte Gleichheits-Joins geeignet, auf Gleichheit beschränkt und durch work_mem begrenzt.
• Merge Join: gleichzeitiges Durchlaufen sortierter Eingaben; ideal, wenn die Daten bereits sortiert sind, oder für Bereichs-Joins.

Der Planer wählt anhand von Kosten und Statistiken. Ein unerwarteter Nested Loop mit sehr vielen Loops bedeutet fast immer eine falsche Zeilenschätzung: Korrigieren Sie die Statistiken.