To understand why the heuristic pruning is so effective
in reducing the optimization times,
consider the reduction in the search space.
Table 7.5 shows the size of the logical search space
under the join order heuristics used above
for simple joins queries.
The join queries
were based on the TPC-D schema,
but involve only the GET
and EQJOIN logical operators.
(The join queries are listed in appendix Q.)
Table 7.5: Size of Logical Search Space With Heuristic Pruning
#joins Size of Logical Search Space Size of Logical Search Space
Left-Deep Only & NOCART Product** With Exhaustive Rules
Join Order Heuristic Pruning (See Figure 3.4)
groups expressions* query trees groups expressions query trees
2 6 9 4 7 15 12
3 13 23 16 15 54 120
4 21 40 44 31 185 1680
5 30 58 104 63 608 30240
6 34 63 164 127 1939 665280
7 44 82 352 255 6058 17297280
* This is an approximate number obtained by counting the total number
of logical and physical expressions and dividing by 2. (The justification
is that the rule set used to generate table 7.5 only included a single
implementation rule for each logical operator.)
** Results on the left side of this table are based on left deep joins
and excluding Cartesian products.
the statistics for heuristic pruning
are very dependent on the topology of the initial query.
For the join queries above,
the initial query tree was left-deep
had no Cartesian Products.
Understanding this caveat,
in the logical search space under
the join order heuristics is very dramatic.
If only the
left deep heuristic is used,
the reduction in search space
is not as dramatic.
The number left deep query trees for a join of n relations
is n! (n factorial).