The Sort-Merge Join is an example of a join algorithm and is used in the implementation of a relational
Relational database
A relational database is a database that conforms to relational model theory. The software used in a relational database is called a relational database management system . Colloquial use of the term "relational database" may refer to the RDBMS software, or the relational database itself...
A database management system is a software package with computer programs that control the creation, maintenance, and use of a database. It allows organizations to conveniently develop databases for various applications by database administrators and other specialists. A database is an integrated...
.
The basic problem of a join algorithm is to find, for each distinct value of the join attribute, the set of tuple
Tuple
In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
s 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.
Let's say that we have two relations and and . fits in pages memory and fits in pages memory. So, in the worst case Sort-Merge Join will run in I/Os. In the case that and are not ordered the worst case will be (where the last two terms are the cost of ordering both of them first).
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.
function sortMerge(relation left, relation right, attribute a) var relation output var list left_sorted := sort(left, a) var list right_sorted := sort(right, a) var left_key var right_key var set left_subset var set right_subset
advance(left_subset, left_sorted, left_key, a)
advance(right_subset, right_sorted, right_key, a) while not empty(left_subset) and not empty(right_subset) if left_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 if left_key < right_key
advance(left_subset, left_sorted, left_key, a) else// left_key > right_key
advance(right_subset, right_sorted, right_key, a) return output
function advance(subset, sorted, key, a)
key = sorted[1].a
subset = emptySet while not empty(sorted) and sorted[1].a = key
insert(subset, sorted[1])
remove first element from sorted
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 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 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);
}
and 
and 
. 
fits in 
pages memory and 
fits in 
pages memory. So, in the worst case Sort-Merge Join will run in 
I/Os. In the case that 
and 
are not ordered the worst case will be 
(where the last two terms are the cost of ordering both of them first).