Cost-based optimization for magic: Algebra and implementation.
Praveen Seshadri, Joseph M. Hellerstein, Hamid Pirahesh, T. Y. Cliff Leung,
Raghu Ramakrishnan, Divesh Srivastava, Peter J. Stuckey and S. Sudarshan.
Magic sets rewriting is a well-known optimization heuristic for
complex decision-support queries. There can be many variants of
this rewriting even for a single query, which differ greatly in
execution performance. We propose cost-based techniques for
selecting an efficient variant from the many choices.
Our first contribution is a practical scheme that models magic
sets rewriting as a special join method that can be added to any
cost-based query optimizer. We derive cost formulas that allow
an optimizer to choose the best variant of the rewriting and to
decide whether it is beneficial. The order of complexity of the
optimization process is preserved by limiting the search space
in a reasonable manner. We have implemented this technique in
IBM's DB2 database system. Our performance measurements
demonstrate that the cost-based magic optimization technique
performs well, and that without it, several poor decisions could
be made.
Our second contribution is a formal algebraic model of magic
sets rewriting, based on an extension of the multiset relational
algebra, which cleanly defines the search space and can be
used in a rule-based optimizer. We introduce the multiset
theta-semijoin operator, and derive equivalence rules involving
this operator. We demonstrate that magic sets rewriting for
non-recursive SQL queries can be modeled as a sequential
composition of these equivalence rules.