Tech Report CS-94-05

Compiling Object-Oriented Queries

Theodore W. Leung

February 1994


The effectiveness of database query optimization is dependent on the optimizer's ability to make efficient use of physical resources in a computer system. The optimizer decides how to use those resources in the plan generation step. We describe an approach to plan generation where physical level rewriting produces performance increases which cannot be obtained via source level transformations. Example optimizations serve as a demonstration of a new rule language based on list and tree pattern matching. A formalism similar to attribute grammars computes information needed by the plan generator. Many of the techniques presented are reminiscent of compiler optimizations. We conclude by describing the work that will be completed in the thesis.

(complete text in pdf or gzipped postscript)