DBScholar

Back to papers

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

Summary: Revisits hash join versus sort-merge join with highly optimized multicore implementations, achieving record CPU throughput and robust performance under skew and varying input sizes. Models predict wider SIMD, more cores, and bandwidth limits will soon favor sort-merge joins. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
hd002d9f853e65366
Venue
VLDB
Year
2009
Pagerank
0.00024851502
Overall Rank
210 | 98.59%
DOI
10.14778/1687553.1687564

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{kim_vldb09,
        title = {{Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs}},
        author = {Kim, Changkyu and Kaldewey, Tim and Lee, Victor W. and Sedlar, Eric and Nguyen, Anthony D. and Satish, Nadathur and Chhugani, Jatin and Di Blas, Andrea and Dubey, Pradeep},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687553.1687564},
        url = {https://doi.org/10.14778/1687553.1687564},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 31 of 81 citing papers.

Rank Citing Paper Year Venue Pagerank
5,884 MCJoin: A Memory-Constrained Join for Column-Store Main-Memory Databases. 2012 SIGMOD 5.9585932e-05
6,091 ThunderRW: An In-Memory Graph Random Walk Engine 2021 VLDB 5.8898055e-05
6,194 Patience is a Virtue: Revisiting Merge and Sort on Modern Processors 2014 SIGMOD 5.8544215e-05
6,213 Data Partitioning for In-Memory Systems: Myths, Challenges, and Opportunities 2019 CIDR 5.8479612e-05
6,288 Elastic Pipelining in an In-Memory Database Cluster 2016 SIGMOD 5.8227911e-05
6,662 UPLIFT: Parallelization Strategies for Feature Transformations in Machine Learning Workloads 2022 VLDB 5.7171651e-05
6,731 What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments 2022 VLDB 5.6939772e-05
7,097 Design and Analysis of a Processing-in-DIMM Join Algorithm: A Case Study with UPMEM DIMMs 2023 SIGMOD 5.601767e-05
7,451 Modularis: Modular Relational Analytics over Heterogeneous Distributed Platforms 2021 VLDB 5.5236802e-05
7,495 Fast Multi-Column Sorting in Main-Memory Column-Stores 2016 SIGMOD 5.5091753e-05
7,814 Analyzing Vectorized Hash Tables Across CPU Architectures 2023 VLDB 5.4482093e-05
7,907 A Practical Approach to Groupjoin and Nested Aggregates 2021 VLDB 5.4287568e-05
7,964 Parallelizing Intra-Window Join on Multicores: An Experimental Study 2021 SIGMOD 5.4165494e-05
8,082 Krypton: Real-time Serving and Analytical SQL Engine at ByteDance 2023 VLDB 5.3942942e-05
8,269 Accelerate Distributed Joins with Predicate Transfer 2025 SIGMOD 5.3648571e-05
8,403 The Case for Learned In-Memory Joins 2023 VLDB 5.3389852e-05
8,493 SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries 2020 SIGMOD 5.3310013e-05
8,673 Adaptive Code Generation for Data-Intensive Analytics 2021 VLDB 5.2913671e-05
9,064 A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory 2023 VLDB 5.2283159e-05
9,429 Efficiently Joining Large Relations on Multi-GPU Systems 2025 VLDB 5.1786456e-05
10,304 Data Chunk Compaction in Vectorized Execution 2025 SIGMOD 5.0400722e-05
10,318 Out-of-order Execution of Database Queries 2020 VLDB 5.0367346e-05
10,601 TQEx: Tensor-based Query Engine Enhanced by Bridging the Gap 2026 SIGMOD 4.9793485e-05
10,830 Bridging the Indexing Gap in Fused GPU Query Engines 2026 VLDB 4.9793485e-05
11,191 Nested Parquet Is Flat, Why Not Use It? How To Scan Nested Data With On-the-Fly Key Generation and Joins 2025 SIGMOD 4.9793485e-05
11,536 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.9793485e-05
11,545 SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs 2024 SIGMOD 4.9793485e-05
11,666 Cache-Efficient Top-k Aggregation over High Cardinality Large Datasets 2024 VLDB 4.9793485e-05
11,750 Cracking-Like Join for Trusted Execution Environments 2023 VLDB 4.9793485e-05
11,865 Scaling Equi-Joins 2022 SIGMOD 4.9793485e-05
11,887 Origami: A High-Performance Mergesort Framework 2022 VLDB 4.9793485e-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
27 Database Architecture Optimized for the New Bottleneck: Memory Access 1999 VLDB 0.0005158963
76 Cache Conscious Algorithms for Relational Query Processing 1994 VLDB 0.00036898845
106 Quickly Generating Billion-Record Synthetic Databases 1994 SIGMOD 0.00033526937
156 Multiprocessor Hash-Based Join Algorithms 1985 VLDB 0.00028522117
223 AlphaSort: A RISC Machine Sort 1994 SIGMOD 0.0002412513
229 A Study of Index Structures for Main Memory Database Management Systems 1986 VLDB 0.00023911856
287 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00021970198
304 GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management 2006 SIGMOD 0.00021604795
616 Relational Joins on Graphics Processors 2008 SIGMOD 0.00015561564
626 Adaptive Aggregation on Chip Multiprocessors 2007 VLDB 0.00015473276
722 Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture 2008 VLDB 0.00014488003
998 What happens during a Join? Dissecting CPU and Memory Optimization Effects 2000 VLDB 0.00012630367
1,254 Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning 1991 VLDB 0.00011330673
1,799 An Adaptive Hash Join Algorithm for Multiuser Environments 1990 VLDB 9.6155018e-05
2,507 Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory 1990 VLDB 8.3723695e-05
2,696 Executing Stream Joins on the Cell Processor 2007 VLDB 8.1205649e-05
2,699 Database Servers on Chip Multiprocessors: Limitations and Opportunities 2007 CIDR 8.1195744e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 4,754 Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor 1991 VLDB
2 2,886 Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment 2021 VLDB
3 2,802 Distributed Join Algorithms on Thousands of Cores 2017 VLDB
4 423 Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems 2012 VLDB
5 249 A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment 1989 SIGMOD
6 156 Multiprocessor Hash-Based Join Algorithms 1985 VLDB
7 2,507 Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory 1990 VLDB
8 3,059 Design and Evaluation of Parallel Pipelined Join Algorithms 1987 SIGMOD
9 251 Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited 2014 VLDB
10 361 Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs 2011 SIGMOD