DBScholar

Back to papers

Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited

Summary: Extensive multi-core/NUMA experiments overturn claims that SIMD and NUMA favor sort-merge: optimized radix-hash join remains clearly faster, except at very large scale. Provides state-of-the-art implementations and hardware insights for parallel operators. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h8b5d1916826b4eb5
Venue
VLDB
Year
2014
Pagerank
0.00023136934
Overall Rank
251 | 98.32%
DOI
10.14778/2732232.2732236

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{balkesen_vldb14,
        title = {{Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited}},
        author = {Balkesen, Cagri and Alonso, Gustavo and Teubner, Jens and Özsu, M. Tamer},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {1},
        pages = {85--96},
        doi = {10.14778/2732232.2732236},
        url = {https://doi.org/10.14778/2732232.2732236},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 82 citing papers.

Rank Citing Paper Year Venue Pagerank
215 Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age 2014 SIGMOD 0.00024589307
627 Rethinking SIMD Vectorization for In-Memory Databases 2015 SIGMOD 0.00015454197
712 Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan 2016 VLDB 0.00014593534
890 Rack-Scale In-Memory Join Processing using RDMA 2015 SIGMOD 0.00013241413
945 The End of Slow Networks: It's Time for a Redesign 2016 VLDB 0.00012933247
963 Memory-Efficient Hash Joins 2015 VLDB 0.00012815832
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,267 An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory 2016 SIGMOD 0.00011265987
1,269 A Study of the Fundamental Performance Characteristics of GPUs and CPUs for Database Analytics 2020 SIGMOD 0.00011254742
1,718 ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout 2015 SIGMOD 9.7983307e-05
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,423 Parallel Data Analysis Directly on Scientific File Formats 2014 SIGMOD 8.4851588e-05
2,487 A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs 2017 SIGMOD 8.3939994e-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,189 Extracting Top-K Insights from Multi-dimensional Data 2017 SIGMOD 7.5499689e-05
3,358 RUMA has it: Rewired User-space Memory Access is Possible! 2016 VLDB 7.377868e-05
3,458 Improving Main Memory Hash Joins on Intel Xeon Phi Processors: An Experimental Approach 2015 VLDB 7.2815031e-05
3,505 Fast Queries Over Heterogeneous Data Through Engine Customization 2016 VLDB 7.2474175e-05
3,628 Triton Join: Efficiently Scaling to a Large Join State on GPUs with Fast Interconnects 2022 SIGMOD 7.1490678e-05
3,658 Maximizing Persistent Memory Bandwidth Utilization for OLAP Workloads 2021 SIGMOD 7.1211998e-05
3,708 The Case for a Learned Sorting Algorithm 2020 SIGMOD 7.0781032e-05
3,775 Hardware-conscious Query Processing in GPU-accelerated Analytical Engines 2019 CIDR 7.0261504e-05
3,955 Tensors: An abstraction for general data processing 2021 VLDB 6.8994712e-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,065 PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort 2015 VLDB 6.8199976e-05
4,138 The Art of Balance: A RateupDB Experience of Building a CPU/GPU Hybrid Database Product 2021 VLDB 6.782996e-05
4,225 SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures 2015 VLDB 6.7180565e-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
4,932 FPGA-based Data Partitioning 2017 SIGMOD 6.3455411e-05
5,134 Holistic Indexing in Main-memory Column-stores 2015 SIGMOD 6.2573427e-05
5,144 The 3D Hash Join: Building On Non-Unique Join Attributes 2022 CIDR 6.2542377e-05
5,180 On the Surprising Difficulty of Simple Things: the Case of Radix Partitioning 2015 VLDB 6.2379001e-05
5,376 Distributed GPU Joins on Fast RDMA-capable Networks 2023 SIGMOD 6.1555648e-05
5,500 Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations 2022 VLDB 6.1020763e-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
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,419 MorphStore: Analytical Query Engine with a Holistic Compression-Enabled Processing Model 2020 VLDB 5.7886634e-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
6,738 What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments 2022 VLDB 5.6912817e-05
7,099 Design and Analysis of a Processing-in-DIMM Join Algorithm: A Case Study with UPMEM DIMMs 2023 SIGMOD 5.5991152e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank Cited Paper Year Venue Pagerank
54 GAMMA - A High Performance Dataflow Database Machine 1986 VLDB 0.00040482761
76 Cache Conscious Algorithms for Relational Query Processing 1994 VLDB 0.00036891569
82 Hashing Methods and Relational Algebra Operations 1984 VLDB 0.00036042975
210 Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs 2009 VLDB 0.00024844328
249 A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment 1989 SIGMOD 0.0002316492
362 Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs 2011 SIGMOD 0.00019999596
425 Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems 2012 VLDB 0.00018485358
657 An Overview of The System Software of A Parallel Relational Database Machine GRACE 1986 VLDB 0.0001506334
663 Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort 2010 SIGMOD 0.00014997516
723 Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture 2008 VLDB 0.00014507399
1,206 NUMA-aware algorithms: the case of data shuffling 2013 CIDR 0.00011536099
2,161 CellSort: High Performance Sorting on the Cell Processor 2007 VLDB 8.9349355e-05
3,393 CloudRAMSort: Fast and Efficient Large-Scale Distributed RAM Sort on Shared-Nothing Cluster 2012 SIGMOD 7.343863e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 9,073 A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory 2023 VLDB
2 156 Multiprocessor Hash-Based Join Algorithms 1985 VLDB
3 1,267 An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory 2016 SIGMOD
4 2,508 Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory 1990 VLDB
5 249 A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment 1989 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 425 Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems 2012 VLDB
9 362 Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs 2011 SIGMOD
10 210 Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs 2009 VLDB