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

Query Execution Techniques for Caching Expensive Methods.

Joseph M. Hellerstein, Jeffrey F. Naughton: Query Execution Techniques for Caching Expensive Methods. SIGMOD Conference 1996: 423-434
@inproceedings{DBLP:conf/sigmod/HellersteinN96,
  author    = {Joseph M. Hellerstein and
               Jeffrey F. Naughton},
  editor    = {H. V. Jagadish and
               Inderpal Singh Mumick},
  title     = {Query Execution Techniques for Caching Expensive Methods},
  booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
               Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
  publisher = {ACM Press},
  year      = {1996},
  pages     = {423-434},
  ee        = {http://doi.acm.org/10.1145/233269.233359, db/conf/sigmod/HellersteinN96.html},
  crossref  = {DBLP:conf/sigmod/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Object-Relational and Object-Oriented DBMSs allow users to invoke time-consuming ("expensive") methods in their queries. When queries containing these expensive methods are run on data with duplicate values, time is wasted redundantly computing methods on the same value. This problem has been studied in the context of programming languages, where "memoization" is the standard solution. In the database literature, sorting has been proposed to deal with this problem. We compare these approaches along with a third solution, a variant of unary hybrid hashing which we call Hybrid Cache. We demonstrate that Hybrid Cache always dominates memoization, and significantly outperforms sorting in many instances. This provides new insights into the tradeoff between hashing and sorting for unary operations. Additionally, our Hybrid Cache algorithm includes some new optimizations for unary hybrid hashing, which can be used for other applications such as grouping and duplicate elimination. We conclude with a discussion of techniques for caching multiple expensive methods in a single query, and raise some new optimization problems in choosing caching techniques.

Copyright © 1996 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 ...

Printed Edition

H. V. Jagadish, Inderpal Singh Mumick (Eds.): Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, June 4-6, 1996. ACM Press 1996 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 25(2), June 1996
Contents

Online Edition: ACM Digital Library

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

References

[Bra84]
Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CGK89]
Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy: Towards on Open Architecture for LDL. VLDB 1989: 195-203 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DKO+84]
David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GM95]
Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gra93]
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hel92]
...
[Hel94]
Joseph M. Hellerstein: Practical Predicate Placement. SIGMOD Conference 1994: 325-335 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HNSS95]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HOT88]
Wen-Chi Hou, Gultekin Özsoyoglu, Baldeo K. Taneja: Statistical Estimators for Relational Algebra Expressions. PODS 1988: 276-287 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HS93]
Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ill94]
...
[ISO94]
...
[KMPS94]
Alfons Kemper, Guido Moerkotte, Klaus Peithner, Michael Steinbrunn: Optimizing Disjunctive Queries with Expensive Predicates. SIGMOD Conference 1994: 336-347 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Knu73]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LS88]
Clifford A. Lynch, Michael Stonebraker: Extended User-Defined Indexing with Application to Textual Databases. VLDB 1988: 306-317 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MFPR90]
Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mic68]
...
[MS86]
David Maier, Jacob Stein: Indexing in an Object-Oriented DBMS. OODBS 1986: 171-182 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NKT88]
Masaya Nakayama, Masaru Kitsuregawa, Mikio Takagi: Hash-Partitioned Join Method Using Dynamic Destaging Strategy. VLDB 1988: 468-478 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sel88]
Timos K. Sellis: Multiple-Query Optimization. ACM Trans. Database Syst. 13(1): 23-52(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SHP+96]
Praveen Seshadri, Joseph M. Hellerstein, Hamid Pirahesh, T. Y. Cliff Leung, Raghu Ramakrishnan, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan: Cost-Based Optimization for Magic: Algebra and Implementation. SIGMOD Conference 1996: 435-446 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SPL96]
Praveen Seshadri, Hamid Pirahesh, T. Y. Cliff Leung: Complex Query Decorrelation. ICDE 1996: 450-458 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SPMK95]
Michael Steinbrunn, Klaus Peithner, Guido Moerkotte, Alfons Kemper: Bypassing Joins in Disjunctive Queries. VLDB 1995: 228-238 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[YKY+91]
Kenichi Yajima, Hiroyuki Kitagawa, Kazunori Yamaguchi, Nobuo Ohbo, Yuzuru Fujiwara: Optimization of Queries Including ADT Functions. DASFAA 1991: 366-373 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:21:33 2010 by Michael Ley (ley@uni-trier.de)