SQL Join Optimization Algorithm

When a query is submitted, the Query Processor runs its parsing and verification checks (see SQL Parsing and Verification), then, if the query passes those checks, the Query Processor begins the optimization phase.

During the optimization phase, the Query Processor runs the SQL Join Optimization algorithm. This allows it to identify the most efficient way to access the data required for your query.

The SQL Join Optimization algorithm consists of these stages:

1. Build the Sub-Clause List
2. Categories the sub-clauses (see Determine the Sub-Clause Types):
   1. Add filter sub-clauses to the filter condition of the referenced table
   2. Add constraint sub-clauses to the constraints of the referenced table
3. Calculate the Table Order Permutations:
4. For each permutation of the join-order:
   1. Examine each access clause:
      • If the access sub-clause references a single table, use it to determine that table’s access path
      • If the access sub-clause references two tables, it is assigned to the right-most table. If the sub-clause references an indexed column, it is used to determine the access path; if it does not reference an indexed column, it is added to the filter condition for the table.
      • If a table already has an access path, and the sub-clause can provide a better access path, the sub-clause used to provide the previous access path is added to the table’s filter condition
   2. Examine each link sub-clause:
   • Assess the link sub-clause to the filter condition of the right-most table that is referenced by the sub-clause
   3. Determine the cost of each access path (see Calculate the Cost and Determine the Final Access Plan)
4. Multiply the cost of each access path together to determine the cost for the join order (see Calculate the Cost and Determine the Final Access Plan). At this stage, the join order and its associated access paths are referred to as the access plan.
5. Choose the access plan with the lowest cost. This access plan is now referred to as the Final Access Plan (see Calculate the Cost and Determine the Final Access Plan).

When the Query Processor has determined the most appropriate access plan (the Final Access Plan), it executes the query by performing the execution algorithm (see SQL Execution).