Accelerating Join-Centric Query Processing with Emerging Large-Scale Memory Technologies
COM1 Level 3
MR1, COM1-03-19
Abstract:
While dynamic random-access memory (DRAM) enabled the shift to high-performance, main-memory database management systems (DBMSs), this paradigm now confronts the "DRAM scaling wall'', where memory capacity and bandwidth lag behind growing workload demands. Emerging technologies such as Non-Volatile Memory (NVM) and Compute Express Link (CXL) offer promising solutions; however, their unique characteristics introduce novel algorithmic challenges within heterogeneous memory systems. This thesis addresses these challenges by optimizing the most critical operations in main-memory DBMSs: join-centric query processing, encompassing both fundamental joins and complex join-aggregate queries.
First, we investigate hash join implementations on NVM. We conduct a design space exploration of two state-of-the-art algorithms, namely Partitioned Hash Join (PHJ) and Non-Partitioned Hash Join (NPHJ), on real hardware to identify principles for NVM-efficient execution. Our analysis reveals that while no single algorithm is universally optimal, PHJ generally outperforms NPHJ in NVM environments.
Next, we examine hash joins on CXL-augmented systems. We demonstrate that while memory interleaving boosts aggregated bandwidth, it is often suboptimal for end-to-end processing due to significant data movement costs. To address this, we develop and propose a novel performance model that quantifies these trade-offs, enabling a paradigm shift toward strategic data migration from CXL memory to DRAM. This approach outperforms static interleaving and proves generalizable to a broader range of data-intensive applications on CXL platforms.
Finally, we address join-aggregate processing, where matrix-multiplication-based methods typically suffer from performance degradation under skewed workloads. This issue is exacerbated on heterogeneous platforms where differing access characteristics lead to cache contention and load imbalance. To overcome these challenges, we propose adaptive morsel scheduling (AMS), a dynamic scheduling framework that simultaneously achieves efficient load balancing and mitigates cache-level contention during execution.
Through these contributions, this thesis provides comprehensive solutions for join-centric query processing using emerging large-scale memory technologies. Our findings demonstrate significant performance gains and establish a new foundation for future memory-intensive system designs.