Loading...
Please wait, while we are loading the content...
Similar Documents
Improving Hash Join Performance through (2004)
| Content Provider | CiteSeerX |
|---|---|
| Author | Chen, Shimin Ailamaki, Anastassia Gibbons, Phillip B. Mowry, Todd C. |
| Description | Hash join algorithms suffer from extensive CPU cache stalls. This article shows that the standard hash join algorithm for disk-oriented databases (i.e. GRACE) spends over 80 % of its user time stalled on CPU cache misses, and explores the use of CPU cache 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 1.29– 4.04X speedups for the join phase and 1.37–3.49X speedups for the partition phase over GRACE and simple prefetching approaches. Moreover, compared with previous cache-aware approaches (i.e. cache partitioning), the schemes are at least 36 % faster on large relations and do not require exclusive use of the CPU cache to be effective. Finally, comparing the elapsed real times when disk This research was supported by a grant from the NSF. |
| File Format | |
| Language | English |
| Publisher Date | 2004-01-01 |
| Publisher Institution | Prefetching”, Proceedings of the 20th Int’l conference on Data Engineering |
| Access Restriction | Open |
| Subject Keyword | Group Prefetching Elapsed Real Time Hash Join Algorithm Join Phase User Time Simple Prefetching Approach Standard Hash Join Algorithm Inherent Randomness Multiple Code Path Cache Performance Large Relation Disk-oriented Database Cpu Cache Extensive Cpu Cache Stall Data Dependency Cpu Cache Miss Previous Cache-aware Approach Partition Phase Software-pipelined Prefetching Hash Join Performance Exclusive Use |
| Content Type | Text |
| Resource Type | Article |
