Retrieval Keyed on Execution Symptoms for Query Plan Repair

When a database runs a slow query, it can report exactly where the time went. The EXPLAIN ANALYZE output shows, for each step of the plan, how many rows the optimizer expected versus how many actually appeared, which operators spilled to disk, and which scans missed the buffer cache. Current systems that use large language models (LLMs) to speed up SQL mostly ignore this signal when they look up past knowledge. They retrieve rewrite rules or example rewrites by matching the query's text or syntax tree, once, before any execution happens. This proposal takes the opposite approach. We build a memory of past repair attempts, each indexed by the execution symptom that prompted it, such as "the optimizer expected 50 rows at this hash join but saw 2 million, and the join spilled." The system writes to this memory itself: every fix it tries, and every measured speedup or regression, becomes a new entry. During an iterative repair loop, retrieval is triggered again each time fresh execution telemetry arrives.

The application regime is the one where LLM latency is affordable: recurring query templates that are optimized offline and then reused many times. Learned Query Superoptimization argues that such templates justify hours of compute. The central claim is testable. A repair loop that retrieves by execution symptom should reach better plans in fewer executed candidates than the same loop retrieving by query structure. It should also transfer to unseen templates and schemas, because the symptoms do not depend on table names. If symptom-keyed retrieval does no better than structure-keyed retrieval over the same memory contents, the idea fails.

Core Claim and What Is New

The closest existing system is QUITE. It already combines all four input directions. A finite-state machine of LLM agents (reasoning, rewrite, a formal equivalence checker, and a decision agent) iterates over SQL rewrites. The agents are backed by a curated knowledge base of 241 optimization units and a hint recommender. QUITE's knowledge base is static and curated offline, and retrieval is not conditioned on runtime behavior. R-Bot retrieves rules and community Q&As by a hybrid of syntax-tree structure and text semantics, then reflects on plans. LLM-R2 retrieves demonstrations with a learned query representation, and its LLM only selects among verified rules. In all three, the retrieval key is the query. FOSS iteratively repairs physical plans with a reinforcement-learning policy scored by a learned plan comparator. It does not read execution diagnostics and keeps no inspectable memory of fixes.

What is new here is the retrieval key and the write path. The key is a schema-agnostic symptom signature extracted from operator-level telemetry. The memory is written by the system's own measured outcomes, including failures. The idea borrows from dynamic retrieval in text generation. RaDIO triggers retrieval when a detector flags a likely hallucination. We trigger retrieval when execution contradicts the optimizer's expectations. The idea also borrows from execution-gated code optimization. POLO profiles C/C++ projects, proposes refactorings, and lets a decision agent accept or reject them on measured speedup. We apply that accept-or-reject discipline to declarative queries and to physical plans.

Research Program

We will build a loop with one LLM proposer and one deterministic judge.

Proposer. Given the current query, its annotated plan, the extracted symptom signature, and the top retrieved memory records, the proposer emits one of two kinds of candidate. The first is a SQL rewrite, for example decorrelating a subquery into a common table expression (a named intermediate result). The second is a physical hint that pins a join order or operator.

Symptom signature. The signature is a small tree mirroring the plan. Each node carries:

  • the operator type,
  • the log ratio of actual to estimated rows,
  • spill and cache-miss flags,
  • the fraction of total time spent in that node.

Like Bao's tree convolutional plan encoder, it omits table and column names so that it can cross schemas.

Memory records. Each record stores four things: the signature, the proposed edit (abstracted from specific identifiers), the equivalence verdict, and the measured latency ratio across parameter bindings. Retrieval uses a tree-convolutional embedding of the signature, trained contrastively so that signatures whose fixes produced similar speedups sit close together. We also compare against plain nearest-neighbor retrieval over hand-built features.

Judge. Multi-agent decomposition enters only as a constraint here, and deliberately so. Peacemaker or Troublemaker reports that LLM critics drift toward agreement. Adversarial Review reports diminishing returns from adding more agents. So the judge is not an LLM. It runs a formal equivalence check of the kind QUITE uses (SQLSolver). It then executes the candidate under a timeout equal to the best latency seen so far, following Balsa's safe-execution idea. Finally, it applies a regression rule across parameter bindings. That rule matters because a plan tuned for one binding of a recurring template can collapse on a skewed binding, which is the failure mode Eraser documents for learned optimizers.

Acceptance rule. Let $B$ be a set of sampled bindings of a template. Let $t_b(p)$ be the measured latency of plan $p$ on binding $b$, and let $\epsilon$ be a small regression tolerance. A candidate $p'$ replaces the incumbent $p$ only if

$$\max_{b \in B} \frac{t_b(p')}{t_b(p)} \le 1+\epsilon \quad \text{and} \quad \Big(\prod_{b \in B} \frac{t_b(p')}{t_b(p)}\Big)^{1/|B|} < 1.$$

The first condition blocks worst-case regressions on any binding. The second requires an overall geometric-mean gain.

Rejected candidates are written to memory too. This is meant to counter the tendency of feedback loops to plateau (Yan et al.) or to fixate on a flawed strategy (Srivastava et al.). A retrieved record showing that "hinting a nested-loop join under this symptom regressed by 3×" steers the proposer away from that move.

