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.
Note that 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 and had no Cartesian Products. Understanding this caveat, the reduction 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).


7. Results:    <Extensibility> <Efficiency> <Heuristics> <Accuracy> <Quality> <Agg Push Down> <Indices>
  7.1: Rules     7.2: Efficiency     7.3: Statistics     7.4: Heuristics     7.5: Search Space     7.6: Cardinalities     7.7: Costs     7.8: Agg     7.9: Indices  

 Page 7