summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/utthesis/ICDE-11/intro.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/intro.tex
Initial commit
Diffstat (limited to 'macros/latex/contrib/utthesis/ICDE-11/intro.tex')
-rw-r--r--macros/latex/contrib/utthesis/ICDE-11/intro.tex82
1 files changed, 82 insertions, 0 deletions
diff --git a/macros/latex/contrib/utthesis/ICDE-11/intro.tex b/macros/latex/contrib/utthesis/ICDE-11/intro.tex
new file mode 100644
index 0000000000..b4ebebe580
--- /dev/null
+++ b/macros/latex/contrib/utthesis/ICDE-11/intro.tex
@@ -0,0 +1,82 @@
+\section{Introduction}
+\label{sec:intro}
+
+Query optimization \cite{Grae93} is a fundamental part of database
+systems. It is the process of generating an efficient access plan for
+a database query. Informally, an access plan is an execution strategy
+for a query; it is the sequence of low-level database retrieval
+operations that, when executed, produce the database records that
+satisfy the query. There are three basic aspects that define and
+influence query optimization: the search space, the cost model, and the
+search strategy.
+
+The {\em search space} is the set of logically equivalent access plans
+that can be used to evaluate a query. All plans in a query's search
+space return the same result; however, some plans are more efficient
+than others. The {\em cost model} assigns a cost to each plan in the
+search space. The cost of a plan is an estimate of the resources used
+when the plan is executed; the lower the cost, the better the plan.
+The {\em search strategy} is a specification of which plans in the
+search space are to be examined.
+
+Traditionally, query optimizers have been built as monolithic
+subsystems of a DBMS. This simply reflects the fact that traditional
+database systems are themselves monolithic: the algorithms used for
+storing and retrieving data are hard-wired and are rather difficult to
+change. The need to have extensible database systems, and in turn
+extensible optimizers, has long been recognized in systems like Genesis
+\cite{Bato88a}, EXODUS \cite{Grae87b}, Starburst \cite{Haas88}, and
+Postgres \cite{Ston86b}. Rule-based query optimizers are among the
+major conceptual advances that have been proposed to deal with query
+optimizer extensibility \cite{Haas88,Frey87a,Grae87b,Grae90b}. The
+extensibility translates into the ability to incorporate new operators,
+algorithms, cost models, or search strategies without changing the
+optimization algorithm.
+
+In this paper, we describe an algebraic framework called \emph{Prairie}
+for specifying rules in a rule-based query optimizer. Prairie is
+similar to other rule specification languages like Starburst
+\cite{Haas88} and Volcano \cite{Grae90b}, and indeed, we have based our
+work on Volcano to capture most of the advantages of rule-based
+optimizers. However, Prairie attempts to provide some key features
+that, we have found, simplify the effort in writing rules:
+
+\begin{enumerate}
+ \item A framework in which users can define a query optimizer
+ concisely in terms of a well-defined set of operators and
+ algorithms. \emph{All} operators and algorithms are considered
+ first-class objects, \ie \emph{any} of them can occur in any
+ rule, and \emph{only} these operators and algorithms can appear
+ in rules. This scheme eliminates the need for special classes
+ of operators and algorithms, such as enforcers in Volcano and
+ glue in Starburst, that significantly complicate rule
+ specification.
+ \item A framework in which users can define a list of properties to
+ characterize the expressions generated in the optimization
+ process. Again, the goal here is to allow the user to treat
+ \emph{all} properties as having equal status. This is different
+ from Volcano where the user must classify properties as logical,
+ physical, or operator/algorithm arguments.
+ \item A framework in which users can specify mapping functions
+ between properties concomitantly with the corresponding rules.
+ This contrasts with existing approaches in which mappings
+ between properties are fragmented into multiple functions and at
+ logically different places than the corresponding rules.
+ Research into rule-based optimizers has revealed that
+ property-mapping functions are a major source of user effort, so
+ this is an important goal.
+ \item The format (Prairie) in which users can cleanly specify rules is
+ not necessarily the same format needed for generating efficient
+ optimizers. Thus, there is a need for a pre-processor (written
+ by us) that translates between these competing representations.
+\end{enumerate}
+
+Prairie strives for uniformity in dealing with issues that have been a
+source of most user effort and potential user errors. In the following
+sections, we present the Prairie framework. We explain how our P2V
+pre-processor maps Prairie rule specifications into Volcano rule
+specifications that can be processed efficiently. Experimental results
+to support this claim are given in Section~\ref{sec:results}, where we
+compare implementations of the Texas Instruments Open OODB query
+optimizer using both Prairie and Volcano. We conclude with a summary
+and related research.