Memory-Efficient Hash Joins

Summary: Introduces memory-efficient hash joins with a concise hash table (CHT): 100% fill-factor, linear probing and a sparse bitmap to avoid collisions. Adds a build-only partitioning variant and a collision-free concise array table (CAT) for dense keys, delivering 1–3 orders of magnitude memory reduction with competitive performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11148
Venue: VLDB
Year: 2015
Pagerank: 0.00014638492
Overall Rank: 1,016 | 92.94%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 33 of 33 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,696	A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing	2016	VLDB	0.00010881034
1,804	An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory	2016	SIGMOD	0.00010501185
2,742	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.1906104e-05
3,175	Asynchronous Memory Access Chaining	2016	VLDB	7.438501e-05
3,721	To Partition, or Not to Partition, That is the Join Question in a Real System	2021	SIGMOD	6.8179379e-05
3,898	Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment	2021	VLDB	6.6551268e-05
4,624	Wildfire: Concurrent Blazing Data Ingest and Analytics	2016	SIGMOD	6.0411906e-05
5,178	FPGA-based Data Partitioning	2017	SIGMOD	5.6438393e-05
5,247	Triton Join: Efficiently Scaling to a Large Join State on GPUs with Fast Interconnects	2022	SIGMOD	5.6057839e-05
5,530	Permutable Compiled Queries: Dynamically Adapting Compiled Queries without Recompiling	2021	VLDB	5.4554282e-05
5,739	InfiniFilter: Expanding Filters to Infinity and Beyond	2023	SIGMOD	5.3471718e-05
5,765	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	5.336442e-05
5,784	What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments	2022	VLDB	5.328804e-05
6,170	PolarDB-IMCI: A Cloud-Native HTAP Database System at Alibaba	2023	SIGMOD	5.171601e-05
6,192	SQLite: Past, Present, and Future	2022	VLDB	5.1641743e-05
6,221	Charting the Design Space of Query Execution using VOILA	2021	VLDB	5.1512158e-05
6,524	The 3D Hash Join: Building On Non-Unique Join Attributes	2022	CIDR	5.0274964e-05
7,127	Guided automated learning for query workload re-optimization	2019	VLDB	4.8230386e-05
7,335	MorphStore: Analytical Query Engine with a Holistic Compression-Enabled Processing Model	2020	VLDB	4.7603723e-05
7,546	Is Perfect Hashing Practical for OLAP Systems?	2024	CIDR	4.7148429e-05
7,836	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	4.6380835e-05
8,018	Parallelizing Intra-Window Join on Multicores: An Experimental Study	2021	SIGMOD	4.6046381e-05
8,051	Building Advanced SQL Analytics From Low-Level Plan Operators	2021	SIGMOD	4.5969549e-05
8,478	Analyzing Vectorized Hash Tables Across CPU Architectures	2023	VLDB	4.5015937e-05
8,479	Excalibur: A Virtual Machine for Adaptive Fine-grained JIT-Compiled Query Execution based on VOILA	2023	VLDB	4.5014929e-05
8,781	Accelerate Distributed Joins with Predicate Transfer	2025	SIGMOD	4.4534753e-05
8,845	Experimental Evaluation of Optimizing Memory Consumption in SAP HANA Using PEOopt	2025	SIGMOD	4.4374415e-05
8,855	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB	4.4348906e-05
9,838	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB	4.2740344e-05
10,993	SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs	2024	SIGMOD	4.1945683e-05
11,142	Cache-Efficient Top-k Aggregation over High Cardinality Large Datasets	2024	VLDB	4.1945683e-05
11,237	Cracking-Like Join for Trusted Execution Environments	2023	VLDB	4.1945683e-05
11,675	GALO: Guided Automated Learning for re-Optimization	2019	VLDB	4.1945683e-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
9	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.0014279444
52	Database Architecture Optimized for the new Bottleneck: Memory Access	1999	VLDB	0.00066474881
196	R* Optimizer Validation and Performance Evaluation for Distributed Queries	1986	VLDB	0.00035261496
241	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.00031420034
351	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.0002636504
404	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00024143076
418	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD	0.00023729211
540	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.0002063443
585	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00019706145
1,079	What happens during a Join? Dissecting CPU and Memory Optimization Effects	2000	VLDB	0.00014233415
1,543	NUMA-aware algorithms: the case of data shuffling	2013	CIDR	0.0001145318
5,714	MCJoin: A Memory-Constrained Join for Column-Store Main-Memory Databases.	2012	SIGMOD	5.3578116e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,166	Inspector Joins	2005	VLDB	5.6521853e-05
351	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.0002636504
5,906	Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results	2005	VLDB	5.2787348e-05
2,619	Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory	1990	VLDB	8.4431973e-05
8,855	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB	4.4348906e-05
6,524	The 3D Hash Join: Building On Non-Unique Join Attributes	2022	CIDR	5.0274964e-05
10,635	Saving Private Hash Join	2025	VLDB	4.1945683e-05
1,856	An Adaptive Hash Join Algorithm for Multiuser Environments	1990	VLDB	0.00010304993
4,149	Memory-Contention Responsive Hash Joins	1994	VLDB	6.4078379e-05
540	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.0002063443