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 aufwendig ist. Ein Hash-Join muss dagegen nur eine Seite vorverarbeiten.
Hinweis in eigener Sache
Ich lebe von SQL-Schulungen, SQL-Tuning und Beratung sowie dem Verkauf meines Buches „SQL Performance Explained“. Mehr auf winand.at.
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.
