SPA: A SQL-Plan-Aware Reinforcement Learning Framework for Query Rewriting with LLMs

Plan-aware RL with adaptive reward shaping and self-improvement for database query optimization

Xinyi Huang; Zhengjie Miao· 2026· DOI 10.48550/arXiv.2606.08620

The core problem

SQL query rewriting improves database performance without schema or index changes, but finding effective rewrites for modern analytical workloads remains difficult. Rule-based methods are limited to predefined transformations, while LLM-based approaches often produce rewrites that are semantically valid but compile to equivalent physical plans or degrade runtime performance. The paper introduces SPA, a SQL-Plan-Aware reinforcement learning framework that trains LLMs to rewrite queries using physical execution feedback. SPA formulates rewriting as a policy optimization problem and extends GRPO with rewards spanning semantic equivalence, textual rewrite distance, physical-plan divergence, and runtime speedup. To handle reward sparsity across query difficulty, SPA introduces Probability-Gated Adaptive Reward Shaping, a query-level curriculum that unlocks higher-level rewards only once a rollout group achieves sufficient mastery of lower-level objectives. It further improves sample efficiency through on-policy self-improvement by recycling slowdown rewrites from the current policy as targeted training signals.

SPA was evaluated on both in-distribution (IID) and out-of-distribution (OOD) workloads. It outperforms rule-based and strong LLM baselines in end-to-end runtime. The framework substantially reduces harmful slowdown rewrites and yields strong tail-latency gains. Specific quantitative results are not provided in the abstract, but the authors report consistent improvements across IID and OOD settings.

SQL query rewriting improves database performance without schema or index changes, but finding effective rewrites for modern analytical workloads remains difficult. Rule-based methods are limited to predefined transformations, while LLM-based approaches often produce rewrites that are semantically valid but compile to equivalent physical plans or degrade runtime performance. The paper introduces SPA, a SQL-Plan-Aware reinforcement learning framework that trains LLMs to rewrite queries using physical execution feedback. SPA formulates rewriting as a policy optimization problem and extends GRPO with rewards spanning semantic equivalence, textual rewrite distance, physical-plan divergence, and runtime speedup. To handle reward sparsity across query difficulty, SPA introduces Probability-Gated Adaptive Reward Shaping, a query-level curriculum that unlocks higher-level rewards only once a rollout group achieves sufficient mastery of lower-level objectives. It further improves sample efficiency through on-policy self-improvement by recycling slowdown rewrites from the current policy as targeted training signals.

SPA casts query rewriting as a policy optimization problem where an LLM policy π_{θ} generates rewritten SQL queries given an original query. The framework extends Group Relative Policy Optimization (GRPO) with a composite reward function:

The key innovation of SPA lies in its plan-aware reward design and adaptive curriculum. By incorporating physical-plan divergence and runtime speedup, SPA directly optimizes for execution efficiency rather than mere textual similarity. The Probability-Gated Adaptive Reward Shaping mechanism effectively addresses reward sparsity, enabling the model to learn progressively. On-policy self-improvement further enhances sample efficiency by turning failures (slowdown rewrites) into learning opportunities. The results demonstrate that SPA can generalize to OOD workloads, suggesting robustness. However, the paper does not discuss potential limitations such as computational overhead of plan evaluation or scalability to very large query sets. Future work could explore integrating SPA with other database optimization techniques or extending it to multi-query workloads.

CS practitioners and researchers

Opening member content…