CSE Roadmap

Core tier · about 2 hours · 5 parts

Part 4 of 5 · 2 min read

Sort-merge join

Sort both sides by the join column, then walk them together in one synchronized pass.

Sort-merge join

Think of merging two separately alphabetized guest lists into one combined list by walking down both lists together, advancing whichever list currently has the earlier name.

In plain words: a sort-merge join sorts both tables by the join column, using the external sort covered on the next page if a table does not fit in memory, then walks through both sorted tables together in one synchronized pass, advancing whichever side currently has the smaller value. This works especially well when both tables are already sorted by the join column, such as when an index on that column already provides the sorted order, avoiding the separate sort step entirely.

A worked example. Joining two tables already indexed, and therefore sorted, on the join column performs a sort-merge join directly off both indexes' existing order, with no separate sort step needed.

The key lines. No new SQL; sort-merge is chosen internally by the optimizer when both sides are sorted, or cheap to sort, on the join column.

Sort-merge join

A sort-merge join sorts both tables by the join column, then walks both sorted tables together in one synchronized pass, matching rows as it goes; it is cheapest when both sides are already sorted.

Example: merging two separately alphabetized guest lists by walking down both together, advancing whichever has the earlier name, mirrors a sort-merge join.

Remember this

Nested loop favors a small outer table or an indexed inner table; hash join favors two large, unindexed tables; sort-merge favors tables already sorted on the join column. The optimizer, covered in depth two pages from now, picks among these using cost estimates.

Quick notes

  • A nested loop join scans the inner table once per outer row; good with a small outer table or an indexed inner table.
  • A hash join builds an in-memory hash table from one side, then probes it with one pass over the other side.
  • A sort-merge join sorts both sides, then merges them in one synchronized pass.
  • Sort-merge is cheapest when both sides are already sorted on the join column, such as via an existing index.
  • The optimizer chooses among these three based on table sizes, available indexes, and existing sort order.