An Efficient Query Optimization Framework Based on MCTS and LTR

Identifying the optimal query plan is always a fundamental task of query optimization in database management system (DBMS). However, traditional query optimization methods face significant challenges in continuously enhancing query performance due to complex query sentences, intricate data distributions and the exponentially growing search space of table joins. In this paper, we propose a formidable query optimization framework called MRQO (Integrating-MCTS-and-LTR-for-Query-Optimization). This framework utilizes the Monte Carlo Tree Search (MCTS) algorithm to find a comprehensive set of join orders for a query, and uses these join orders as hints to generate corresponding query plans. Additionally, it employs the Learning-to-Rank (LTR) approach to train a relative ranking model, achieving higher efficiency and accuracy in identifying the optimal query plan from all plans. Experimental results on PostgreSQL demonstrate that the proposed MRQO can achieve stable performance and match or even outperform both traditional query optimizers and advanced learned optimizers based on Deep Reinforcement Learning (DRL) in terms of query optimization efficiency.