ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Predicate Migration: Optimizing Queries with Expensive Predicates.

Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276
@inproceedings{DBLP:conf/sigmod/HellersteinS93,
  author    = {Joseph M. Hellerstein and
               Michael Stonebraker},
  editor    = {Peter Buneman and
               Sushil Jajodia},
  title     = {Predicate Migration: Optimizing Queries with Expensive Predicates},
  booktitle = {Proceedings of the 1993 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 26-28, 1993},
  publisher = {ACM Press},
  year      = {1993},
  pages     = {267-276},
  ee        = {http://doi.acm.org/10.1145/170035.170078, db/conf/sigmod/HellersteinS93.html},
  crossref  = {DBLP:conf/sigmod/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

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 order before as many joins as possible. These rules work under the assumption that restriction is essentially a zero-time operation. However, today's extensible and object-oriented database systems allow users to define time-consuming functions, which may be used in a query's restriction and join predicates. Furthermore, SQL has long supported subquery predicates, which may be arbitrarily time-consuming to check. Thus restrictions should not be considered zero-time operations, and the model of query optimization must be enhanced.

In this paper we develop a theory for moving expensive predicates in a query plan so that the total cost of the plan - including the costs of both joins and restrictions - is minimal. We present an algorithm to implement the theory, as well as results of our implementation in POSTGRES. Our experience with the newly enhanced POSTGRES query optimizer demonstrates that correctly optimizing queries with expensive predicates often produces plans that are orders of magnitude faster than plans generated by a traditional query optimizer. The additional complexity of considering expensive predicates during optimization is found to be manageably small.

Copyright © 1993 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

Online Version (ACM WWW Account required): Full Text in PDF Format

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

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Peter Buneman, Sushil Jajodia (Eds.): Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993. ACM Press 1993 BibTeX , SIGMOD Record 22(2), June 1993
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1222 KB]

References

[CGK89]
Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy: Towards on Open Architecture for LDL. VLDB 1989: 195-203 BibTeX
[D+90]
O. Deux: The Story of O2. IEEE Trans. Knowl. Data Eng. 2(1): 91-108(1990) BibTeX
[Day87]
Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 BibTeX
[Han77]
Michael Z. Hanani: An Optimal Evaluation of Boolean Expressions in an Online Query System. Commun. ACM 20(5): 344-347(1977) BibTeX
[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) BibTeX
[Hel92]
...
[HOT88]
Wen-Chi Hou, Gultekin Özsoyoglu, Baldeo K. Taneja: Statistical Estimators for Relational Algebra Expressions. PODS 1988: 276-287 BibTeX
[IK84]
Toshihide Ibaraki, Tiko Kameda: On the Optimal Nesting Order for Computing N-Relational Joins. ACM Trans. Database Syst. 9(3): 482-502(1984) BibTeX
[ISO91]
...
[Jhi88]
Anant Jhingran: A Performance Study of Query Optimization Algorithms on a Database System Supporting Procedures. VLDB 1988: 88-99 BibTeX
[KBZ86]
Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137 BibTeX
[LDH+87]
Guy M. Lohman, Dean Daniels, Laura M. Haas, Ruth Kistler, Patricia G. Selinger: Optimization of Nested Queries in a Distributed Relational Database. VLDB 1984: 403-415 BibTeX
[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) BibTeX
[LS88]
Clifford A. Lynch, Michael Stonebraker: Extended User-Defined Indexing with Application to Textual Databases. VLDB 1988: 306-317 BibTeX
[Mos90]
...
[MS79]
...
[MS86]
David Maier, Jacob Stein: Indexing in an Object-Oriented DBMS. OODBS 1986: 171-182 BibTeX
[MS87]
...
[Ols92]
...
[O'N89]
...
[ONT92]
...
[PHH92]
Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48 BibTeX
[Pro87]
Peter M. Stocker, William Kent, Peter Hammersley (Eds.): VLDB'87, Proceedings of 13th International Conference on Very Large Data Bases, September 1-4, 1987, Brighton, England. Morgan Kaufmann 1987, ISBN 0-934613-46-X
Contents BibTeX
[Pro88]
...
[RS87]
Lawrence A. Rowe, Michael Stonebraker: The POSTGRES Data Model. VLDB 1987: 83-96 BibTeX
[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 BibTeX
[SD92]
...
[SFGM93]
Michael Stonebraker, James Frew, Kenn Gardels, Jeff Meredith: The Sequoia 2000 Benchmark. SIGMOD Conference 1993: 2-11 BibTeX
[SI92]
...
[Smi56]
...
[SR86]
Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355 BibTeX
[Sto91]
Michael Stonebraker: Managing Persistent Objects in a Multi-Level Store. SIGMOD Conference 1991: 2-11 BibTeX
[TOB89]
...
[Ull89]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[WLH90]
W. Kevin Wilkinson, Peter Lyngbæk, Waqar Hasan: The Iris Architecture and Implementation. IEEE Trans. Knowl. Data Eng. 2(1): 63-75(1990) BibTeX

Referenced by

  1. Eric Simon: Review - Predicate Migration: Optimizing Queries with Expensive Predicates. ACM SIGMOD Digital Review 2: (2000)
  2. Manuel Rodriguez-Martinez, Nick Roussopoulos: MOCHA: A Self-Extensible Database Middleware System for Distributed Data Sources. SIGMOD Conference 2000: 213-224
  3. Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-Defined Predicates. ACM Trans. Database Syst. 24(2): 177-228(1999)
  4. Jihad Boulos, Kinji Ono: Cost Estimation of User-Defined Methods in Object-Relational Database Systems. SIGMOD Record 28(3): 22-28(1999)
  5. Mary Tork Roth, Fatma Ozcan, Laura M. Haas: Cost Models DO Matter: Providing Cost Information for Diverse Data Sources in a Federated System. VLDB 1999: 599-610
  6. Michael Jaedicke, Bernhard Mitschang: User-Defined Table Operators: Enhancing Extensibility for ORDBMS. VLDB 1999: 494-505
  7. Weidong Chen, Jyh-Herng Chow, You-Chin Fuh, Jean Grandbois, Michelle Jou, Nelson Mendonça Mattos, Brian T. Tran, Yun Wang: High Level Indexing of User-Defined Types. VLDB 1999: 554-564
  8. Tobias Mayr, Praveen Seshadri: Client-Site Query Extensions. SIGMOD Conference 1999: 347-358
  9. Daniela Florescu, Alon Y. Levy, Ioana Manolescu, Dan Suciu: Query Optimization in the Presence of Limited Access Patterns. SIGMOD Conference 1999: 311-322
  10. Joseph M. Hellerstein: Optimization Techniques for Queries with Expensive Methods. ACM Trans. Database Syst. 23(2): 113-157(1998)
  11. Nick Roussopoulos: Materialized Views and Data Warehouses. SIGMOD Record 27(1): 21-26(1998)
  12. Narayanan Shivakumar, Hector Garcia-Molina, Chandra Chekuri: Filtering with Approximate Predicates. VLDB 1998: 263-274
  13. M. Seetha Lakshmi, Shaoyu Zhou: Selectivity Estimation in Extensible Databases - A Neural Network Approach. VLDB 1998: 623-627
  14. Felipe Cariño, William O'Connell: Plan-Per-Tuple Optimization Solution - Parallel Execution of Expensive User-Defined Functions. VLDB 1998: 690-695
  15. Michael Jaedicke, Bernhard Mitschang: On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS. SIGMOD Conference 1998: 379-389
  16. Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43
  17. Wolfgang Scheufele, Guido Moerkotte: Efficient Dynamic Programming Algorithms for Ordering Expensive Joins and Selections. EDBT 1998: 201-215
  18. Stefan Deßloch, Nelson Mendonça Mattos: Integrating SQL Databases with Content-Specific Search Engines. VLDB 1997: 528-537
  19. Laura M. Haas, Donald Kossmann, Edward L. Wimmers, Jun Yang: An Optimizer for Heterogeneous Systems with NonStandard Data and Search Capabilities. IEEE Data Eng. Bull. 19(4): 37-44(1996)
  20. Surajit Chaudhuri, Luis Gravano: Optimizing Queries over Multimedia Repositories. IEEE Data Eng. Bull. 19(4): 45-52(1996)
  21. William J. McKenna, Louis Burger, Chi Hoang, Melissa Truong: EROC: A Toolkit for Building NEATO Query Optimizers. VLDB 1996: 111-121
  22. Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-defined Predicates. VLDB 1996: 87-98
  23. Michael H. Böhlen, Richard T. Snodgrass, Michael D. Soo: Coalescing in Temporal Databases. VLDB 1996: 180-191
  24. Bennet Vance, David Maier: Rapid Bushy Join-order Optimization with Cartesian Products. SIGMOD Conference 1996: 35-46
  25. Joseph M. Hellerstein, Jeffrey F. Naughton: Query Execution Techniques for Caching Expensive Methods. SIGMOD Conference 1996: 423-434
  26. Surajit Chaudhuri, Luis Gravano: Optimizing Queries over Multimedia Repositories. SIGMOD Conference 1996: 91-102
  27. Chengwen Liu, Hao Chen, Warren Krueger: A Distributed Query Processing Strategy Using Placement Dependency. ICDE 1996: 477-484
  28. Chengwen Liu, Hao Chen: A Hash Partition Strategy for Distributed Query Processing. EDBT 1996: 373-387
  29. Alon Y. Levy, Inderpal Singh Mumick: Reasoning with Aggregation Constraints. EDBT 1996: 514-534
  30. Michael Steinbrunn, Klaus Peithner, Guido Moerkotte, Alfons Kemper: Bypassing Joins in Disjunctive Queries. VLDB 1995: 228-238
  31. Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995: 562-573
  32. Peter J. Haas, Jeffrey F. Naughton, S. Seshadri, Lynne Stokes: Sampling-Based Estimation of the Number of Distinct Values of an Attribute. VLDB 1995: 311-322
  33. Staffan Flodin, Tore Risch: Processing Object-Oriented Queries with Invertible Late Bound Functions. VLDB 1995: 335-344
  34. Surajit Chaudhuri, Umeshwar Dayal, Tak W. Yan: Join Queries with External Text Sources: Execution and Optimization Techniques. SIGMOD Conference 1995: 410-422
  35. Karl Aberer, Gisela Fischer: Semantic Query Optimization for Methods in Object-Oriented Database Systems. ICDE 1995: 70-79
  36. Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv: Query Optimization by Predicate Move-Around. VLDB 1994: 96-107
  37. Michael Stonebraker: SEQUOIA 2000: A Reflection of the First Three Years. SSDBM 1994: 108-116
  38. Alfons Kemper, Guido Moerkotte, Klaus Peithner, Michael Steinbrunn: Optimizing Disjunctive Queries with Expensive Predicates. SIGMOD Conference 1994: 336-347
  39. Joseph M. Hellerstein: Practical Predicate Placement. SIGMOD Conference 1994: 325-335
  40. Chung-Min Chen, Nick Roussopoulos: The Implementation and Performance Evaluation of the ADMS Query Optimizer: Integrating Query Result Caching and Matching. EDBT 1994: 323-336
  41. Michael Stonebraker: The SEQUOIA 2000 project. IEEE Data Eng. Bull. 16(1): 24-28(1993)
  42. Surajit Chaudhuri, Kyuseok Shim: Query Optimization in the Presence of Foreign Functions. VLDB 1993: 529-542
  43. R. Ananthanarayanan, Vibby Gottemukkala, Wolfgang Käfer, Tobin J. Lehman, Hamid Pirahesh: Using the Co-existence Approach to Achieve Combined Functionality of Object-Oriented and Relational Systems. SIGMOD Conference 1993: 109-118
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:15 2009