Full Sort Merge Node
The full sort merge (FSM) is a more optimal join: it typically joins the inner and outer subtrees with many fewer comparisons than the cart-prod requires. This is done by assuring that both subtrees are sorted in the order of the join columns. If one or the other is not already sorted (for example, by being read from a B-tree index constructed on the join columns), the query plan can include a sort to put the rows in the correct order. This allows the rows of the outer subtree to be joined to the matching rows of the inner subtree with one pass over each. The inner subtree is not scanned multiple times, as with the cart-prod join.
A typical abbreviated example of a QEP diagram involving an FSM is shown below:
join
/ \
sort sort
/ /
proj-rest proj-rest
/ /
table table
This node is displayed with the following information on a QEP diagram:
• A label identifying it as a FSM join node, along with the column(s) on which join processing is done
• If an outer join has been requested, one of the following labels indicating the type of join:
[LEFT JOIN]
[FULL JOIN]
[RIGHT JOIN]
• Storage structure (which is usually heap) or a list of sort columns if the data is being sorted
• Total number of pages and tuples
• Query cost information
• Optionally, sort information (whether the data produced by this node is already sorted or requires sorting)
The FSM is most common when a “bulk” join takes place with no row restrictions on either table involved in the join, as with a SELECT statement of the following form:
SELECT * FROM r1, r2 WHERE r1.joincol = r2.joincol;
This example shows a QEP diagram with an FSM join node resulting from such a bulk join:
SELECT a.col2, b.col2 FROM arel a, brel b
WHERE a.col1 = b.col1;
QUERY PLAN 5,1, no timeout, of main query
FSM Join(col1)
Heap
Pages 1 Tups 156
D9 C40
/ \
Proj-rest Proj-rest
Sorted(eno) Sorted(eno)
Pages 1 Tups 156 Pages 1 Tups 156
D8 C1 D1 C1
/ /
arel brel
Hashed (NU) Isam (NU)
Pages 70 Tups 156 Pages 3 Tups 156