One of the key tasks of the query optimizer is to generate a query plan for join queries so that the order of the relations in the joins processed during query execution is optimal. This involves elaborate plan search strategies that can consume significant time and memory. The query optimizer uses several effective techniques to obtain the optimal join ordering. The key techniques are:
Use of a greedy strategy to obtain an initial good ordering that can be used as an upper boundary to prune out other, subsequent join orderings. The greedy strategy employs join row estimates and the nested-loop-join method to arrive at the initial ordering.
An exhaustive ordering strategy follows the greedy strategy. In this strategy, a potentially better join ordering replaces the join ordering obtained in the greedy strategy. This ordering may employ any join method.
Use of extensive cost-based and rule-based pruning techniques eliminates undesirable join orders from consideration. The key aspect of the pruning technique is that it always compares partial join orders (the prefix of a potential join ordering) against the best complete join ordering to decide whether to proceed with the given prefix. This significantly improves the time required determine an optimal join order.
The query optimizer can recognize and process star or snowflake schema joins and process their join ordering in the most efficient way. A typical star schema join involves a large Fact table that has equi-join predicates that join it with several Dimension tables. The Dimension tables have no join predicates connecting each other; that is, there are no joins between the Dimension tables themselves, but there are join predicates between the Dimension tables and the Fact table. The query optimizer employs special join ordering techniques during which the large Fact table is pushed to the end of the join order and the Dimension tables are pulled up front, yielding highly efficient query plans. The query optimizer does not, however, use this technique if the star schema joins contain subqueries, outer joins, or or predicates.
