2026-09-26T18:54:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25631 2026-09-23T23:45:29Z ddc:004 open_access

Algorithms for Optimizing Acyclic Queries Luo, Zheng Van den Broeck, Wim Van den Broeck, Guy Wang, Yisu Remy Query Optimization Join Trees Enumeration Most research on query optimization has centered on binary join algorithms like hash join and sort-merge join. However, recent years have seen growing interest in theoretically optimal algorithms, notably Yannakakis' algorithm. These algorithms rely on join trees, which differ from the operator trees for binary joins and require new optimization techniques. We propose three approaches to constructing join trees for acyclic queries. First, we give an algorithm to enumerate all join trees of an α-acyclic query by edits in linear time with amortized constant delay, which forms the basis of a cost-based optimizer for acyclic joins. Second, we show the Maximum Cardinality Search algorithm by Tarjan and Yannakakis constructs the unique shallowest join tree for any Berge-acyclic query, thus enabling parallel execution of large join queries. Finally, we prove that a simple algorithm by Hu et al. converts any connected left-deep linear plan of a γ-acyclic query into a join tree, allowing reuse of optimizers developed for binary joins. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zheng Luo and Wim Van den Broeck and Guy Van den Broeck and Yisu Remy Wang 2026 Is Part Of LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2026.17 urn:nbn:de:0030-drops-256319 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.17 eng https://creativecommons.org/licenses/by/4.0/legalcode