Merge Join
A merge join requires both tables sorted by the join column, synchronously scanning and merging matching rows; suited to sorted data or post-sort joins.
Purpose
To understand the efficient algorithm for ordered joins and analyze the trade-off against sorting costs.
Mechanism
After sorting both tables on the join column, scan synchronously comparing current rows: equal outputs a match, the smaller advances. Complexity O(N+M) but sorting costs O(N log N + M log M). With sorted indexes, sorting is free — very efficient.
Use cases
- Ordered join optimization
- Join algorithm selection
- Execution plan analysis