A general framework for improving query processing performance on multi-level memory hierarchies

Bingsheng He, Yinan Li, Qiong Luo, Dongqing YangDaMoN 2007 · DOI

TL;DR

This paper introduces a novel framework to systematically analyze and improve database query processing performance across complex, multi-level memory hierarchies. By categorizing tuning levels based on the amount of memory hierarchy knowledge utilized, the authors demonstrate how to achieve better performance than purely cache-oblivious or overly tuned approaches.

What Problem Does This Paper Address?

Modern computer systems feature increasingly complex memory hierarchies, with multiple levels of caches (L1, L2, etc.) and main memory, each with different capacities, latencies, and transfer characteristics. This hierarchy significantly impacts the performance of database query processing, as data movement between these levels can become a major bottleneck. While cache-conscious techniques aim to exploit this hierarchy, they often require extensive, platform-specific tuning. Conversely, cache-oblivious techniques offer generality but may not achieve peak performance. The challenge is to find a balance: how to systematically improve performance by leveraging knowledge of the memory hierarchy without incurring prohibitive tuning costs, especially as hardware becomes more diverse.

Methods

The core contribution is a general framework for memory performance tuning. This framework categorizes tuning approaches into four levels:

  • T0 (Cache-oblivious): No knowledge of cache parameters is used. Algorithms rely on general principles like divide-and-conquer.
  • T1 (Cache Capacity/Block Size Aware): Utilizes knowledge of cache capacity and/or block size. This allows for techniques like blocking and tiling to fit data into cache lines or cache levels.
  • T2 (Latency Aware): Builds upon T1 by incorporating knowledge of memory access latency. This helps in identifying the most critical cache levels for optimization.
  • T3 (Prefetching/Non-blocking Aware): Extends T2 by considering software prefetching and non-blocking data transfer capabilities. This aims to hide memory latency by overlapping computation with data transfers.

The authors propose a cost model to determine the most significant cache levels for tuning, allowing them to focus optimization efforts. They then apply this framework to four common database operations: storage models (array/linked list scans), B+-trees, nested-loop joins, and hash joins, developing variants of these algorithms at different tuning levels.

Datasets

Not discussed in the paper. The evaluation uses synthetic workloads designed to mimic typical database operations, including selection and join queries on tables R and S with varying attributes and tuple sizes.

Key Insights and Ideas

  • Tuning is a spectrum, not a binary choice: The framework highlights that performance improvement is not a simple "tuned vs. not tuned" scenario but rather a gradient based on the degree of memory hierarchy knowledge applied.
  • More knowledge doesn't always mean better performance: The study shows that intermediate tuning levels (T1, T2) can sometimes perform worse than cache-oblivious approaches (T0) if they make incorrect assumptions (e.g., misidentifying the most critical cache level due to unknown latency).
  • T3 offers the best potential, but requires careful tuning: The highest tuning level (T3), which incorporates prefetching, generally yields the best performance, but its effectiveness is highly dependent on correctly setting parameters like prefetching distance.
  • Hardware prefetching complicates software prefetching: On platforms with robust hardware prefetching (like P4 and AMD), software prefetching might offer diminishing returns or even degrade performance if not carefully tuned, as it can interfere with hardware mechanisms.
  • Platform diversity matters: The performance gains from different tuning levels vary significantly across different architectures (P4, AMD, Ultra-Sparc), underscoring the need for a framework that can guide tuning for diverse hardware.

Key Results

  • Storage Models: Software prefetching (T3) improved array and linked list scans on P4 and AMD, especially for larger tuple sizes, but had less impact on Ultra-Sparc. Tuning the prefetching distance was crucial.
  • B+-trees: T3 consistently outperformed T0, T1, and T2, showing a 20-30% improvement. The VEB layout at T0 provided good spatial locality, but T3's prefetching further reduced cache stalls.
  • Nested-Loop Joins: T1 (targeting L2 cache) performed worse than T0, highlighting the risk of suboptimal tuning. T3 showed improvements, but the gains were less dramatic than in other cases due to the effectiveness of blocking techniques already present in T0.
  • Hash Joins: Both partitioning (T1/T2) and prefetching (T3) improved performance. Combining them yielded significant speedups (up to 85% on AMD), but careful tuning of partition granularity and prefetching distance was essential.

Limitations and Future Work

  • Static Characteristics Focus: The framework primarily considers static memory hierarchy characteristics (capacity, latency, block size). The authors acknowledge that dynamic characteristics (like concurrent threads in multi-tasking systems) are also important and leave their study for future work.
  • Hardware Profile Dependence: While the framework aims to guide tuning, achieving optimal performance still requires careful parameter tuning (e.g., prefetching distance), which can be complex.
  • Future Work: The authors express interest in extending the framework to handle runtime dynamics of memory hierarchies on chip-multiprocessors and adapting cache-conscious algorithms to these dynamic environments. They also suggest exploring the use of hardware profiles for tuning.

Summary updated

BibTeX
@inproceedings{he2007general,
  author = {Bingsheng He and Yinan Li and Qiong Luo and Dongqing Yang},
  title = {{A general framework for improving query processing performance on multi-level memory hierarchies}},
  booktitle = {DaMoN},
  year = {2007},
  doi = {10.1145/1363189.1363193},
}

Loading related content...

Figure