Esc: An Early-Stopping Checker for Budget-aware Index Tuning

Summary: Introduces early stopping for budget-aware index tuning: terminate when projected remaining-budget gains fall within a user-specified quality-loss threshold. Esc cheaply estimates this point, substantially reducing what-if optimizer calls with negligible quality or runtime overhead. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 13984
Venue: VLDB
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,815 | 25.80%
DOI: 10.14778/3718057.3718059

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Xiaoying Wang (Simon Fraser University)
2. Wentao Wu (Microsoft)
3. Vivek Narasayya (Microsoft)
4. Surajit Chaudhuri (Microsoft)

BibTeX Citation

@article{wang_vldb25,
        title = {{Esc: An Early-Stopping Checker for Budget-aware Index Tuning}},
        author = {Wang, Xiaoying and Wu, Wentao and Narasayya, Vivek and Chaudhuri, Surajit},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {5},
        pages = {1278--1290},
        doi = {10.14778/3718057.3718059},
        url = {https://doi.org/10.14778/3718057.3718059},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,413	Understanding and Detecting Query Performance Regression in Practical Index Tuning: [Experiments & Analysis]	2026	SIGMOD	5.093636e-05
10,494	RIB: Robust Learning-based Index Benefit Estimation	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 30 of 30 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
87	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00035281619
154	Neo: A Learned Query Optimizer	2019	VLDB	0.00028726181
156	An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server	1997	VLDB	0.00028636811
387	AutoAdmin "What-if" Index Analysis Utility	1998	SIGMOD	0.00019442332
465	An End-to-End Learning-based Cost Estimator	2020	VLDB	0.0001803934
563	Plan-Structured Deep Neural Network Models for Query Performance Prediction	2019	VLDB	0.0001650812
682	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB	0.00015014887
768	Automatic Physical Database Tuning: A Relaxation-based Approach	2005	SIGMOD	0.00014173242
1,256	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00011457194
1,279	AI Meets AI: Leveraging Query Executions to Improve Index Recommendations	2019	SIGMOD	0.00011361878
1,481	Magic mirror in my hand, which is the best in the land? An Experimental Evaluation of Index Selection Algorithms	2020	VLDB	0.00010644613
1,904	CoPhy: A Scalable, Portable, and Interactive Index Advisor for Large Workloads	2011	VLDB	9.5040429e-05
1,997	Efficient Use of the Query Optimizer for Automated Physical Design	2007	VLDB	9.3378162e-05
2,355	QueryFormer: A Tree Transformer Model for Query Plan Representation	2022	VLDB	8.7022189e-05
2,822	Cost Models for Big Data Query Processing: Learning, Retrofitting, and Our Findings	2020	SIGMOD	8.0898536e-05
2,844	Zero-Shot Cost Models for Out-of-the-box Learned Cost Prediction	2022	VLDB	8.0608767e-05
3,482	Towards Predicting Query Execution Time for Concurrent and Dynamic Database Workloads	2013	VLDB	7.3751635e-05
4,550	Index Interactions in Physical Design Tuning: Modeling, Analysis, and Applications	2009	VLDB	6.635765e-05
4,643	Learned Index Benefits: Machine Learning Based Index Performance Estimation	2022	VLDB	6.5907466e-05
5,073	Database Workload Characterization with Query Plan Encoders	2022	VLDB	6.3751266e-05
5,091	Budget-aware Index Tuning with Reinforcement Learning	2022	SIGMOD	6.3669569e-05
5,537	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	6.1820087e-05
5,558	HMAB: Self-Driving Hierarchy of Bandits for Integrated Physical Database Design Tuning	2023	VLDB	6.1749098e-05
5,869	ISUM: Efficiently Compressing Large and Complex Workloads for Scalable Index Tuning	2022	SIGMOD	6.0610922e-05
6,327	Breaking It Down: An In-depth Study of Index Advisors	2024	VLDB	5.9124005e-05
7,076	Refactoring Index Tuning Process with Benefit Estimation	2024	VLDB	5.7098893e-05
7,655	Plan Stitch: Harnessing the Best of Many Plans	2018	VLDB	5.5741093e-05
7,750	DISTILL: Low-Overhead Data-Driven Techniques for Filtering and Costing Indexes for Scalable Index Tuning	2022	VLDB	5.5523652e-05
9,615	Wii: Dynamic Budget Reallocation In Index Tuning	2024	SIGMOD	5.2436464e-05
10,082	Wred: Workload Reduction for Scalable Index Tuning	2024	SIGMOD	5.1587525e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,279	AI Meets AI: Leveraging Query Executions to Improve Index Recommendations	2019	SIGMOD
2	11,306	Looking Deeply into the Magic Mirror: An Interactive Analysis of Database Index Selection Approaches	2024	VLDB
3	1,904	CoPhy: A Scalable, Portable, and Interactive Index Advisor for Large Workloads	2011	VLDB
4	5,869	ISUM: Efficiently Compressing Large and Complex Workloads for Scalable Index Tuning	2022	SIGMOD
5	10,413	Understanding and Detecting Query Performance Regression in Practical Index Tuning: [Experiments & Analysis]	2026	SIGMOD
6	4,643	Learned Index Benefits: Machine Learning Based Index Performance Estimation	2022	VLDB
7	5,359	QUIET: Continuous Query-driven Index Tuning	2003	VLDB
8	7,750	DISTILL: Low-Overhead Data-Driven Techniques for Filtering and Costing Indexes for Scalable Index Tuning	2022	VLDB
9	9,615	Wii: Dynamic Budget Reallocation In Index Tuning	2024	SIGMOD
10	5,091	Budget-aware Index Tuning with Reinforcement Learning	2022	SIGMOD