DBScholar

Back to papers

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

Summary: Introduces NUMA-affine massively parallel sort-merge joins using partial partition-based sorting, avoiding the traditionally serial final merge. On 1-TB/32-core hardware, MPSM scales nearly linearly and beats state-of-the-art parallel hash joins by up to 4×. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
hdaff7d266f3c8fbb
Venue
VLDB
Year
2012
Pagerank
0.00018485358
Overall Rank
425 | 97.15%
DOI
10.14778/2336664.2336675

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{albutiu_vldb12,
        title = {{Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems}},
        author = {Albutiu, Martina-Cezara and Kemper, Alfons and Neumann, Thomas},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {10},
        pages = {1064--1075},
        doi = {10.14778/2336664.2336675},
        url = {https://doi.org/10.14778/2336664.2336675},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 53 citing papers.

Rank Citing Paper Year Venue Pagerank
163 DB2 with BLU Acceleration: So Much More than Just a Column Store 2013 VLDB 0.00027480091
215 Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age 2014 SIGMOD 0.00024589307
251 Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited 2014 VLDB 0.00023136934
627 Rethinking SIMD Vectorization for In-Memory Databases 2015 SIGMOD 0.00015454197
685 Trill: A High-Performance Incremental Query Processor for Diverse Analytics 2015 VLDB 0.00014778299
890 Rack-Scale In-Memory Join Processing using RDMA 2015 SIGMOD 0.00013241413
963 Memory-Efficient Hash Joins 2015 VLDB 0.00012815832
1,028 High-Speed Query Processing over High-Speed Networks 2016 VLDB 0.00012416417
1,116 A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort 2014 SIGMOD 0.00011957053
1,167 DimmWitted: A Study of Main-Memory Statistical Analytics 2014 VLDB 0.0001172597
1,206 NUMA-aware algorithms: the case of data shuffling 2013 CIDR 0.00011536099
1,267 An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory 2016 SIGMOD 0.00011265987
1,534 Pipelined Query Processing in Coprocessor Environments 2018 SIGMOD 0.00010327147
1,997 Track Join: Distributed Joins with Minimal Network Traffic 2014 SIGMOD 9.2126022e-05
2,245 Cache-Efficient Aggregation: Hashing Is Sorting 2015 SIGMOD 8.7615858e-05
2,487 A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs 2017 SIGMOD 8.3939994e-05
2,674 Asynchronous Memory Access Chaining 2016 VLDB 8.1445101e-05
2,802 Distributed Join Algorithms on Thousands of Cores 2017 VLDB 7.9866934e-05
2,818 To Partition, or Not to Partition, That is the Join Question in a Real System 2021 SIGMOD 7.9703078e-05
2,887 Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment 2021 VLDB 7.9044174e-05
3,374 A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms 2016 SIGMOD 7.3606793e-05
4,012 Deployment of Query Plans on Multicores 2015 VLDB 6.8540959e-05
4,056 Scaling Up Concurrent Main-Memory Column-Store Scans: Towards Adaptive NUMA-aware Data and Task Placement 2015 VLDB 6.8239192e-05
4,138 The Art of Balance: A RateupDB Experience of Building a CPU/GPU Hybrid Database Product 2021 VLDB 6.782996e-05
4,704 Adaptive NUMA-aware data placement and task scheduling for analytical workloads in main-memory column-stores 2017 VLDB 6.4600076e-05
4,732 MQJoin: Efficient Shared Execution of Main-Memory Joins 2016 VLDB 6.4439712e-05
5,144 The 3D Hash Join: Building On Non-Unique Join Attributes 2022 CIDR 6.2542377e-05
5,545 Charting the Design Space of Query Execution using VOILA 2021 VLDB 6.0860849e-05
5,629 FPGA-based Multithreading for In-Memory Hash Joins 2015 CIDR 6.0574868e-05
5,827 Design and Evaluation of Storage Organizations for Read-Optimized Main Memory Databases 2013 VLDB 5.9772416e-05
6,197 Patience is a Virtue: Revisiting Merge and Sort on Modern Processors 2014 SIGMOD 5.8518899e-05
6,216 Data Partitioning for In-Memory Systems: Myths, Challenges, and Opportunities 2019 CIDR 5.8451996e-05
6,291 Elastic Pipelining in an In-Memory Database Cluster 2016 SIGMOD 5.8200348e-05
6,417 Evaluating Multi-GPU Sorting with Modern Interconnects 2022 SIGMOD 5.7900099e-05
6,662 A Morsel-Driven Query Execution Engine for Heterogeneous Multi-Cores 2019 VLDB 5.7155423e-05
6,666 UPLIFT: Parallelization Strategies for Feature Transformations in Machine Learning Workloads 2022 VLDB 5.7144587e-05
7,099 Design and Analysis of a Processing-in-DIMM Join Algorithm: A Case Study with UPMEM DIMMs 2023 SIGMOD 5.5991152e-05
7,473 Fast Multi-Column Sorting in Main-Memory Column-Stores 2016 SIGMOD 5.5162245e-05
7,871 Building Advanced SQL Analytics From Low-Level Plan Operators 2021 SIGMOD 5.434014e-05
7,927 NOCAP: Near-Optimal Correlation-Aware Partitioning Joins 2023 SIGMOD 5.4234567e-05
7,968 Parallelizing Intra-Window Join on Multicores: An Experimental Study 2021 SIGMOD 5.4139853e-05
8,089 Krypton: Real-time Serving and Analytical SQL Engine at ByteDance 2023 VLDB 5.3917406e-05
8,402 The Case for Learned In-Memory Joins 2023 VLDB 5.3375308e-05
8,860 SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms 2023 VLDB 5.2620362e-05
9,438 Efficiently Joining Large Relations on Multi-GPU Systems 2025 VLDB 5.1761941e-05
9,465 How to Stop Under-Utilization and Love Multicores 2014 SIGMOD 5.1710564e-05
9,561 Engineering High-Performance Database Engines 2014 VLDB 5.1561699e-05
9,829 BlockJoin: Efficient Matrix Partitioning Through Joins 2017 VLDB 5.1230568e-05
10,325 Out-of-order Execution of Database Queries 2020 VLDB 5.0343502e-05
10,677 P-MOSS: Scheduling Main-Memory Indexes Over NUMA Servers Using Next Token Prediction 2026 SIGMOD 4.9769913e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
21 Efficiently Compiling Efficient Query Plans for Modern Hardware 2011 VLDB 0.00056835296
27 Database Architecture Optimized for the New Bottleneck: Memory Access 1999 VLDB 0.00051576613
210 Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs 2009 VLDB 0.00024844328
362 Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs 2011 SIGMOD 0.00019999596
490 Practical Skew Handling in Parallel Joins 1992 VLDB 0.00017433989
616 Relational Joins on Graphics Processors 2008 SIGMOD 0.00015554627
702 Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct 2009 VLDB 0.00014668058
723 Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture 2008 VLDB 0.00014507399
1,388 How Soccer Players Would do Stream Joins 2011 SIGMOD 0.00010820564
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 4,757 Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor 1991 VLDB
2 2,887 Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment 2021 VLDB
3 4,732 MQJoin: Efficient Shared Execution of Main-Memory Joins 2016 VLDB
4 9,438 Efficiently Joining Large Relations on Multi-GPU Systems 2025 VLDB
5 1,116 A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort 2014 SIGMOD
6 2,802 Distributed Join Algorithms on Thousands of Cores 2017 VLDB
7 3,062 Design and Evaluation of Parallel Pipelined Join Algorithms 1987 SIGMOD
8 210 Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs 2009 VLDB
9 362 Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs 2011 SIGMOD
10 251 Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited 2014 VLDB