GenRewrite: Query Rewriting via Large Language Models

1 Introduction

• Manual rewriting is error-prone and unscalable, rule-based methods cannot optimize unseen patterns, and synthesis-based methods handle only simple queries in practice.Poorly written queries can impede efficient query plans and cause slow performance and higher expenses.Source: §1 · p. 1
• GenRewrite uses Natural Language Rewrite Rules (NLR2s) as LLM hints, human-readable explanations, and a means to transfer rewriting knowledge across queries.A utility score selects relevant rules, while counterexample-guided iteration corrects syntactic and semantic errors in candidate rewrites.Source: §1 · p. 2
• GenRewrite iterates through rewrite suggestion, correction, and evaluation, then uses automated verification or human inspection before deployment.Its target workloads are recurrent queries whose rewrite costs can be amortized and highly expensive queries; it is not designed for real-time, light ad hoc workloads.Source: §1 · p. 2
• The paper analyzes LLM query rewriting challenges and presents GenRewrite as a holistic system for autonomous rewriting beyond traditional rules.Its evaluation covers TPC-DS and JOB and their SQLStorm-generated variants.Source: §1 · pp. 2–3
• At the ≥2x threshold on TPCDS, GenRewrite improves 25 queries—1.35x more than LLM-driven baselines and 2.6x more than LLM-enhanced rule-based baselines.It optimizes more queries at every speedup threshold than all baselines; the gap widens further on TPC-DS (SQLStorm), while gains are smaller but GenRewrite still leads on JOB and its SQLStorm variant.Source: §1 · p. 3

2.1 Limitations of Traditional Query Rewriting

• Rule-based rewriters cannot optimize patterns absent from their rule sets, synthesis-based methods handle only simple queries, and manually finding new anti-patterns is infeasible.LLMs offer a potential way to identify and exploit such rewrite opportunities through reasoning.Source: §2.1 · p. 3
• A rewrite of the second-highest-salary query is approximately 2000x faster than the human-written query on a database with one million rows.The rewrite reduces comparisons by first finding the maximum salary and then finding the second maximum; no existing rewrite rule captures the transformation.Source: §2.1 · p. 3
• The TPC-DS Q11 rewrite is 9x faster, although no existing rewrite rules achieve the transformation.It separates store and web sales into distinct CTEs and removes filters that cancel the effect of the original UNION ALL and subsequent filtering.Source: §2.1 · p. 3

2.2 Large Language Models: Background

• Baseline LLM rewriting concatenates a task prompt with the input query, denoted p||q.The prompt provides natural-language instructions to guide the model’s output.Source: §2.2 · p. 4

Lesson 1

• With GPT-4 and the basic prompt, none of ten attempts on TPC-DS Q4 suggested removing UNION ALL, compared with four of ten Q11 attempts and six of ten Q74 attempts moving in that direction.Q4 had the highest token count, most UNION ALL segments, and most joins among the three queries; a correct direction did not guarantee an equivalent rewrite.Source: §3 · p. 4
• LLMs’ likelihood of finding meaningful transformations decreases with query complexity, requiring more runs and higher costs; even sound transformation logic may yield incorrect rewrites.The paper reports that LLMs are effective on simpler workloads but struggle with complex rewrites.Source: §3 · p. 4

Lesson 2

• A concise hint such as “avoid the unnecessary UNION ALL” consistently led LLMs to suggest that transformation across attempts.Compared with few-shot examples, concise hints use fewer tokens and are easier for humans to interpret, but manually tailoring them to each query is impractical.Source: §3 · p. 4

4 Our Approach

• The pipeline suggests candidate rewrites, corrects them iteratively, and evaluates their effectiveness while integrating an NLR2 repository for knowledge transfer.Correction feedback comes from the LLM for semantics and the database for syntax; evaluation uses a verifier or tester for equivalence and execution or a cost model for performance.Source: §4 · pp. 4–5

4.1 Natural Language Rewrite Rules (NLR2s)

• NLR2s express contextual rewrite hints and explanations in natural language rather than fixed pattern-matching transformations.GenRewrite collects rules alongside effective rewrites, then uses dominant-rule identification and LLM-based grouping to attribute benefits and reduce redundant invocations.Source: §4.1 · pp. 5–6

4.2 Suggesting Candidate Rewrites

• GenRewrite analyzes query plans for performance bottlenecks, retrieves similar past queries, and applies the selected query’s most beneficial associated NLR2.It uses embedding-based top-k retrieval followed by LLM refinement, falling back to the basic prompt if none of the candidates is a good match.Source: §4.2 · p. 7

4.3 Correcting Candidate Rewrites

• Counterexample-guided correction separates semantic errors from syntax errors and iteratively refines candidate rewrites for equivalence and executability.Semantic correction uses LLM-identified counterexamples; syntax correction uses database feedback from EXPLAIN.Source: §4.3 · p. 7

4.4 Evaluating Candidate Rewrites

