Database Paper Browser

Back to papers

Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs

Summary: Revisits hash join vs sort-merge join on modern multi-core CPUs with optimized parallel implementations. Hash join hits >100M tuples/s on Intel Core i7; sort-merge delivers 47–80M. Analytical models indicate wider SIMD and more cores favor sort-merge, suggesting future architectures may swing dominance away from hash. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
9866
Venue
VLDB
Year
2009
Pagerank
0.00026368305
Overall Rank
350 | 97.57%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 30 of 80 citing papers.

Rank Citing Paper Year Venue Pagerank
6,218 Charting the Design Space of Query Execution using VOILA 2021 VLDB 5.1462707e-05
6,301 Elastic Pipelining in an In-Memory Database Cluster 2016 SIGMOD 5.1172165e-05
6,416 Patience is a Virtue: Revisiting Merge and Sort on Modern Processors 2014 SIGMOD 5.0645953e-05
6,523 The 3D Hash Join: Building On Non-Unique Join Attributes 2022 CIDR 5.0228804e-05
6,525 Database Technology for the Masses: Sub-Operators as First-Class Entities 2021 VLDB 5.0223854e-05
6,538 Data Partitioning for In-Memory Systems: Myths, Challenges, and Opportunities 2019 CIDR 5.0173391e-05
7,095 Fast Multi-Column Sorting in Main-Memory Column-Stores 2016 SIGMOD 4.8289712e-05
7,491 Krypton: Real-time Serving and Analytical SQL Engine at ByteDance 2023 VLDB 4.7135369e-05
8,021 Parallelizing Intra-Window Join on Multicores: An Experimental Study 2021 SIGMOD 4.600223e-05
8,098 Modularis: Modular Relational Analytics over Heterogeneous Distributed Platforms 2021 VLDB 4.5824106e-05
8,411 The Case for Learned In-Memory Joins 2023 VLDB 4.5151296e-05
8,423 SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries 2020 SIGMOD 4.5112315e-05
8,476 Analyzing Vectorized Hash Tables Across CPU Architectures 2023 VLDB 4.4972784e-05
8,515 UPLIFT: Parallelization Strategies for Feature Transformations in Machine Learning Workloads 2022 VLDB 4.4901466e-05
8,623 Adaptive Code Generation for Data-Intensive Analytics 2021 VLDB 4.4786182e-05
8,676 A Practical Approach to Groupjoin and Nested Aggregates 2021 VLDB 4.4652082e-05
8,777 Accelerate Distributed Joins with Predicate Transfer 2025 SIGMOD 4.4492064e-05
8,855 A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory 2023 VLDB 4.4306395e-05
9,143 Design and Analysis of a Processing-in-DIMM Join Algorithm: A Case Study with UPMEM DIMMs 2023 SIGMOD 4.381112e-05
9,837 Efficiently Joining Large Relations on Multi-GPU Systems 2025 VLDB 4.269939e-05
9,939 Out-of-order Execution of Database Queries 2020 VLDB 4.2416883e-05
10,121 TQEx: Tensor-based Query Engine Enhanced by Bridging the Gap 2026 SIGMOD 4.1905499e-05
10,384 Data Chunk Compaction in Vectorized Execution 2025 SIGMOD 4.1905499e-05
10,504 Nested Parquet Is Flat, Why Not Use It? How To Scan Nested Data With On-the-Fly Key Generation and Joins 2025 SIGMOD 4.1905499e-05
10,984 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.1905499e-05
10,996 SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs 2024 SIGMOD 4.1905499e-05
11,145 Cache-Efficient Top-k Aggregation over High Cardinality Large Datasets 2024 VLDB 4.1905499e-05
11,239 Cracking-Like Join for Trusted Execution Environments 2023 VLDB 4.1905499e-05
11,360 Scaling Equi-Joins 2022 SIGMOD 4.1905499e-05
11,383 Origami: A High-Performance Mergesort Framework 2022 VLDB 4.1905499e-05
Previous Page 2 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank Cited Paper Year Venue Pagerank
52 Database Architecture Optimized for the new Bottleneck: Memory Access 1999 VLDB 0.00066322421
77 Multiprocessor Hash-Based Join Algorithms 1985 VLDB 0.00056488357
81 Cache Conscious Algorithms for Relational Query Processing 1994 VLDB 0.00055253195
85 AlphaSort: A RISC Machine Sort 1994 SIGMOD 0.00053652634
145 Quickly Generating Billion-Record Synthetic Databases 1994 SIGMOD 0.00041403894
235 A Study of Index Structures for Main Memory Database Management Systems 1986 VLDB 0.00031980259
238 GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management 2006 SIGMOD 0.00031596093
343 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00026756534
711 Adaptive Aggregation on Chip Multiprocessors 2007 VLDB 0.00017724982
771 Relational Joins on Graphics Processors 2008 SIGMOD 0.00016813054
944 Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture 2008 VLDB 0.0001512998
1,077 What happens during a Join? Dissecting CPU and Memory Optimization Effects 2000 VLDB 0.00014224986
1,355 Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning 1991 VLDB 0.00012417228
1,861 An Adaptive Hash Join Algorithm for Multiuser Environments 1990 VLDB 0.00010297093
2,622 Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory 1990 VLDB 8.4404954e-05
2,768 Executing Stream Joins on the Cell Processor 2007 VLDB 8.1518597e-05
2,782 Database Servers on Chip Multiprocessors: Limitations and Opportunities 2007 CIDR 8.1278531e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
4,398 Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor 1991 VLDB 6.2137073e-05
3,899 Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment 2021 VLDB 6.6513982e-05
3,428 Distributed Join Algorithms on Thousands of Cores 2017 VLDB 7.1002401e-05
584 Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems 2012 VLDB 0.00019700451
230 A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment 1989 SIGMOD 0.00032145125
77 Multiprocessor Hash-Based Join Algorithms 1985 VLDB 0.00056488357
2,622 Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory 1990 VLDB 8.4404954e-05
2,599 Design and Evaluation of Parallel Pipelined Join Algorithms 1987 SIGMOD 8.4655075e-05
403 Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited 2014 VLDB 0.00024176677
538 Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs 2011 SIGMOD 0.00020632609