How good are query optimizers, really?

Leis et al. asked this exact question in 2015. Then, they asked it again 10 years later.

Despite an enormous body of research spanning a decade since their original exploration, they found that query optimizers continue to leave much to be desired.

I was surprised when I first learned about this. A Postgres database should know everything about the stuff that lives in its tables, no? How hard can it be?

As it turns out: enormously hard. In fact, one particular task a query optimizer needs to do, join ordering, is known to be NP-hard.

So query optimizers are hard. What’s not as hard is verifying whether a query plan an optimizer picks is good or not. Put simply, a good query optimizer produces plans that run fast, and a bad one produces slow plans. Language models are particularly good at learning how to do tasks with easily verifiable outputs. Because there’s a single axis to optimize for—execution time of a query—the problem beautifully reduces to reinforcing the behaviors that guide a model to produce faster query plans.

What follows is a breakdown of an experiment I ran to explore the question: can a small, open-weights model be post-trained via supervised fine-tuning (SFT) and agentic reinforcement learning (RL) to produce Postgres query plans that beat Postgres’s default plans?

The answer to our question is a resounding yes. Highlights include:

• Attaining a 44.7% latency reduction across 113 join-heavy queries from a 4B model initially unable to produce a query plan for 99 of them
• Constructing a Postgres measurement rig that minimizes Linux page cache contention noise across concurrent containers
• Designing a custom GRPO variant for scoring RL rollouts in an inherently noisy environment
• Splitting RL across two machines: vLLM and the trainer on a rented 2x H100 node and four Postgres containers running on my desk
• Running off-policy distillation across half a thousand GPT-6 Astra agent trajectories

Let’s start from the beginning.

Inside a query optimizer

Consider the following slice of the IMDb dataset:

-- An IMDb title (movie, series, episode, etc.) [~1M rows]
title (
  id              integer PRIMARY KEY,
  title           text,
  production_year integer,
  kind_id         integer -- FK -> kind_type
)

-- Movie <> company junction table [~2M rows]
movie_companies (
  id              integer PRIMARY KEY,
  movie_id        integer, -- FK -> title.id
  company_id      integer, -- FK -> company_name.id
  company_type_id integer, -- FK -> company_type.id
  note            text
)

-- A company's name, origin, etc. [~100k rows]
company_name (
  id           integer PRIMARY KEY,
  name         text,
  country_code text     -- '[us]', '[jp]', ...
)

-- Lookup table of company roles for a title [4 rows]
company_type (
  id   integer PRIMARY KEY,
  kind text -- 'production companies', 'distributors', ...
)

-- Lookup table for what a title _is_ [7 rows]
kind_type (
  id   integer PRIMARY KEY,
  kind text -- 'movie', 'tv series', 'episode', ...
)

Let’s say I’m trying to answer the question: “Which Japanese companies put out the most titles in the 2000s?” We might write the following query:

SELECT cn.name,
       COUNT(*) AS titles
FROM   title AS t,
       movie_companies AS mc,
       company_name AS cn
WHERE  t.id = mc.movie_id
  AND  mc.company_id = cn.id
  AND  cn.country_code = '[jp]'
  AND  t.production_year BETWEEN 2000 AND 2009
GROUP  BY cn.name
ORDER  BY titles DESC
LIMIT  10;

Running this query outputs 10 Japanese companies with the number of titles they were associated with between 2000 and 2009, sorted from highest to lowest.

But how did Postgres get these results?

The path Postgres took to get this data for us is not a foregone conclusion, and it has everything to do with what we call selective predicates (i.e. the filtering conditions in a WHERE clause).

To illustrate this, let’s imagine our same query without the Japanese company filter or the date range filter:

SELECT cn.name,
       COUNT(*) AS titles
FROM   title AS t,
       movie_companies AS mc,
       company_name AS cn
WHERE  t.id = mc.movie_id
  AND  mc.company_id = cn.id
GROUP  BY cn.name
ORDER  BY titles DESC
LIMIT  10;

mc can only join with cn via mc.company_id = cn.id, and t can only join with mc via t.id = mc.movie_id.

These constraints produce two There are technically eight join trees if we take commutativity into account. In this case, we don’t because it doesn’t affect the size of the relations resulting from the joins. valid join trees:

