{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T09:01:19Z","timestamp":1775638879808,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":64,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T00:00:00Z","timestamp":1654819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,10]]},"DOI":"10.1145\/3514221.3526128","type":"proceedings-article","created":{"date-parts":[[2022,6,12]],"date-time":"2022-06-12T02:33:49Z","timestamp":1655001229000},"page":"1528-1541","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Budget-aware Index Tuning with Reinforcement Learning"],"prefix":"10.1145","author":[{"given":"Wentao","family":"Wu","sequence":"first","affiliation":[{"name":"Microsoft Research, Redmond, WA, USA"}]},{"given":"Chi","family":"Wang","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA, USA"}]},{"given":"Tarique","family":"Siddiqui","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA, USA"}]},{"given":"Junxiong","family":"Wang","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}]},{"given":"Vivek","family":"Narasayya","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA, USA"}]},{"given":"Surajit","family":"Chaudhuri","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA, USA"}]},{"given":"Philip A.","family":"Bernstein","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"[n.d.]. Amazon Relational Database Service. https:\/\/aws.amazon.com\/rds\/."},{"key":"e_1_3_2_1_2_1","unstructured":"[n.d.]. Azure SQL Database. https:\/\/azure.microsoft.com\/en-us\/products\/azure-sql\/database\/."},{"key":"e_1_3_2_1_3_1","unstructured":"[n.d.]. DTA utility. https:\/\/docs.microsoft.com\/en-us\/sql\/tools\/dta\/dta-utility?view=sql-server-ver15."},{"key":"e_1_3_2_1_4_1","unstructured":"[n.d.]. GitHub Repository of No DBA. https:\/\/github.com\/shankur\/autoindex."},{"key":"e_1_3_2_1_5_1","unstructured":"[n.d.]. Google Cloud SQL. https:\/\/cloud.google.com\/sql."},{"key":"e_1_3_2_1_6_1","unstructured":"[n.d.]. Oracle Database Cloud Service. https:\/\/www.oracle.com\/database\/."},{"key":"e_1_3_2_1_7_1","volume-title":"Narasayya","author":"Agrawal Sanjay","year":"2000","unstructured":"Sanjay Agrawal, Surajit Chaudhuri, and Vivek R. Narasayya. 2000. Automated Selection of Materialized Views and Indexes in SQL Databases. In VLDB. 496--505."},{"key":"e_1_3_2_1_8_1","unstructured":"Jean-Yves Audibert R\u00e9mi Munos and Csaba Szepesvari. 2006. Use of variance estimation in the multi-armed bandit problem. (2006)."},{"key":"e_1_3_2_1_9_1","first-page":"397","article-title":"Using Confidence Bounds for Exploitation-Exploration Trade-offs","volume":"3","author":"Auer Peter","year":"2002","unstructured":"Peter Auer. 2002. Using Confidence Bounds for Exploitation-Exploration Trade-offs. J. Mach. Learn. Res. 3 (2002), 397--422.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013689704352"},{"key":"e_1_3_2_1_11_1","volume-title":"Zihong Yuan, Pierre Senellart, and St\u00e9phane Bressan.","author":"Basu Debabrota","year":"2015","unstructured":"Debabrota Basu, Qian Lin, Weidong Chen, Hoang Tam Vo, Zihong Yuan, Pierre Senellart, and St\u00e9phane Bressan. 2015. Cost-Model Oblivious Database Tuning with Reinforcement Learning. In DEXA. 253--268."},{"key":"e_1_3_2_1_12_1","volume-title":"Dynamic Programming","author":"Bellman R. E.","unstructured":"R. E. Bellman. 1957. Dynamic Programming. Princeton University Press."},{"key":"e_1_3_2_1_13_1","volume-title":"Dynamic programming and optimal control","author":"Bertsekas Dimitri P.","unstructured":"Dimitri P. Bertsekas. 2005. Dynamic programming and optimal control, 3rd Edition. Athena Scientific.","edition":"3"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCIAIG.2012.2186810"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Nicolas Bruno and Surajit Chaudhuri. 2005. Automatic Physical Database Tuning: A Relaxation-based Approach. In SIGMOD. 227--238.","DOI":"10.1145\/1066157.1066184"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Nicolas Bruno and Surajit Chaudhuri. 2007. An Online Approach to Physical Design Tuning. In ICDE. 826--835.","DOI":"10.1109\/ICDE.2007.367928"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1292609.1292618"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453863"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.75"},{"key":"e_1_3_2_1_20_1","volume-title":"Ashish Kumar Gupta, and Vivek R. Narasayya","author":"Chaudhuri Surajit","year":"2002","unstructured":"Surajit Chaudhuri, Ashish Kumar Gupta, and Vivek R. Narasayya. 2002. Compressing SQL workloads. In SIGMOD. 488--499."},{"key":"e_1_3_2_1_21_1","unstructured":"Surajit Chaudhuri and Vivek Narasayya. 2020. Anytime Algorithm of Database Tuning Advisor for Microsoft SQL Server."},{"key":"e_1_3_2_1_22_1","volume-title":"Narasayya","author":"Chaudhuri Surajit","year":"1997","unstructured":"Surajit Chaudhuri and Vivek R. Narasayya. 1997. An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server. In VLDB. 146--155."},{"key":"e_1_3_2_1_23_1","volume-title":"Narasayya","author":"Chaudhuri Surajit","year":"1998","unstructured":"Surajit Chaudhuri and Vivek R. Narasayya. 1998. AutoAdmin 'What-if' Index Analysis Utility. In SIGMOD. 367--378."},{"key":"e_1_3_2_1_24_1","volume-title":"Narasayya","author":"Chaudhuri Surajit","year":"1999","unstructured":"Surajit Chaudhuri and Vivek R. Narasayya. 1999. Index Merging. In ICDE."},{"key":"e_1_3_2_1_25_1","volume-title":"On the Selection of Secondary Indices in Relational Databases. Data Knowl. Eng. 11, 3","author":"Choenni Sunil","year":"1993","unstructured":"Sunil Choenni, Henk M. Blanken, and Thiel Chang. 1993. On the Selection of Secondary Indices in Relational Databases. Data Knowl. Eng. 11, 3 (1993)."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/320289.320296"},{"key":"e_1_3_2_1_27_1","unstructured":"Sudipto Das Miroslav Grbic Igor Ilic Isidora Jovandic Andrija Jovanovic Vivek R. Narasayya Miodrag Radulovic Maja Stikic Gaoxiang Xu and Surajit Chaudhuri. 2019. Automatically Indexing Millions of Databases in Microsoft Azure SQL Database. In SIGMOD. 666--679."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/1978665.1978668"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3430915.3430931"},{"key":"e_1_3_2_1_30_1","volume-title":"Narasayya","author":"Ding Bailu","year":"2019","unstructured":"Bailu Ding, Sudipto Das, Ryan Marcus, Wentao Wu, Surajit Chaudhuri, and Vivek R. Narasayya. 2019. AI Meets AI: Leveraging Query Executions to Improve Index Recommendations. In SIGMOD. 1241--1258."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/42201.42205"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000071"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.03.007"},{"key":"e_1_3_2_1_34_1","volume-title":"Ullman","author":"Gupta Himanshu","year":"1997","unstructured":"Himanshu Gupta, Venky Harinarayan, Anand Rajaraman, and Jeffrey D. Ullman. 1997. Index Selection for OLAP. In ICDE. 208--219."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Todd Hester Matej Vecer\u00edk Olivier Pietquin Marc Lanctot Tom Schaul Bilal Piot Dan Horgan John Quan Andrew Sendonaris Ian Osband Gabriel Dulac-Arnold John P. Agapiou Joel Z. Leibo and Audrunas Gruslys. 2018. Deep Q-learning From Demonstrations. In AAAI. 3223--3230.","DOI":"10.1609\/aaai.v32i1.11757"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.301"},{"key":"e_1_3_2_1_37_1","unstructured":"Andrew Kane. 2017. Introducing Dexter the Automatic Indexer for Postgres. https:\/\/medium.com\/@ankane\/introducing-dexter-the-automatic-indexer-for-postgres-5f8fa8b28f27."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Levente Kocsis and Csaba Szepesv\u00e1ri. 2006. Bandit Based Monte-Carlo Planning. In ECML. 282--293.","DOI":"10.1007\/11871842_29"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407832"},{"key":"e_1_3_2_1_40_1","volume-title":"Tractability: Practical Approaches to Hard Problems","author":"Krause Andreas","unstructured":"Andreas Krause and Daniel Golovin. 2014. Submodular Function Maximization. In Tractability: Practical Approaches to Hard Problems. Cambridge University Press, 71--104."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Hai Lan Zhifeng Bao and Yuwei Peng. 2020. An Index Advisor Using Deep Reinforcement Learning. In CIKM. 2105--2108.","DOI":"10.1145\/3340531.3412106"},{"key":"e_1_3_2_1_42_1","unstructured":"Viktor Leis. [n.d.]. Join Order Benchmark. https:\/\/github.com\/gregrahn\/join-order-benchmark."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_3_2_1_44_1","unstructured":"Timothy P. Lillicrap Jonathan J. Hunt Alexander Pritzel Nicolas Heess Tom Erez Yuval Tassa David Silver and Daan Wierstra. 2016. Continuous control with deep reinforcement learning. In ICLR."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"crossref","unstructured":"G. L. Nemhauser et al. 1978. An analysis of approximations for maximizing submodular set functions - I. Math. Program. 14 1 (1978).","DOI":"10.1007\/BF01588971"},{"key":"e_1_3_2_1_46_1","unstructured":"Stratos Papadomanolakis Debabrata Dash and Anastassia Ailamaki. 2007. Efficient Use of the Query Optimizer for Automated Database Design. ACM."},{"key":"e_1_3_2_1_47_1","volume-title":"DBA bandits: Self-driving index tuning under ad-hoc, analytical workloads with safety guarantees. CoRR abs\/2010.09208","author":"Perera Malinga","year":"2020","unstructured":"Malinga Perera, Bastian Oetomo, Benjamin I. P. Rubinstein, and Renata Borovica- Gajic. 2020. DBA bandits: Self-driving index tuning under ad-hoc, analytical workloads with safety guarantees. CoRR abs\/2010.09208 (2020)."},{"key":"e_1_3_2_1_48_1","unstructured":"Laurent P\u00e9ret and Fr\u00e9d\u00e9rick Garcia. 2004. On-Line Search for Solving Markov Decision Processes via Heuristic Sampling. In ECAI. 530--534."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"crossref","unstructured":"M. L. Puterman and M. C. Shin. 1978. Modified policy iteration algorithms for discounted Markov decision problems. Management Science 24 11 (1978).","DOI":"10.1287\/mnsc.24.11.1127"},{"key":"e_1_3_2_1_50_1","unstructured":"Lijing Qin Shouyuan Chen and Xiaoyan Zhu. 2014. Contextual Combinatorial Bandit and its Application on Diversified Online Recommendation. In SDM. 461--469."},{"key":"e_1_3_2_1_51_1","volume-title":"Introduction to stochastic dynamic programming","author":"Ross S.","unstructured":"S. Ross. 2014. Introduction to stochastic dynamic programming. Academic press."},{"key":"e_1_3_2_1_52_1","volume-title":"The cross-entropy method for combinatorial and continuous optimization. Methodology and computing in applied probability 1, 2","author":"Rubinstein Reuven","year":"1999","unstructured":"Reuven Rubinstein. 1999. The cross-entropy method for combinatorial and continuous optimization. Methodology and computing in applied probability 1, 2 (1999), 127--190."},{"key":"e_1_3_2_1_53_1","volume-title":"On-line Q-learning using connectionist systems","author":"Rummery Gavin A","unstructured":"Gavin A Rummery and Mahesan Niranjan. 1994. On-line Q-learning using connectionist systems. Vol. 37. University of Cambridge."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW49219.2020.00035"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Rainer Schlosser Jan Kossmann and Martin Boissier. 2019. Efficient Scalable Multi-attribute Index Selection Using Recursive Strategies. In ICDE. 1238--1249.","DOI":"10.1109\/ICDE.2019.00113"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687766"},{"key":"e_1_3_2_1_57_1","volume-title":"Felix Martin Schuhknecht, and Jens Dittrich","author":"Sharma Ankur","year":"2018","unstructured":"Ankur Sharma, Felix Martin Schuhknecht, and Jens Dittrich. 2018. The Case for Automatic Database Administration using Deep Reinforcement Learning. CoRR abs\/1801.05643 (2018)."},{"key":"e_1_3_2_1_58_1","volume-title":"Reinforcement learning: An introduction","author":"Sutton Richard S","unstructured":"Richard S Sutton and Andrew G Barto. 2018. Reinforcement learning: An introduction. MIT press."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"crossref","unstructured":"Immanuel Trummer Junxiong Wang Deepak Maram Samuel Moseley Saehan Jo and Joseph Antonakakis. 2019. SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning. In SIGMOD. 1153--1170.","DOI":"10.1145\/3299869.3300088"},{"key":"e_1_3_2_1_60_1","unstructured":"Gary Valentin Michael Zuliani Daniel C. Zilio Guy M. Lohman and Alan Skelley. 2000. DB2 Advisor: An Optimizer Smart Enough to Recommend Its Own Indexes. In ICDE. 101--110."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00992698"},{"key":"e_1_3_2_1_62_1","volume-title":"Index Selection in Relational Databases","author":"Whang Kyu-Young","unstructured":"Kyu-Young Whang. 1985. Index Selection in Relational Databases. In Foundations of Data Organization. 487--500."},{"key":"e_1_3_2_1_63_1","volume-title":"Naughton","author":"Wu Wentao","year":"2013","unstructured":"Wentao Wu, Yun Chi, Shenghuo Zhu, Jun'ichi Tatemura, Hakan Hacig\u00fcm\u00fcs, and Jeffrey F. Naughton. 2013. Predicting query execution time: Are optimizer cost models really unusable?. In ICDE. 1081--1092."},{"key":"e_1_3_2_1_64_1","volume-title":"Bernstein","author":"Wu Wentao","year":"2022","unstructured":"Wentao Wu, Chi Wang, Tarique Siddiqui, Junxiong Wang, Vivek Narasayya, Surajit Chaudhuri, and Philip A. Bernstein. 2022. Budget-aware Index Tuning with Reinforcement Learning (Extended Version). Technical Report. Microsoft Research. https:\/\/www.microsoft.com\/en-us\/research\/people\/wentwu\/publications\/"}],"event":{"name":"SIGMOD\/PODS '22: International Conference on Management of Data","location":"Philadelphia PA USA","acronym":"SIGMOD\/PODS '22","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 2022 International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514221.3526128","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3514221.3526128","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:10:07Z","timestamp":1750183807000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514221.3526128"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,10]]},"references-count":64,"alternative-id":["10.1145\/3514221.3526128","10.1145\/3514221"],"URL":"https:\/\/doi.org\/10.1145\/3514221.3526128","relation":{},"subject":[],"published":{"date-parts":[[2022,6,10]]},"assertion":[{"value":"2022-06-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}