Cost-Based Query Optimization via AI Planning


  • Nathan Robinson Australian National University
  • Sheila McIlraith University of Toronto
  • David Toman University of Waterloo



Planning, Query optimization, Join-order Selection


In this paper we revisit the problem of generating query plans using AI automated planning with a view to leveraging significant recent advances in state-of-the-art planning techniques. Our efforts focus on the specific problem of cost-based join-order optimization for conjunctive relational queries, a critical component of production-quality query optimizers. We characterize the general query-planning problem as a delete-free 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 domain-independent and domain-specific optimization criteria. Experimental results demonstrate the effectiveness of AI planning techniques for query plan generation and optimization.




How to Cite

Robinson, N., McIlraith, S., & Toman, D. (2014). Cost-Based Query Optimization via AI Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1).