The sort-merge join, also known as merge join, is a join algorithm commonly used in a relational database management system. It works by sorting both relations on the join attribute so that linear scans can find matching sets of tuples simultaneously. The most costly part of the process is ensuring inputs are sorted, often requiring an external sort. However, sorting may be avoided if one or both inputs already have an appropriate order, known as an interesting order. Such orders can result from index scans or prior operations and can be exploited by query optimizers to improve performance, even if it means a less optimal plan for earlier steps.
Complexity
Let R {\displaystyle R} and S {\displaystyle S} be relations where | R | < | S | {\displaystyle |R|<|S|} . R {\displaystyle R} fits in P r {\displaystyle P_{r}} pages memory and S {\displaystyle S} fits in P s {\displaystyle P_{s}} pages memory. In the worst case, a sort-merge join will run in O ( P r + P s ) {\displaystyle O(P_{r}+P_{s})} I/O operations. In the case that R {\displaystyle R} and S {\displaystyle S} are not ordered the worst case time cost will contain additional terms of sorting time: O ( P r + P s + P r log ( P r ) + P s log ( P s ) ) {\displaystyle O(P_{r}+P_{s}+P_{r}\log(P_{r})+P_{s}\log(P_{s}))} , which equals O ( P r log ( P r ) + P s log ( P s ) ) {\displaystyle O(P_{r}\log(P_{r})+P_{s}\log(P_{s}))} (as linearithmic terms outweigh the linear terms, see Big O notation – Orders of common functions).
Pseudocode
For simplicity, the algorithm is described in the case of an inner join of two relations left and right. Generalization to other join types is straightforward. The output of the algorithm will contain only rows contained in the left and right relation and duplicates form a Cartesian product.
function Sort-Merge Join(left: Relation, right: Relation, comparator: Comparator) { result = new Relation() // Ensure that at least one element is present if (!left.hasNext() || !right.hasNext()) { return result } // Sort left and right relation with comparator left.sort(comparator) right.sort(comparator) // Start Merge Join algorithm leftRow = left.next() rightRow = right.next() outerForeverLoop: while (true) { while (comparator.compare(leftRow, rightRow) != 0) { if (comparator.compare(leftRow, rightRow) < 0) { // Left row is less than right row if (left.hasNext()) { // Advance to next left row leftRow = left.next() } else { break outerForeverLoop } } else { // Left row is greater than right row if (right.hasNext()) { // Advance to next right row rightRow = right.next() } else { break outerForeverLoop } } } // Mark position of left row and keep copy of current left row left.mark() markedLeftRow = leftRow while (true) { while (comparator.compare(leftRow, rightRow) == 0) { // Left row and right row are equal // Add rows to result result = add(leftRow, rightRow) // Advance to next left row leftRow = left.next() // Check if left row exists if (!leftRow) { // Continue with inner forever loop break } } if (right.hasNext()) { // Advance to next right row rightRow = right.next() } else { break outerForeverLoop } if (comparator.compare(markedLeftRow, rightRow) == 0) { // Restore left to stored mark left.restoreMark() leftRow = markedLeftRow } else { // Check if left row exists if (!leftRow) { break outerForeverLoop } else { // Continue with outer forever loop break } } } } return result }Since the comparison logic is not the central aspect of this algorithm, it is hidden behind a generic comparator and can also consist of several comparison criteria (e.g. multiple columns). The compare function should return if a row is less(-1), equal(0) or bigger(1) than another row:
function compare(leftRow: RelationRow, rightRow: RelationRow): number { // Return -1 if leftRow is less than rightRow // Return 0 if leftRow is equal to rightRow // Return 1 if leftRow is greater than rightRow }Note that a relation in terms of this pseudocode supports some basic operations:
interface Relation { // Returns true if relation has a next row (otherwise false) hasNext(): boolean // Returns the next row of the relation (if any) next(): RelationRow // Sorts the relation with the given comparator sort(comparator: Comparator): void // Marks the current row index mark(): void // Restores the current row index to the marked row index restoreMark(): void }Simple C# implementation
Note that this implementation assumes the join attributes are unique, i.e., there is no need to output multiple tuples for a given value of the key.
public class MergeJoin { // Assume that left and right are already sorted public static Relation Merge(Relation left, Relation right) { Relation output = new Relation(); while (!left.IsPastEnd && !right.IsPastEnd) { if (left.Key == right.Key) { output.Add(left.Key); left.Advance(); right.Advance(); } else if (left.Key < right.Key) left.Advance(); else // if (left.Key > right.Key) right.Advance(); } return output; } } public class Relation { private const int ENDPOS = -1; private List<int> list; private int position = 0; public Relation() { this.list = new List<int>(); } public Relation(List<int> list) { this.list = list; } public int Position => position; public int Key => list[position]; public bool IsPastEnd => position == ENDPOS; public bool Advance() { if (position == list.Count - 1 || position == ENDPOS) { position = ENDPOS; return false; } position++; return true; } public void Add(int key) { list.Add(key); } public void Print() { foreach (int key in list) Console.WriteLine(key); } }See also
External links
C# Implementations of Various Join Algorithms
References
"Sort-Merge Joins". www.dcs.ed.ac.uk. Retrieved 2022-11-02. https://www.dcs.ed.ac.uk/home/tz/phd/thesis/node20.htm ↩