# Sort-merge join

### From Wikipedia, the free encyclopedia

The **Sort-Merge Join** is an example of a join algorithm and is used in the implementation of a relational database management system.

The basic problem of a join algorithm is to find, for each distinct value of the join attribute, the set of tuples in each relation which display that value. The key idea of the Sort-merge algorithm is to first sort the relations by the join attribute, so that interleaved linear scans will encounter these sets at the same time.

In practice, the most expensive part of performing a sort-merge join is arranging for both inputs to the algorithm to be presented in sorted order. This can be achieved via an explicit sort operation (often an external sort), or by taking advantage of a pre-existing ordering in one or both of the join relations. The latter condition can occur because an input to the join might be produced by an index scan of a tree-based index, another merge join, or some other plan operator that happens to produce output sorted on an appropriate key.

## [edit] Pseudocode

For simplicity, the algorithm is described in the case of an inner join of two relations on a single attribute. Generalization to other join types, more relations and more keys is straightforward.

functionsortMerge(relationleft,relationright,attributea)var relationoutputvar listleft_sorted := sort(left, a)var listright_sorted := sort(right, a)varleft_keyvarright_keyvar setleft_subsetvar setright_subset advance(left_subset, left_sorted, left_key, a) advance(right_subset, right_sorted, right_key, a)while notempty(left_sorted)and notempty(right_sorted)ifleft_key = right_key add cross product of left_subset and right_subset to output advance(left_subset, left_sorted, left_key, a) advance(right_subset, right_sorted, right_key, a)else ifleft_key < right_key advance(left_subset, left_sorted, left_key, a)else// left_key > right_keyadvance(right_subset, right_sorted, right_key, a)returnoutputfunctionadvance(subset, sorted, key, a) key = sorted[1].a subset =emptySetwhile notempty(sorted)andsorted[1].a = key insert(subset, sorted[1]) remove first element from sorted

## [edit] Simple C# Implementation

public class MergeJoin { // Assume that left and right are already sorted public static Relation Sort(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 //(left.Key > right.Key) right.Advance(); } return output; } }

public class Relation { private List<int> list; public const int ENDPOS = -1; public int position = 0; public int Position { get { return position; } } public int Key { get { return list[position]; } } 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 bool IsPastEnd() { return position == ENDPOS; } public void Print() { foreach (int key in list) Console.WriteLine(key); } public Relation(List<int> list) { this.list = list; } public Relation() { this.list = new List<int>(); } }