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/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.tex | 82 |
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. |