skip to main content
10.1145/191839.191904acmconferencesArticle/Chapter ViewAbstractPublication PagesmodConference Proceedingsconference-collections
Article
Free Access

Practical predicate placement

Authors Info & Claims
Published:24 May 1994Publication History

ABSTRACT

Recent work in query optimization has addressed the issue of placing expensive predicates in a query plan. In this paper we explore the predicate placement options considered in the Montage DBMS, presenting a family of algorithms that form successively more complex and effective optimization solutions. Through analysis and performance measurements of Montage SQL queries, we classify queries and highlight the simplest solution that will optimize each class correctly. We demonstrate limitations of previously published algorithms, and discuss the challenges and feasibility of implementing the various algorithms in a commercial-grade system.

References

  1. BMSU86.Francois Bancilhon, David Maier, Yehoshua Sagiv, and Jeffrey D. Ullman. Magic Sets and other Strange Ways to Implement Logic Programs. In Proc. 5th A CM SIGA CT- SIGMOD-SIGART Symposium on Principtes of Database Systems, pages 1-15, Cambridge, March 1986. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. CGK89.Danette Chimenti, Ruben Gamboa, and Ravi Krishnamurthy. Towards an Open Architecture for LDL. In Proc. 15th International Conference on Very Large Data Bases, Amsterdam, August 1989. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. CS93.Surajit Chaudhuri and Kyuseok Shim. Query Optimization in the Presence of Foreign Functions. In Proc. 19th International Conference on Very Large Data Bases, pages 526-541, Dublin, August 1993. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. CYY+92.Hanxiong Chen, Xu Yu, Kazunori Yamaguchi, Hiroyuki Kitagawa, Nobuo Ohbo, and Yuzuru Fujiwara. Decomposition- An Approach for Optimizing Queries Including ADT Functions. Information Processing Letters, 43(6):327-333, 1992. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. DKS92.Weimin Du, Ravi Krishnamurthy, and Ming-Chien Shah. Query Optimization in Heterogeneous DBMS. In Proc. 18th International Conference on Very Large Data Bases, Vancouver, August 1992. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Hel92.Joseph M. Hellerstein. Predicate Migration: Optimizing Queries With Expensive Predicates. Technical Report Sequoia 2000 92/13, University of California, Berkeley, December 1992. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. HS93a.Joseph M. Hellerstein and Michael Stonebraker. Predicate Migration: Optimizing Queries With Expensive Predicates. In Proc. A CM-SIGMOD International Conference on Management of Data, Washington, D.C., May 1993. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. HS93b.Wei Hong and Michael Stonebraker. Optimization of Parallel Query Execution Plans in XPRS. Distributed and Parallel Databases, An international Journal, 1(1):9-32, January 1993. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. IK84.Toshihide Ibaraki and Tiko Kameda. Optimal Nesting for Computing N-relational Joins. A CM Transactions on Database Systems, 9(3):482-502, October 1984. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. Jhi88.Anant Jhingran. A Performance Study of Query Optimization Algorithms on a Database System Supporting Procedures. In Proc. l#th International Conference on Very Large Data Bases, Los Angeles, August- September 1988. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. KBZ86.Ravi Krishnamurthy, Haran Boral, and Carlo Zaniolo. Optimization of Nonrecursive Queries. In Proc. 12th International Conference on Very Large Data Bases, pages 128- 137, Kyoto, August 1986. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. KZ88.Ravi Krishnamurthy and Carlo ZanioIo. Optimization in a Logic Based Language for Knowledge and Data Intensive Applications. In Joachim W. Schmidt, Stefano Ceri, and M. Missikoff, editors, Proc. International Conference on Extending Data Base Technology, Advances in Database Technology - EDBT '88. Lecture Notes in Computer Science, Volume 303, Venice, March 1988. Springer-Verlag. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. LH93.Guy M. Lohman and Laura M. Haas. Personal correspondence, November 1993.Google ScholarGoogle Scholar
  14. MFPR90.inderpal Singh Mumick, Sheldon j. Finkelstein, Hamid Pirahesh, and Raghu Ramakrishnan. Magic is Relevant. In Proc. ACM- SIGMOD International Conference on Management of Data, pages 247-258, Atlantic City, May 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. MS79.C.L. Monma and J.B. Sidney. Sequencing with Series-Parallel Precedence Constraints. Mathematics of Operations Research, 4:215- 224, 1979.Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. Nau93.Jeff Naughton. Presentation at Fifth International High Performance Transaction Workshop, September 1993.Google ScholarGoogle Scholar
  17. PHH92.Hamid Pirahesh, Joseph M. Hellerstein, and Waqar Hasan. Extensible/Rule-Based Query Rewrite Optimization in Starburst. In Proc. A CM-SIGMOD International Conference on Management of Data, pages 39- 48, San Diego, June 1992. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. SAC+79.Patricia G. Selinger, M. Astrahan, D. Chainberlin, Raymond Lorie, and T. Price. Access Path Selection in a Relational Database Management System. In Proc. A CM- SIGMOD International Conference on Management of Data, Boston, June 1979. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. Sha86.Leonard D. Shapiro. Join Processing in Database Systems with Large Main Memories. A CM Transactions on Database Systems, 11(3):239-264, September 1986. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. SK91.Michael Stonebraker and Greg Kemnitz. The POSTGRES Next- Generation Database Management System. Communications of the ACM, 34(10), 1991. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. Sto93.Michael Stonebraker. The Mir6 DBMS. In Proc. A CM-SIGMOD International Conference on Management of Data, Washington, D.C., May 1993. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. TPC93.TPC. TPC BenchmarkTM D (Decision Support). Working Draft 6.0, Transaction Processing Performance Council, August 1993.Google ScholarGoogle Scholar
  23. Ull88.Jeffrey D. UlIman. Principles of Database and Knowledge-Base Systems, volume 1. Computer Science Press, 1988. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. YKY+91.Kenichi Yajima, Hiroyuki Kitagawa, Kazunori Yamaguchi, Nobuo Ohbo, and Yuzura Fujiwara. Optimization of Queries Including ADT Functions. In Proc. 2nd International Symposium on Database Systems for Advanced Applications, pages 366- 373, Tokyo, April 1991. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Practical predicate placement

                  Recommendations

                  Comments

                  Login options

                  Check if you have access through your login credentials or your institution to get full access on this article.

                  Sign in
                  • Published in

                    cover image ACM Conferences
                    SIGMOD '94: Proceedings of the 1994 ACM SIGMOD international conference on Management of data
                    May 1994
                    525 pages
                    ISBN:0897916395
                    DOI:10.1145/191839

                    Copyright © 1994 ACM

                    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

                    Publisher

                    Association for Computing Machinery

                    New York, NY, United States

                    Publication History

                    • Published: 24 May 1994

                    Permissions

                    Request permissions about this article.

                    Request Permissions

                    Check for updates

                    Qualifiers

                    • Article

                    Acceptance Rates

                    Overall Acceptance Rate785of4,003submissions,20%

                  PDF Format

                  View or Download as a PDF file.

                  PDF

                  eReader

                  View online with eReader.

                  eReader