DBScholar

Back to papers

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
h3f6704645119e949
Venue
SIGMOD
Year
2024
Pagerank
5.206112e-05
Overall Rank
9,211 | 38.08%
DOI
10.1145/3698809

Incoming Non-self Citations Over Time

Authors

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,365 Size Bound-Adorned Datalog 2026 PODS 4.9793485e-05
10,508 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

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.0023947656
15 How Good Are Query Optimizers, Really? 2016 VLDB 0.00061066921
143 Optimization of Nonrecursive Queries 1986 VLDB 0.00029179719
196 Grammar-like Functional Rules for Representing Query Optimization Alternatives 1988 SIGMOD 0.00025626873
321 Measuring the Complexity of Join Enumeration in Query Optimization 1990 VLDB 0.00021088704
402 Worst-case Optimal Join Algorithms 2012 PODS 0.00019104625
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
1,726 Optimal Top-Down Join Enumeration 2007 SIGMOD 9.788916e-05
1,734 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 9.7545773e-05
3,139 Solving the Join Ordering Problem via Mixed Integer Linear Programming 2017 SIGMOD 7.6046928e-05
3,563 Auto-WLM: Machine Learning Enhanced Workload Management in Amazon Redshift 2023 SIGMOD 7.2042148e-05
3,567 On the Complexity of Approximate Query Optimization 2002 PODS 7.2010667e-05
3,797 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 7.0163619e-05
4,404 Ready to Leap (by Co-Design)? Join Order Optimisation on Quantum Hardware 2023 SIGMOD 6.6135132e-05
6,240 Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses 2024 SIGMOD 5.8382355e-05
8,039 Efficiently Computing Join Orders with Heuristic Search 2023 SIGMOD 5.4017809e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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