ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Query Optimization in the Presence of Foreign Functions.

Surajit Chaudhuri, Kyuseok Shim: Query Optimization in the Presence of Foreign Functions. VLDB 1993: 529-542
@inproceedings{DBLP:conf/vldb/ChaudhuriS93,
  author    = {Surajit Chaudhuri and
               Kyuseok Shim},
  editor    = {Rakesh Agrawal and
               Se{\'a}n Baker and
               David A. Bell},
  title     = {Query Optimization in the Presence of Foreign Functions},
  booktitle = {19th International Conference on Very Large Data Bases, August
               24-27, 1993, Dublin, Ireland, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1993},
  isbn      = {1-55860-152-X},
  pages     = {529-542},
  ee        = {db/conf/vldb/ChaudhuriS93.html},
  crossref  = {DBLP:conf/vldb/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The declarativeness of relational query languages is very attractive for developing applications. However, many applications also need to invoke external functions or to access data that is not stored in the database. It is not hard to express references to such foreign functions in the query language. However, theissue of cost-based optimization of relational queries in the presence of such foreign functions has not previously been addressed satisfactorily. In this paper, we describe a comprehensive approach to this problem. Our key observation is that the optimization must take into account semantic information about foreign functions. Therefore, we provide a simple declarative rule language to express such semantics. We present algorithms necessary for applying the rules and for generating the space of equivalent queries. The equivalent queries provide the optimizer with an enriched execution space. We show how we can modify the traditional join reordering algorithm based on dynamic programming to obtain an optimal plan from the execution space. We provide necessary extensions to the cost model that are needed in the presence of foreign functions.

Copyright © 1993 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Rakesh Agrawal, Seán Baker, David A. Bell (Eds.): 19th International Conference on Very Large Data Bases, August 24-27, 1993, Dublin, Ireland, Proceedings. Morgan Kaufmann 1993, ISBN 1-55860-152-X
Contents BibTeX

References

[AS91]
Walid G. Aref, Hanan Samet: Optimization for Spatial Query Processing. VLDB 1991: 81-90 BibTeX
[Ban86]
...
[BG92]
Ludger Becker, Ralf Hartmut Güting: Rule-Based Optimization and Query Processing in an Extensible Geometric Database System. ACM Trans. Database Syst. 17(2): 247-303(1992) BibTeX
[CGK89]
Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy: Towards on Open Architecture for LDL. VLDB 1989: 195-203 BibTeX
[CGM90]
Upen S. Chakravarthy, John Grant, Jack Minker: Logic-Based Approach to Semantic Query Optimization. ACM Trans. Database Syst. 15(2): 162-207(1990) BibTeX
[CH90]
Michael J. Carey, Laura M. Haas: Extensible Database Management Systems. SIGMOD Record 19(4): 54-60(1990) BibTeX
[CHK+91]
Tim Connors, Waqar Hasan, Curtis P. Kolovson, Marie-Anne Neimat, Donovan A. Schneider, W. Kevin Wilkinson: The Papyrus Integrated Data Server. PDIS 1991: 139 BibTeX
[CLR90]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company 1989, ISBN 0-262-03141-8,0-07-013143-0
BibTeX
[CS93]
...
[GD87]
Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 BibTeX
[GHK92]
Sumit Ganguly, Waqar Hasan, Ravi Krishnamurthy: Query Optimization for Parallel Execution. SIGMOD Conference 1992: 9-18 BibTeX
[HS93]
Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276 BibTeX
[KNP92]
Curtis P. Kolovson, Marie-Anne Neimat, Spyros Potamianos: Interoperability of Spatial and Attribute Data Managers: A Case Study. SSD 1993: 239-263 BibTeX
[Loh88]
Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27 BibTeX
[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
[SJGP90]
Michael Stonebraker, Anant Jhingran, Jeffrey Goh, Spyros Potamianos: On Rules, Procedures, Caching and Views in Data Base Systems. SIGMOD Conference 1990: 281-290 BibTeX
[Ull88]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

Referenced by

  1. Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-Defined Predicates. ACM Trans. Database Syst. 24(2): 177-228(1999)
  2. 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
  3. Tobias Mayr, Praveen Seshadri: Client-Site Query Extensions. SIGMOD Conference 1999: 347-358
  4. Daniela Florescu, Alon Y. Levy, Ioana Manolescu, Dan Suciu: Query Optimization in the Presence of Limited Access Patterns. SIGMOD Conference 1999: 311-322
  5. Berthold Reinwald, Hamid Pirahesh, Ganapathy Krishnamoorthy, George Lapis, Brian T. Tran, Swati Vora: Heterogeneous Query Processing through SQL Table Functions. ICDE 1999: 366-373
  6. Vladimir Zadorozhny: Cost-based Magic for Web Queries (Extended Abstract). ADBIS (Short Papers) 1999: 185-192
  7. Praveen Seshadri: Enhanced Abstract Data Types in Object-Relational Databases. VLDB J. 7(3): 130-140(1998)
  8. Joseph M. Hellerstein: Optimization Techniques for Queries with Expensive Methods. ACM Trans. Database Syst. 23(2): 113-157(1998)
  9. Narayanan Shivakumar, Hector Garcia-Molina, Chandra Chekuri: Filtering with Approximate Predicates. VLDB 1998: 263-274
  10. Mitch Cherniack, Stanley B. Zdonik: Inferring Function Semantics to Optimize Queries. VLDB 1998: 239-250
  11. Wolfgang Scheufele, Guido Moerkotte: Efficient Dynamic Programming Algorithms for Ordering Expensive Joins and Selections. EDBT 1998: 201-215
  12. Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: The Case for Enhanced Abstract Data Types. VLDB 1997: 66-75
  13. Laura M. Haas, Donald Kossmann, Edward L. Wimmers, Jun Yang: Optimizing Queries Across Diverse Data Sources. VLDB 1997: 276-285
  14. Stefan Deßloch, Nelson Mendonça Mattos: Integrating SQL Databases with Content-Specific Search Engines. VLDB 1997: 528-537
  15. Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-defined Predicates. VLDB 1996: 87-98
  16. Sibel Adali, K. Selçuk Candan, Yannis Papakonstantinou, V. S. Subrahmanian: Query Caching and Optimization in Distributed Mediator Systems. SIGMOD Conference 1996: 137-148
  17. Surajit Chaudhuri, Umeshwar Dayal, Tak W. Yan: Join Queries with External Text Sources: Execution and Optimization Techniques. SIGMOD Conference 1995: 410-422
  18. Anand Rajaraman, Yehoshua Sagiv, Jeffrey D. Ullman: Answering Queries Using Templates with Binding Patterns. PODS 1995: 105-112
  19. Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200
  20. Karl Aberer, Gisela Fischer: Semantic Query Optimization for Methods in Object-Oriented Database Systems. ICDE 1995: 70-79
  21. Tak W. Yan, Jurgen Annevelink: Integrating a Structured-Text Retrieval System with an Object-Oriented Database System. VLDB 1994: 740-749
  22. Joseph M. Hellerstein: Practical Predicate Placement. SIGMOD Conference 1994: 325-335
  23. Val Tannen: Tutorial: Languages for Collection Types. PODS 1994: 150-154
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
 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:45:57 2009