A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment.
Donovan A. Schneider, David J. DeWitt:
A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment.
SIGMOD Conference 1989: 110-121@inproceedings{DBLP:conf/sigmod/SchneiderD89,
author = {Donovan A. Schneider and
David J. DeWitt},
editor = {James Clifford and
Bruce G. Lindsay and
David Maier},
title = {A Performance Evaluation of Four Parallel Join Algorithms in
a Shared-Nothing Multiprocessor Environment},
booktitle = {Proceedings of the 1989 ACM SIGMOD International Conference on
Management of Data, Portland, Oregon, May 31 - June 2, 1989},
publisher = {ACM Press},
year = {1989},
pages = {110-121},
ee = {http://doi.acm.org/10.1145/67544.66937, db/conf/sigmod/SchneiderD89.html},
crossref = {DBLP:conf/sigmod/89},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
In this paper we analyze and compare four
parallel join algorithms. Grace and Hybrid hash represent the
class of hash-based join methods, Simple hash represents a looping algorithm with hashing, and our last algorithm is the more traditional sort-merge. The performance of each of the algorithms
with different tuple distribution policies, the addition of bit
vector filters, varying amounts of main-memory for joining, and
non-uniformly distributed join attribute values is studied. The Hybrid hash-join algorithm is found to be superior except when
the join attribute values of the inner relation are non-uniformly distributed and memory is limited. In this case, a more conservative algorithm such as the sort-merge algorithm should be used. The Gamma database machine serves as the host for the performance comparison.
Copyright © 1989 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 ...
Printed Edition
James Clifford, Bruce G. Lindsay, David Maier (Eds.):
Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 - June 2, 1989.
ACM Press 1989
,
SIGMOD Record 18(2), June 1989
Contents
References
- [BABB79]
- Edward Babb:
Implementing a Relational Database by Means of Specialized Hardware.
ACM Trans. Database Syst. 4(1): 1-29(1979)
![bibliographical record in XML](../../xml.gif)
- [BITT83]
- Dina Bitton, David J. DeWitt, Carolyn Turbyfill:
Benchmarking Database Systems A Systematic Approach.
VLDB 1983: 8-19
![bibliographical record in XML](../../xml.gif)
- [BORA88]
- Haran Boral:
Parallelism in Bubba.
DPDS 1988: 68-71
![bibliographical record in XML](../../xml.gif)
- [BRAT84]
- Kjell Bratbergsengen:
Hashing Methods and Relational Algebra Operations.
VLDB 1984: 323-333
![bibliographical record in XML](../../xml.gif)
- [BRAT87]
- Kjell Bratbergsengen:
Algebra Operations on a Parallel Computer - Performance Evaluation.
IWDM 1987: 415-428
![bibliographical record in XML](../../xml.gif)
- [CHOU85]
- Hong-Tai Chou, David J. DeWitt, Randy H. Katz, Anthony C. Klug:
Design and Implementation of the Wisconsin Storage System.
Softw., Pract. Exper. 15(10): 943-962(1985)
![bibliographical record in XML](../../xml.gif)
- [DEWI84]
- 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
![bibliographical record in XML](../../xml.gif)
- [DEWI85]
- David J. DeWitt, Robert H. Gerber:
Multiprocessor Hash-Based Join Algorithms.
VLDB 1985: 151-164
![bibliographical record in XML](../../xml.gif)
- [DEWI86]
- David J. DeWitt, Robert H. Gerber, Goetz Graefe, Michael L. Heytens, Krishna B. Kumar, M. Muralikrishna:
GAMMA - A High Performance Dataflow Database Machine.
VLDB 1986: 228-237
![bibliographical record in XML](../../xml.gif)
- [DEWI88]
- David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider:
A Performance Analysis of the Gamma Database Machine.
SIGMOD Conference 1988: 350-360
![bibliographical record in XML](../../xml.gif)
- [KITS83]
- Masaru Kitsuregawa, Hidehiko Tanaka, Tohru Moto-Oka:
Application of Hash to Data Base Machine and Its Architecture.
New Generation Comput. 1(1): 63-74(1983)
![bibliographical record in XML](../../xml.gif)
- [KITS88]
- Masaru Kitsuregawa, Miyuki Nakano, Mikio Takagi:
Query Execution for Large Relations on Functional Disk Systems.
ICDE 1989: 159-167
![bibliographical record in XML](../../xml.gif)
- [LORI88]
- Raymond A. Lorie, Jean-Jacques Daudenarde, Gary Hallmark, James W. Stamos, Honesty C. Young:
Adding Intra-transaction Parallelism to an Existing DBMS: Early Experience.
IEEE Data Eng. Bull. 12(1): 2-8(1989)
![bibliographical record in XML](../../xml.gif)
- [RIES78]
- ...
- [SELI79]
- 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
![bibliographical record in XML](../../xml.gif)
- [TAND88]
- The Tandem Performance Group:
A Benchmark of NonStop SQL on the Debit Credit Transaction (Invited Paper).
SIGMOD Conference 1988: 337-341
![bibliographical record in XML](../../xml.gif)
- [TERA83]
- ...
- [VALD84]
- Patrick Valduriez, Georges Gardarin:
Join and Semijoin Algorithms for a Multiprocessor Database Machine.
ACM Trans. Database Syst. 9(1): 133-161(1984)
![bibliographical record in XML](../../xml.gif)
Copyright © Fri Mar 12 17:21:28 2010
by Michael Ley (ley@uni-trier.de)