summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/utthesis/ICDE-11/related.tex
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /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.tex59
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.