Configurable and Extensible Query Optimization by Controlled Term Rewriting.
Mazeyar E. Makoui · 2006
Abstract. Classic query optimization in relational database systems relies on phases (algebraic, physical, cost-based) and heuristic strategies for these phases (e. g. push selections). This, however, proves to be too inflexible not only for certain standard situations, but in particular for non-standard, e. g. spatial or multimedia applications which introduce expensive selection and join predicates, and which could profit from computing redundant data like indexes during query execution. Our goal is a uniform development environment for query optimizers of object-relational DBMSs. Therefore, we propose to base optimization on controlled term rewriting. This framework uses a general spectrum of operators covering relational algebra operators, their physical implementation alternatives, non-standard predicates, etc. The application of rewriting rules between corresponding terms should be controlled a) locally by rule-specific conditions which can consider syntactical as well as quantitative (size/cost-dependent) criteria, b) compositionally by regular sequencing patterns, and c) globally by strategies for optimum searches. We have developed an optimizer simulator which is thus extensible wrt operators and configurable wrt control mechanisms. 1