this is for holding javascript data
Nuwan Wajirasena(110607D) edited section_Query_Optimization_and_Execution__.tex
about 8 years ago
Commit id: 6a3fb73366d3fc23a539080c04a79f59d0a0a858
deletions | additions
diff --git a/section_Query_Optimization_and_Execution__.tex b/section_Query_Optimization_and_Execution__.tex
index efc4f72..e3e81c7 100644
--- a/section_Query_Optimization_and_Execution__.tex
+++ b/section_Query_Optimization_and_Execution__.tex
...
\section{Query Optimization and Execution Plans}
Query optimization is one of the most important role in relational databases. Almost all the relational database systems such as MySQL, Postgres, Oracle DB, Apache Derby consist of query optimizers.
\subsection{Join Query Execution Plans}
...
JOIN D ON A.ID = D.ID
\end{verbatim}
Two possible execution plans are
deep-left left-deep tree (shown in
Figure-1 ) Figure-1) and Bushy Tree (shown in Figure-2). Other possible structures include right-deep trees zig-zag trees. Similar to
deep-left trees left-deep trees, right-deep and zig-zag are linear tree structure. But bushy trees are different and more complicated
structures compared to others.
\subsection{Challenegs in Bushy Tree Implementation}
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 On the other hand left-deep trees have only one structure regardless of the number of tables involved. Therefor the number of possible permutations are
N! . N!. But for bushy trees possible number of structures is given
by
\\ by,\\
$$ $S(N) = \displaystyle \sum_{N=1}^{i} (N)(N-i)$ \ $ for N > 1$ $$\\
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 (~7). Therefore it is required to come
up with a heuristic to select set of permutations for cost computations.
\subsection{Heuristics to Select Bushy Trees}
\textit{QUIKPICK-1000}
Here we build pseudo-random joining
trees . 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.
\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 tree. This approach is capable of building join orders fast enough. Advantage of this approach is due to the evaluation of intermediate results.
\cite{GOO} L. Fegaras\cite{GOO} have shown the superiority of this approach compared with others.