Bhathiya edited section_Challenegs_in_Bushy_Trees__.tex  about 8 years ago

Commit id: da15fd20dc2bb907425f3946d2e353e5dfa272df

deletions | additions      

       

Therefore the number of possible permutations are $S(N)*N!$. Unlike left-deep tree case, estimating the cost for all the possible bushy trees is computationally infeasible for moderately large N. Therefore it is required to come with a heuristic to select set of permutations for cost computations.Some heuristics considered are  \textbf{QUIKPICK-1000} \textit{QUIKPICK-1000}  Here we build pseudo-random joining trees . This approach can build trees very fast and  due to this nature we can build large number of trees and choose 1000 cheapest plans. While being simple and fast this approach may fail to come up with reasonable optimized plan.  \textbf{Greedy \textit{Greedy  Operator Order(GOO)} GOO maintains a set of join trees, each of which initially consists of one base relation. The algorithm then combines the pair of join trees with the lowest cost to a single join tree.This approach is capable of building join orders fast enough. Advantage of this approach is due to the evaluation of intermediate results. [L. Fegaras. A new heuristic for optimizing large queries. In  DEXA, pages 726–735, 1998.] have shown the superiority of this approach compared with others