Sort Merge


Applies to
MySQLNo
OracleYes
PostgreSQLYes
SQL ServerYes

The sort-merge join combines two sorted lists like a zipper. Both sides of the join must be sorted by the join predicates.

A sort-merge join needs the same indexes as the hash join, that is an index for the independent conditions to read all candidate records in one shot. Indexing the join predicates is useless. Everything is just like a hash join so far. Nevertheless there is one aspect that is unique to the sort-merge join: absolute symmetry. The join order does not make any difference—not even for performance. This property is very useful for outer joins. For other algorithms the direction of the outer joins (left or right) implies the join order—but not for the sort-merge join. The sort-merge join can even do a left and right outer join at the same time—a so-called full outer join, like shown in the following animation.

Figure 4.1. Sort-Merge Join Executing a FULL OUTER JOIN


Although the sort-merge join performs very well once the inputs are sorted, it is hardly used because sorting both sides is very expensive. The hash join, on the other hand, needs to preprocess only one side.

About our book “SQL Performance Explained”
Probably the best book on SQL performance I've read
Guillaume Lelarge on Amazon.co.uk (5 stars)

The strength of the sort-merge join emerges if the inputs are already sorted. This is possible by exploiting the index order to avoid the sort operations entirely. Chapter 6, “Sorting and Grouping, explains this concept in detail. The hash join algorithm is superior in many cases nevertheless.

If you like my way of explaining things, you’ll love my book.

Factbox

  • Sort-merge joins do not need indexes on the join predicates.

  • MySQL does not support sort-merge joins at all.

About the Author

Photo of Markus Winand
Markus Winand tunes developers for high SQL performance. He also published the book SQL Performance Explained and offers in-house training as well as remote coaching at http://winand.at/

?Recent questions at
Ask.Use-The-Index-Luke.com

0
votes
2
answers
732
views

different execution plans after failing over from primary to standby server

2 days ago Markus Winand ♦♦ 741
oracle index update
1
vote
1
answer
69
views

Generate test data for a given case

Sep 14 at 18:11 Markus Winand ♦♦ 741
testcase postgres
0
votes
1
answer
220
views

Database design suggestions for a data scraping/warehouse application?

Aug 27 at 09:29 Markus Winand ♦♦ 741
mysql optimization database