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.0001278184
Overall Rank: 969 | 93.49%
DOI: 10.14778/2735496.2735501

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,266	An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory	2016	SIGMOD	0.00011269175
1,283	A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing	2016	VLDB	0.00011209209
2,245	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.7649358e-05
2,673	Asynchronous Memory Access Chaining	2016	VLDB	8.1482775e-05
2,818	To Partition, or Not to Partition, That is the Join Question in a Real System	2021	SIGMOD	7.9739791e-05
2,886	Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment	2021	VLDB	7.9081605e-05
3,626	Triton Join: Efficiently Scaling to a Large Join State on GPUs with Fast Interconnects	2022	SIGMOD	7.1524537e-05
4,162	Wildfire: Concurrent Blazing Data Ingest and Analytics	2016	SIGMOD	6.769737e-05
4,369	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	6.6315141e-05
4,758	SQLite: Past, Present, and Future	2022	VLDB	6.4318211e-05
4,793	Permutable Compiled Queries: Dynamically Adapting Compiled Queries without Recompiling	2021	VLDB	6.4127583e-05
4,931	FPGA-based Data Partitioning	2017	SIGMOD	6.348544e-05
5,081	InfiniFilter: Expanding Filters to Infinity and Beyond	2023	SIGMOD	6.2854372e-05
5,142	The 3D Hash Join: Building On Non-Unique Join Attributes	2022	CIDR	6.2571095e-05
5,288	PolarDB-IMCI: A Cloud-Native HTAP Database System at Alibaba	2023	SIGMOD	6.1944376e-05
5,543	Charting the Design Space of Query Execution using VOILA	2021	VLDB	6.0889645e-05
6,417	MorphStore: Analytical Query Engine with a Holistic Compression-Enabled Processing Model	2020	VLDB	5.791405e-05
6,731	What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments	2022	VLDB	5.6939772e-05
6,764	Guided automated learning for query workload re-optimization	2019	VLDB	5.6873334e-05
7,416	Is Perfect Hashing Practical for OLAP Systems?	2024	CIDR	5.5331654e-05
7,814	Analyzing Vectorized Hash Tables Across CPU Architectures	2023	VLDB	5.4482093e-05
7,866	Building Advanced SQL Analytics From Low-Level Plan Operators	2021	SIGMOD	5.4365876e-05
7,923	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	5.4260253e-05
7,962	Excalibur: A Virtual Machine for Adaptive Fine-grained JIT-Compiled Query Execution based on VOILA	2023	VLDB	5.4167003e-05
7,964	Parallelizing Intra-Window Join on Multicores: An Experimental Study	2021	SIGMOD	5.4165494e-05
8,269	Accelerate Distributed Joins with Predicate Transfer	2025	SIGMOD	5.3648571e-05
9,064	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB	5.2283159e-05
9,168	Experimental Evaluation of Optimizing Memory Consumption in SAP HANA Using PEOopt	2025	SIGMOD	5.214147e-05
9,429	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB	5.1786456e-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
12,170	GALO: Guided Automated Learning for re-Optimization	2019	VLDB	4.9793485e-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.00081992507
27	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.0005158963
163	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.0002749118
210	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024851502
215	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD	0.00024598661
251	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023143736
344	R* Optimizer Validation and Performance Evaluation for Distributed Queries	1986	VLDB	0.00020461727
361	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00020006406
423	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00018491327
998	What happens during a Join? Dissecting CPU and Memory Optimization Effects	2000	VLDB	0.00012630367
1,206	NUMA-aware algorithms: the case of data shuffling	2013	CIDR	0.00011541214
5,884	MCJoin: A Memory-Constrained Join for Column-Store Main-Memory Databases.	2012	SIGMOD	5.9585932e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,922	Inspector Joins	2005	VLDB
2	210	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB
3	5,452	Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results	2005	VLDB
4	2,507	Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory	1990	VLDB
5	9,064	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB
6	5,142	The 3D Hash Join: Building On Non-Unique Join Attributes	2022	CIDR
7	9,566	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	361	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD