diff options
author | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
commit | e0c6872cf40896c7be36b11dcc744620f10adf1d (patch) | |
tree | 60335e10d2f4354b0674ec22d7b53f0f8abee672 /macros/latex/contrib/utthesis/ICDE-11/related.tex |
Initial commit
Diffstat (limited to 'macros/latex/contrib/utthesis/ICDE-11/related.tex')
-rw-r--r-- | macros/latex/contrib/utthesis/ICDE-11/related.tex | 59 |
1 files changed, 59 insertions, 0 deletions
diff --git a/macros/latex/contrib/utthesis/ICDE-11/related.tex b/macros/latex/contrib/utthesis/ICDE-11/related.tex new file mode 100644 index 0000000000..76f83db64e --- /dev/null +++ b/macros/latex/contrib/utthesis/ICDE-11/related.tex @@ -0,0 +1,59 @@ +\section{Related research} +\label{sec:related} + +The System R optimizer \cite{Seli79} was the most important development +in query optimization research. It was a cost-based centralized +relational query optimizer and introduced a variety of key concepts +like ``interesting'' expressions, cardinality estimation using +selectivity factors and dynamic programming with pruning of search +space. These concepts continue to be important in query optimizer +research. + +The query optimizer in R$^*$ \cite{Dani82} works in essentially +the same way as that of System R, except that R$^*$ is a distributed +database system which introduces some subtle complications in its query +optimizer. + +The Starburst query optimizer \cite{Haas88} uses rules for all +decisions that need to be taken by the query optimizer. The rules are +functional in nature and transform a given operator tree into another. +The rules are commonly those that reflect relational calculus facts. +In Starburst, the query rewriting phase is different from the +optimization phase. The rewriting phase transforms the query itself +into equivalent operator trees based on relational calculus rules. The +plan optimization phase selects algorithms for each operator in the +operator tree that is obtained after rewriting. The disadvantage of +separating the query rewrite and the optimization phases is that +pruning of the search space is not possible during query rewrite, since +the rewrite phase is non-cost-based. + +Freytag \cite{Frey87a} describes a rule-based query optimizer similar +to Starburst. The rules are based on LISP-like representations of +access plans. The rules themselves are recursively defined on smaller +expressions (operator trees). Although several expressions can contain +a common sub-expression, Freytag doesn't consider the possibility of +sharing. Expressions are evaluated each time they are encountered. +This is obviously inefficient. In addition, as in Starburst, he +doesn't consider the cost transformations inherent in any query +optimizer; rules are syntactic transformation rules. + +EXODUS \cite{Grae87b} provides an optimizer generator which accepts a +rule-based specification of the data model as input. The optimizer +generator compiles these rules, together with pre-defined rules, to +generate an optimizer for the particular data model and set of +operators. Unlike Freytag, the optimizer generator for EXODUS allows +for C code along with definitions of new rules. This allows the +database implementor the freedom to associate any action with a +particular rule. Operator trees in EXODUS are constructed bottom-up +from previously constructed trees. + +The Volcano optimizer generator project \cite{Grae90b} evolved from the +EXODUS project. It is different from all the above optimizers in one +significant way: it is a top-down optimizer compared with the bottom-up +strategy of the others. Operator trees are optimized starting from the +root while sub-trees are not yet optimized. This leads to a +constraint-driven generation of the search space. While this method +results in a tight control of the search space, it is unconventional +and requires careful attention on the part of the optimizer implementor +to ensure that legal operator trees are not accidently left out of +the search space. We have used Volcano as our back-end search engine. |