this is for holding javascript data
Bhathiya added section_Challenegs_in_Bushy_Trees__.tex
about 8 years ago
Commit id: 475a86298455d2a663798b10f6c989a3f7d0a75b
deletions | additions
diff --git a/section_Challenegs_in_Bushy_Trees__.tex b/section_Challenegs_in_Bushy_Trees__.tex
new file mode 100644
index 0000000..84477b5
--- /dev/null
+++ b/section_Challenegs_in_Bushy_Trees__.tex
...
\section{Challenegs in Bushy Trees}
Moving from left-deep tree to a Bushy tree is a challenge as the number of possible structures in bushy trees are much larger. Left-deep trees have only one structure regardless of the number of attributes involved. Therefor the number of possible permutations are N! . But for bushy trees possible number of structures are given by
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}
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 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