• Only rewrites that pass the correctness gate undergo performance evaluation, and a rewrite is accepted only under a “never-worse-off” policy.The system uses verification or testing for equivalence and offline shadow execution against the target database for performance, with a static cost proxy to pre-filter trials.Source: §4.4 · pp. 7–8

5.1 Experimental Setup

• The evaluation covers TPC-DS, JOB, and SQLStorm-generated variants, using the 100 slowest TPC-DS and 50 slowest JOB SQLStorm queries.LLM-based methods produce four candidates per query; GenRewrite starts without pre-seeded rules, then retrieves relevant NLR2s in later iterations.Source: §5.1 · pp. 8–9

5.2 Comparison with LLM-based Methods

• On original TPC-DS, GenRewrite speeds up 25 queries by at least 2x and 9 by at least 10x, versus Baseline LLM’s 18 and 6 and LITHE’s 16 and 6.On TPC-DS (SQLStorm), GenRewrite speeds up 25 queries by at least 2x and 13 by at least 10x, compared with Baseline LLM’s 12 and 9 and LITHE’s 19 and 11.Source: Table 3 · p. 9, §5.2 · p. 9

5.3 Comparison with Rule-based Methods

• On original TPC-DS, GenRewrite achieves at least 2x speedup on 25 queries, versus 10 for LLM-R2, 9 for R-Bot, and 6 for LR.The gap widens on TPC-DS (SQLStorm), where Calcite-based baselines face parser and rule coverage limits, while GenRewrite can refine rewrites for those queries.Source: Table 3 · p. 9, §5.3 · p. 11

5.2 Comparison with LLM-based Methods

• On TPC-DS, GenRewrite finds an equivalent rewrite for 85.9% of queries versus Baseline LLM’s 74.7%, and 70% of its generated rewrites are correct versus 51.8%.About one-third of Baseline LLM rewrites fail to execute, compared with 13.3% for GenRewrite; counterexample-guided correction repairs invalid or inequivalent rewrites, while NLR2s transfer rewrite knowledge.Source: Table 4 · p. 10, §5.2 · p. 10

5.3 Comparison with Rule-based Methods

• On SQLStorm workloads, retrieved demonstrations and fixed rule inventories can fail to match new query forms, whereas GenRewrite accumulates transferable rewrite knowledge and iteratively refines rewrites.Patterns discovered include replacing UNION-then-self-join with conditional aggregation and consolidating repetitive subqueries; the reported evaluation also notes LLM-enhanced rule-based methods can fall behind LR on SQLStorm.Source: §5.3 · p. 11

5.4 Detailed Analysis and Ablation Study

• NLR2 grouping reduces the average rules per input query from 13.24 to 5.08; without grouping, average LLM runtime rises 153.9% and monetary cost 140.3%.Plan-based dominant NLR2 identification reduces execution overhead by avoiding runtime measurement for every rewrite generated from a single NLR2.Source: §5.4 · p. 12
• Bottleneck-aware NLR2 retrieval improves performance, while applying globally top-ranked NLR2s performs essentially like Baseline LLM.The ablation indicates that effective reuse depends on matching NLR2s to query performance bottlenecks.Source: §5.4 · p. 12
• GenRewrite with gpt-4o is outperformed by o3-mini, and supplying gpt-4o with o3-mini-discovered NLR2s raises queries with at least 10x speedup from 5 to 8.The reported weakness of gpt-4o is primarily in discovering effective rewrites and summarizing NLR2s, rather than applying supplied NLR2s.Source: §5.4 · p. 12
• Semantic plus syntax correction outperformed no correction and semantic-only correction at every candidate budget k, while larger k improved coverage with diminishing returns and higher cost.The comparison counts queries achieving at least one equivalent rewrite and at least one equivalent rewrite at least 20% faster as k ranges from 1 to 4.Source: §5.4 · p. 12
• Increasing the desired speedup threshold reduces coverage but raises the average speedup among accepted rewrites; the implementation sets θ to 1.2x.With a lower threshold, more rewrites are retained, including many that are only modestly faster.Source: §5.4 · p. 12
• The counterexample-based prompt produced 29% equivalent rewrites before syntax correction with a 6% false-positive rate, versus 26% and 22% for Miniature & Mull.The authors conclude that their prompt better supports iterative correction by producing more verified equivalents and fewer false positives.Source: §5.4 · p. 12

5.5 Time and Monetary Cost

• An o3-mini rewrite for a TPC-DS query costs $0.029 and takes 36.15 s on average, compared with ($0.026, 25.1 s) for gpt-4o and ($0.004, 71.71 s) for gpt-4o-mini.Cost scales approximately linearly with the number of candidate rewrites; auxiliary LLM steps add negligible overhead, and the expense is described as a one-time, amortized cost for recurring workloads.Source: §5.5 · p. 12
• Semantic correction dominates time and cost across models, while o3-mini uses more iterations and gpt-4o and gpt-4o-mini rewrite more conservatively.Equivalence testing used 60-second tester and 5-second verifier timeouts; performance-evaluation time ranged from seconds to hours, with early termination when a candidate failed the desired speedup threshold.Source: §5.5 · p. 12

