EUVIMEDEUVIMED entdecken
Crossref

DPconv: Super-Polynomially Faster Join Ordering

Mihail Stoian, Andreas Kipf

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →