{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:53:37Z","timestamp":1775638417865,"version":"3.50.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>Index tuning aims to find the optimal index configuration for an input workload. It is often a time-consuming and resource-intensive process, largely attributed to the huge amount of \"what-if\" calls made to the query optimizer during configuration enumeration. Therefore, in practice it is desirable to set a budget constraint that limits the number of what-if calls allowed. This yields a new problem of budget allocation, namely, deciding on which query-configuration pairs (QCP's) to issue what-if calls. Unfortunately, optimal budget allocation is NP-hard, and budget allocation decisions made by existing solutions can be inferior. In particular, many of the what-if calls allocated by using existing solutions are devoted to QCP's whose what-if costs can be approximated by using cost derivation, a well-known technique that is computationally much more efficient and has been adopted by commercial index tuning software. This results in considerable waste of the budget, as these what-if calls are unnecessary. In this paper, we propose \"Wii,\" a lightweight mechanism that aims to avoid such spurious what-if calls. It can be seamlessly integrated with existing configuration enumeration algorithms. Experimental evaluation on top of both standard industrial benchmarks and real workloads demonstrates that Wii can eliminate significant number of spurious what-if calls. Moreover, by reallocating the saved budget to QCP's where cost derivation is less accurate, existing algorithms can be significantly improved in terms of the final configuration found.<\/jats:p>","DOI":"10.1145\/3654985","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-26","source":"Crossref","is-referenced-by-count":6,"title":["Wii: Dynamic Budget Reallocation In Index Tuning"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-7817-7196","authenticated-orcid":false,"given":"Xiaoying","family":"Wang","sequence":"first","affiliation":[{"name":"Simon Fraser University, Burnaby, British Columbia, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-2454-7109","authenticated-orcid":false,"given":"Wentao","family":"Wu","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, Washington, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5610-5547","authenticated-orcid":false,"given":"Chi","family":"Wang","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, Washington, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7011-7886","authenticated-orcid":false,"given":"Vivek","family":"Narasayya","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, Washington, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8252-5270","authenticated-orcid":false,"given":"Surajit","family":"Chaudhuri","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, Washington, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2023. DTA utility. https:\/\/docs.microsoft.com\/en-us\/sql\/tools\/dta\/dta-utility?view=sql-server-ver15."},{"key":"e_1_2_1_2_1","volume-title":"Matteo Riondato, Eli Upfal, and Stanley B. Zdonik.","author":"Akdere Mert","year":"2012","unstructured":"Mert Akdere, Ugur cCetintemel, Matteo Riondato, Eli Upfal, and Stanley B. Zdonik. 2012. Learning-based Query Performance Modeling and Prediction. In ICDE. 390--401."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCIAIG.2012.2186810"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639305"},{"key":"e_1_2_1_5_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_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.75"},{"key":"e_1_2_1_7_1","unstructured":"Surajit Chaudhuri and Vivek Narasayya. 2020. Anytime Algorithm of Database Tuning Advisor for Microsoft SQL Server."},{"key":"e_1_2_1_8_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_2_1_9_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_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0169-023X(93)90023-I"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/320289.320296"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/1978665.1978668"},{"key":"e_1_2_1_13_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_2_1_14_1","volume-title":"Patterson","author":"Ganapathi Archana","year":"2009","unstructured":"Archana Ganapathi, Harumi A. Kuno, Umeshwar Dayal, Janet L. Wiener, Armando Fox, Michael I. Jordan, and David A. Patterson. 2009. Predicting Multiple Metrics for Queries: Better Decisions Enabled by Machine Learning. In ICDE."},{"key":"e_1_2_1_15_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_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551799"},{"key":"e_1_2_1_17_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_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Levente Kocsis and Csaba Szepesv\u00e1 ri. 2006. Bandit Based Monte-Carlo Planning. In ECML. 282--293.","DOI":"10.1007\/11871842_29"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407832"},{"key":"e_1_2_1_20_1","first-page":"155","article-title":"SWIRL: Selection of Workload-aware Indexes using Reinforcement Learning","volume":"2","author":"Kossmann Jan","year":"2022","unstructured":"Jan Kossmann, Alexander Kastius, and Rainer Schlosser. 2022. SWIRL: Selection of Workload-aware Indexes using Reinforcement Learning. In EDBT. 2:155--2:168.","journal-title":"EDBT."},{"key":"e_1_2_1_21_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_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350269"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342644"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342646"},{"key":"e_1_2_1_26_1","unstructured":"Stratos Papadomanolakis Debabrata Dash and Anastassia Ailamaki. 2007. Efficient Use of the Query Optimizer for Automated Database Design. ACM."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503600"},{"key":"e_1_2_1_28_1","volume-title":"DBA bandits: Self-driving index tuning under ad-hoc, analytical workloads with safety guarantees","author":"Perera R. Malinga","unstructured":"R. Malinga Perera, Bastian Oetomo, Benjamin I. P. Rubinstein, and Renata Borovica-Gajic. 2021. DBA bandits: Self-driving index tuning under ad-hoc, analytical workloads with safety guarantees. In ICDE. IEEE, 600--611."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565816.3565824"},{"key":"e_1_2_1_30_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_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687766"},{"key":"e_1_2_1_32_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, Vol. abs\/1801.05643 (2018)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565848"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Tarique Siddiqui Alekh Jindal Shi Qiao Hiren Patel and Wangchao Le. 2020. Cost Models for Big Data Query Processing: Learning Retrofitting and Our Findings. In SIGMOD. ACM 99--113.","DOI":"10.1145\/3318464.3380584"},{"key":"e_1_2_1_35_1","volume-title":"ISUM: Efficiently Compressing Large and Complex Workloads for Scalable Index Tuning. In SIGMOD. ACM, 660--673.","author":"Siddiqui Tarique","year":"2022","unstructured":"Tarique Siddiqui, Saehan Jo, Wentao Wu, Chi Wang, Vivek R. Narasayya, and Surajit Chaudhuri. 2022a. ISUM: Efficiently Compressing Large and Complex Workloads for Scalable Index Tuning. In SIGMOD. ACM, 660--673."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3641832.3641836"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547309"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368296"},{"key":"e_1_2_1_39_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_2_1_40_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_2_1_41_1","volume-title":"Wii: Dynamic Budget Reallocation In Index Tuning (Extended Version). Technical Report. Microsoft Research. https:\/\/www.microsoft.com\/en-us\/research\/people\/wentwu\/publications\/","author":"Wang Xiaoying","year":"2024","unstructured":"Xiaoying Wang, Wentao Wu, Chi Wang, Vivek Narasayya, and Surajit Chaudhuri. 2024. Wii: Dynamic Budget Reallocation In Index Tuning (Extended Version). Technical Report. Microsoft Research. https:\/\/www.microsoft.com\/en-us\/research\/people\/wentwu\/publications\/"},{"key":"e_1_2_1_42_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_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536219"},{"key":"e_1_2_1_44_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. 2013b. Predicting query execution time: Are optimizer cost models really unusable?. In ICDE. 1081--1092."},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Wentao Wu Jeffrey F. Naughton and Harneet Singh. 2016. Sampling-Based Query Re-Optimization. In SIGMOD. ACM 1721--1736.","DOI":"10.1145\/2882903.2882914"},{"key":"e_1_2_1_46_1","volume-title":"Bernstein","author":"Wu Wentao","year":"2022","unstructured":"Wentao Wu, Chi Wang, Tarique Siddiqui, Junxiong Wang, Vivek R. Narasayya, Surajit Chaudhuri, and Philip A. Bernstein. 2022. Budget-aware Index Tuning with Reinforcement Learning. In SIGMOD. ACM, 1528--1541."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733092"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529349"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654985","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654985","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:39:46Z","timestamp":1755787186000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654985"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654985"],"URL":"https:\/\/doi.org\/10.1145\/3654985","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}