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.
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Hel92.Joseph M. Hellerstein. Predicate Migration: Optimizing Queries With Expensive Predicates. Technical Report Sequoia 2000 92/13, University of California, Berkeley, December 1992. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- LH93.Guy M. Lohman and Laura M. Haas. Personal correspondence, November 1993.Google Scholar
- 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 ScholarDigital Library
- MS79.C.L. Monma and J.B. Sidney. Sequencing with Series-Parallel Precedence Constraints. Mathematics of Operations Research, 4:215- 224, 1979.Google ScholarDigital Library
- Nau93.Jeff Naughton. Presentation at Fifth International High Performance Transaction Workshop, September 1993.Google Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- SK91.Michael Stonebraker and Greg Kemnitz. The POSTGRES Next- Generation Database Management System. Communications of the ACM, 34(10), 1991. Google ScholarDigital Library
- Sto93.Michael Stonebraker. The Mir6 DBMS. In Proc. A CM-SIGMOD International Conference on Management of Data, Washington, D.C., May 1993. Google ScholarDigital Library
- TPC93.TPC. TPC BenchmarkTM D (Decision Support). Working Draft 6.0, Transaction Processing Performance Council, August 1993.Google Scholar
- Ull88.Jeffrey D. UlIman. Principles of Database and Knowledge-Base Systems, volume 1. Computer Science Press, 1988. Google ScholarDigital Library
- 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 ScholarDigital Library
Index Terms
Practical predicate placement
Recommendations
Predicate migration: optimizing queries with expensive predicates
SIGMOD '93: Proceedings of the 1993 ACM SIGMOD international conference on Management of dataThe traditional focus of relational query optimization schemes has been on the choice of join methods and join orders. Restrictions have typically been handled in query optimizers by “predicate pushdown” rules, which apply restrictions in some random ...
Practical predicate placement
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 ...
Predicate migration: optimizing queries with expensive predicates
The traditional focus of relational query optimization schemes has been on the choice of join methods and join orders. Restrictions have typically been handled in query optimizers by “predicate pushdown” rules, which apply restrictions in some random ...
Comments