Sort-Merge


Gilt für
DB2Ja
MySQLNein
OracleJa
PostgreSQLJa
SQL ServerJa

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.

Für alle Anwendungsentwickler […] sollte der schmale Band […] eine Pflichtlektüre sein — ADMIN-Magazin

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

Photo of Markus Winand
Markus Winand stimmt Entwickler auf SQL-Performance ein. Er hat das Buch SQL Performance Explained veröffentlicht und bietet inhouse Schulungen sowie Tuning-Leistungen auf http://winand.at/ an.