DPconv: Super-Polynomially Faster Join Ordering

Summary: DPconv introduces a subset-convolution based framework for exact join ordering. It breaks the O(3^n) barrier, delivering super-polynomial speedups over DPccp, up to 30x faster for large-clique C_max cost queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7044
Venue: SIGMOD
Year: 2024
Pagerank: 5.3256042e-05
Overall Rank: 9,042 | 37.97%
DOI: 10.1145/3698809

Incoming Non-self Citations Over Time

Authors

1. Mihail Stoian (University of Technology Nuremberg)
2. Andreas Kipf (University of Technology Nuremberg)

BibTeX Citation

@inproceedings{stoian_sigmod24,
        title = {{DPconv: Super-Polynomially Faster Join Ordering}},
        author = {Stoian, Mihail and Kipf, Andreas},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3698809},
        url = {https://dl.acm.org/doi/10.1145/3698809},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,148	Size Bound-Adorned Datalog	2026	PODS	5.093636e-05
10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 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.0024089429
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
143	Optimization of Nonrecursive Queries	1986	VLDB	0.0002959213
192	Grammar-like Functional Rules for Representing Query Optimization Alternatives	1988	SIGMOD	0.00026028406
316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.0002141607
411	Worst-case Optimal Join Algorithms	2012	PODS	0.00018902089
774	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014123979
1,013	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012652549
1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011320736
1,298	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00011259156
1,727	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.91063e-05
1,876	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	9.5717543e-05
3,158	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.6888079e-05
3,553	On the Complexity of Approximate Query Optimization	2002	PODS	7.3175599e-05
3,809	Auto-WLM: Machine Learning Enhanced Workload Management in Amazon Redshift	2023	SIGMOD	7.1074195e-05
3,813	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	7.1051056e-05
5,626	Ready to Leap (by Co-Design)? Join Order Optimisation on Quantum Hardware	2023	SIGMOD	6.1440728e-05
6,602	Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses	2024	SIGMOD	5.8246665e-05
7,882	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	5.5237338e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,399	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD
2	1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
3	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
4	7,882	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD
5	3,553	On the Complexity of Approximate Query Optimization	2002	PODS
6	3,959	Simplicity Done Right for Join Ordering	2021	CIDR
7	3,813	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD
8	7,467	On the Complexity of Join Predicates	2001	PODS
9	2,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
10	1,013	Dynamic Programming Strikes Back	2008	SIGMOD