A rule-based query optimizer with multiple search strategies

摘要

This paper describes a rule-based query optimizer. The originality of the approach is through a uniform high-level rule language used to model both query rewriting and planning, as well as search strategies. Rules are given to specify operation permutation, recursive query optimization, integrity constraint addition, to model join ordering and access path selection. Therefore, meta-rules are presented to model multiple search strategies, including enumerative and randomized search. To illustrate these ideas, we describe a query optimizer for an extensible database server that supports abstract data types, complex objects, deductive capabilities and integrity constraints. A prototype of the query optimizer proposed in this paper is operational and has been demonstrated at the 1991 ESPRIT week in the EDS project.