Determining the Order of Joins | Join Planning/Optimization | Teradata Vantage - Determining the Order of Joins - Analytics Database - Teradata Vantage

Because of the exponentially escalating choices of binary join orders available to the Optimizer, algorithms and heuristics must replace the brute force method of evaluating all possible combinations against one another to determine the lowest cost join plan.

Join order evaluation is a critical aspect of query optimization that is highly dependent on accurate statistics. Using out of date statistical and demographic data can result in inaccurate assumptions about the cardinalities of intermediate results. Such inaccurate assumptions cause errors in join plan estimation that propagate exponentially as a function of the number of joins a query makes.

Join Order Evaluation Process Overview

The following provides a simplified explanation of the process the Optimizer follows when evaluating join orders in the process of generating a join plan.

1. Generate a 1-join lookahead plan.

2. Conditions	Optimizer Action
   The cost of the 1-join lookahead plan exceeds a threshold value. There exists one relation larger than a threshold value. The query has no outer join requirement.	Generate a 5-join lookahead plan and evaluate its cost. Keep the less-costly plan from the 1- and 5-join lookahead plans.

3. Conditions	Optimizer Action
   The cost of the current plan exceeds a threshold value. A star join may be required.	Generate a plan that uses star/snowflake join optimization, if such a plan can be found, compare the star/snowflake and lookahead join plans, and keep the less-costly plan.

Lookahead Join Planning

When planning an optimal join sequence for a query, the Optimizer uses a "what if?" method to evaluate the possible sequences for their relative usefulness to the query plan. This "what if?" method is called lookahead, because the evaluation looks forward one or more plans to examine the ultimate cost of joining relations in different orders.

The goal of join order analysis is to reduce the number of join order possibilities to a workable subset. The Optimizer search of join space is driven by join conditions, and uses a recursive greedy algorithm to search and evaluate connected relations. In this context, the term greedy means the search generates the next logical expression for evaluation based on the result of the costing determined by the previous step. From the perspective of search trees, a greedy algorithm always begins at the bottom of the tree and works its way toward the top.

The following is a simplified explanation of lookahead join planning:

1. Find the best 3-way or n-way join plans among the combinations considered.
   Follow these rules to find them:

   • Use a depth-first search.
   • Skip a join plan if any one of the following conditions is detected:
     • A less costly plan exists that delivers a result with similar or better attributes.
     • The accumulated cost exceeds that of the current candidate join plan.
   • Only consider joins between connected relations.
   • Join an unconnected relation only after all connected relations have been joined.

   The Optimizer does not evaluate all possible combinations of relations, because the effort exceeds any realized optimizations. For example, a 10-way join has 17.6 x 109 possible combinations, and a 64-way join has 1.2 x 10124 possible combinations.

   In pursuit of combinations driven mainly by join conditions, the Optimizer may overlook the best possible join plan, but in practice, that generally does not happen.

2. Evaluate the best current join plan.

   Conditions	Optimizer Action
   For the first 2 joins of the best join plan: The joins involve one relation connected with 2 relations not connected to each other Neither join is a product join	Try a compromise join where the 2 unconnected relations are product-joined in the first join and that result is then joined with a third relation.
   Compromise join plan is less costly than the best current join plan.	Replace the first 2 joins on the best join plan with the compromise plan.

   The compromise plan is designed to enable a star join plan.

3. Materialize the first join of the best n-way join into a relation and evaluate the materialized relation for the following conditions:
   • The number of lookaheads is sufficient to generate the complete join plan.
   • The compromise join plan is not used.

   Conditions	Optimizer Action
   Met	Remaining joins of the best plan are also committed.
   Not met	Second join is also committed if joining another relation with the result of the first join using the primary index for the newly joined relation.

4. Generate connection information for new relations based on the predicates.
5. Iterate Stages 1 through 4 until only one active relation remains.