Cost-Based Optimization for Magic: Algebra and Implementation.

@inproceedings{DBLP:conf/sigmod/SeshadriHPLRSSS96,
  author    = {Praveen Seshadri and
               Joseph M. Hellerstein and
               Hamid Pirahesh and
               T. Y. Cliff Leung and
               Raghu Ramakrishnan and
               Divesh Srivastava and
               Peter J. Stuckey and
               S. Sudarshan},
  editor    = {H. V. Jagadish and
               Inderpal Singh Mumick},
  title     = {Cost-Based Optimization for Magic: Algebra and Implementation},
  booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
               Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
  publisher = {ACM Press},
  year      = {1996},
  pages     = {435-446},
  ee        = {http://doi.acm.org/10.1145/233269.233360, db/conf/sigmod/SeshadriHPLRSSS96.html},
  crossref  = {DBLP:conf/sigmod/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Magic set 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 set 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 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.

Copyright © 1996 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod9397 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[BGW+81]

Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981)

[BMSU86]

François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15

[BR91]

Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. J. Log. Program. 10(1/2/3&4): 255-299(1991)

[Blo70]

Burton H. Bloom: Space/Time Trade-offs in Hash Coding with Allowable Errors. Commun. ACM 13(7): 422-426(1970)

[CG85]

Stefano Ceri, Georg Gottlob: Translating SQL Into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries. IEEE Trans. Software Eng. 11(4): 324-345(1985)

[DGK82]

Umeshwar Dayal, Nathan Goodman, Randy H. Katz: An Extended Relational Algebra with Control over Duplicate Elimination. PODS 1982: 117-123

[EN94]

Ramez Elmasri, Shamkant B. Navathe: Fundamentals of Database Systems, 2nd Edition. Benjamin/Cummings 1994, ISBN 0-8053-1748-1
Contents

[GHK92]

Sumit Ganguly, Waqar Hasan, Ravi Krishnamurthy: Query Optimization for Parallel Execution. SIGMOD Conference 1992: 9-18

[GM93]

Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218

[HCL+90]

Laura M. Haas, Walter Chang, Guy M. Lohman, John McPherson, Paul F. Wilms, George Lapis, Bruce G. Lindsay, Hamid Pirahesh, Michael J. Carey, Eugene J. Shekita: Starburst Mid-Flight: As the Dust Clears. IEEE Trans. Knowl. Data Eng. 2(1): 143-160(1990)

[Hel95]

Joseph M. Hellerstein: Optimization and Execution Techniques for Queries With Expensive Methods. Ph.D. thesis, Univ. of Wisconsin-Madison 1995

[IK84]

Toshihide Ibaraki, Tiko Kameda: On the Optimal Nesting Order for Computing N-Relational Joins. ACM Trans. Database Syst. 9(3): 482-502(1984)

[INSS92]

Yannis E. Ioannidis, Raymond T. Ng, Kyuseok Shim, Timos K. Sellis: Parametric Query Optimization. VLDB 1992: 103-114

[KBZ86]

Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137

[Klu82]

Anthony C. Klug: Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions. J. ACM 29(3): 699-717(1982)

[LMH+85]

...

[LNSS93]

Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider, S. Seshadri: Efficient Sampling Strategies for Relational Database Operations. Theor. Comput. Sci. 116(1&2): 195-226(1993)

[MFPR90]

Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258

[MP94]

Inderpal Singh Mumick, Hamid Pirahesh: Implementation of Magic-sets in a Relational Database System. SIGMOD Conference 1994: 103-114

[RLK86]

J. Rohmer, R. Lescoeur, Jean-Marc Kerisit: The Alexander Method - A Technique for The Processing of Recursive Axioms in Deductive Databases. New Generation Comput. 4(3): 273-285(1986)

[RSSS94]

Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan, Praveen Seshadri: The CORAL Deductive System. VLDB J. 3(2): 161-210(1994)

[SAC+79]

Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34

[Sag90]

Yehoshua Sagiv: Is There Anything Better than Magic? NACLP 1990: 235-254

[SPL96]

Praveen Seshadri, Hamid Pirahesh, T. Y. Cliff Leung: Complex Query Decorrelation. ICDE 1996: 450-458

[SS88]

Seppo Sippu, Eljas Soisalon-Soininen: An Optimization Strategy for Recursive Queries in Logic Databases. ICDE 1988: 470-477

[SS94]

Peter J. Stuckey, S. Sudarshan: Compiling Query Constraints. PODS 1994: 56-67

[SSS95]

...

[TPCD94]

...

[Yao77]

S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977)