Baselines

PostgreSQL defaults. The naive reference is PostgreSQL's own plan with no intervention. All speedups are reported relative to it on our hardware.

Exhaustive hint enumeration. The strongest cheap competitor for the offline recurring-template regime is to execute every one of Bao's coarse hint sets on each template's bindings and keep the best plan that passes the same judge. It uses no learning and no LLM. Given hours per template, it is very hard to beat inside the hint space. No reported result found on Lacuna for exhaustive offline hint enumeration. We will run it ourselves under the same execution budget and timeouts.

Learned optimizers. - Bao, as reported, reduces cost and latency by up to 50% on PostgreSQL. - Balsa reports a 2.1× speedup over PostgreSQL on the Join Order Benchmark (JOB). - FOSS reports a 6.25× total-latency speedup on JOB (measured during training) and up to 8.33× on unseen queries.

FOSS is the strongest published number on JOB, so beating it there means exceeding its speedup on held-out JOB templates when rerun on our hardware with its released training budget.

LLM rewriters. - QUITE reports a 31.9% to 81.7% reduction in execution time across benchmarks, 96.8% semantic equivalence on DSB, and a 37.5× latency reduction on specific complex DSB queries. - R-Bot reports a 1.68× latency reduction on DSB at scale 50. - LLM-R2 reports reducing execution time to 52.5% of the original across TPC-H, IMDB, and DSB.

QUITE is the strongest LLM competitor. All LLM systems will use the same model, the same token budget, and the same cap on executed candidates per template.

Ablations. The ablations isolate the key ingredient. We run our exact loop with four memory configurations:

  • no retrieval at all;
  • QUITE-style static curated knowledge only;
  • the self-written memory, retrieved by syntax tree plus text as in R-Bot;
  • the same self-written memory, retrieved by symptom signature.

The third and fourth configurations hold memory contents fixed and change only the key. Beating the structure-keyed variant is the result that validates the proposal. Concretely, we require a lower geometric-mean workload latency on held-out templates at equal executed-candidate budget, and fewer candidates to come within 5% of the best plan found.

Why not just…?

Why not just paste EXPLAIN ANALYZE into a single LLM and iterate? This is the real threat. Frontier models may already read row-estimate errors well enough that retrieval adds nothing. The no-retrieval ablation is exactly this system, run with the same judge. If it matches the symptom-keyed variant on held-out templates, the memory contributes nothing and we will say so. Our expectation of a gap rests on transfer. A single loop rediscovers fixes from scratch for every template and spends executions doing so. Memory should reduce that cost, and the executed-candidate curve will show whether it does.

Why not just enumerate Bao's hint sets offline? For many JOB queries this may be as good as anything. We will break down every accepted improvement by action type: pure hint, SQL rewrite, or combined. If nearly all gains fall inside the hint space, the proposal reduces to offline Bao and the LLM is unnecessary. The contrary evidence we expect comes from DSB and TPC-DS. QUITE's decorrelation wins there lie outside any hint set, but whether they dominate is an empirical question we will settle.

Why not just use QUITE with its curated knowledge base and append telemetry to the prompt? That configuration is one of the ablations. Curated units encode general wisdom, not the outcome of trying fix X under symptom Y on this engine. The test is whether self-written, outcome-labeled records outperform the 241 curated units at equal token budget. The comparison is sharpest on Ext-JOB-style unseen templates and on cross-schema transfer.

Why not just add an LLM critic agent instead of a deterministic judge? Sycophancy results suggest a critic will approve regressive but plausible rewrites. We will run a variant with an LLM critic ahead of the judge and count how often it vetoes candidates the judge would have accepted, and how often it approves candidates that later fail. If it catches nothing the judge misses, it is only cost.

Proposed Experiments

Benchmarks and splits. We use JOB with its Ext-JOB held-out templates, DSB with its skewed parameterized templates, TPC-DS, and the Stack workload, all on PostgreSQL. Within each benchmark, memory is built on 60% of templates and evaluated on the rest. We sample 10 parameter bindings per template. Half the bindings are used for acceptance and the other half are reserved for final scoring, so the regression rule is tested on bindings it never saw.

Cross-schema transfer. Memory built only on JOB is evaluated on Stack. This is the direct test of whether name-free signatures transfer.

Metrics. We report:

  • geometric-mean and total workload latency versus PostgreSQL;
  • the number of held-out bindings regressing beyond 1.1×;
  • the worst-binding ratio;
  • executed candidates and LLM tokens to reach within 5% of the final best plan;
  • the equivalence-failure rate.

Decisive checks. Three results decide the outcome:

  1. Symptom-keyed versus structure-keyed retrieval over identical memory. This is the go/no-go.
  2. Gains beyond exhaustive hint enumeration, concentrated in rewrite actions.
  3. Zero-shot transfer from JOB memory to Stack beating no-retrieval at equal budget.

If only the first holds, the contribution is narrower: faster convergence for offline repair. If none holds, the telemetry signal is best consumed directly in the prompt, and indexing past repairs by execution symptom adds nothing.