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
10056
Venue
VLDB
Year
2009
Pagerank
0.00024932174
Overall Rank
209 | 98.57%
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 30 of 80 citing papers.

Rank Citing Paper Year Venue Pagerank
6,113 Patience is a Virtue: Revisiting Merge and Sort on Modern Processors 2014 SIGMOD 5.9715554e-05
6,161 Data Partitioning for In-Memory Systems: Myths, Challenges, and Opportunities 2019 CIDR 5.9537202e-05
6,207 The 3D Hash Join: Building On Non-Unique Join Attributes 2022 CIDR 5.9429869e-05
6,255 Elastic Pipelining in an In-Memory Database Cluster 2016 SIGMOD 5.9399698e-05
6,263 Database Technology for the Masses: Sub-Operators as First-Class Entities 2021 VLDB 5.936052e-05
6,538 UPLIFT: Parallelization Strategies for Feature Transformations in Machine Learning Workloads 2022 VLDB 5.8477764e-05
6,601 What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments 2022 VLDB 5.8246671e-05
6,957 Design and Analysis of a Processing-in-DIMM Join Algorithm: A Case Study with UPMEM DIMMs 2023 SIGMOD 5.7303405e-05
7,242 Fast Multi-Column Sorting in Main-Memory Column-Stores 2016 SIGMOD 5.6641994e-05
7,787 A Practical Approach to Groupjoin and Nested Aggregates 2021 VLDB 5.5449593e-05
7,820 Parallelizing Intra-Window Join on Multicores: An Experimental Study 2021 SIGMOD 5.5373345e-05
7,899 Modularis: Modular Relational Analytics over Heterogeneous Distributed Platforms 2021 VLDB 5.5195553e-05
7,915 Krypton: Real-time Serving and Analytical SQL Engine at ByteDance 2023 VLDB 5.5181056e-05
8,234 The Case for Learned In-Memory Joins 2023 VLDB 5.460955e-05
8,374 SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries 2020 SIGMOD 5.4399097e-05
8,443 Analyzing Vectorized Hash Tables Across CPU Architectures 2023 VLDB 5.4243766e-05
8,636 Adaptive Code Generation for Data-Intensive Analytics 2021 VLDB 5.3954959e-05
8,721 Accelerate Distributed Joins with Predicate Transfer 2025 SIGMOD 5.3772617e-05
8,904 A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory 2023 VLDB 5.3483178e-05
9,333 Efficiently Joining Large Relations on Multi-GPU Systems 2025 VLDB 5.2887551e-05
10,096 Out-of-order Execution of Database Queries 2020 VLDB 5.1523392e-05
10,409 TQEx: Tensor-based Query Engine Enhanced by Bridging the Gap 2026 SIGMOD 5.093636e-05
10,662 Data Chunk Compaction in Vectorized Execution 2025 SIGMOD 5.093636e-05
10,771 Nested Parquet Is Flat, Why Not Use It? How To Scan Nested Data With On-the-Fly Key Generation and Joins 2025 SIGMOD 5.093636e-05
11,194 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 5.093636e-05
11,204 SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs 2024 SIGMOD 5.093636e-05
11,348 Cache-Efficient Top-k Aggregation over High Cardinality Large Datasets 2024 VLDB 5.093636e-05
11,437 Cracking-Like Join for Trusted Execution Environments 2023 VLDB 5.093636e-05
11,556 Scaling Equi-Joins 2022 SIGMOD 5.093636e-05
11,579 Origami: A High-Performance Mergesort Framework 2022 VLDB 5.093636e-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
29 Database Architecture Optimized for the New Bottleneck: Memory Access 1999 VLDB 0.00052093615
74 Cache Conscious Algorithms for Relational Query Processing 1994 VLDB 0.00037330605
105 Quickly Generating Billion-Record Synthetic Databases 1994 SIGMOD 0.00033877899
152 Multiprocessor Hash-Based Join Algorithms 1985 VLDB 0.00029038365
215 AlphaSort: A RISC Machine Sort 1994 SIGMOD 0.00024507963
219 A Study of Index Structures for Main Memory Database Management Systems 1986 VLDB 0.00024293529
293 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00022259273
305 GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management 2006 SIGMOD 0.00021872796
631 Relational Joins on Graphics Processors 2008 SIGMOD 0.00015591241
632 Adaptive Aggregation on Chip Multiprocessors 2007 VLDB 0.00015575286
712 Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture 2008 VLDB 0.0001468812
987 What happens during a Join? Dissecting CPU and Memory Optimization Effects 2000 VLDB 0.00012814017
1,236 Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning 1991 VLDB 0.00011548179
1,779 An Adaptive Hash Join Algorithm for Multiuser Environments 1990 VLDB 9.7764427e-05
2,470 Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory 1990 VLDB 8.5330174e-05
2,655 Executing Stream Joins on the Cell Processor 2007 VLDB 8.2888851e-05
2,679 Database Servers on Chip Multiprocessors: Limitations and Opportunities 2007 CIDR 8.2675008e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 4,668 Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor 1991 VLDB
2 3,134 Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment 2021 VLDB
3 2,926 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 242 A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment 1989 SIGMOD
6 152 Multiprocessor Hash-Based Join Algorithms 1985 VLDB
7 2,470 Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory 1990 VLDB
8 3,011 Design and Evaluation of Parallel Pipelined Join Algorithms 1987 SIGMOD
9 252 Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited 2014 VLDB
10 360 Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs 2011 SIGMOD