Evaluation analyses

• The discussion evaluates design choices by LLM runtime, cost, and speedup shares, alongside candidate-budget effects under different correction strategies and per-candidate cost.Source: Table 6 · p. 13, Table 7 · p. 13, Table 9 · p. 13

Verification and rule extraction

• SQLSolver verifies only 18.9% of generated TPCDS rewrites and 74.4% of JOB rewrites, so all evaluation rewrites were manually inspected.The passage notes that inequivalent rewrites become harder to spot as query complexity grows.Source: §6 · p. 13
• Equivalence verification can be resource-intensive, though finding a substantially faster rewrite may justify the cost, especially for recurring queries.Source: §6 · p. 13
• GenRewrite is intended to propose verified query pairs with measured speedups and associated NLR2s, not to replace rule-based methods.Source: §6 · p. 13
• Aggregating verified pairs linked to the same NLR2 supports extracting shared AST or plan transformations with explicit guards and preconditions.A rule distilled from one pair can overfit incidental syntax and miss necessary preconditions; additional pairs make the pattern more general while remaining safe.Source: §6 · p. 13

Query rewriting

• Rule-based systems cannot optimize unseen query patterns, while synthesis-based approaches struggle with complex queries such as those in TPC-DS.Source: §7 · p. 13
• LITHE uses a fixed set of six handcrafted rules, whereas QUITE selects refinement actions from a curated knowledge base of documented heuristics.Source: §7 · p. 13
• Unlike fixed-rule or curated-action approaches, GenRewrite can propose novel rewrites and accumulate generalizable NLR2 knowledge over time.The passage says this includes patterns absent from existing literature.Source: §7 · p. 13

LLMs in databases

• Other database uses of LLMs include NL2SQL, schema matching, SQL data augmentation, equivalence checking, tuning, diagnostics, optimization, and indexing.Source: §7 · pp. 13–14
• NLR2 clusters query pairs with shared issues to support extracting robust rewrite rules for database implementation.Source: §7 · p. 13

Conclusion

• GenRewrite introduces NLR2s for transferring rewriting knowledge between queries and counterexample-guided correction of syntactic and semantic errors.Source: §8 · p. 14
• Across TPC-DS, JOB, and their SQLStorm variants, GenRewrite optimizes a wider range of complex queries and achieves faster speedups than all baselines.Source: §8 · p. 14

• Other patterns pivot per-slice aggregates, consolidate repetitive subqueries with conditional expressions, decorrelate IN through a distinct-key mapping, and replace bounded recursion with a numbers-table cross join.Source: A Representative rewrite patterns… · p. 16
• Several EXISTS checks can be replaced by one precomputed eligibility set joined once, while correlated COUNT(*)>0 can become EXISTS.Source: A Representative rewrite patterns… · p. 16
• A per-key summary can be lifted into one CTE and reused across branches, eliminating rescans of the fact table.Source: A Representative rewrite patterns… · p. 16

A.1 Pattern 1

• Per-channel conditional aggregates pivot each slice into columns, allowing one join to express cross-slice ratio predicates instead of UNION output and multiple self-joins.Source: SELECT · p. 16

SELECT

• Prior work describes fusion and branch tagging, but not pivoting per-slice aggregates into columns to avoid the downstream multi-self-join.Source: SELECT · p. 16

A.2 Pattern 2

• Multiple correlated EXISTS predicates across fact tables can be factored into one eligibility set using UNION/INTERSECT and joined once.Source: §A.2 · pp. 16–17

A.3 Pattern 3

• A correlated COUNT(*)>0 subquery can be rewritten as EXISTS, removing the aggregate and enabling semi-join evaluation.Source: §A.3 · p. 17

A.4 Pattern 4

• A bounded self-recursive CTE can be replaced by a non-recursive base query cross joined with a small numbers table to generate expanded rows.Source: §A.4 · p. 17, UNION ALL SELECT · p. 17

A.5 Pattern 5

• A per-key summary can be lifted into one CTE and used as the input for all branches, eliminating rescans of the fact table.Source: SELECT · p. 18, §A.5 · p. 18

B NLR2 →guarded executable rules

• The pivot rule requires shared grouping keys, a finite slice domain, downstream selection of particular channel-slice rows, and NULL-ignoring aggregation.Source: B NLR2 →guarded executable rules · p. 19
• The rule creates one column per channel and slice, preserving per-slice values while converting self-join filters into column selections and retaining equality joins on grouping keys.Source: B NLR2 →guarded executable rules · p. 19
• Across TPC-DS Q4, Q11, and Q74, the same NLR2 successfully guides rewrites that jointly support a single guarded, executable rule.Source: B NLR2 →guarded executable rules · p. 19, Table 10 · p. 19
• Aggregating multiple verified pairs tied to one NLR2 helps remove query-specific quirks and derive a more general rule with explicit guards and preconditions.Source: B NLR2 →guarded executable rules · p. 19