.png){kind=icon}
.png){kind=icon}
Return
Algorithms for Optimizing Acyclic Queries
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.ICDT.2026.17.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 a-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.
Keywords:
Query Optimization
Join Trees
Enumeration
Journal
2
IF:
0
Papers:
28
Citations:
0
