Information about Sort Merge Join
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.
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_sorted) and not empty(right_sorted) 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
In mathematics, a tuple is a finite sequence (also known as an "ordered list") of objects, each of a specified type. A tuple containing n objects is known as an "n-tuple".
..... Click the link for more information.
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.
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_sorted) and not empty(right_sorted) 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
External links
- Example of a more advanced Python implementation
- Java implementation of NestedLoop, Sort-Merge and Hash joins.
A relational database is a database that conforms to the relational model, and refers to a database's data and schema (the database's structure of how that data is arranged).
..... Click the link for more information.
..... Click the link for more information.
A database management system (DBMS) is computer software designed for the purpose of managing databases. Typical examples of DBMSs include Oracle, DB2, Microsoft Access, Microsoft SQL Server, PostgreSQL, MySQL, FileMaker and Sybase Adaptive Server Enterprise.
..... Click the link for more information.
..... Click the link for more information.
For the musical term, see .
In mathematics, a tuple is a finite sequence (also known as an "ordered list") of objects, each of a specified type. A tuple containing n objects is known as an "n-tuple".
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
