Abstract
As main memory capacities reach terabytes and multi-core processors become the norm, traditional database join algorithms face new bottlenecks. This paper introduces MPSM (Massively Parallel Sort-Merge), a join algorithm redesigned for modern hardware. By prioritizing NUMA-affinity and replacing global synchronization with local processing and sequential remote reads, MPSM achieves near-linear scalability. Experimental results show it outperforms state-of-the-art hash joins and commercial engines like Vectorwise by up to 4x.
The NUMA Challenge in Modern Systems
In modern servers, the primary performance bottleneck has shifted from Disk I/O to memory bandwidth and CPU utilization. Modern architectures utilize Non-Uniform Memory Access (NUMA), where local RAM access is significantly faster than accessing RAM attached to a different processor socket.
Traditional hash joins struggle in this environment due to random memory accesses across NUMA boundaries when probing large hash tables. Furthermore, building shared hash tables often requires expensive synchronization that limits parallelism.
As shown in the figure above, remote memory access imposes a massive penalty on sorting and partitioning. However, sequential reads (as seen in the merge join phase) are much more resilient to NUMA boundaries because hardware prefetchers can effectively hide the latency. MPSM leverages this by turning the join into a series of sequential scans.
The MPSM Algorithm
The authors propose a suite of MPSM algorithms based on three core principles for NUMA-aware design: write locally, read remote memory sequentially, and avoid fine-grained synchronization. Unlike traditional sort-merge joins that attempt to create a single global sort order—a major parallelization bottleneck—MPSM works on independently created runs in parallel.
Key Variants and Innovations
- P-MPSM (Partitioned): This variant uses range-partitioning to ensure each worker only joins its local chunk with relevant portions of the public input.
- Interpolation Search: Workers use interpolation search to rapidly locate join ranges within sorted runs, avoiding redundant scanning.
- Skew Resilience: MPSM uses Cumulative Distribution Functions (CDFs) to calculate dynamic "splitters," ensuring balanced workloads even with heavily skewed data.
Performance and Scalability
Evaluation on a 32-core server with 1 TB of RAM demonstrated that MPSM scales almost linearly with the number of cores. The algorithm's performance only plateaus when reaching the limits of physical execution units during hyper-threading.
Key results include:
- 4x Speedup: P-MPSM outperformed the "cutting-edge" Vectorwise engine by a factor of four on large-scale joins.
- NUMA Sensitivity: Ignoring NUMA boundaries during sorting resulted in a 3x performance penalty, validating the algorithm's NUMA-affine design.
- Robustness: The CDF-based splitter logic maintained balanced execution times across various data distributions, whereas static partitioning would have left cores idle.
Conclusion
MPSM demonstrates that sort-merge joins are highly effective on modern multi-core NUMA systems when implemented with hardware-conscious principles. By favoring sequential access and local writes, MPSM overcomes the scalability limits of traditional hash-based approaches. Future work includes integrating SIMD instructions for faster local sorting and extending the algorithm to support a broader range of join types, such as outer and semi-joins.
Summary updated