An Efficient Query Optimization Framework Based on MCTS and LTR

Chaofan Zhao, Yize Sui, Ruochun Jin, Jing Ren
Proceedings of the 16th Asian Conference on Machine Learning, PMLR 260:1224-1239, 2025.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v260-zhao25b, title = {An Efficient Query Optimization Framework Based on MCTS and LTR}, author = {Zhao, Chaofan and Sui, Yize and Jin, Ruochun and Ren, Jing}, booktitle = {Proceedings of the 16th Asian Conference on Machine Learning}, pages = {1224--1239}, year = {2025}, editor = {Nguyen, Vu and Lin, Hsuan-Tien}, volume = {260}, series = {Proceedings of Machine Learning Research}, month = {05--08 Dec}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v260/main/assets/zhao25b/zhao25b.pdf}, url = {https://proceedings.mlr.press/v260/zhao25b.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T An Efficient Query Optimization Framework Based on MCTS and LTR %A Chaofan Zhao %A Yize Sui %A Ruochun Jin %A Jing Ren %B Proceedings of the 16th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Vu Nguyen %E Hsuan-Tien Lin %F pmlr-v260-zhao25b %I PMLR %P 1224--1239 %U https://proceedings.mlr.press/v260/zhao25b.html %V 260 %X 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.
APA
Zhao, C., Sui, Y., Jin, R. & Ren, J.. (2025). An Efficient Query Optimization Framework Based on MCTS and LTR. Proceedings of the 16th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 260:1224-1239 Available from https://proceedings.mlr.press/v260/zhao25b.html.

Related Material