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