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: 11149
Venue: VLDB
Year: 2015
Pagerank: 0.00014630024
Overall Rank: 1,016 | 92.95%
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,692	A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing	2016	VLDB	0.00010887129
1,800	An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory	2016	SIGMOD	0.00010494121
2,741	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.1977375e-05
3,179	Asynchronous Memory Access Chaining	2016	VLDB	7.4350144e-05
3,719	To Partition, or Not to Partition, That is the Join Question in a Real System	2021	SIGMOD	6.8141176e-05
3,899	Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment	2021	VLDB	6.6513982e-05
4,619	Wildfire: Concurrent Blazing Data Ingest and Analytics	2016	SIGMOD	6.0376316e-05
5,179	FPGA-based Data Partitioning	2017	SIGMOD	5.6384436e-05
5,251	Triton Join: Efficiently Scaling to a Large Join State on GPUs with Fast Interconnects	2022	SIGMOD	5.6003972e-05
5,540	Permutable Compiled Queries: Dynamically Adapting Compiled Queries without Recompiling	2021	VLDB	5.450319e-05
5,749	InfiniFilter: Expanding Filters to Infinity and Beyond	2023	SIGMOD	5.3420354e-05
5,772	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	5.3313794e-05
5,795	What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments	2022	VLDB	5.3236883e-05
6,154	PolarDB-IMCI: A Cloud-Native HTAP Database System at Alibaba	2023	SIGMOD	5.1795738e-05
6,193	SQLite: Past, Present, and Future	2022	VLDB	5.1593011e-05
6,218	Charting the Design Space of Query Execution using VOILA	2021	VLDB	5.1462707e-05
6,523	The 3D Hash Join: Building On Non-Unique Join Attributes	2022	CIDR	5.0228804e-05
7,126	Guided automated learning for query workload re-optimization	2019	VLDB	4.8184704e-05
7,331	MorphStore: Analytical Query Engine with a Holistic Compression-Enabled Processing Model	2020	VLDB	4.7558046e-05
7,544	Is Perfect Hashing Practical for OLAP Systems?	2024	CIDR	4.710321e-05
7,842	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	4.6336361e-05
8,021	Parallelizing Intra-Window Join on Multicores: An Experimental Study	2021	SIGMOD	4.600223e-05
8,053	Building Advanced SQL Analytics From Low-Level Plan Operators	2021	SIGMOD	4.5925468e-05
8,476	Analyzing Vectorized Hash Tables Across CPU Architectures	2023	VLDB	4.4972784e-05
8,477	Excalibur: A Virtual Machine for Adaptive Fine-grained JIT-Compiled Query Execution based on VOILA	2023	VLDB	4.4971772e-05
8,777	Accelerate Distributed Joins with Predicate Transfer	2025	SIGMOD	4.4492064e-05
8,845	Experimental Evaluation of Optimizing Memory Consumption in SAP HANA Using PEOopt	2025	SIGMOD	4.4331879e-05
8,855	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB	4.4306395e-05
9,837	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB	4.269939e-05
10,996	SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs	2024	SIGMOD	4.1905499e-05
11,145	Cache-Efficient Top-k Aggregation over High Cardinality Large Datasets	2024	VLDB	4.1905499e-05
11,239	Cracking-Like Join for Trusted Execution Environments	2023	VLDB	4.1905499e-05
11,680	GALO: Guided Automated Learning for re-Optimization	2019	VLDB	4.1905499e-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.001426258
52	Database Architecture Optimized for the new Bottleneck: Memory Access	1999	VLDB	0.00066322421
196	R* Optimizer Validation and Performance Evaluation for Distributed Queries	1986	VLDB	0.00035240105
241	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.00031314629
350	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00026368305
403	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00024176677
417	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD	0.00023734582
538	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00020632609
584	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00019700451
1,077	What happens during a Join? Dissecting CPU and Memory Optimization Effects	2000	VLDB	0.00014224986
1,540	NUMA-aware algorithms: the case of data shuffling	2013	CIDR	0.00011451745
5,723	MCJoin: A Memory-Constrained Join for Column-Store Main-Memory Databases.	2012	SIGMOD	5.3530385e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,165	Inspector Joins	2005	VLDB	5.6477024e-05
350	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00026368305
5,916	Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results	2005	VLDB	5.269117e-05
2,622	Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory	1990	VLDB	8.4404954e-05
8,855	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB	4.4306395e-05
6,523	The 3D Hash Join: Building On Non-Unique Join Attributes	2022	CIDR	5.0228804e-05
10,643	Saving Private Hash Join	2025	VLDB	4.1905499e-05
1,861	An Adaptive Hash Join Algorithm for Multiuser Environments	1990	VLDB	0.00010297093
4,149	Memory-Contention Responsive Hash Joins	1994	VLDB	6.4043572e-05
538	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00020632609