Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems

Martina-Cezara Albutiu, Alfons Kemper, Thomas Neumann

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.

Impact of NUMA-local vs. remote memory access on different join phases.

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.

Architectural comparison between Wisconsin hash join, Radix join, and MPSM join.

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

Abstract

Two emerging hardware trends will dominate the database system technology in the near future: increasing main memory capacities of several TB per server and massively parallel multi-core processing. Many algorithmic and control techniques in current database technology were devised for disk-based systems where I/O dominated the performance. In this work we take a new look at the well-known sort-merge join which, so far, has not been in the focus of research in scalable massively parallel multi-core data processing as it was deemed inferior to hash joins. We devise a suite of new massively parallel sort-merge (MPSM) join algorithms that are based on partial partition-based sorting. Contrary to classical sort-merge joins, our MPSM algorithms do not rely on a hard to parallelize final merge step to create one complete sort order. Rather they work on the independently created runs in parallel. This way our MPSM algorithms are NUMA-affine as all the sorting is carried out on local memory partitions. An extensive experimental evaluation on a modern 32-core machine with one TB of main memory proves the competitive performance of MPSM on large main memory databases with billions of objects. It scales (almost) linearly in the number of employed cores and clearly outperforms competing hash join proposals - in particular it outperforms the "cutting-edge" Vectorwise parallel query engine by a factor of four.
BibTeX
@article{albutiu2012massively,
  author = {Martina-Cezara Albutiu and Alfons Kemper and Thomas Neumann},
  title = {{Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems}},
  journal = {Proc. VLDB Endow.},
  year = {2012},
  url = {https://openreview.net/forum?id=SfBRzOmwtb},
}
Figure