Cost-Based Query Optimization via AI Planning

Authors

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

DOI:

https://doi.org/10.1609/aaai.v28i1.9045

Keywords:

Planning, Query optimization, Join-order Selection

Abstract

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.

Downloads

Published

2014-06-21

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). https://doi.org/10.1609/aaai.v28i1.9045