Inproceedings,
Specifying Rule-based Query Optimizers in a Reflective Framework
Third International Conference on Deductive and Object-Oriented Databases, page 146--168. Phoenix, Arizona, (December 1993)
Abstract
Numerous structures for database query optimizers have been proposed.
Many of those proposals aimed at automating the construction of query
optimizers from some kind of specification of optimizer behavior.
These specification frameworks do a good job of partitioning and
modularizing the kinds of information needed to generate a query
optimizer. Most of them represent at least part of this information
in a rule-like form. Nevertheless, large portions of these specifications
still take a procedural form. The contributions of this work are
threefold. We present a language for specifying optimizers that captures
a larger portion of the necessary information in a declarative manner.
This language is in turn based on a model of query rewriting where
query expressions carry annotations that are propagated during query
transformation and planning. This framework is reminiscent of inherited
and synthesized attributes for attribute grammars, and we believe
it is expressive of a wide range of information: logical and physical
properties, both desired and delivered, cost estimates, optimization
contexts, and control strategies. Finally, we present a mechanism
for processing optimizer specifications that is based on compile-time
reflection. This mechanism proves to be succinct and flexible, allowing
modifications of the specification syntax, incorporation of new capabilities
into generated optimizers, and retargeting the translation to a variety
of optimization frameworks. We report on an implementation of our
ideas using the CRML reflective functional language and on optimizer
specifications we have written for several query algebras
