Query Execution Plan Search Space Enumeration by Reinforcement Learning

Abstract

Join order selection, a critical subfield of query optimization, focuses on determining the optimal join sequence for SQL queries to minimize execution cost. This problem becomes increasingly challenging as the number of tables in a query expands, leading to an exponentially growing search space. Exhaustive enumeration of all possible join orders is computationally infeasible. Recent advances in join order selection have leveraged deep reinforcement learning (DRL) to address this challenge, offering dynamic and adaptive solutions that improve on traditional rule-based or cost-based approaches. This thesis proposes a DRL framework specifically designed for join order selection. Our approach reformulates join order selection as a sequential decision-making problem, where an agent learns to select joins by maximizing query performance. By integrating graph neural networks (GNN) to model relationships between tables and Tree-LSTM networks to capture the hierarchical nature of join sequences, we create informative representations. Additionally, we replace the vanilla DQN with a dueling-DQN to enhance training stability and convergence time. The DRL-based framework adaptively explores the search space and learns optimal join sequences through iterative interactions. Our experimental results demonstrate that our method consistently outperforms other baselines, including both traditional methods and other DRL-based techniques. This highlights the potential of reinforcement learning to significantly enhance query optimization, offering a more adaptive and efficient solution for join order selection.