Review - Query Optimization by Predicate Move-Around.

Review

Query optimization (the problem of efficiently identifying a good, though not necessarily the best, evaluation plan for a given query) is a fundamental problem in databases, especially given the complexity of decision support queries, and the vast (orders of magnitude) difference between the performances of good and the not-so-good evaluation plans.

A very large number of query optimization techniques have been proposed in the literature, but much remains to be accomplished in understanding:

• the benefits of combining different query optimization techniques, and
• how these techniques can be easily incorporated into commercial optimizers.

It is rare to find a principled query optimization technique that complements existing optimization techniques, is easy to integrate into an optimizer, and does not dramatically increase the search space (and hence the query optimization time). This paper describes such a technique.

The interesting observation made by Levy et al. in this paper is that the benefits of predicate push-down in SQL query optimization can be considerably enhanced if the push-down phase is preceded by a pull-up phase. In this way, in particular, predicates pulled up from one query block (such as a subquery or view) in a multi-block SQL query can be pushed down into a different query block (hence the name predicate move-around). The key insights developed in this paper are that:

1. predicates can be easily moved around even when query block merging is either complicated or impossible (such as with some views involving the aggregates min and max), while preserving SQL's multiset semantics,
2. predicate move-around complements and can be performed before traditional join order optimization, and
3. the algorithm for predicate move-around is applicable to a variety of predicates, such as arithmetic and string comparisons, and the EXISTS and NOT EXISTS predicates.

The simplicity and utility of the ideas developed in this paper makes it worthwhile reading for anyone interested in the subject of query optimization in databases.

[Full Disclosure: The authors of this paper are former colleagues and/or former co-authors. However, this has not affected my views on the paper.]

Copyright © 2000 by the author(s). Review published with permission.

References

[1]

Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv: Query Optimization by Predicate Move-Around. VLDB 1994: 96-107 BibTeX