Seminar: "Prefetching for Database Memory Hierarchy Performance"
Shimin Chen
Carnegie Mellon University
Department of Computer Science
Faculty Host: Mark Corner
"Prefetching for Database Memory Hierarchy Performance"
Computer systems have enjoyed an exponential growth in processor speed for the last 20 years, while DRAM main memory speed improves only moderately. A cache miss to main memory takes hundreds of processor cycles today, and the gap between processor and DRAM speeds is increasing exponentially. Cache performance is especially critical for data-intensive applications whose data footprints cannot fit into the cache. Recent database performance studies have pointed out that about 50% or more of the execution time of database systems is often wasted due to cache misses.
I exploit the use of software prefetch instructions supported by most modern processors to improve the CPU cache performance for relational database systems. By overlapping cache misses with computations and other misses, prefetching can benefit all kinds of cache misses including cold misses. Since prefetching for sequential accesses to arrays has already been well studied before, I focus on important structures and algorithms containing more intriguing, non-contiguous memory access patterns: the B+-Tree index, and the hash join algorithm. In this talk, I will present novel prefetching techniques for B+-trees and hash joins. I will report on the results of extensive performance studies, demonstrating the dramatic performance improvements of the prefetching techniques over traditional algorithms and other cache friendly schemes.
Refreshments at 3:30 p.m. in the atrium, outside the presentation room.
