E3-Rewrite: Learning to Rewrite SQL for Executability, Equivalence, and Efficiency¶
Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM Reasoning
Keywords: SQL Query Rewriting, Reinforcement Learning, GRPO, Execution-Aware Context, Hybrid Demonstration Retrieval
TL;DR¶
E3-Rewrite is an end-to-end LLM-based SQL rewriting framework that breaks free from rigid rule-based paradigms by incorporating execution plan hints into context and optimizing executability, equivalence, and latency through a two-stage curriculum-guided GRPO framework, reducing query execution time by up to 25.6% over strong baselines.
Background & Motivation¶
Efficient query processing is a cornerstone of modern relational database systems, and SQL query rewriting serves as a crucial optimization technique aimed at reformulating a query into an equivalent variant that incurs lower execution latency. Historically, query rewriting has been dominated by rule-based systems that rely on hand-crafted heuristic rules (e.g., in Volcano or PostgreSQL optimizers) or search-based rule selectors such as LearnedRewrite, which utilizes Monte Carlo Tree Search (MCTS) guided by cost models. Recently, large language models (LLMs) have been introduced into this domain through systems like LLM-R² and R-Bot, which deploy LLMs as prompt-based selectors or retrievers for predefined rewrite rules (e.g., Apache Calcite rules). Despite reducing manual rule engineering, these approaches remain inherently constrained by the bounded expressiveness of fixed rule sets, fragile rule inter-dependencies, and an inability to generalize to unseen query patterns, such as complex multi-table joins and correlated subqueries requiring holistic transformations like pre-aggregated Common Table Expressions (CTEs).
While LLMs possess impressive symbolic reasoning and structural generalization capabilities that could enable direct, rule-free SQL-to-SQL rewriting, adapting them to this domain introduces severe challenges. Supervised fine-tuning (SFT) is ill-suited because SQL query rewriting lacks unique ground-truth references—many equivalent rewrites exist, and their quality can only be determined through physical database execution feedback. However, foundational LLMs suffer from a fundamental lack of execution awareness. When operating strictly on plain-text SQL queries, models cannot perceive physical execution realities such as join orderings, table scan overheads, or operator bottlenecks. Consequently, naive LLM generation frequently produces invalid SQL syntax, introduces semantic drift that corrupts query results, or generates syntactically valid rewrites that actually degrade execution performance.
The fundamental tension lies in the severe optimization conflicts and reward sparsity among three competing criteria: Executability (adhering to DBMS dialect syntax), Semantic Equivalence (producing identical result tuples across arbitrary database states), and Efficiency (strictly reducing physical execution latency). Directly optimizing raw latency through reinforcement learning (RL) destabilizes policy gradients, causing catastrophic degradation in equivalence and syntax validity. The core idea of this work is to construct an execution-aware context by linearizing DBMS query execution plans to expose physical performance bottlenecks, and employ a two-stage curriculum GRPO training pipeline that establishes correctness before optimizing efficiency, augmented by a dynamic hybrid structural-semantic demonstration retrieval library.
Method¶
Overall Architecture¶
E3-Rewrite operates through an end-to-end framework encompassing execution-aware prompting, two-stage reinforcement learning, and dynamic demonstration retrieval. Given an input query, the system first interfaces with the database engine to extract its query plan (using detailed EXPLAIN ANALYZE during offline training and lightweight EXPLAIN during online inference). This hierarchical tree is linearized into an indented, human-readable execution hint and prepended to the input query to expose operator-level bottlenecks (e.g., sequential scans and correlated subquery loops). During policy optimization, E3-Rewrite employs Group-Relative Policy Optimization (GRPO) to sample candidate rewrites and compute group-normalized advantages, optimizing a composite reward that balances executability, strict equivalence, and optimizer cost reduction. To prevent reward conflicts, training follows a progressive curriculum: Stage 1 focuses strictly on correctness (executability and multi-tier semantic equivalence), while Stage 2 activates the performance reward alongside experience rehearsal to refine latency. At inference time, a hybrid retriever selects top-\(k\) demonstrations from a dynamic pool using both AST tree-edit distance and embedding cosine similarity; rewrites yielding significant speedups (>0.5×) are dynamically added back to continuously enrich the pool.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Input Raw SQL & Target DBMS Context"] --> B["Execution Hint Injection<br/>EXPLAIN Plan Linearization & Bottleneck Exposure"]
B --> C["Two-Stage Curriculum GRPO Training<br/>Stage 1 Correctness First → Stage 2 Efficiency Refinement"]
C --> D["Hybrid Demonstration Retrieval & Pool Evolution<br/>AST Tree-Edit Distance + Dense Semantic Similarity"]
D --> E["Output Executable, Equivalent & Efficient Rewritten SQL"]
Key Designs¶
1. Execution Hint Injection: Textual SQL representations are decoupled from physical database runtime bottlenecks
Standard language models cannot deduce the physical execution cost of relational operators from declarative SQL syntax alone, often missing opportunities to push down predicates or resolve unindexed table scans. E3-Rewrite bridges this gap by extracting the physical query plan generated by the DBMS optimizer (e.g., PostgreSQL). The tree-structured plan is linearized into an indented text sequence preserving operator hierarchy, node costs (startup and total cost), output row counts, and filter discard metrics (Rows Removed by Filter). Prepending this linearized hint to the SQL query provides direct structural cues, enabling the model to immediately recognize inefficient execution paths (such as row-by-row correlated subquery evaluations) and formulate targeted rewrites, such as restructuring the subquery into an explicit join against an aggregated CTE.
2. Two-Stage Curriculum GRPO Training: Multiobjective reward conflict and training instability between correctness and latency
Optimizing for execution latency from the outset frequently causes RL agents to exploit degenerate shortcuts that violate SQL syntax or destroy semantic equivalence. E3-Rewrite adopts Group-Relative Policy Optimization (GRPO), eliminating the value network and stabilizing gradient updates via intra-group reward normalization across \(N\) sampled candidates. The composite reward is defined as \(R_{\text{total}} = \lambda_{\text{eq}}R_{\text{eq}} + \lambda_{\text{exec}}R_{\text{exec}} + \lambda_{\text{perf}}R_{\text{perf}}\). Executability \(R_{\text{exec}} \in \{0, 1\}\) is verified via DBMS parsing. Equivalence \(R_{\text{eq}} \in \{0, 1\}\) uses a tiered cascade: first invoking symbolic provers (SQLSolver and QED), then falling back to a lightweight LLM judge, and finally executing queries over sample database instances. Efficiency \(R_{\text{perf}} = \max(0, \frac{T(q) - T(q')}{T(q)})\) measures relative optimizer-estimated cost reduction. The optimization is orchestrated through a two-stage curriculum: Stage 1 trains exclusively with correctness rewards (\(\lambda_{\text{perf}} = 0\)), guiding the policy to reliably master dialect syntax and semantic preservation. Once correctness stabilizes, Stage 2 introduces \(R_{\text{perf}}\) alongside rehearsal samples from Stage 1, enabling the policy to pursue aggressive speedups without compromising equivalence.
3. Hybrid Demonstration Retrieval and Pool Evolution: Limited generalization of static in-context examples across diverse query structures
Relying solely on semantic embedding similarity retrieves examples with similar business topics but divergent syntax trees, while pure AST structural matching misses semantic intent and table relationships. E3-Rewrite implements a hybrid similarity metric:
Structural similarity \(\mathrm{Sim}_{\text{struct}}(q, q_i) = 1 - \frac{\mathrm{TED}(\mathcal{T}(q), \mathcal{T}(q_i))}{\max(|\mathcal{T}(q)|, |\mathcal{T}(q_i)|)}\) is computed using the APTED algorithm over operator-level ASTs, while semantic similarity \(\mathrm{Sim}_{\text{sem}}(q, q_i) = \cos(e_q, e_{q_i})\) uses sentence transformer embeddings. At inference time, top-\(k\) relevant pairs are retrieved as in-context demonstrations. Furthermore, the demonstration pool is dynamically updated: whenever a newly generated rewrite passes equivalence verification and achieves a speedup greater than 0.5×, the input-rewrite pair is appended to the pool, allowing the model to continually accumulate generalizable optimization patterns across evolving workloads.
Loss & Training¶
The rewriting policy is initialized from open-source Qwen3 models (Qwen3-14B and Qwen3-32B). Training is conducted over approximately 8,000 source SQL queries from the training partitions of TPC-H, IMDB, and DSB on 8× NVIDIA A100 (80GB) GPUs, requiring approximately 60 GPU hours. The batch size is set to 256, sampling 4 to 8 candidate rewrites per prompt. Policy updates utilize clipped surrogate objectives with KL divergence regularization against the reference policy to prevent policy drift.
Key Experimental Results¶
Main Results¶
All queries are evaluated on PostgreSQL v14 under an identical server environment (24-core Intel Xeon @ 3.0GHz, 512 GB RAM) with a strict 300-second execution timeout. Each query is executed five times, discarding the minimum and maximum runs before averaging.
| Benchmark | Metric | Original | LearnedRewrite | LLM-R² | R-Bot | E3-Rewrite (Ours) |
|---|---|---|---|---|---|---|
| TPC-H (10G) | Average Latency (s) | 78.81 | 41.34 | 54.76 | 39.89 | 29.67 |
| Median Latency (s) | 10.75 | 9.73 | 10.02 | 9.15 | 8.63 | |
| p90 Tail Latency (s) | 300.00 | 103.41 | 300.00 | 84.27 | 51.37 | |
| Equivalence Rate (%) | - | 88.8 | 91.2 | 96.8 | 99.6 | |
| IMDB (JOB) | Average Latency (s) | 5.74 | 5.73 | 5.32 | 5.54 | 5.01 |
| Median Latency (s) | 1.54 | 1.54 | 1.47 | 1.52 | 1.44 | |
| p90 Tail Latency (s) | 18.53 | 18.51 | 17.44 | 18.07 | 16.71 | |
| Equivalence Rate (%) | - | 100.0 | 99.2 | 98.6 | 99.4 | |
| DSB | Average Latency (s) | 38.83 | 32.61 | 20.12 | 27.75 | 16.93 |
| Median Latency (s) | 3.53 | 3.19 | 2.96 | 3.12 | 2.46 | |
| p90 Tail Latency (s) | 300.00 | 98.67 | 48.67 | 89.96 | 38.47 | |
| Equivalence Rate (%) | - | 76.4 | 86.4 | 95.4 | 98.8 |
Ablation Study¶
Component-wise ablations conducted on the TPC-H benchmark isolate the contribution of each design element:
| Configuration | Avg. Latency (s) | Improved Queries (#) | Equiv. Ratio (%) | Key Impact Analysis |
|---|---|---|---|---|
| E3-Rewrite (Full Model) | 29.67 | 210 | 99.6 | Full model with hints, curriculum GRPO, and dynamic retrieval |
| w/o Execution Plan Hints | 39.56 | 163 | 98.4 | Highest latency inflation (+9.89s); loses physical bottleneck insight |
| w/o Reinforcement Learning (RL) | 32.29 | 194 | 90.2 | Severe collapse in equivalence (-9.4%); proves necessity of reward alignment |
| w/o Demonstration Retrieval | 35.39 | 177 | 96.4 | 33 fewer improved queries; demonstrates degraded in-context transfer |
| Vanilla (Base LLM, zero-shot) | 56.71 | 125 | 84.8 | Baseline LLM fails across all three evaluation dimensions |
Key Findings¶
- Reinforcement learning is crucial for semantic preservation: Disabling the RL module causes the equivalence ratio to drop sharply from 99.6% to 90.2%, demonstrating that prompting base LLMs without reward alignment is insufficient for the strict correctness standards of relational database systems.
- Execution hints drive dramatic tail latency reductions: Omitting execution hints leads to the highest latency increase (29.67s to 39.56s), proving that physical optimizer feedback is essential for the model to identify hidden full scans and nested loops.
- Cascaded verification minimizes training overhead: Symbolic provers (SQLSolver and QED) successfully resolved 84.4%, 98.4%, and 79.6% of queries across TPC-H, IMDB, and DSB in under 0.9s, leaving only 4.4%, 0.6%, and 7.6% of difficult queries to expensive execution-based verification.
- Cross-dataset generalization is robust: When trained exclusively on TPC-H and evaluated on DSB, E3-Rewrite incurs only a slight latency increase (16.93s to 17.44s) while maintaining a 97.4% equivalence ratio, indicating that the model learns transferable relational algebra optimizations rather than dataset-specific memorization.
Highlights & Insights¶
- Tiered verification pipeline for scalable RL: By placing low-cost formal symbolic provers before an LLM judge and reserving actual database execution for rare edge cases, the framework solves the long-standing bottleneck of high verification overhead in execution-guided RL for SQL.
- Paradigm shift from rule selection to generative rewriting: Moving beyond the conventional constraint of selecting from a fixed catalogue of rewrite rules, E3-Rewrite demonstrates that an LLM can directly synthesize complex, multi-operator transformations such as CTE pre-aggregation and decorrelation.
- Transferable correctness-to-efficiency curriculum: The staged optimization strategy—locking in syntactic and semantic validity before optimizing non-functional execution latency—provides an actionable template for applying RL to compiler optimization, code translation, and hardware synthesis.
Limitations & Future Work¶
- Dependency on PostgreSQL optimizer ecosystem: The current implementation is tailored to PostgreSQL's plan formatting and cost estimation; porting to commercial DBMSs or distributed analytical engines (e.g., ClickHouse, Snowflake) requires developing engine-specific plan parsers and cost normalizers.
- Computational overhead of execution-in-the-loop training: Despite the tiered equivalence verifier, sampling candidate executions across thousands of queries requires significant database interaction time (60 A100 GPU hours).
- Static weighting of hybrid retrieval: The balance parameter \(\alpha\) and reward coefficients are currently tuned via manual grid search, lacking dynamic adaptation across diverse OLTP and OLAP workload characteristics.
Related Work & Insights¶
- vs. LearnedRewrite (VLDB 2021): LearnedRewrite relies on MCTS and learned cost estimators over a fixed set of rule combinations. E3-Rewrite eliminates the rule catalog bottleneck, directly generating complex CTE transformations that reduce TPC-H latency by an additional 28.2%.
- vs. LLM-R² (VLDB 2024) / R-Bot (VLDB 2025): LLM-R² and R-Bot use LLMs primarily to retrieve or recommend rules executed via Apache Calcite. E3-Rewrite operates in an end-to-end generative fashion, optimizing the SQL output directly with RL and achieving substantially higher equivalence and improvement counts.
- vs. QUITE (arXiv 2025): QUITE implements a training-free multi-agent pipeline with iterative correction. E3-Rewrite demonstrates that end-to-end parameter fine-tuning combined with execution-aware prompting yields superior single-pass inference latency (3.91s per query) while avoiding multi-agent coordination overhead.
Rating¶
- Novelty: ⭐⭐⭐⭐⭐ Pioneering end-to-end LLM-based SQL rewriting without explicit rule sets, featuring execution-aware plan linearization and a curriculum GRPO framework.
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ Comprehensive evaluation across TPC-H, IMDB, and DSB benchmarks, including latency percentiles, data scale scalability (1G to 10G), ablations, and cross-dataset testing.
- Writing Quality: ⭐⭐⭐⭐⭐ Rigorous technical exposition, clear formulation of database optimization concepts, and informative illustrative query transformations.
- Value: ⭐⭐⭐⭐⭐ Exceptional practical utility for autonomous database optimization and a compelling blueprint for non-functional code optimization with LLMs.