Factoring commutativity back in now While commutativity doesn’t change the number of rows produced, it must be considered now because it does affect performance regarding the join algorithm used. , there are 4 different outer/inner join orientations, resulting in 8 possible combinations:

There are 4,608 different ways to run this query This is actually an undercount. Plans can run in parallel, aggregates can be hashed or sorted, etc.

It’s also worth noting that Postgres doesn’t evaluate all of these plans. It uses dynamic programming (and a genetic algorithm for queries involving 12+ joins) to prune the search space. !

To make matters worse, every join combinatorially explodes the search space:

SELECT cn.name,
       COUNT(*) AS titles
FROM   movie_companies AS mc,
       company_name AS cn
WHERE  mc.company_id = cn.id
  AND  cn.country_code = '[jp]'
GROUP  BY cn.name
ORDER  BY titles DESC
LIMIT  10;

SELECT cn.name,
       COUNT(*) AS titles
FROM   title AS t,
       movie_companies AS mc,
       company_name AS cn
WHERE  t.id = mc.movie_id
  AND  mc.company_id = cn.id
  AND  cn.country_code = '[jp]'
  AND  t.production_year BETWEEN 2000 AND 2009
GROUP  BY cn.name
ORDER  BY titles DESC
LIMIT  10;

SELECT MIN(t.title) AS movie_title
FROM keyword AS k,
     movie_info AS mi,
     movie_keyword AS mk,
     title AS t
WHERE k.keyword LIKE '%sequel%'
  AND mi.info IN ('Bulgaria')
  AND t.production_year > 2010
  AND t.id = mi.movie_id
  AND t.id = mk.movie_id
  AND mk.movie_id = mi.movie_id
  AND k.id = mk.keyword_id;

SELECT MIN(t.title) AS movie_title
FROM company_name AS cn,
     keyword AS k,
     movie_companies AS mc,
     movie_keyword AS mk,
     title AS t
WHERE cn.country_code ='[de]'
  AND k.keyword ='character-name-in-title'
  AND cn.id = mc.company_id
  AND mc.movie_id = t.id
  AND t.id = mk.movie_id
  AND mk.keyword_id = k.id
  AND mc.movie_id = mk.movie_id;

SELECT MIN(lt.link) AS link_type,
       MIN(t1.title) AS first_movie,
       MIN(t2.title) AS second_movie
FROM keyword AS k,
     link_type AS lt,
     movie_keyword AS mk,
     movie_link AS ml,
     title AS t1,
     title AS t2
WHERE k.keyword ='10,000-mile-club'
  AND mk.keyword_id = k.id
  AND t1.id = mk.movie_id
  AND ml.movie_id = t1.id
  AND ml.linked_movie_id = t2.id
  AND lt.id = ml.link_type_id
  AND mk.movie_id = t1.id;

SELECT MIN(a1.name) AS writer_pseudo_name,
       MIN(t.title) AS movie_title
FROM aka_name AS a1,
     cast_info AS ci,
     company_name AS cn,
     movie_companies AS mc,
     name AS n1,
     role_type AS rt,
     title AS t
WHERE cn.country_code ='[us]'
  AND rt.role ='writer'
  AND a1.person_id = n1.id
  AND n1.id = ci.person_id
  AND ci.movie_id = t.id
  AND t.id = mc.movie_id
  AND mc.company_id = cn.id
  AND ci.role_id = rt.id
  AND a1.person_id = ci.person_id
  AND ci.movie_id = mc.movie_id;

SELECT MIN(an.name) AS cool_actor_pseudonym,
       MIN(t.title) AS series_named_after_char
FROM aka_name AS an,
     cast_info AS ci,
     company_name AS cn,
     keyword AS k,
     movie_companies AS mc,
     movie_keyword AS mk,
     name AS n,
     title AS t
WHERE cn.country_code ='[us]'
  AND k.keyword ='character-name-in-title'
  AND an.person_id = n.id
  AND n.id = ci.person_id
  AND ci.movie_id = t.id
  AND t.id = mk.movie_id
  AND mk.keyword_id = k.id
  AND t.id = mc.movie_id
  AND mc.company_id = cn.id
  AND an.person_id = ci.person_id
  AND ci.movie_id = mc.movie_id
  AND ci.movie_id = mk.movie_id
  AND mc.movie_id = mk.movie_id;

SELECT MIN(cn.name) AS producing_company,
       MIN(miidx.info) AS rating,
       MIN(t.title) AS movie
