Published Articles >> Table of Contents >> Abstract

20th International Conference on Data Engineering (ICDE'04)   p. 116
Improving Hash Join Performance through Prefetching
Shimin Chen, Carnegie Mellon University
Anastassia Ailamaki, Carnegie Mellon University
Phillip B. Gibbons, Intel Research Pittsburgh
Todd C. Mowry, Carnegie Mellon University

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDE.2004.1319989
Send link to a friend

Abstract
Hash join algorithms suffer from extensive CPU cache stalls. This paper shows that the standard hash join algorithm for disk-oriented databases (i.e. GRACE) spends over 73% of its user time stalled on CPU cache misses, and explores the use of prefetching to improve its cache performance. Applying prefetching to hash joins is complicated by the data dependencies, multiple code paths, and inherent randomness of hashing. We present two techniques, group prefetching and software-pipelined prefetching, that overcome these complications.These schemes achieve 2.0- 2.9X speedups for the join phase and 1.4-2.6X speedups for the partition phase over GRACE and simple prefetching approaches. Compared with previous cache-aware approaches (i.e. cache partitioning), the schemes are at least 50% faster on large relations and do not require exclusive use of the CPU cache to be effective.
Back to Top Additional Information
Citation:  Shimin Chen, Anastassia Ailamaki, Phillip B. Gibbons, Todd C. Mowry, "Improving Hash Join Performance through Prefetching," icde, p. 116,  20th International Conference on Data Engineering (ICDE'04),  2004