Leveraging Query Optimizers to Verify the Soundness of LLM-based Query Rewrites for Real-World Workloads, and More!

Summary: Empirical study on Microsoft SQL Server shows LLM-based query rewriting improves real-world workloads but cannot guarantee semantic equivalence. Propose a sound, efficient equivalence-checking technique leveraging optimizer capabilities and show LLM rewrites expose missing optimizer transformation rules. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h40d13bba55364df7
Venue: CIDR
Year: 2026
Pagerank: 5.115551e-05
Overall Rank: 9,754 | 34.62%
DOI: -
PDF: Download (CC BY 4.0)

Incoming Non-self Citations Over Time

Authors

1. Vivek Narasayya (Microsoft)
2. Surajit Chaudhuri (Microsoft)

BibTeX Citation

@inproceedings{narasayya_cidr26,
        address = {Amsterdam, Netherlands},
        series = {{CIDR} '26},
        title = {{Leveraging Query Optimizers to Verify the Soundness of LLM-based Query Rewrites for Real-World Workloads, and More!}},
        booktitle = {Proceedings of the {Conference} on {Innovative} {Data} {Systems} {Research}},
        author = {Narasayya, Vivek and Chaudhuri, Surajit},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,382	Automated Database Testing via LLM-Synthesized SQL Features	2027	SIGMOD	4.9605343e-05
10,988	Evaluating the Practical Effectiveness of LLM-Driven Index Tuning on Microsoft SQL Server	2026	VLDB	4.9605343e-05
11,041	Verified LLM-Based Query Rewriting for Microsoft SQL Server	2026	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 24 of 24 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061463175
473	The Making of TPC-DS	2006	VLDB	0.00017656775
493	Database Tuning Advisor for Microsoft SQL Server 2005	2004	VLDB	0.0001735831
554	Orthogonal Optimization of Subqueries and Aggregation	2001	SIGMOD	0.00016487919
787	Cosette: An Automated Prover for SQL	2017	CIDR	0.00013959502
1,513	DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems	2021	VLDB	0.00010394557
1,678	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB	9.8966017e-05
1,888	WeTune: Automatic Discovery and Verification of Query Rewrite Rules	2022	SIGMOD	9.4148912e-05
1,956	LLM-R^2: A Large Language Model Enhanced Rule-based Rewrite System for Boosting Query Efficiency	2025	VLDB	9.2927535e-05
2,054	WinMagic : Subquery Elimination Using Window Aggregation	2003	SIGMOD	9.1030561e-05
2,389	A Learned Query Rewrite System using Monte Carlo Tree Search	2022	VLDB	8.5228689e-05
2,971	Proving Query Equivalence Using Linear Integer Arithmetic	2023	SIGMOD	7.7851336e-05
2,995	Panda: Performance Debugging for Databases using LLM Agents	2024	CIDR	7.7556154e-05
3,050	Configuration-Parametric Query Optimization for Physical Design Tuning	2008	SIGMOD	7.6969161e-05
3,158	GenRewrite: Query Rewriting via Large Language Models	2026	SIGMOD	7.5676704e-05
4,079	QueryBooster: Improving SQL Performance Using Middleware Services for Human-Centered Query Rewriting	2023	VLDB	6.8026178e-05
4,116	QED: A Powerful Query Equivalence Decider for SQL	2024	VLDB	6.7846764e-05
4,383	R-Bot: An LLM-based Query Rewrite System	2025	VLDB	6.6140223e-05
5,896	Unified Query Optimization in the Fabric Data Warehouse	2024	SIGMOD	5.9383626e-05
6,294	Incorporating Super-Operators in Big-Data Query Optimizers	2020	VLDB	5.8043081e-05
7,388	Towards Foundation Database Models	2025	CIDR	5.5211011e-05
7,768	DBG-PT: A Large Language Model Assisted Query Performance Regression Debugger	2024	VLDB	5.4392507e-05
8,286	User-Optimizer Communication using Abstract Plans in Sybase ASE	2001	VLDB	5.3449621e-05
10,225	COMPARE: Accelerating Groupwise Comparison in Relational Databases for Data Analytics	2021	VLDB	5.0460607e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,963	Developing and Benchmarking Verification Algorithms to Improve Text-to-SQL Generation	2026	VLDB
2	10,323	This is Going to Sound Crazy, But What If We Used Large Language Models to Boost Automatic Database Tuning Algorithms By Leveraging Prior History? We Will Find Better Configurations More Quickly Than Retraining From Scratch!	2026	SIGMOD
3	4,383	R-Bot: An LLM-based Query Rewrite System	2025	VLDB
4	10,988	Evaluating the Practical Effectiveness of LLM-Driven Index Tuning on Microsoft SQL Server	2026	VLDB
5	3,717	Logical and Physical Optimizations for SQL Query Execution over Large Language Models	2025	SIGMOD
6	10,903	ReSequel: Robust LLM-assisted Query Rewriting and Optimization using Templatization and Sampling	2026	VLDB
7	6,584	Can Large Language Models Be Query Optimizer for Relational Databases?	2026	SIGMOD
8	1,956	LLM-R^2: A Large Language Model Enhanced Rule-based Rewrite System for Boosting Query Efficiency	2025	VLDB
9	3,158	GenRewrite: Query Rewriting via Large Language Models	2026	SIGMOD
10	11,041	Verified LLM-Based Query Rewriting for Microsoft SQL Server	2026	VLDB