FROM company_name AS cn,
     company_type AS ct,
     info_type AS it,
     info_type AS it2,
     kind_type AS kt,
     movie_companies AS mc,
     movie_info AS mi,
     movie_info_idx AS miidx,
     title AS t
WHERE cn.country_code ='[us]'
  AND ct.kind ='production companies'
  AND it.info ='rating'
  AND it2.info ='release dates'
  AND kt.kind ='movie'
  AND mi.movie_id = t.id
  AND it2.id = mi.info_type_id
  AND kt.id = t.kind_id
  AND mc.movie_id = t.id
  AND cn.id = mc.company_id
  AND ct.id = mc.company_type_id
  AND miidx.movie_id = t.id
  AND it.id = miidx.info_type_id
  AND mi.movie_id = miidx.movie_id
  AND mi.movie_id = mc.movie_id
  AND miidx.movie_id = mc.movie_id;

SELECT MIN(n.name) AS voicing_actress,
       MIN(t.title) AS jap_engl_voiced_movie
FROM aka_name AS an,
     char_name AS chn,
     cast_info AS ci,
     company_name AS cn,
     info_type AS it,
     movie_companies AS mc,
     movie_info AS mi,
     name AS n,
     role_type AS rt,
     title AS t
WHERE ci.note IN ('(voice)',
                  '(voice: Japanese version)',
                  '(voice) (uncredited)',
                  '(voice: English version)')
  AND cn.country_code ='[us]'
  AND it.info = 'release dates'
  AND n.gender ='f'
  AND rt.role ='actress'
  AND t.production_year > 2000
  AND t.id = mi.movie_id
  AND t.id = mc.movie_id
  AND t.id = ci.movie_id
  AND mc.movie_id = ci.movie_id
  AND mc.movie_id = mi.movie_id
  AND mi.movie_id = ci.movie_id
  AND cn.id = mc.company_id
  AND it.id = mi.info_type_id
  AND n.id = ci.person_id
  AND rt.id = ci.role_id
  AND n.id = an.person_id
  AND ci.person_id = an.person_id
  AND chn.id = ci.person_role_id;

SELECT MIN(kt.kind) AS movie_kind,
       MIN(t.title) AS complete_us_internet_movie
FROM complete_cast AS cc,
     comp_cast_type AS cct1,
     company_name AS cn,
     company_type AS ct,
     info_type AS it1,
     keyword AS k,
     kind_type AS kt,
     movie_companies AS mc,
     movie_info AS mi,
     movie_keyword AS mk,
     title AS t
WHERE cct1.kind = 'complete+verified'
  AND cn.country_code = '[us]'
  AND it1.info = 'release dates'
  AND kt.kind IN ('movie')
  AND mi.note LIKE '%internet%'
  AND mi.info IS NOT NULL
  AND (mi.info LIKE 'USA:% 199%'
       OR mi.info LIKE 'USA:% 200%')
  AND t.production_year > 2000
  AND kt.id = t.kind_id
  AND t.id = mi.movie_id
  AND t.id = mk.movie_id
  AND t.id = mc.movie_id
  AND t.id = cc.movie_id
  AND mk.movie_id = mi.movie_id
  AND mk.movie_id = mc.movie_id
  AND mk.movie_id = cc.movie_id
  AND mi.movie_id = mc.movie_id
  AND mi.movie_id = cc.movie_id
  AND mc.movie_id = cc.movie_id
  AND k.id = mk.keyword_id
  AND it1.id = mi.info_type_id
  AND cn.id = mc.company_id
  AND ct.id = mc.company_type_id
  AND cct1.id = cc.status_id;

SELECT MIN(chn.name) AS character_name,
       MIN(mi_idx.info) AS rating,
       MIN(t.title) AS complete_hero_movie
FROM complete_cast AS cc,
     comp_cast_type AS cct1,
     comp_cast_type AS cct2,
     char_name AS chn,
     cast_info AS ci,
     info_type AS it2,
     keyword AS k,
     kind_type AS kt,
     movie_info_idx AS mi_idx,
     movie_keyword AS mk,
     name AS n,
     title AS t
