Query Optimization in the CROQUE Project (extended version)

This paper describes some concepts for the evaluation and optimization of ODMG-OQL queries.We present a logical object algebra for the internal representation of OQL queries. Algebraic expressions are also represented more naturally as query trees. Different optimization techniques are sketched: factorization of common subexpressions, dependency-based optimization, and query rewriting. Afterwards, our physical algebra is briefly presented and a complex example of the optimization process is given. We describe our implementation and the present investigations using search strategies to find the best execution plan. In contrast to previous studies on the evaluation of object-oriented queries, we use a logical and a physical algebra in the process of evaluation and optimization of OQL queries, thus achieving logical data independence. Other basic ideas of our work are the integration of different optimization techniques into one approach and the use of cost functions especially valid for the object-oriented database system ObjectStore