von Markus Winand.

Sort-Merge


Der Sort-Merge-Join verbindet zwei Tabellen wie ein Reißverschluss. Dafür müssen beide Seiten nach den Join-Spalten vorsortiert sein.

Ein Sort-Merge-Join benötigt dieselbe Indizierung wie ein Hash-Join. Also Indizes auf den unabhängigen Prädikaten, um alle potenziell passenden Einträge in einem Zug zu lesen. Die Indizierung der Join-Prädikate ist nutzlos. So weit ist also alles wie beim Hash-Join. Der Sort-Merge-Join ist jedoch noch symmetrischer als ein Hash-Join. Die Join-Richtung macht keinen Unterschied – nicht einmal für die Performance. Dadurch ist der Sort-Merge-Join besonders gut für Outer-Joins geeignet. Denn bei anderen Algorithmen legt ein Outer-Join die Join-Richtung fest – nicht so beim Sort-Merge-Join. Dadurch kann der Sort-Merge-Algorithmus einen Left- und Right-Outer-Join sogar gleichzeitig durchführen – also einen Full-Outer-Join, wie in der folgenden Animation zu sehen ist.

Abbildung 4.1 Sort-Merge-Join führt einen Full-Outer-Join aus

Obwohl der Sort-Merge-Join sehr gute Performance liefert, sobald beide Seiten sortiert sind, wird er kaum benutzt, weil das Sortieren sehr auf­wen­dig ist. Ein Hash-Join muss dagegen nur eine Seite vorverarbeiten.

Die Stärke des Sort-Merge-Joins kommt zum Tragen, wenn die beiden Seiten bereits vorsortiert sind. Dadurch wird der Sortieraufwand völlig vermieden. Das kann man zum Beispiel erreichen, indem man die Index-Reihenfolge dafür ausnutzt. Dieses Konzept wird in Kapitel 6, „Sortieren und Gruppieren, genauer beschrieben. Dennoch ist der Hash-Join in vielen Bereichen überlegen.

Fakten

  • Sort-Merge-Join benötigt keine Indizes für die Join-Prädikate.

  • MySQL hat keinen Sort-Merge-Join.

Wenn dir gefällt, wie ich die Dinge erkläre, wirst du meine Kurse lieben.

Über den Autor

Foto von Markus Winand

Markus Winand lehrt effizientes SQL – inhouse und online. Er minimiert die Entwicklungszeit durch modernes SQL und optimiert die Laufzeit durch schlaue Indizierung – dazu hat er auch das Buch SQL Performance Explained veröffentlicht.

Sein Buch

Titelbild von „SQL Performance Explained“: Eichhörnchen läuft durchs Grass

Die Essenz: SQL-Tuning auf 200 Seiten.

Von Markus kaufen
(Taschenbuch und PDF)

Bei Amazon kaufen
(nur Taschenbuch)

Hol dir Markus

…für ein Training in dein Büro.

Das beliebte SQL-Performance Training für Entwickler lässt dich die Datenbank besser verstehen. Erfahre mehr»

„Use The Index, Luke!“ von Markus Winand ist unter einer Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License lizenziert.
Impressum | Kontakt | KEINE GEWÄHR | Handelsmarken | Datenschutz | CC-BY-NC-ND 3.0 Lizenz