Cost-Based Query Optimization via AI Planning

In this paper we revisit the problem of generating query plans using AI automated planning with a view to leveraging significant advances in state-of-the-art planning techniques. Our efforts focus on the specific problem of cost-based joinorder optimization for conjunctive relational queries, a critical component of production-quality query optimizers. We characterize the general query-planning problem as a deletefree planning problem, and query plan optimization as a context-sensitive cost-optimal planning problem. We propose algorithms that generate high-quality query plans, guaranteeing optimality under certain conditions. Our approach is general, supporting the use of a broad suite of domainindependent and domain-specific optimization criteria. Experimental results demonstrate the effectiveness of AI planning techniques for query plan generation and optimization.

Authors

• Nathan Robinson Australian National University
• Sheila McIlraith
• David Toman

Keywords

No keywords are indexed for this paper.