WHERE cct1.kind = 'cast'
  AND cct2.kind LIKE '%complete%'
  AND chn.name IS NOT NULL
  AND (chn.name LIKE '%man%'
       OR chn.name LIKE '%Man%')
  AND it2.info = 'rating'
  AND k.keyword IN ('superhero',
                    'marvel-comics',
                    'based-on-comic',
                    'fight')
  AND kt.kind = 'movie'
  AND mi_idx.info > '8.0'
  AND t.production_year > 2005
  AND kt.id = t.kind_id
  AND t.id = mk.movie_id
  AND t.id = ci.movie_id
  AND t.id = cc.movie_id
  AND t.id = mi_idx.movie_id
  AND mk.movie_id = ci.movie_id
  AND mk.movie_id = cc.movie_id
  AND mk.movie_id = mi_idx.movie_id
  AND ci.movie_id = cc.movie_id
  AND ci.movie_id = mi_idx.movie_id
  AND cc.movie_id = mi_idx.movie_id
  AND chn.id = ci.person_role_id
  AND n.id = ci.person_id
  AND k.id = mk.keyword_id
  AND cct1.id = cc.subject_id
  AND cct2.id = cc.status_id
  AND it2.id = mi_idx.info_type_id;

Estimating, not counting

Postgres is in a tough spot here. It would be reasonable to think it could simply count cardinalities and pick the plan that minimizes the number of rows passed through to successive joins.

But this would imply Postgres can count cardinalities during query planning. It can’t. In order to know this, it would need to actually run each join and count the resulting rows. This defeats the whole point of a fast query optimizer. A query optimizer does not aim to be exact in its cost minimization… it aims to be good enough across many types of queries.

Instead, Postgres uses statistics to estimate cardinalities. The planner queries the pg_statistic table, getting back common values for each column and their frequencies, and a histogram for the rest. Things get a bit more complicated when you tack on joins. Postgres doesn’t know how the rows in one table are distributed over the other. To get around this, it assumes that the frequency of a given value in the first table can simply be applied over the second table. This is the uniform distribution assumption I mentioned earlier.

