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

Practical Predicate Placement.

Joseph M. Hellerstein: Practical Predicate Placement. SIGMOD Conference 1994: 325-335
@inproceedings{DBLP:conf/sigmod/Hellerstein94,
  author    = {Joseph M. Hellerstein},
  editor    = {Richard T. Snodgrass and
               Marianne Winslett},
  title     = {Practical Predicate Placement},
  booktitle = {Proceedings of the 1994 ACM SIGMOD International Conference on
               Management of Data, Minneapolis, Minnesota, May 24-27, 1994},
  publisher = {ACM Press},
  year      = {1994},
  pages     = {325-335},
  ee        = {http://doi.acm.org/10.1145/191839.191904, db/conf/sigmod/Hellerstein94.html},
  crossref  = {DBLP:conf/sigmod/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

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.

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

Richard T. Snodgrass, Marianne Winslett (Eds.): Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, Minneapolis, Minnesota, May 24-27, 1994. ACM Press 1994 BibTeX , SIGMOD Record 23(2), June 1994
Contents

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1194 KB]

References

[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 BibTeX
[CGK89]
Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy: Towards on Open Architecture for LDL. VLDB 1989: 195-203 BibTeX
[CS93]
Surajit Chaudhuri, Kyuseok Shim: Query Optimization in the Presence of Foreign Functions. VLDB 1993: 529-542 BibTeX
[CYY+92]
Hanxiong Chen, Xu Yu, Kazunori Yamaguchi, Hiroyuki Kitagawa, Nobuo Ohbo, Yuzuru Fujiwara: Decomposition - An Approach for Optimizing Queries Including ADT Functions. Inf. Process. Lett. 43(6): 327-333(1992) BibTeX
[DKS92]
Weimin Du, Ravi Krishnamurthy, Ming-Chien Shan: Query Optimization in a Heterogeneous DBMS. VLDB 1992: 277-291 BibTeX
[Hel92]
...
[HS93a]
Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276 BibTeX
[HS93b]
Wei Hong, Michael Stonebraker: Optimization of Parallel Query Execution Plans in XPRS. Distributed and Parallel Databases 1(1): 9-32(1993) 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
[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
[KZ88]
Ravi Krishnamurthy, Carlo Zaniolo: Optimization in a Logic Based Language for Knowledge and Data Intensive Applications. EDBT 1988: 16-33 BibTeX
[LH93]
...
[MFPR90]
Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258 BibTeX
[MS79]
...
[Nau93]
...
[PHH92]
Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48 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
[Sha86]
Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986) BibTeX
[SK91]
Michael Stonebraker, Greg Kemnitz: The Postgres Next Generation Database Management System. Commun. ACM 34(10): 78-92(1991) BibTeX
[Sto93]
Michael Stonebraker: The Miro DBMS. SIGMOD Conference 1993: 439 BibTeX
[TPC93]
...
[Ull88]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[YKY+91]
Kenichi Yajima, Hiroyuki Kitagawa, Kazunori Yamaguchi, Nobuo Ohbo, Yuzuru Fujiwara: Optimization of Queries Including ADT Functions. DASFAA 1991: 366-373 BibTeX

Referenced by

  1. Navin Kabra, David J. DeWitt: OPT++: An Object-Oriented Implementation for Extensible Database Query Optimization. VLDB J. 8(1): 55-78(1999)
  2. Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-Defined Predicates. ACM Trans. Database Syst. 24(2): 177-228(1999)
  3. Jihad Boulos, Kinji Ono: Cost Estimation of User-Defined Methods in Object-Relational Database Systems. SIGMOD Record 28(3): 22-28(1999)
  4. Joseph M. Hellerstein: Optimization Techniques for Queries with Expensive Methods. ACM Trans. Database Syst. 23(2): 113-157(1998)
  5. Jun Rao, Kenneth A. Ross: Reusing Invariants: A New Strategy for Correlated Queries. SIGMOD Conference 1998: 37-48
  6. Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43
  7. Wolfgang Scheufele, Guido Moerkotte: Efficient Dynamic Programming Algorithms for Ordering Expensive Joins and Selections. EDBT 1998: 201-215
  8. Peter Scheuermann, Junho Shim, Radek Vingralek: WATCHMAN : A Data Warehouse Intelligent Cache Manager. VLDB 1996: 51-62
  9. Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-defined Predicates. VLDB 1996: 87-98
  10. Michael H. Böhlen, Richard T. Snodgrass, Michael D. Soo: Coalescing in Temporal Databases. VLDB 1996: 180-191
  11. David E. Simmen, Eugene J. Shekita, Timothy Malkemus: Fundamental Techniques for Order Optimization. SIGMOD Conference 1996: 57-67
  12. Joseph M. Hellerstein, Jeffrey F. Naughton: Query Execution Techniques for Caching Expensive Methods. SIGMOD Conference 1996: 423-434
  13. Chengwen Liu, Hao Chen, Warren Krueger: A Distributed Query Processing Strategy Using Placement Dependency. ICDE 1996: 477-484
  14. Chengwen Liu, Hao Chen: A Hash Partition Strategy for Distributed Query Processing. EDBT 1996: 373-387
  15. Alon Y. Levy, Inderpal Singh Mumick: Reasoning with Aggregation Constraints. EDBT 1996: 514-534
  16. Michael Steinbrunn, Klaus Peithner, Guido Moerkotte, Alfons Kemper: Bypassing Joins in Disjunctive Queries. VLDB 1995: 228-238
  17. Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv: Query Optimization by Predicate Move-Around. VLDB 1994: 96-107
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:21 2009