Query optimization for object-relational database systems
Navin Kabra, David J. DeWitt · 1999
Modern database systems are placing an increasingly heavy burden upon their query optimizers. Commercial vendors are all scrambling to add object-relational features to their database systems, but unfortunately, optimizer technology has not kept pace with these advances for a number of reasons. Writing an optimizer, debugging it, and evaluating different optimization strategies remains a time-consuming and difficult task. Another problem is that attempts to design optimizers that can easily be extended to incorporate new operators, algorithms, or search strategies have enjoyed limited success. Finally, even the best of optimizers very often produce sub-optimal query evaluation plans. This problem is further aggravated by the presence of novel data domains and user-definable data-types and functions which make it very difficult to maintain statistics and estimate query execution costs. In this thesis, we present some solutions to the problems that are currently facing query optimizers. We describe OPT++ an architecture that significantly improves the extensibility and maintainability of a query optimizer. We use this as a tool to implement a number of relational and object-relational optimization techniques and search strategies and perform a study to compare their relative performance. We also describe Dynamic Re-Optimization, a technique that can be used to tackle suboptimality of plans produced by a query optimizer. OPT++ is an architecture for implementing extensible query optimizers. It uses an object-oriented design to simplify the task of implementing, extending, and modifying an optimizer. Building an optimizer using OPT++ makes it easy to extend the query algebra (to add new query algebra operators and physical implementation algorithms