The sort-merge join (also known as 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.
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 (as linearithmic terms outweigh the linear terms, see Big O notation – Orders of common functions).
Read more about Sort-merge Join: Pseudocode, Simple C# Implementation
Famous quotes containing the word join:
“The idea was to prove at every foot of the way up that you were one of the elected and anointed ones who had the right stuff and could move higher and higher and even—ultimately, God willing, one day—that you might be able to join that special few at the very top, that elite who had the capacity to bring tears to men’s eyes, the very Brotherhood of the Right Stuff itself.”
—Tom Wolfe (b. 1931)