DBScholar

Back to papers

Memory-Efficient Hash Joins

Summary: Introduces CHT, a 100%-full linear-probing table using sparse bitmaps and popcounts to suppress collisions, plus collision-free CAT for dense keys. Enables non-/build-only-partitioned joins, reducing memory 10–1000× while matching or exceeding prior methods. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
11336
Venue
VLDB
Year
2015
Pagerank
0.00012953588
Overall Rank
959 | 93.43%
DOI
10.14778/2735496.2735501

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{barber_vldb15,
        title = {{Memory-Efficient Hash Joins}},
        author = {Barber, R. and Lohman, G. and Pandis, I. and Raman, V. and Sidle, R. and Attaluri, G. and Chainani, N. and Lightstone, S. and Sharpe, D.},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {4},
        pages = {353--364},
        doi = {10.14778/2735496.2735501},
        url = {https://doi.org/10.14778/2735496.2735501},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 33 of 33 citing papers.

Rank Citing Paper Year Venue Pagerank
1,265 An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory 2016 SIGMOD 0.00011415709
1,278 A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing 2016 VLDB 0.00011362007
2,250 Cache-Efficient Aggregation: Hashing Is Sorting 2015 SIGMOD 8.8694486e-05
2,649 Asynchronous Memory Access Chaining 2016 VLDB 8.2926258e-05
2,962 To Partition, or Not to Partition, That is the Join Question in a Real System 2021 SIGMOD 7.9170451e-05
3,134 Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment 2021 VLDB 7.7231028e-05
4,162 Wildfire: Concurrent Blazing Data Ingest and Analytics 2016 SIGMOD 6.8617165e-05
4,535 Triton Join: Efficiently Scaling to a Large Join State on GPUs with Fast Interconnects 2022 SIGMOD 6.6419266e-05
4,553 Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries 2024 CIDR 6.6346951e-05
4,840 FPGA-based Data Partitioning 2017 SIGMOD 6.483442e-05
4,960 InfiniFilter: Expanding Filters to Infinity and Beyond 2023 SIGMOD 6.4280133e-05
5,000 Permutable Compiled Queries: Dynamically Adapting Compiled Queries without Recompiling 2021 VLDB 6.4069917e-05
5,284 SQLite: Past, Present, and Future 2022 VLDB 6.2827906e-05
5,477 PolarDB-IMCI: A Cloud-Native HTAP Database System at Alibaba 2023 SIGMOD 6.2051869e-05
5,765 Charting the Design Space of Query Execution using VOILA 2021 VLDB 6.0953705e-05
6,207 The 3D Hash Join: Building On Non-Unique Join Attributes 2022 CIDR 5.9429869e-05
6,601 What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments 2022 VLDB 5.8246671e-05
6,665 MorphStore: Analytical Query Engine with a Holistic Compression-Enabled Processing Model 2020 VLDB 5.8089595e-05
6,938 Guided automated learning for query workload re-optimization 2019 VLDB 5.733869e-05
7,287 Is Perfect Hashing Practical for OLAP Systems? 2024 CIDR 5.6544795e-05
7,760 NOCAP: Near-Optimal Correlation-Aware Partitioning Joins 2023 SIGMOD 5.5505651e-05
7,774 Building Advanced SQL Analytics From Low-Level Plan Operators 2021 SIGMOD 5.5468469e-05
7,820 Parallelizing Intra-Window Join on Multicores: An Experimental Study 2021 SIGMOD 5.5373345e-05
8,368 Excalibur: A Virtual Machine for Adaptive Fine-grained JIT-Compiled Query Execution based on VOILA 2023 VLDB 5.4419148e-05
8,443 Analyzing Vectorized Hash Tables Across CPU Architectures 2023 VLDB 5.4243766e-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,007 Experimental Evaluation of Optimizing Memory Consumption in SAP HANA Using PEOopt 2025 SIGMOD 5.3338237e-05
9,333 Efficiently Joining Large Relations on Multi-GPU Systems 2025 VLDB 5.2887551e-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,870 GALO: Guided Automated Learning for re-Optimization 2019 VLDB 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank Cited Paper Year Venue Pagerank
7 Implementation Techniques For Main Memory Database Systems 1984 SIGMOD 0.00083340894
29 Database Architecture Optimized for the New Bottleneck: Memory Access 1999 VLDB 0.00052093615
165 DB2 with BLU Acceleration: So Much More than Just a Column Store 2013 VLDB 0.00027693424
209 Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs 2009 VLDB 0.00024932174
241 Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age 2014 SIGMOD 0.00023654664
252 Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited 2014 VLDB 0.00023242719
342 R* Optimizer Validation and Performance Evaluation for Distributed Queries 1986 VLDB 0.00020673706
360 Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs 2011 SIGMOD 0.00020182846
423 Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems 2012 VLDB 0.00018725853
987 What happens during a Join? Dissecting CPU and Memory Optimization Effects 2000 VLDB 0.00012814017
1,203 NUMA-aware algorithms: the case of data shuffling 2013 CIDR 0.00011671169
5,812 MCJoin: A Memory-Constrained Join for Column-Store Main-Memory Databases. 2012 SIGMOD 6.0782357e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 5,829 Inspector Joins 2005 VLDB
2 209 Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs 2009 VLDB
3 5,663 Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results 2005 VLDB
4 2,470 Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory 1990 VLDB
5 8,904 A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory 2023 VLDB
6 6,207 The 3D Hash Join: Building On Non-Unique Join Attributes 2022 CIDR
7 10,888 Saving Private Hash Join 2025 VLDB
8 1,779 An Adaptive Hash Join Algorithm for Multiuser Environments 1990 VLDB
9 4,104 Memory-Contention Responsive Hash Joins 1994 VLDB
10 360 Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs 2011 SIGMOD