Sort-merge join


The sort-merge join is 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, or by taking advantage of a pre-existing ordering in one or both of the join relations. The latter condition, called interesting order, 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. Interesting orders need not be serendipitous: the optimizer may seek out this possibility and choose a plan that is suboptimal for a specific preceding operation if it yields an interesting order that one or more downstream nodes can exploit.
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 time cost will contain additional terms of sorting time:, which equals .

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
var relation output
var list left_sorted := sort // Relation left sorted on attribute a
var list right_sorted := sort
var attribute left_key, right_key
var set left_subset, right_subset // These sets discarded except where join predicate is satisfied
advance
advance
while not empty and not empty
if left_key = right_key // Join predicate satisfied
add cartesian product of left_subset and right_subset to output
advance
advance
else if left_key < right_key
advance
else // left_key > right_key
advance
return output
// Remove tuples from sorted to subset until the sorted.a value changes
function advance
key := sorted.a
subset := emptySet
while not empty and sorted.a = key
insert sorted into subset
remove 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
public class Relation