DPconv: Super-Polynomially Faster Join Ordering
ACM SIGMOD Record · 23.04.2026 · 55 (1) · 8-18
DOI: 10.1145/3810900.3810902 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGMOD Record, online erschienen am 23.04.2026. Verfasst von Mihail Stoian und 1 weiteren Autor:innen. Die Arbeit nennt 46 Literaturangaben.
Abstract (Originalsprache)
We revisit the join ordering problem in query optimization. The standard exact algorithm, DPccp, has a worst-case running time of O(3 n ). This is prohibitively expensive for large queries, which are not that uncommon anymore. We develop a new algorithmic framework based on subset convolution. DPconv achieves a super-polynomial speedup over DPccp, breaking the O(3 n ) time-barrier for the first time. We show that the framework instantiation for the Cmax cost function is up to 30x faster than DPccp for large clique queries.
Zitieren
APA
Stoian, M., & Kipf, A. (2026). DPconv: Super-Polynomially Faster Join Ordering. ACM SIGMOD Record, 55(1), 8-18. https://doi.org/10.1145/3810900.3810902
Vancouver
Stoian M, Kipf A. DPconv: Super-Polynomially Faster Join Ordering. ACM SIGMOD Record. 2026;55(1):8-18. doi:10.1145/3810900.3810902
BibTeX
@article{Stoian2026,
author = {Stoian, Mihail and Kipf, Andreas},
title = {DPconv: Super-Polynomially Faster Join Ordering},
journal = {ACM SIGMOD Record},
year = {2026},
volume = {55},
number = {1},
pages = {8--18},
doi = {10.1145/3810900.3810902}
}
EUVIMED