16. Using the Query Optimizer : Types of Nodes in a QEP : Join Nodes in a QEP : Full Sort Merge Node
 
Share this page                  
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