EUVIMEDEUVIMED entdecken
Crossref

Succinct Structure Representations for Efficient Query Optimization

Zhekai Jiang, Qichen Wang, Christoph Koch

Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-27

DOI: 10.1145/3802117 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Zhekai Jiang und 2 weiteren Autor:innen. Die Arbeit nennt 62 Literaturangaben. Gefördert von: Ministry of Education - Singapore, Nanyang Technological University.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Structural decomposition methods offer powerful theoretical guarantees for join evaluation, yet they are rarely used in real-world query optimizers. A major reason is the difficulty of combining cost-based plan search and structure-based evaluation. In this work, we bridge this gap by introducing meta-decompositions for acyclic queries, a novel representation that succinctly represents all possible join trees and enables their efficient enumeration. Meta-decompositions can be constructed in polynomial time and have sizes linear in the query size. We design an efficient polynomial-time cost-based optimizer based directly on the meta-decomposition, without the need to explicitly enumerate all possible join trees. We characterize plans found by this approach using a novel notion of width, which effectively implies the theoretical worst-case asymptotic bounds of intermediate result sizes and running time of any query plan. Experimental results demonstrate that, in practice, the plans in our class are consistently comparable to—even in many cases better than—the optimal ones found by the state-of-the-art dynamic programming approach, especially on large and complex queries, while our planning process runs by orders of magnitude faster, comparable to the time taken by common heuristic methods.

Förderung

  • Ministry of Education - Singapore
  • Nanyang Technological University

Zitieren

APA

Jiang, Z., Wang, Q., & Koch, C. (2026). Succinct Structure Representations for Efficient Query Optimization. Proceedings of the ACM on Management of Data, 4(3), 1-27. https://doi.org/10.1145/3802117

Vancouver

Jiang Z, Wang Q, Koch C. Succinct Structure Representations for Efficient Query Optimization. Proceedings of the ACM on Management of Data. 2026;4(3):1-27. doi:10.1145/3802117

BibTeX
@article{Jiang2026,
  author = {Jiang, Zhekai and Wang, Qichen and Koch, Christoph},
  title = {Succinct Structure Representations for Efficient Query Optimization},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {3},
  pages = {1--27},
  doi = {10.1145/3802117}
}
Kostenlos starten →