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}
}

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 ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

, 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)
[Car88]: Michael J. Carey, David J. DeWitt, Scott L. Vandenberg: A Data Model and Query Language for EXODUS. SIGMOD Conference 1988: 413-423
[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
[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
[Dewi85]: David J. DeWitt, Robert H. Gerber: Multiprocessor Hash-Based Join Algorithms. VLDB 1985: 151-164
[Deaux90]: O. Deux: The Story of O2. IEEE Trans. Knowl. Data Eng. 2(1): 91-108(1990)
[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)
[Kim89]: Won Kim: A Model of Queries for Object-Oriented Databases. VLDB 1989: 423-432
[Mack86]: Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95
[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)
[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)
[Shap86]: Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986)
[Shek90]: ...
[Ship81]: David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981)
[Vald87]: Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987)
[Vele89]: Fernando Vélez, Guy Bernard, Vineeta Darnis: The O2 Object Manager: an Overview. VLDB 1989: 357-366
[Yao77]: ...
[Zani83]: Carlo Zaniolo: The Database Language GEM. SIGMOD Conference 1983: 207-218