<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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.
</pre></body></html>