Abstract
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.
- BGW+81 P. A. Bemstein, N. Goodman, E. Wong, C. L. Reeve and J. B. Rothnie. Query processing in a system for distributed databases (SDD-1) ACMTransactions on Database Systems, 6(4):602-625, 1981. Google ScholarDigital Library
- BMSU86 F. Bancilhon, D. Maier, Y. Sagiv and J. D. Ullman. Magic sets and other strange ways to execute logic programs. In Proceedings of the ACM Symposium on Principles of Database Systems, 1-15,1986. Google ScholarDigital Library
- BR91 C. Beeri and R. Ramakrishnan. On the power of Magic. Journal of Logic Programming, 10(3&4):255-300, 1991. Google ScholarDigital Library
- Blo70 B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422-426, 1970. Google ScholarDigital Library
- CG85 S. Ceil and G. Gotflob. Translating SQL into relational algebra: Optimization, semantics, and equivalence of SQL queries. IEEE Transactions on Software Engineering, 11(4):324-345, 1985. Google ScholarDigital Library
- DGK82 U. Dayal, N. Goodman, and R. I-I. Katz. Art extended relational algebra with control over duplicate elimination. In Proceedings of the ACM Symposium on Principles of Database Systems, 1982. Google ScholarDigital Library
- EN94 R. Elmasri and S. B. Navathe. Fundamentals of database systems. Benjamin/Cummings Publishers, 2nd edition, 1994. Google ScholarDigital Library
- GHK92 S. Ganguly, W. Hasan and R. Krishnamurthy. Query optimization for parallel execution. In Proceedings of ACM SIGMOD International Conference on Management of Data, 1992. Google ScholarDigital Library
- GM93 G. Graefe and W. J. McKenna. The Volcano optimizer generator: Extensibility and efficient search. In Proceedings of the IEEE International Conference on Data Engineering, 1993. Google ScholarDigital Library
- HCL+90 L. Haas, W. Chang, G. M. Lehman, J. McPherson, P. F. Wilms, G. Lapis, B. Lindsay, H. Pirahesh, M. Carey, and E. Shekita. Starburst mid-flight: As the dust clears, IEEE Transactions on Knowledge and Data Engineering, March 1990. Google ScholarDigital Library
- Hel95 J.M. Hellerstein. Optimization and execution techniques for queries with expensive methods Ph.D. Thesis, University of Wisconsin, August 1995. Google ScholarDigital Library
- IK84 T. Ibaraki and T. Kameda. Optimal nesting for computing N-relational joins. In ACM Transactions on Database Systems, 9(3):482-502, 1984. Google ScholarDigital Library
- INSS92 Y. Ioannidis, R. Ni~, K. Shim and T. K. Sellis. Parametric query optimization. In Proceedings of the International Conference on Very Large Databases (VLDB), 103-114, 1992. Google ScholarDigital Library
- KBZ86 R. Krishnamurthy, H. Boral, and C. Zaniolo. Optimization of nonrecursivequeries. In Proceedings of the International Conference on Very Large Databases (VLDB), 128-137, 1986. Google ScholarDigital Library
- Klu82 A. Klug. Equivalence of relational algebra and relational calculus query languages having aggregate functions. Journal of the ACM, 29(3):699-717, 1982. Google ScholarDigital Library
- LMH+85 G. M. Lehman, C. Mohan, L. M. Haas, D. Daniels, B. G. Lindsay, P. G. Selinger and P. F. Wilms. Query processing in R*. In Query Processing in Database Systems, (W. Kim, D. S. Reiner, and D. S. Batory, eds.), Springer-Ve'rlag, 30-47, t985.Google Scholar
- LNSS93 R. J. Lipton, J. F. Naughton, D. /~. Schneider and S. Seshadri. Efficient sampling strategies for relational database operations. Theoretical Computer Science, 116:195-226, 1993. Google ScholarDigital Library
- MFPR90 I. S. Mumick, S. Finkelstein, H. Pirahesh, and R. Ramakrishnan. Magic is relevant. In Proceedings of ACM SIGMOD International Conference on Management of Data, 1990. Google ScholarDigital Library
- MP94 I. S. Mumick and H. Pirahesh. Implementation of magicsets in a relational database system. In Proceedings of ACM SIGMOD International Conference on Management of Data, 1994. Google ScholarDigital Library
- RLK86 J. Rohmer, R. Lescoeur, and J. M. Kerisit. The Alexander method: A technique for the l~rocess'.mg of recursive axioms in deductive databases. In New cieneraaon Computing, 4(3):273- 285, 1986. Google ScholarDigital Library
- RSSS94 R. Ramakrishnan, D. Srivastava, S. Sudarshan and P. Seshadri. The CORAL deductive system. The VLDB Journal, Special Issue on Prototypes of Deductive Database Systems, 1994. Google ScholarDigital Library
- SAC+79 P. G. Selinger, M. Astrahan, D. Chamberlin, R. Lorie, and T. Price. Access path selection in a relational database management system. In Proceedings of ACM SIGMOD international Conference on Management of Data, 23-34, 1979. Google ScholarDigital Library
- Sag90 Y. Sagiv. Is there anything better than magic? In Proceedings of the North American Conference on Logic Programming, 235-254, 1990. Google ScholarDigital Library
- SPL96 P. Seshadri, H. Pirahesh, and T. Y. C. Leung. Decorrelating complex queries. In Proceedings of the Twelfth International Conference on Data Engineering, 1996.Google ScholarCross Ref
- SS88 S. Sippu and E. Soisalon-Soinen. An optimization strategy for recurswe queries in logic databases. In Proceedings of the Fourth International Conference on Data Engineering, 1988. Google ScholarDigital Library
- SS94 P. J. Stuckey and S. Sudarshan. Compiling query constraints. In Procaadin g s of the A CM Symposium on Principles of Database Systems, 1994. Google ScholarDigital Library
- SSS95 D. Sfivastava, P. J. Stuckey and S. Sudarshan. The magic of theta-semijoins. AT&T Bell Laboratories Technical Report, 1995.Google Scholar
- TPCD94 TPC benchmark group. TPC-D Draft, December 1994. Information Paradigm. Suite 7, 115 North Wahsatch Avenue, Colorado Springs, CO 80903.Google Scholar
- Yao77 S. B. Yao. Approximating the number of accesses in database organizanons. Communications of the ACM, 20(4):260-261, 1977. Google ScholarDigital Library
Index Terms
- Cost-based optimization for magic: algebra and implementation
Recommendations
Cost-based optimization for magic: algebra and implementation
SIGMOD '96: Proceedings of the 1996 ACM SIGMOD international conference on Management of dataMagic 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 ...
Magic Sets in Interpolation-Based Rule Driven Query Optimization
Rules and ReasoningAbstractQuery reformulation under constraints is an essential part of modern query optimizers. This paper introduces an enhancement to an interpolation-based rule-driven query optimizer that extends the space of valid rewritings for a user query in order ...
Comments