Efficient Massively Parallel Join Optimization for Large Queries*

Summary: MPDP is a massively parallel join-optimization algorithm that prunes huge search spaces through a novel plan enumeration on GPUs. Benchmarks show ≥10× speedups over prior work, extend the heuristic fallback to 25 relations, and, with IDP2 and UnionDP, yield up to 7× cheaper plans. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hd6b635fa01190fd7
Venue: SIGMOD
Year: 2022
Pagerank: 6.1349269e-05
Overall Rank: 5,425 | 63.53%
DOI: 10.1145/3514221.3517871

Incoming Non-self Citations Over Time

Authors

1. Riccardo Mancini (Scuola Superiore Sant'Anna)
2. Srinivas Karthik (EPFL)
3. Bikash Chandra (EPFL)
4. Vasilis Mageirakos (University of Patras)
5. Anastasia Ailamaki (EPFL; RAW Labs)

BibTeX Citation

@inproceedings{mancini_sigmod22,
        title = {{Efficient Massively Parallel Join Optimization for Large Queries*}},
        author = {Mancini, Riccardo and Karthik, Srinivas and Chandra, Bikash and Mageirakos, Vasilis and Ailamaki, Anastasia},
        series = {{SIGMOD} '22},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3514221.3517871},
        url = {https://dl.acm.org/doi/10.1145/3514221.3517871},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,404	Ready to Leap (by Co-Design)? Join Order Optimisation on Quantum Hardware	2023	SIGMOD	6.6135132e-05
6,632	Join Order Selection with Deep Reinforcement Learning: Fundamentals, Techniques, and Challenges	2023	VLDB	5.7270153e-05
6,805	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB	5.6780394e-05
7,917	Avoiding Materialisation for Guarded Aggregate Queries	2025	VLDB	5.4276002e-05
10,508	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD	4.9793485e-05
10,590	Query Optimization for Database-Returning Queries	2026	SIGMOD	4.9793485e-05
10,713	Robust Predicate Transfer with Dynamic Execution	2026	VLDB	4.9793485e-05
11,536	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023947656
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00029179719
362	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00019989474
487	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017462723
708	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00014629998
796	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00013938011
884	Dynamic Programming Strikes Back	2008	SIGMOD	0.00013267935
1,186	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.0001160797
1,301	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00011112842
3,139	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.6046928e-05
3,775	Parallelizing Query Optimization	2008	VLDB	7.0272615e-05
4,001	Partial Join Order Optimization in the ParAccel Analytic Database	2009	SIGMOD	6.8607903e-05
6,049	Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs	2009	SIGMOD	5.9047797e-05
6,396	Optimizing Join Enumeration in Transformation-based Query Optimizers	2014	VLDB	5.7993259e-05
9,621	Parallelizing Query Optimization on Shared-Nothing Architectures	2016	VLDB	5.1497631e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,164	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD
2	3,139	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD
3	8,409	Effective Resource Utilization for Multiprocessor Join Execution	1989	VLDB
4	1,186	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
5	9,621	Parallelizing Query Optimization on Shared-Nothing Architectures	2016	VLDB
6	1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
7	6,049	Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs	2009	SIGMOD
8	2,886	Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment	2021	VLDB
9	2,136	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
10	3,775	Parallelizing Query Optimization	2008	VLDB