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.
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
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
- Reinhard Braumandl, Jens Claußen, Alfons Kemper, Donald Kossmann:
Functional-Join Processing.
VLDB J. 8(3-4): 156-177(2000)
- 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
- Zhe Li, Kenneth A. Ross:
Fast Joins Using Join Indices.
VLDB J. 8(1): 1-24(1999)
- Navin Kabra, David J. DeWitt:
OPT++: An Object-Oriented Implementation for Extensible Database Query Optimization.
VLDB J. 8(1): 55-78(1999)
- 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
- 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)
- Sven Helmer, Guido Moerkotte:
Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates.
VLDB 1997: 386-395
- 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
- Michael Gesmann:
A Cost Model for Parallel Navigational Access in Complex-Object DBMSs.
DASFAA 1997: 1-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
- Peter A. Buhr, Anil K. Goel, Naomi Nishimura, Prabhakar Ragde:
Parallel Pointer-Based Join Algorithms in Memory-mapped Environments.
ICDE 1996: 266-275
- Hennie J. Steenhagen, Rolf A. de By, Henk M. Blanken:
Translating OSQL-Queries into Efficient Set Expressions.
EDBT 1996: 183-197
- Nadejda Biscondi, André Flory, Lionel Brunie:
Parallel Databases: Structured Query Optimization.
ADBIS 1996: 146-152
- 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)
- Georges Gardarin, Fernando Machuca, Philippe Pucheral:
OFL: A Functional Execution Model for Object Query Languages.
SIGMOD Conference 1995: 59-70
- 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
- Goetz Graefe:
Query Evaluation Techniques for Large Databases.
ACM Comput. Surv. 25(2): 73-170(1993)
- José A. Blakeley, William J. McKenna, Goetz Graefe:
Experiences Building the Open OODB Query Optimizer.
SIGMOD Conference 1993: 287-296
- Valery Soloviev:
A Truncating Hash Algorithm for Processing Band-Join Queries.
ICDE 1993: 419-427
- Priti Mishra, Margaret H. Eich:
Join Processing in Relational Databases.
ACM Comput. Surv. 24(1): 63-113(1992)
- Daniel F. Lieuwen, David J. DeWitt:
A Transformation-Based Approach to Optimizing Loops in Database Programming Languages.
SIGMOD Conference 1992: 91-100
- Philippe Pucheral, Jean-Marc Thévenin:
Pipelined Query Processing in the DBGraph Storage Model.
EDBT 1992: 516-533
- Thomas Keller, Goetz Graefe, David Maier:
Efficient Assembly of Complex Objects.
SIGMOD Conference 1991: 148-157
- William Perrizo, James Gustafson, Daniel Thureen, David Wenberg:
Domain Vector Accelerator for Relational Operations.
ICDE 1991: 491-498
- Daniel F. Lieuwen, David J. DeWitt:
Optimizing Loops in Database Programming Languages.
DBPL 1991: 287-305
- Philippe Pucheral, Jean-Marc Thévenin, Patrick Valduriez:
Efficient Main Memory Data Management Using the DBGraph Storage Model.
VLDB 1990: 683-695
- 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