Succinct Structure Representations for Efficient Query Optimization
This work addresses a bottleneck in database systems by improving query optimization efficiency, particularly for large and complex queries, though it is incremental as it builds on existing structural decomposition methods.
The paper tackles the problem of integrating structural decomposition methods into real-world query optimizers by introducing meta-decompositions for acyclic queries, which enable efficient enumeration of join trees and cost-based optimization without explicit enumeration, resulting in plans comparable to or better than state-of-the-art dynamic programming approaches while running orders of magnitude faster.
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.