TY - JOUR
T1 - Cost-Based Optimization for Magic
T2 - Algebra and Implementation
AU - Seshadri, Praveen
AU - Ramakrishnan, Raghu
AU - Hellerstein, Joseph M.
AU - Srivastava, Divesh
AU - Pirahesh, Hamid
AU - Stuckey, Peter J.
AU - Leung, T. Y.Cliff
AU - Sudarshan, S.
PY - 1996/1/1
Y1 - 1996/1/1
N2 - 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 C/S V2 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 θ-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.
AB - 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 C/S V2 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 θ-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.
UR - http://www.scopus.com/inward/record.url?scp=1842615028&partnerID=8YFLogxK
U2 - 10.1145/235968.233360
DO - 10.1145/235968.233360
M3 - Article
AN - SCOPUS:1842615028
SN - 0163-5808
VL - 25
SP - 435
EP - 446
JO - SIGMOD Record (ACM Special Interest Group on Management of Data)
JF - SIGMOD Record (ACM Special Interest Group on Management of Data)
IS - 2
ER -