language: en

Building Query Optimizers with Combinators:

[Dissertation Proposal]

Mitch Cherniack

Abstract Query optimizers generate plans to retrieve data specified by queries. Query optimization for object databases (i.e., object-oriented and object-relational databases) is an immature field, and stands to benefit from adaptation of techniques that have proved useful for relations. One technique uses query-to-query transformations to rewrite queries into queries that are potentially more amenable to plan generation. For transformations to be useful, they must preserve the semantics of the queries they rewrite (correctness) and usually result in queries that generate better plans (effectiveness). Object databases complicate the expression of correct and effective transformations. Transformation correctness is problematic even for relational queries. Especially error-prone are transformations that rewrite complex nested queries (queries containing other queries) or queries that return duplicates. Objects make correctness more difficult because object queries can be far more complex than relational queries. The effectiveness of a relational transformation typically depends on the syntax of a query rather than the semantics of of its data or functions. On the other hand, the lack of uniformity in data functions and collections in an object query makes effectiveness more subtle. The effectiveness of a transformation for object queries may depend on the semantics of data functions, and may vary from object to object in a collection. Therefore, optimizers may have to perform sophisticated reasoning and apply transformations on a per object basis to ensure that they are used only when appropriate. This thesis considers the correctness and effectiveness of optimizer transformations. To address correctness, we propose a formally specified query algebra and two-tiered language (COKO-KOLA) for expressing transformations that can be verified with a theorem prover. To address effectiveness, we propose semantic and dynamic extensions to the traditional optimizer architecture. The high-level contribution of the thesis is the observation that the choice of query representation impacts the quality of the optimizer. Specifically, a combinator-based (variable-free) query representation simplifies the query manipulations that are required to make transformations correct and effective.

1 Introduction