Assuming a uniform distribution is fine as a heuristic, but when it fails, it fails hard. Looking back at an earlier join ordering $(cn' \bowtie mc) \approx 100\text{k}, \text{ then } \bowtie\ t' \approx 20\text{k}$

One bad estimate in an early join can cascade through the rest of the join tree, corrupting all other estimates.

How to steer an elephant

Postgres always picks the plan with the lowest cost, and we can’t change its cost model without modifying its source code, so how can we actually steer it to pick different plans that have higher costs?

Enter pg_hint_plan.

pg_hint_plan is a beautifully simple third-party extension: just by adding structured “hints” as comments above SQL statements, you can nudge Postgres towards plans that use the instructions provided in the hint. For example:

/*+  HashJoin(a b)  SeqScan(a)*/EXPLAIN SELECT *  FROM pgbench_branches b  JOIN pgbench_accounts a ON b.bid = a.bid  ORDER BY a.aid;

                                   QUERY PLAN--------------------------------------------------------------------------------- Sort  (cost=31465.84..31715.84 rows=100000 width=197)   Sort Key: a.aid   ->  Hash Join  (cost=1.02..4016.02 rows=100000 width=197)         Hash Cond: (a.bid = b.bid)         ->  Seq Scan on pgbench_accounts a  (cost=0.00..2640.00 rows=100000 width=97)         ->  Hash  (cost=1.01..1.01 rows=1 width=100)               ->  Seq Scan on pgbench_branches b  (cost=0.00..1.01 rows=1 width=100)(7 rows)

The hint mandates usage of a HashJoin for joining pgbench_accounts and pgbench_branches, and doing a sequential scan of the pgbench_accounts table; the actual query plan follows suit nicely.

Formulating our problem

Given that we can influence Postgres to pick different—and potentially better—query plans using pg_hint_plan hints, the question we’re starting with is:

Can a language model learn to produce hints that result in better query plans?

Useful research

What might make this a worthwhile problem to solve?

My first idea was to give the model the query and the exact same set of information Postgres’s planner has. This amounts to seeing if we could build a better cardinality estimator. I came to the conclusion this is not a worthwhile avenue to explore; we would be fighting decades of cardinality estimation research. Furthermore, the inference latency alone would far outweigh any learned usefulness compared to Postgres’s ultra-fast query optimizer.

The second idea—and what I believe is the correct formulation—lies in a specific database usage pattern: heavy analytic workloads. If queries are getting run thousands of times using sub-optimal default Postgres plans, efficiency gains are being left on the table. Instead, a model could be trained to find a better way to run a specific query. The training process might require execution of that query tens to hundreds of times upfront, but the amortized cost across all runs of the query would be drastically lower.

The goal isn’t to try and beat Postgres on the time/efficiency Pareto frontier for one-off queries, but we may be able to beat it on queries that run over and over again.

A model and its harness

I decided to start with a small 4B model because it would be easiest to train/inference myself on the 2x RTX 3090 rig (affectionately named FLOPper) I have at home.

Around the time I started this project, the Qwen 3.8 family of models was released, unfortunately without a 4B variant. However, I came across a Qwen 3.8 4B distillation from a small lab in Germany called Empero and was intrigued. They used Qwen 3.8’s 2.4T model as a teacher model to distill learnings into Qwen 3.5 4B, producing empero-ai/Qwen3.8-4B-Distill. This distilled model is not outright better than its base 3.5 model; it performs better on MMLU tasks and slightly worse on GSM8K tasks. In other words, this distillation performs better when evaluated on breadth of general knowledge, and slightly worse on multi-step mathematical reasoning. As to which is better for our task, I do not know; I decided to stick with the distilled model either way.

With the model locked in, I built a lightweight agent harness, qo-agent, that would orchestrate hint production. It was given the following six tools:

1. inspect_relation — Lists a table’s columns with types and nullability, index definitions and estimated rows and bytes
2. get_column_stats — Gets Postgres planner statistics for 1-8 columns of a relation
3. get_plan — Gets the default plan’s estimates or a submitted candidate’s stored plan
4. evaluate_candidate — Validates a proposed plan action and then executes it for timing/plan diagnostics
5. keep_default — Returns Postgres’s default plan itself as the candidate and ends the search
6. finish — Takes as input a submitted candidate ID or the default plan and ends the search

To take advantage of structured outputs, the agent was instructed to produce PlanAction JSON objects. Calls to evaluate_candidate then compiled PlanAction objects into hints and prepended them to the original query.

A sample agent trajectory:

Agent → get_plan("default")Tool  ← Default plan: (t ⋈ mc) ⋈ cn, hash joins, estimated rows per node Agent → evaluate_candidate({          "leading": { "left": { "left": "cn", "right": "mc" }, "right": "t" },          "joins": [{ "relations": ["cn", "mc"], "force": "hash" }]        })Tool  ← c1 · valid · novel plan · 118 ms · 0.91× default · 2 attempts left Agent → evaluate_candidate({          "leading": { "left": { "left": "t", "right": "mc" }, "right": "cn" },          "joins": [{ "relations": ["t", "mc"], "force": "nestloop" }],          "scans": [{ "relation": "mc", "force": "index" }]        })Tool  ← c2 · valid · novel plan · 87 ms · 1.24× default · 1 attempt left Agent → evaluate_candidate({          "leading": { "left": { "left": "t", "right": "mc" }, "right": "cn" },          "joins": [{ "relations": ["t", "mc"], "force": "hash" }]        })Tool  ← c3 · valid · novel plan · 100 ms · 1.08× default · 0 attempts left Agent → finish({ "selected_candidate_id": "c2" })Tool  ← Finished · selected c2

Benchmarks

An agent is useless without something to benchmark its performance against. Fortunately for us, the hard work of creating these benchmarks was already done.

The Join Order Benchmark

Leis et al. introduced the Join Order Benchmark (JOB) in How Good Are Query Optimizers, Really?. They used it to evaluate cardinality estimation and join-order optimization using our familiar IMDb dataset.

It consists of 113 queries spread across 33 query templates. Query templates differ via their relational skeleton. They reference different tables and connect them with different join predicates. You can think about them as a structural family of questions that can be answered. Queries derived from templates preserve the tables used and the join graph topology but change selection predicates.

Looking at an example:

SELECT MIN(t.title) AS movie_title
FROM   company_name AS cn
JOIN   movie_companies AS mc ON mc.company_id = cn.id
JOIN   title AS t ON t.id = mc.movie_id
JOIN   movie_keyword AS mk ON mk.movie_id = t.id
JOIN   keyword AS k ON k.id = mk.keyword_id
WHERE  cn.country_code = :country_code
  AND  k.keyword = 'character-name-in-title';

…and here are two real queries from JOB derived from this template:

SELECT MIN(t.title) AS movie_title
FROM   company_name AS cn,
       keyword AS k,
       movie_companies AS mc,
       movie_keyword AS mk,
       title AS t
WHERE  cn.country_code = '[de]'
  AND  k.keyword = 'character-name-in-title'
  AND  cn.id = mc.company_id
  AND  mc.movie_id = t.id
  AND  t.id = mk.movie_id
  AND  mk.keyword_id = k.id
  AND  mc.movie_id = mk.movie_id;

SELECT MIN(t.title) AS movie_title
FROM   company_name AS cn,
       keyword AS k,
       movie_companies AS mc,
       movie_keyword AS mk,
       title AS t
WHERE  cn.country_code = '[us]'
  AND  k.keyword = 'character-name-in-title'
  AND  cn.id = mc.company_id
  AND  mc.movie_id = t.id
  AND  t.id = mk.movie_id
  AND  mk.keyword_id = k.id
  AND  mc.movie_id = mk.movie_id;

The Cardinality Estimation Benchmark

Another relevant benchmark is the Cardinality Estimation Benchmark (CEB), introduced in Flow-loss: Learning Cardinality Estimates That Matter. It uses the same IMDb database and is a much larger benchmark consisting of ~13.6k synthetically generated queries organized across 16 query templates CEB’s definition of a template is looser than JOB's. Two CEB templates can share the same join graph, differing only in their selectivity predicates. In JOB, every template's join graph is unique. .

How to muffle an elephant

Before getting into benchmarking the agent and doing training runs, we have to talk about how Postgres was actually run, because it directly impacts the training process.

First, some facts:

• FLOPper has a CPU with 16 physical cores, 64 GB of RAM and a 2 TB NVMe SSD
• The slice of IMDb we’re using is 8.5 GB on disk
• Postgres caches pages of data retrieved during query execution into a buffer
• The operating system has its own filesystem cache doing the same thing one level down

If we run the exact same query on Postgres 20 times in a row, it won’t take the same amount of time each run. In day-to-day work, this isn’t a big deal. But the whole thesis, and the training process itself, relies on measuring whether one way of running a query is faster than the Postgres default. This means we need to do everything in our power to de-noise Postgres.

First, I needed to understand just how noisy Postgres query executions are.

I started by building a “calibration” capability into my experimentation workflow. The calibration process was simple: run $N$ Docker containers built from a Postgres image, each given a fixed slice of CPU cores and RAM to use. I set $N = 4$

On startup, each container initialized Postgres with identical settings and loaded the IMDb data. Calibration then opened a thread pool of size four and pushed all 113 queries onto a shared queue. Whenever a container finished measuring a query, it pulled the next one off the queue.

The actual measurement process had two phases:

1. Run the query a few times to “warm it up”
2. Then run the query 20 more times and record each execution time

So what does it mean to warm a query up? We need to bust out some OS fundamentals to understand.

Whenever Postgres executes a query, it asks the operating system (in our case, Linux) for pages of data. Linux first checks its own filesystem cache, the page cache. If the pages are present, Linux sends them over; else it reads them from disk, stores them in its cache and then sends them over. Postgres, in turn, keeps received pages in its own shared_buffers cache for easy reuse. When shared_buffers begins to overflow, Postgres evicts pages. If it needs those pages again, it must ask Linux once more.

Every time there’s a cache hit in shared_buffers for a page, Postgres increments a counter called “shared hit blocks” (SHBs). If it has to ask Linux, it increments “shared read blocks” (SRBs).

Postgres conveniently reports both counters if we run EXPLAIN with the BUFFERS option. For example, running EXPLAIN (ANALYZE, TIMING OFF, BUFFERS, FORMAT JSON) outputs something like:

{
  "Plan": {
    "Node Type": "Aggregate",
    "Shared Hit Blocks": 1800786,
    "Shared Read Blocks": 52990,
    ...
  },
  "Execution Time": 189.2,
  ...,
}

These counters give us some notion of the “warmness” of a query. After each warmup run, we compared its hit and read counts to the previous run’s. If both were within 2% of each other (and the plan hadn’t changed), we called the query warm and started measuring. A query needed at least two warmups to have something to compare, and was cut off at five regardless. The idea was that if the counters stopped moving, the data could be considered settled and cache churn would be minimized during the 20 measurements.

I set shared_buffers to a conservative 128 MB and ran the first calibration:

Half the queries were declared warm after only two runs. Not bad… at least until I dug deeper. The SRB counts weren’t dropping to zero; rather, they were hovering steady at some large number. With only 128 MB of shared_buffers against an 8.5 GB database, Postgres was consistently missing its own cache on every execution and asking Linux for more pages. “Stable” did not mean “resident.”

Linux’s page cache is fast, so this isn’t the end of the world. Unfortunately, a new problem emerged when I actually looked at the 20 measurements taken for various queries. Let’s look at one query in particular, job-13b:

14 of the 20 landed between 186 and 204 ms. The other 6 landed between 227 and 253 ms, somewhere between 14% and 26% slower. The query wasn’t even uniformly noisy, it just had two different speeds at different times, and a third of the time it ran at the slower speed.

I initially wanted to quantify noise using the coefficient of variation:

The CV tells us the “wobble” of a measurement. If a query takes 100 ms and has a CV of 5%, we could say it wobbles by about 5 ms. For job-13b, the CV was 10.3%. It wasn’t great. CV is also not a great measurement to use here. Because it’s built on the mean, it’s easily influenced by a few outlier runs.

We don’t actually care as much about how spread out the 20 runs are. We do care about how often this causes our measurement criteria during training runs to get fooled.

To fool an agent

Bear with me here as I skip ahead a little bit in order to provide more color on what exactly we needed to measure.

To de-noise during actual agent runs, I couldn’t just run the agent’s proposed plan a single time. Instead, I ran three interleaved (candidate, default) pairs sequentially. Three was picked somewhat arbitrarily to provide some measure of variability while being small enough to prevent agent evaluation runs from spending most of their time in Postgres. Once the three candidate/default execution time tuples were obtained, the medians of both the three candidates and the three defaults were taken and expressed as a ratio of each other to determine the final speedup or slowdown. If the two medians differed by less than an arbitrarily declared 5%, it was a tie. Outside of that tie zone, a candidate could be declared as a speedup or a slowdown.

Now let’s go back to our earlier job-13b example. We had 14 executions in one clump, and 6 in another slower clump. The median of three strategy sounds good until you realize that if, in theory, at least two of the three measurements landed in that “slower” clump, the median would bias towards the less frequent slower clump.

Imagine a candidate plan that executes identically to the default. No real difference exists, so the correct reward is zero. Draw three timings for the “candidate” and three for the “default” out of the 20 we observed. There are $\binom{20}{3} = 1{,}140$

That’s a totally phantom 14-26% speedup or slowdown that we would show to our model as signal ~20% of the time. Dangerous!

So we can’t just rely on CV as the golden number to minimize, as two queries with the exact same CV can fool the measurement reward at different rates depending on whether the spreads are a uniform blur or two clumps sitting more than 5% apart. The actual number to minimize is this fooling rate itself.

I wrote a small script to compute the fooling rate directly from raw calibration data. It worked by sliding a window of six sequential runs across the 20. For each window, we took interleaved pairs of size two to represent an interleaved (candidate, default) pair. A window of size six gives us pairings like: (t1, t2), (t3, t4), (t5, t6). In any given pair, $t_n$

At 128 MB for shared_buffers and four concurrent containers, the “fool rate” script produced the following mean no-op error rates and p90 query numbers I ran the calibration twice per config to provide a sense of how much two runs may disagree with each other. :

Before running the untrained 4B model through the qo-agent harness, I wanted to validate this problem was actually solveable by today’s frontier models. If a model like GPT-6 Astra or Qwen 3.8 2.4T couldn’t improve upon the default Postgres query plan, I couldn’t really expect the 4B model to either.

I took a small sample of 10 JOB queries and benchmarked them on both Astra and Qwen 3.8 2.4T running through the qo-agent harness:

Given the difference between the single-candidate scores and the 5-candidate scores, the agent was clearly capable of doing in-context learning across sequential executions of its candidates. This gave me the confidence to stick with an agentic multi-turn approach rather than try and train the 4B model to get really good at one-shotting a plan.

During a run of the agent, each candidate was warmed once and then measured once. After exhausting the candidate attempts budget, the model was only presented with a single tool to call, finish, and the model was told to select the best scoring candidate (or keep the default plan). After the candidate was selected, three interleaved (candidate, default) pairs were run and passed through a clipper: