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

A Performance Evaluation of Pointer-Based Joins.

Eugene J. Shekita, Michael J. Carey: A Performance Evaluation of Pointer-Based Joins. SIGMOD Conference 1990: 300-311
@inproceedings{DBLP:conf/sigmod/ShekitaC90,
  author    = {Eugene J. Shekita and
               Michael J. Carey},
  editor    = {Hector Garcia-Molina and
               H. V. Jagadish},
  title     = {A Performance Evaluation of Pointer-Based Joins},
  booktitle = {Proceedings of the 1990 ACM SIGMOD International Conference on
               Management of Data, Atlantic City, NJ, May 23-25, 1990},
  publisher = {ACM Press},
  year      = {1990},
  pages     = {300-311},
  ee        = {http://doi.acm.org/10.1145/93597.98739, db/conf/sigmod/ShekitaC90.html},
  crossref  = {DBLP:conf/sigmod/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In this paper we describe three pointer-based join algorithms that are simple variants of the nested-loops, sort-merge, and hybrid-hash join algorithms used in relational data-base systems. Each join algorithm is described and an analysis is carried out to compare the performance of the pointer-based algorithms to their standard, non-pointer-based counterparts. The results of the analysis show that the pointer-based algorithms can provide significant performance gains in many situations. The results also show that the pointer-based nested-loops join algorithm, which is perhaps the most natural pointer-based join algorithm to consider using in an object-oriented database system, performs quite poorly on most medium to large joins.

Copyright © 1990 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 2, SIGMOD '75-'92" and ...

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

Printed Edition

Hector Garcia-Molina, H. V. Jagadish (Eds.): Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990. ACM Press 1990 BibTeX , SIGMOD Record 19(2), June 1990
Contents

Online Edition: ACM Digital Library


References

[Blas77]
Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) BibTeX
[Car88]
Michael J. Carey, David J. DeWitt, Scott L. Vandenberg: A Data Model and Query Language for EXODUS. SIGMOD Conference 1988: 413-423 BibTeX
[Car89]
...
[Car90]
Michael J. Carey, Eugene J. Shekita, George Lapis, Bruce G. Lindsay, John McPherson: An Incremental Join Attachment for Starburst. VLDB 1990: 662-673 BibTeX
[Chan82]
Arvola Chan, Sy Danberg, Stephen Fox, Wen-Te K. Lin, Anil Nori, Daniel R. Ries: Storage and Access Structures to Support a Semantic Data Model. VLDB 1982: 122-130 BibTeX
[Dewi85]
David J. DeWitt, Robert H. Gerber: Multiprocessor Hash-Based Join Algorithms. VLDB 1985: 151-164 BibTeX
[Deaux90]
O. Deux: The Story of O2. IEEE Trans. Knowl. Data Eng. 2(1): 91-108(1990) BibTeX
[Haas90]
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
[Kim89]
Won Kim: A Model of Queries for Object-Oriented Databases. VLDB 1989: 423-432 BibTeX
[Mack86]
Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95 BibTeX
[Mack89]
Lothar F. Mackert, Guy M. Lohman: Index Scans Using a Finite LRU Buffer: A Validated I/O Model. ACM Trans. Database Syst. 14(3): 401-424(1989) BibTeX
[Seve76]
Dennis G. Severance, Guy M. Lohman: Differential Files: Their Application to the Maintenance of Large Databases. ACM Trans. Database Syst. 1(3): 256-267(1976) BibTeX
[Shap86]
Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986) BibTeX
[Shek90]
...
[Ship81]
David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) BibTeX
[Vald87]
Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) BibTeX
[Vele89]
Fernando Vélez, Guy Bernard, Vineeta Darnis: The O2 Object Manager: an Overview. VLDB 1989: 357-366 BibTeX
[Yao77]
...
[Zani83]
Carlo Zaniolo: The Database Language GEM. SIGMOD Conference 1983: 207-218 BibTeX

Referenced by

  1. Reinhard Braumandl, Jens Claußen, Alfons Kemper, Donald Kossmann: Functional-Join Processing. VLDB J. 8(3-4): 156-177(2000)
  2. Fanny Wattez, Sophie Cluet, Véronique Benzaken, Guy Ferran, Christian Fiegel: Benchmarking Queries over Trees: Learning the Hard Truth the Hard Way. SIGMOD Conference 2000: 510-511
  3. Zhe Li, Kenneth A. Ross: Fast Joins Using Join Indices. VLDB J. 8(1): 1-24(1999)
  4. Navin Kabra, David J. DeWitt: OPT++: An Object-Oriented Implementation for Extensible Database Query Optimization. VLDB J. 8(1): 55-78(1999)
  5. Reinhard Braumandl, Jens Claußen, Alfons Kemper: Evaluating Functional Joins Along Nested Reference Sets in Object-Relational and Object-Oriented Databases. VLDB 1998: 110-122
  6. Laura M. Haas, Michael J. Carey, Miron Livny, Amit Shukla: Seeking the Truth About ad hoc Join Costs. VLDB J. 6(3): 241-256(1997)
  7. Sven Helmer, Guido Moerkotte: Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates. VLDB 1997: 386-395
  8. Jie-Bing Yu, David J. DeWitt: Query Pre-Execution and Batching in Paradise: A Two-Pronged Approach to the Efficient Processing of Queries on Tape-Resident Raster Images. SSDBM 1997: 64-78
  9. Michael Gesmann: A Cost Model for Parallel Navigational Access in Complex-Object DBMSs. DASFAA 1997: 1-10
  10. Wan-Sup Cho, Seung-Sun Lee, Kyu-Young Whang, Yong-Ik Yoon: Query Optimization Techniques Utilizing Path Indexes in Object-Oriented Database Systems. DASFAA 1997: 21-29
  11. Peter A. Buhr, Anil K. Goel, Naomi Nishimura, Prabhakar Ragde: Parallel Pointer-Based Join Algorithms in Memory-mapped Environments. ICDE 1996: 266-275
  12. Hennie J. Steenhagen, Rolf A. de By, Henk M. Blanken: Translating OSQL-Queries into Efficient Set Expressions. EDBT 1996: 183-197
  13. Nadejda Biscondi, André Flory, Lionel Brunie: Parallel Databases: Structured Query Optimization. ADBIS 1996: 146-152
  14. Arie Segev, J. Leon Zhao: A Framework for Join Pattern Indexing in Intelligent Database Systems. IEEE Trans. Knowl. Data Eng. 7(6): 941-947(1995)
  15. Georges Gardarin, Fernando Machuca, Philippe Pucheral: OFL: A Functional Execution Model for Object Query Languages. SIGMOD Conference 1995: 59-70
  16. Hennie J. Steenhagen, Peter M. G. Apers, Henk M. Blanken, Rolf A. de By: From Nested-Loop to Join Queries in OODB. VLDB 1994: 618-629
  17. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  18. José A. Blakeley, William J. McKenna, Goetz Graefe: Experiences Building the Open OODB Query Optimizer. SIGMOD Conference 1993: 287-296
  19. Valery Soloviev: A Truncating Hash Algorithm for Processing Band-Join Queries. ICDE 1993: 419-427
  20. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
  21. Daniel F. Lieuwen, David J. DeWitt: A Transformation-Based Approach to Optimizing Loops in Database Programming Languages. SIGMOD Conference 1992: 91-100
  22. Philippe Pucheral, Jean-Marc Thévenin: Pipelined Query Processing in the DBGraph Storage Model. EDBT 1992: 516-533
  23. Thomas Keller, Goetz Graefe, David Maier: Efficient Assembly of Complex Objects. SIGMOD Conference 1991: 148-157
  24. William Perrizo, James Gustafson, Daniel Thureen, David Wenberg: Domain Vector Accelerator for Relational Operations. ICDE 1991: 491-498
  25. Daniel F. Lieuwen, David J. DeWitt: Optimizing Loops in Database Programming Languages. DBPL 1991: 287-305
  26. Philippe Pucheral, Jean-Marc Thévenin, Patrick Valduriez: Efficient Main Memory Data Management Using the DBGraph Storage Model. VLDB 1990: 683-695
  27. Michael J. Carey, Eugene J. Shekita, George Lapis, Bruce G. Lindsay, John McPherson: An Incremental Join Attachment for Starburst. VLDB 1990: 662-673
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:03 2009