{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T05:12:34Z","timestamp":1775538754700,"version":"3.50.1"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>Existing index tuners typically rely on the ''what if'' API provided by the query optimizer to estimate the execution cost of a query on top of an index configuration. Such cost estimates can be inaccurate and may therefore lead to significant query performance regression (QPR) once the recommended indexes are materialized. This becomes a serious problem for cloud database providers, such as Microsoft's Azure SQL Database, that offer index tuning as an automated service (a.k.a. ''auto-indexing''). Previous work has explored use of supervised machine learning (ML) to reduce the likelihood of QPR. However, the trained ML models have limited generalization capability when applied to new databases and workloads. We propose an alternative approach where we analyze the query plans with significant QPRs and look for structural changes due to the new index configuration that could explain the QPR. We perform such study for index tuning data across many benchmark and real-world database workloads, for multiple realistic index tuning scenarios. Our study reveals that most of the significant QPRs can be attributed to a small number of common ''regression patterns'' characterizing the structural plan changes, and we further propose a pattern-based QPR detector accordingly. Our experimental evaluation shows that the pattern-based QPR detector can significantly outperform existing ML-based QPR detectors.<\/jats:p>","DOI":"10.1145\/3769839","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["Understanding and Detecting Query Performance Regression in Practical Index Tuning: [Experiments &amp; Analysis]"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-2454-7109","authenticated-orcid":false,"given":"Wentao","family":"Wu","sequence":"first","affiliation":[{"name":"Microsoft Research, Redmond, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2861-4883","authenticated-orcid":false,"given":"Anshuman","family":"Dutt","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7319-2857","authenticated-orcid":false,"given":"Gaoxiang","family":"Xu","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7011-7886","authenticated-orcid":false,"given":"Vivek","family":"Narasayya","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8252-5270","authenticated-orcid":false,"given":"Surajit","family":"Chaudhuri","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Mert Akdere et al. 2012. Learning-based Query Performance Modeling and Prediction. In ICDE.","DOI":"10.1109\/ICDE.2012.64"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639305"},{"key":"e_1_2_1_3_1","first-page":"227","article-title":"Automatic Physical Database Tuning","author":"Bruno Nicolas","year":"2005","unstructured":"Nicolas Bruno and Surajit Chaudhuri. 2005. Automatic Physical Database Tuning: A Relaxation-based Approach. In SIGMOD. 227-238.","journal-title":"A Relaxation-based Approach. In SIGMOD."},{"key":"e_1_2_1_4_1","unstructured":"Surajit Chaudhuri et al. 2020. Anytime Algorithm of Database Tuning Advisor for Microsoft SQL Server."},{"key":"e_1_2_1_5_1","first-page":"146","article-title":"An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server","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.","journal-title":"VLDB."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/276305.276337"},{"key":"e_1_2_1_7_1","unstructured":"Sudipto Das et al. 2019. Automatically Indexing Millions of Databases in Microsoft Azure SQL Database. In SIGMOD."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/1978665.1978668"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3484224.3484234"},{"key":"e_1_2_1_10_1","first-page":"1241","article-title":"AI Meets AI: Leveraging Query Executions to Improve Index Recommendations","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.","journal-title":"SIGMOD."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231761"},{"key":"e_1_2_1_12_1","first-page":"1539","article-title":"Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees","author":"Dutt Anshuman","year":"2017","unstructured":"Anshuman Dutt, Vivek R. Narasayya, and Surajit Chaudhuri. 2017. Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees. In SIGMOD. 1539-1554.","journal-title":"SIGMOD."},{"key":"e_1_2_1_13_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_14_1","first-page":"752","volume":"15","author":"Yuxing Han","year":"2021","unstructured":"Yuxing Han et al., 2021. Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation. Proc. VLDB Endow., Vol. 15, 4 (2021), 752-765.","journal-title":"Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation. Proc. VLDB Endow."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551799"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/119995.115835"},{"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","volume-title":"Kingma and Jimmy Ba","author":"Diederik","year":"2015","unstructured":"Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In ICLR."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407832"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13748-016-0094-0"},{"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.","DOI":"10.1145\/3340531.3412106"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611494"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350269"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2016.12.038"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342644"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342646"},{"key":"e_1_2_1_28_1","unstructured":"Microsoft. 2025a. Apply a Fixed Query Plan to a Plan Guide. https:\/\/learn.microsoft.com\/en-us\/sql\/relational-databases\/performance\/apply-a-fixed-query-plan-to-a-plan-guide?view=sql-server-ver16."},{"key":"e_1_2_1_29_1","unstructured":"Microsoft. 2025b. Azure SQL Database. https:\/\/azure.microsoft.com\/en-us\/products\/azure-sql\/database."},{"key":"e_1_2_1_30_1","unstructured":"Microsoft. 2025c. CREATE INDEX (Transact-SQL). https:\/\/learn.microsoft.com\/en-us\/sql\/t-sql\/statements\/create-index-transact-sql?view=sql-server-ver16."},{"key":"e_1_2_1_31_1","unstructured":"Microsoft. 2025d. Intro to Query Execution Bitmap Filters. https:\/\/techcommunity.microsoft.com\/t5\/sql-server-blog\/intro-to-query-execution-bitmap-filters\/ba-p\/383175."},{"key":"e_1_2_1_32_1","unstructured":"Microsoft. 2025 e. Program for TPC-H Data Generation with Skew. https:\/\/www.microsoft.com\/en-us\/download\/details.aspx?id=52430."},{"key":"e_1_2_1_33_1","unstructured":"Microsoft. 2025 f. Table hints (Transact-SQL). https:\/\/learn.microsoft.com\/en-us\/sql\/t-sql\/queries\/hints-transact-sql-table?view=sql-server-ver16."},{"key":"e_1_2_1_34_1","first-page":"1287","article-title":"Convolutional Neural Networks over Tree Structures for Programming Language Processing","author":"Lili Mou","year":"2016","unstructured":"Lili Mou et al., 2016. Convolutional Neural Networks over Tree Structures for Programming Language Processing. In AAAI. 1287-1293.","journal-title":"AAAI."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503600"},{"key":"e_1_2_1_36_1","first-page":"600","article-title":"DBA bandits: Self-driving index tuning under ad-hoc, analytical workloads with safety guarantees","author":"Perera R. Malinga","year":"2021","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. 600-611.","journal-title":"ICDE."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565816.3565824"},{"key":"e_1_2_1_38_1","first-page":"1238","article-title":"Efficient Scalable Multi-attribute Index Selection Using Recursive Strategies","author":"Schlosser Rainer","year":"2019","unstructured":"Rainer Schlosser, Jan Kossmann, and Martin Boissier. 2019. Efficient Scalable Multi-attribute Index Selection Using Recursive Strategies. In ICDE. 1238-1249.","journal-title":"ICDE."},{"key":"e_1_2_1_39_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_40_1","first-page":"3950","article-title":"Learned Index Benefits","volume":"15","author":"Shi Jiachen","year":"2022","unstructured":"Jiachen Shi, Gao Cong, and Xiaoli Li. 2022. Learned Index Benefits: Machine Learning Based Index Performance Estimation. PVLDB, Vol. 15, 13 (2022), 3950-3962.","journal-title":"Machine Learning Based Index Performance Estimation. PVLDB"},{"key":"e_1_2_1_41_1","first-page":"99","article-title":"Cost Models for Big Data Query Processing","author":"Siddiqui Tarique","year":"2020","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. 99-113.","journal-title":"Learning, Retrofitting, and Our Findings. In SIGMOD."},{"key":"e_1_2_1_42_1","first-page":"660","article-title":"ISUM","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. 660-673.","journal-title":"In SIGMOD."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3641832.3641836"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547309"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368296"},{"key":"e_1_2_1_46_1","first-page":"101","article-title":"DB2 Advisor: An Optimizer Smart Enough to Recommend Its Own Indexes","author":"Valentin Gary","year":"2000","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.","journal-title":"ICDE."},{"key":"e_1_2_1_47_1","first-page":"5998","article-title":"Attention is All you Need","author":"Vaswani Ashish","year":"2017","unstructured":"Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is All you Need. In NIPS. 5998-6008.","journal-title":"NIPS."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461552"},{"key":"e_1_2_1_49_1","first-page":"1278","article-title":"Esc","volume":"18","author":"Wang Xiaoying","year":"2025","unstructured":"Xiaoying Wang, Wentao Wu, Vivek R. Narasayya, and Surajit Chaudhuri. 2025. Esc: An Early-Stopping Checker for Budget-aware Index Tuning. Proc. VLDB Endow., Vol. 18, 5 (2025), 1278-1290.","journal-title":"An Early-Stopping Checker for Budget-aware Index Tuning. Proc. VLDB Endow."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654985"},{"key":"e_1_2_1_51_1","first-page":"487","article-title":"Index Selection in Relational Databases","author":"Whang Kyu-Young","year":"1985","unstructured":"Kyu-Young Whang. 1985. Index Selection in Relational Databases. In Foundations of Data Organization. 487-500.","journal-title":"Foundations of Data Organization."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3484954"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536219"},{"key":"e_1_2_1_54_1","first-page":"1081","article-title":"Predicting query execution time: Are optimizer cost models really unusable?","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.","journal-title":"ICDE."},{"key":"e_1_2_1_55_1","unstructured":"Wentao Wu Anshuman Dutt Gaoxiang Xu Vivek Narasayya and Surajit Chaudhuri. 2025. Understanding and Detecting Query Performance Regression in Practical Index Tuning (Extended Version). Technical Report. Microsoft Research. https:\/\/www.microsoft.com\/en-us\/research\/publication\/understanding-and-detecting-query-performance-regression-in-practical-index-tuning\/"},{"key":"e_1_2_1_56_1","unstructured":"Wentao Wu Jeffrey F. Naughton and Harneet Singh. 2016. Sampling-Based Query Re-Optimization. In SIGMOD."},{"key":"e_1_2_1_57_1","first-page":"1528","article-title":"Budget-aware Index Tuning with Reinforcement Learning","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. 1528-1541.","journal-title":"SIGMOD."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733092"},{"key":"e_1_2_1_59_1","volume-title":"AIM: A practical approach to automated index management for SQL databases. In ICDE.","author":"Yadav Ritwik","year":"2023","unstructured":"Ritwik Yadav, Satyanarayana R. Valluri, and Mohamed Za\u00eft. 2023. AIM: A practical approach to automated index management for SQL databases. In ICDE."},{"key":"e_1_2_1_60_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\/pdf\/10.1145\/3769839","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T04:31:45Z","timestamp":1775536305000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769839"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":60,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769839"],"URL":"https:\/\/doi.org\/10.1145\/3769839","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}