\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.
