{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T04:12:56Z","timestamp":1784261576070,"version":"3.55.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:p>Query rewrite transforms a SQL query into an equivalent one but with higher performance. However, SQL rewrite is an NP-hard problem, and existing approaches adopt heuristics to rewrite the queries. These heuristics have two main limitations. First, the order of applying different rewrite rules significantly affects the query performance. However, the search space of all possible rewrite orders grows exponentially with the number of query operators and rules and it is rather hard to find the optimal rewrite order. Existing methods apply a pre-defined order to rewrite queries and will fall in a local optimum. Second, different rewrite rules have different benefits for different queries. Existing methods work on single plans but cannot effectively estimate the benefits of rewriting a query. To address these challenges, we propose a<jats:italic>policy tree<\/jats:italic>based query rewrite framework, where the root is the input query and each node is a rewritten query from its parent. We aim to explore the tree nodes in the<jats:italic>policy tree<\/jats:italic>to find the optimal rewrite query. We propose to use<jats:italic>Monte Carlo Tree Search<\/jats:italic>to explore the policy tree, which navigates the policy tree to efficiently get the optimal node. Moreover, we propose a learning-based model to estimate the expected performance improvement of each rewritten query, which guides the tree search more accurately. We also propose a parallel algorithm that can explore the tree search in parallel in order to improve the performance. Experimental results showed that our method significantly outperformed existing approaches.<\/jats:p>","DOI":"10.14778\/3485450.3485456","type":"journal-article","created":{"date-parts":[[2022,1,14]],"date-time":"2022-01-14T23:26:50Z","timestamp":1642202810000},"page":"46-58","source":"Crossref","is-referenced-by-count":57,"title":["A learned query rewrite system using Monte Carlo tree search"],"prefix":"10.14778","volume":"15","author":[{"given":"Xuanhe","family":"Zhou","sequence":"first","affiliation":[{"name":"Tsinghua University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guoliang","family":"Li","sequence":"additional","affiliation":[{"name":"Tsinghua University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chengliang","family":"Chai","sequence":"additional","affiliation":[{"name":"Tsinghua University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianhua","family":"Feng","sequence":"additional","affiliation":[{"name":"Tsinghua University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,1,14]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"https:\/\/github.com\/xiaomi\/soar\/. https:\/\/github.com\/xiaomi\/soar\/."},{"key":"e_1_2_1_2_1","unstructured":"https:\/\/spinningup.openai.com\/en\/latest\/spinningup\/rl_intro2.html#citations-below. https:\/\/spinningup.openai.com\/en\/latest\/spinningup\/rl_intro2.html#citations-below."},{"key":"e_1_2_1_3_1","unstructured":"https:\/\/www.postgresql.org\/. https:\/\/www.postgresql.org\/."},{"key":"e_1_2_1_4_1","first-page":"1026","volume-title":"VLDB","author":"Ahmed R.","year":"2006","unstructured":"R. Ahmed , A. W. Lee , A. Witkowski, and et al. Cost-based query transformation in oracle . In VLDB , pages 1026 -- 1036 , 2006 . R. Ahmed, A. W. Lee, A. Witkowski, and et al. Cost-based query transformation in oracle. In VLDB, pages 1026--1036, 2006."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.64"},{"key":"e_1_2_1_6_1","first-page":"221","volume-title":"SIGMOD","author":"Begoli E.","year":"2018","unstructured":"E. Begoli , J. Camacho-Rodr\u00edguez , J. Hyde, and et al. Apache calcite: A foundational framework for optimized query processing over heterogeneous data sources . In SIGMOD , pages 221 -- 230 , 2018 . E. Begoli, J. Camacho-Rodr\u00edguez, J. Hyde, and et al. Apache calcite: A foundational framework for optimized query processing over heterogeneous data sources. In SIGMOD, pages 221--230, 2018."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCIAIG.2012.2186810"},{"key":"e_1_2_1_8_1","volume-title":"Inf. Data Manag.","author":"A. H.","year":"2014","unstructured":"A. H. M. de Ara\u00fajo and et al. On using an online, automatic and non-intrusive approach for rewriting SQL queries. J . Inf. Data Manag. , 2014 . A. H. M. de Ara\u00fajo and et al. On using an online, automatic and non-intrusive approach for rewriting SQL queries. J. Inf. Data Manag., 2014."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1991.131472"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-019-00115-y"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.06.020"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00217"},{"key":"e_1_2_1_13_1","first-page":"1165","volume-title":"Pruning game tree by rollouts","author":"Huang B.","year":"2015","unstructured":"B. Huang . Pruning game tree by rollouts . In B. Bonet and S. Koenig, editors, AAAI , pages 1165 -- 1173 , 2015 . B. Huang. Pruning game tree by rollouts. In B. Bonet and S. Koenig, editors, AAAI, pages 1165--1173, 2015."},{"key":"e_1_2_1_14_1","volume-title":"CIDR","author":"Kipf A.","year":"2019","unstructured":"A. Kipf , T. Kipf , B. Radke , V. Leis , P. A. Boncz , and A. Kemper . Learned cardinalities: Estimating correlated joins with deep learning . In CIDR , 2019 . A. Kipf, T. Kipf, B. Radke, V. Leis, P. A. Boncz, and A. Kemper. Learned cardinalities: Estimating correlated joins with deep learning. In CIDR, 2019."},{"key":"e_1_2_1_15_1","volume-title":"Learning to optimize join queries with deep reinforcement learning. CoRR, abs\/1808.03196","author":"Krishnan S.","year":"2018","unstructured":"S. Krishnan , Z. Yang , K. Goldberg , J. M. Hellerstein , and I. Stoica . Learning to optimize join queries with deep reinforcement learning. CoRR, abs\/1808.03196 , 2018 . S. Krishnan, Z. Yang, K. Goldberg, J. M. Hellerstein, and I. Stoica. Learning to optimize join queries with deep reinforcement learning. CoRR, abs\/1808.03196, 2018."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"issue":"12","key":"e_1_2_1_17_1","first-page":"2263","article-title":"Cloud native database systems at alibaba: Opportunities and challenges","volume":"12","author":"Li F.","year":"2019","unstructured":"F. Li . Cloud native database systems at alibaba: Opportunities and challenges . VLDB , 12 ( 12 ): 2263 -- 2272 , 2019 . F. Li. Cloud native database systems at alibaba: Opportunities and challenges. VLDB, 12(12):2263--2272, 2019.","journal-title":"VLDB"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457542"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476405"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476380"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352129"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350269"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.26599\/BDMA.2019.9020019"},{"key":"e_1_2_1_24_1","volume-title":"ICLR","author":"Liu A.","year":"2020","unstructured":"A. Liu , J. Chen , M. Yu, and et al. Watch the unobserved: A simple approach to parallelizing monte carlo tree search . In ICLR , 2020 . A. Liu, J. Chen, M. Yu, and et al. Watch the unobserved: A simple approach to parallelizing monte carlo tree search. In ICLR, 2020."},{"key":"e_1_2_1_25_1","volume-title":"Bao: Learning to steer query optimizers. CoRR, abs\/2004.03814","author":"Marcus R.","year":"2020","unstructured":"R. Marcus , P. Negi , H. Mao , N. Tatbul , M. Alizadeh , and T. Kraska . Bao: Learning to steer query optimizers. CoRR, abs\/2004.03814 , 2020 . R. Marcus, P. Negi, H. Mao, N. Tatbul, M. Alizadeh, and T. Kraska. Bao: Learning to steer query optimizers. CoRR, abs\/2004.03814, 2020."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452838"},{"key":"e_1_2_1_27_1","first-page":"1","volume-title":"Proceedings of the First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM@SIGMOD 2018","author":"Marcus R.","year":"2018","unstructured":"R. Marcus and O. Papaemmanouil . Deep reinforcement learning for join order enumeration. In R. Bordawekar and O. Shmueli, editors , Proceedings of the First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM@SIGMOD 2018 , Houston, TX, USA , June 10, 2018 , pages 3: 1 -- 3 :4. ACM, 2018. R. Marcus and O. Papaemmanouil. Deep reinforcement learning for join order enumeration. In R. Bordawekar and O. Shmueli, editors, Proceedings of the First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM@SIGMOD 2018, Houston, TX, USA, June 10, 2018, pages 3:1--3:4. ACM, 2018."},{"key":"e_1_2_1_28_1","volume-title":"Plan-structured deep neural network models for query performance prediction. arXiv preprint arXiv:1902.00132","author":"Marcus R.","year":"2019","unstructured":"R. Marcus and O. Papaemmanouil . Plan-structured deep neural network models for query performance prediction. arXiv preprint arXiv:1902.00132 , 2019 . R. Marcus and O. Papaemmanouil. Plan-structured deep neural network models for query performance prediction. arXiv preprint arXiv:1902.00132, 2019."},{"key":"e_1_2_1_29_1","volume-title":"Plan-structured deep neural network models for query performance prediction. CoRR, abs\/1902.00132","author":"Marcus R.","year":"2019","unstructured":"R. Marcus and O. Papaemmanouil . Plan-structured deep neural network models for query performance prediction. CoRR, abs\/1902.00132 , 2019 . R. Marcus and O. Papaemmanouil. Plan-structured deep neural network models for query performance prediction. CoRR, abs\/1902.00132, 2019."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342644"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457568"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1145\/130283.130294","volume-title":"SIGMOD","author":"Pirahesh H.","year":"1992","unstructured":"H. Pirahesh , J. M. Hellerstein , and W. Hasan . Extensible\/rule based query rewrite optimization in starburst. In M. Stonebraker, editor , SIGMOD , pages 39 -- 48 , 1992 . H. Pirahesh, J. M. Hellerstein, and W. Hasan. Extensible\/rule based query rewrite optimization in starburst. In M. Stonebraker, editor, SIGMOD, pages 39--48, 1992."},{"key":"e_1_2_1_33_1","unstructured":"A. Seltenreich. Sqlsmith 2020. https:\/\/github.com\/anse1\/sqlsmith. A. Seltenreich. Sqlsmith 2020. https:\/\/github.com\/anse1\/sqlsmith."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368296"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452790"},{"key":"e_1_2_1_36_1","volume-title":"VLDB","author":"Sun J.","year":"2021","unstructured":"J. Sun , J. Zhang , Z. Sun , G. Li , and N. Tang . Learned cardinality estimation: A design space exploration and a comparative evaluation . VLDB , 2021 . J. Sun, J. Zhang, Z. Sun, G. Li, and N. Tang. Learned cardinality estimation: A design space exploration and a comparative evaluation. VLDB, 2021."},{"key":"e_1_2_1_37_1","volume-title":"Reinforcement learning: An introduction","author":"Sutton R. S.","year":"2018","unstructured":"R. S. Sutton and A. G. Barto . Reinforcement learning: An introduction . MIT press , 2018 . R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-020-00117-1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300088"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3291264.3291267"},{"key":"e_1_2_1_41_1","first-page":"1081","volume-title":"ICDE","author":"Wu W.","year":"2013","unstructured":"W. Wu , Y. Chi , S. Zhu , J. Tatemura , H. Hacig\u00fcm\u00fcs , and J. F. Naughton . Predicting query execution time: Are optimizer cost models really unusable ? In ICDE , pages 1081 -- 1092 , 2013 . W. Wu, Y. Chi, S. Zhu, J. Tatemura, H. Hacig\u00fcm\u00fcs, and J. F. Naughton. Predicting query execution time: Are optimizer cost models really unusable? In ICDE, pages 1081--1092, 2013."},{"issue":"3","key":"e_1_2_1_42_1","first-page":"279","article-title":"Deep unsupervised cardinality estimation","volume":"13","author":"Yang Z.","year":"2019","unstructured":"Z. Yang , E. Liang , A. Kamsetty , C. Wu , and . Deep unsupervised cardinality estimation . VLDB , 13 ( 3 ): 279 -- 292 , 2019 . Z. Yang, E. Liang, A. Kamsetty, C. Wu, and et al. Deep unsupervised cardinality estimation. VLDB, 13(3):279--292, 2019.","journal-title":"VLDB"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00116"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00133"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300085"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2994641"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476334"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397238"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3485450.3485456","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,15]],"date-time":"2023-11-15T21:25:57Z","timestamp":1700083557000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3485450.3485456"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["10.14778\/3485450.3485456"],"URL":"https:\/\/doi.org\/10.14778\/3485450.3485456","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,9]]}}}