Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment

Summary: Multi-GPU join algorithms for very large tables; three designs: nested-loop, global-sort-merge, hybrid. Addresses CPU–GPU data-transfer bottlenecks; shows scalability and up to 25× vs multi-core CPU and 2.8× vs single-GPU. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h4f765816a95b6a48
Venue: VLDB
Year: 2021
Pagerank: 7.9044174e-05
Overall Rank: 2,887 | 80.60%
DOI: 10.14778/3436905.3436927
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Ran Rui (University of South Florida)
2. Hao Li (University of South Florida)
3. Yi-Cheng Tu (University of South Florida)

BibTeX Citation

@article{rui_vldb21,
        title = {{Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment}},
        author = {Rui, Ran and Li, Hao and Tu, Yi-Cheng},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {4},
        pages = {708--720},
        doi = {10.14778/3436905.3436927},
        url = {https://doi.org/10.14778/3436905.3436927},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,628	Triton Join: Efficiently Scaling to a Large Join State on GPUs with Fast Interconnects	2022	SIGMOD	7.1490678e-05
3,657	Tile-based Lightweight Integer Compression in GPU	2022	SIGMOD	7.1227107e-05
3,691	RTIndex: Exploiting Hardware-Accelerated GPU Raytracing for Database Indexing	2023	VLDB	7.0909492e-05
3,888	Orchestrating Data Placement and Query Execution in Heterogeneous CPU-GPU DBMS	2022	VLDB	6.942437e-05
4,138	The Art of Balance: A RateupDB Experience of Building a CPU/GPU Hybrid Database Product	2021	VLDB	6.782996e-05
5,376	Distributed GPU Joins on Fast RDMA-capable Networks	2023	SIGMOD	6.1555648e-05
5,543	Vortex: Overcoming Memory Capacity Limitations in GPU-Accelerated Large-Scale Data Analytics	2025	VLDB	6.0873423e-05
5,616	BOSS - An Architecture for Database Kernel Composition	2024	VLDB	6.0623704e-05
6,153	Efficiently Processing Joins and Grouped Aggregations on GPUs	2025	SIGMOD	5.8669913e-05
6,417	Evaluating Multi-GPU Sorting with Modern Interconnects	2022	SIGMOD	5.7900099e-05
6,671	Powerful GPUs or Fast Interconnects: Analyzing Relational Workloads on Modern GPUs	2025	VLDB	5.7125893e-05
7,099	Design and Analysis of a Processing-in-DIMM Join Algorithm: A Case Study with UPMEM DIMMs	2023	SIGMOD	5.5991152e-05
8,242	Scaling your Hybrid CPU-GPU DBMS to Multiple GPUs	2024	VLDB	5.3684987e-05
8,280	Scaling GPU-Accelerated Databases beyond GPU Memory Size	2025	VLDB	5.3616863e-05
8,602	A Case for Graphics-driven Query Processing	2023	VLDB	5.3037284e-05
9,438	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB	5.1761941e-05
9,870	GPU Acceleration of SQL Analytics on Compressed Data	2026	VLDB	5.115241e-05
10,047	MEMO: Fine-grained Tensor Management For Ultra-long Context LLM Training	2025	SIGMOD	5.0896901e-05
10,733	Scalable GPU Acceleration of Scalar Functions in Analytical Databases: Compilation, Benchmarking, and Optimization	2026	VLDB	4.9769913e-05
10,914	ZipFlow: a Compiler-based Framework to Unleash Compressed Data Movement for Modern GPUs	2026	VLDB	4.9769913e-05
10,915	RayBooster: A Ray Tracing Engine to Accelerate SedonaDB	2026	VLDB	4.9769913e-05
11,871	Scaling Equi-Joins	2022	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
210	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024844328
251	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023136934
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
616	Relational Joins on Graphics Processors	2008	SIGMOD	0.00015554627
775	The Yin and Yang of Processing Data Warehousing Queries on GPU Devices	2013	VLDB	0.0001407924
963	Memory-Efficient Hash Joins	2015	VLDB	0.00012815832
2,124	Revisiting Co-Processing for Hash Joins on the Coupled CPU-GPU Architecture	2013	VLDB	9.0041425e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	210	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB
2	3,062	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD
3	1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
4	2,138	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
5	5,429	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD
6	5,376	Distributed GPU Joins on Fast RDMA-capable Networks	2023	SIGMOD
7	3,628	Triton Join: Efficiently Scaling to a Large Join State on GPUs with Fast Interconnects	2022	SIGMOD
8	6,153	Efficiently Processing Joins and Grouped Aggregations on GPUs	2025	SIGMOD
9	616	Relational Joins on Graphics Processors	2008	SIGMOD
10	9,438	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB