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: h95185f0561588210
Venue: VLDB
Year: 2015
Pagerank: 0.00012815832
Overall Rank: 963 | 93.53%
DOI: 10.14778/2735496.2735501
PDF: Download (CC BY-NC-ND 3.0)

Incoming Non-self Citations Over Time

Authors

1. R. Barber (IBM)
2. G. Lohman (IBM)
3. I. Pandis (IBM)
4. V. Raman (IBM)
5. R. Sidle (IBM)
6. G. Attaluri (IBM)
7. N. Chainani (IBM)
8. S. Lightstone (IBM)
9. D. Sharpe (IBM)

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,212	A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing	2016	VLDB	0.00011521857
1,267	An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory	2016	SIGMOD	0.00011265987
2,245	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.7615858e-05
2,674	Asynchronous Memory Access Chaining	2016	VLDB	8.1445101e-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,628	Triton Join: Efficiently Scaling to a Large Join State on GPUs with Fast Interconnects	2022	SIGMOD	7.1490678e-05
4,162	Wildfire: Concurrent Blazing Data Ingest and Analytics	2016	SIGMOD	6.7666033e-05
4,371	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	6.6284915e-05
4,760	SQLite: Past, Present, and Future	2022	VLDB	6.4288554e-05
4,796	Permutable Compiled Queries: Dynamically Adapting Compiled Queries without Recompiling	2021	VLDB	6.409726e-05
4,932	FPGA-based Data Partitioning	2017	SIGMOD	6.3455411e-05
5,084	InfiniFilter: Expanding Filters to Infinity and Beyond	2023	SIGMOD	6.2824822e-05
5,144	The 3D Hash Join: Building On Non-Unique Join Attributes	2022	CIDR	6.2542377e-05
5,291	PolarDB-IMCI: A Cloud-Native HTAP Database System at Alibaba	2023	SIGMOD	6.1915052e-05
5,545	Charting the Design Space of Query Execution using VOILA	2021	VLDB	6.0860849e-05
6,419	MorphStore: Analytical Query Engine with a Holistic Compression-Enabled Processing Model	2020	VLDB	5.7886634e-05
6,738	What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments	2022	VLDB	5.6912817e-05
6,763	Guided automated learning for query workload re-optimization	2019	VLDB	5.6870172e-05
7,419	Is Perfect Hashing Practical for OLAP Systems?	2024	CIDR	5.5305461e-05
7,808	Analyzing Vectorized Hash Tables Across CPU Architectures	2023	VLDB	5.448023e-05
7,871	Building Advanced SQL Analytics From Low-Level Plan Operators	2021	SIGMOD	5.434014e-05
7,927	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	5.4234567e-05
7,966	Excalibur: A Virtual Machine for Adaptive Fine-grained JIT-Compiled Query Execution based on VOILA	2023	VLDB	5.4141361e-05
7,968	Parallelizing Intra-Window Join on Multicores: An Experimental Study	2021	SIGMOD	5.4139853e-05
8,275	Accelerate Distributed Joins with Predicate Transfer	2025	SIGMOD	5.3623175e-05
9,073	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB	5.2258409e-05
9,178	Experimental Evaluation of Optimizing Memory Consumption in SAP HANA Using PEOopt	2025	SIGMOD	5.2116787e-05
9,438	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB	5.1761941e-05
11,551	SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs	2024	SIGMOD	4.9769913e-05
11,672	Cache-Efficient Top-k Aggregation over High Cardinality Large Datasets	2024	VLDB	4.9769913e-05
11,756	Cracking-Like Join for Trusted Execution Environments	2023	VLDB	4.9769913e-05
12,176	GALO: Guided Automated Learning for re-Optimization	2019	VLDB	4.9769913e-05

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.00081971778
27	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.00051576613
163	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.00027480091
210	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024844328
215	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD	0.00024589307
251	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023136934
345	R* Optimizer Validation and Performance Evaluation for Distributed Queries	1986	VLDB	0.0002045459
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
997	What happens during a Join? Dissecting CPU and Memory Optimization Effects	2000	VLDB	0.00012628913
1,206	NUMA-aware algorithms: the case of data shuffling	2013	CIDR	0.00011536099
5,881	MCJoin: A Memory-Constrained Join for Column-Store Main-Memory Databases.	2012	SIGMOD	5.9575926e-05

Semantically Similar Papers

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