Multiprocessor hash-based join algorithms
David J. DeWitt, Robert H. Gerber · 1985
This paper extends earlier research on hash-join algorithms to a multiprocessor architecture. Implementations of a number of centralized join algorithms are described and measured. Evaluation of these algorithms served to verify earlier analytical results. In addition, they demonstrate that bit vector filtering provides dramatic improvement in the performance of all algorithms including the sort merge join algorithm. Multiprocessor configurations of the centralized Grace and Hybrid hash-join algorithms are also presented. Both algorithms are shown to provide linear increases in throughput with corresponding increases in processor and disk resources. 1. Introduction After the publication of the classic join algorithm paper in 1977 by Blasgen and Eswaran [BLAS77], the topic was virtually abandoned as a research area. Everybody "knew" that a nested-loops algorithm provided acceptable performance on small relations or large relations when a suitable index existed and that sort-merge was...
Cited by 237 works.
Authors
References
- The Art of Computer Programming
- The Art of Computer Programming: Volume 3: Sorting and Searching
- System R
- The design and implementation of INGRES
- Implementation techniques for main memory database systems
- Benchmarking Database Systems A Systematic Approach
- Computer Structures: Principles and Examples
- Implementing a relational database by means of specialzed hardware
- Storage and access in relational data bases
- Application of hash to data base machine and its architecture