A reinforcement-learning policy update
Four RL rollouts commence for a single query. Qwen produces a candidate strategy per rollout and sends it off to Postgres for measurement against its own default plan. Scalar rewards are assigned to each rollout, which flow backwards to update Qwen's weights.
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
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.
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:
The cardinality of a table or query result is the number of rows it contains. Assume the relevant tables have the following cardinalities:
c n = 100 k cn = 100\text{k} c n = 100 k
m c = 2 m mc = 2\text{m} m c = 2 m
Taking into account our joins, we get the following cardinalities:
Regardless of the order in which these three tables are joined, the same 2m rows are always passed into the second join.
Now let’s add back our selective predicates:
c n ′ = 5 k cn' = 5\text{k} c n ′ = 5 k (assuming 5% of our 100k companies are Japanese)
m c = 2 m mc = 2\text{m} m c = 2 m (does not change)
t ′ = 200 k t' = 200\text{k} t ′ = 200 k (assuming 20% of our 1m titles were made in the 2000s)
The first join ordering filters the 2m movie_companies entries down to the 5% slice of companies that are Japanese. Assuming uniform distribution (we’ll discuss later why we assume this), this join results in approximately 100k rows. Joining the result with the filtered title table keeps only the 20% of those rows from the 2000s.
The second join ordering filters the 2m movie_companies entries down to the 20% slice of titles that were made in the 2000s. The same uniformity assumption holds, so the first join results in 400k rows, meaning we’re passing 400k rows into the second join.
We do 4x the work if we picked the second join ordering.
A combinatorial explosion
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:
( c n ⋈ m c ) ⋈ t (cn \bowtie mc) \bowtie t ( c n ⋈ m c ) ⋈ t t ⋈ ( c n ⋈ m c ) t \bowtie (cn \bowtie mc) t ⋈ ( c n ⋈ m c )
( m c ⋈ c n ) ⋈ t (mc \bowtie cn) \bowtie t ( m c ⋈ c n ) ⋈ t t ⋈ ( m c ⋈ c n ) t \bowtie (mc \bowtie cn) t ⋈ ( m c ⋈ c n )
( t ⋈ m c ) ⋈ c n (t \bowtie mc) \bowtie cn ( t ⋈ m c ) ⋈ c n c n ⋈ ( t ⋈ m c ) cn \bowtie (t \bowtie mc) c n ⋈ ( t ⋈ m c )
( m c ⋈ t ) ⋈ c n (mc \bowtie t) \bowtie cn ( m c ⋈ t ) ⋈ c n c n ⋈ ( m c ⋈ t ) cn \bowtie (mc \bowtie t) c n ⋈ ( m c ⋈ t )
Lastly, each table can be scanned in different ways. Considering just four types of scans:
2 Join trees: which pair of tables joins first. × 2 2 Orientations: each of the 2 joins can swap which input is outer and which is inner. × 3 2 Algorithms: each of the 2 joins picks hash, merge, or nested loop. × 4 3 Scans: each of the 3 tables is either read sequentially or via index, index-only or bitmap scans. = 4 , 608
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 ;
1 Join trees: with two tables there is only one way to join them. × 2 1 Orientation: 1 join means there are only 2 orientations. × 3 1 Algorithm: the join algorithm can be a hash join, merge join or nested loop. × 4 2 Scans: each of the 2 tables is either read sequentially or via index, index-only or bitmap scans. = 96
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 ;
2 Join trees: the ways 3 tables can be joined up, before any swapping of inputs. × 2 2 Orientations: each of the 2 joins can swap which input is outer and which is inner. × 3 2 Algorithms: each of the 2 joins picks hash, merge, or nested loop. × 4 3 Scans: each of the 3 tables is either read sequentially or via index, index-only or bitmap scans. = 4 , 608
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 ;
8 Join trees: the ways 4 tables can be joined up, before any swapping of inputs. × 2 3 Orientations: each of the 3 joins can swap which input is outer and which is inner. × 3 3 Algorithms: each of the 3 joins picks hash, merge, or nested loop. × 4 4 Scans: each of the 4 tables is either read sequentially or via index, index-only or bitmap scans. = 442 , 368
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 ;
25 Join trees: the ways 5 tables can be joined up, before any swapping of inputs. × 2 4 Orientations: each of the 4 joins can swap which input is outer and which is inner. × 3 4 Algorithms: each of the 4 joins picks hash, merge, or nested loop. × 4 5 Scans: each of the 5 tables is either read sequentially or via index, index-only or bitmap scans. = 33 , 177 , 600
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 ;
56 Join trees: the ways 6 tables can be joined up, before any swapping of inputs. × 2 5 Orientations: each of the 5 joins can swap which input is outer and which is inner. × 3 5 Algorithms: each of the 5 joins picks hash, merge, or nested loop. × 4 6 Scans: each of the 6 tables is either read sequentially or via index, index-only or bitmap scans. = 1 , 783 , 627 , 776
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 ;
696 Join trees: the ways 7 tables can be joined up, before any swapping of inputs. × 2 6 Orientations: each of the 6 joins can swap which input is outer and which is inner. × 3 6 Algorithms: each of the 6 joins picks hash, merge, or nested loop. × 4 7 Scans: each of the 7 tables is either read sequentially or via index, index-only or bitmap scans. = 532 , 030 , 685 , 184
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 ;
4 , 698 Join trees: the ways 8 tables can be joined up, before any swapping of inputs. × 2 7 Orientations: each of the 7 joins can swap which input is outer and which is inner. × 3 7 Algorithms: each of the 7 joins picks hash, merge, or nested loop. × 4 8 Scans: each of the 8 tables is either read sequentially or via index, index-only or bitmap scans. = 86 , 188 , 970 , 999 , 808
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 ;
20 , 340 Join trees: the ways 9 tables can be joined up, before any swapping of inputs. × 2 8 Orientations: each of the 8 joins can swap which input is outer and which is inner. × 3 8 Algorithms: each of the 8 joins picks hash, merge, or nested loop. × 4 9 Scans: each of the 9 tables is either read sequentially or via index, index-only or bitmap scans. = 8 , 955 , 727 , 561 , 359 , 360
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 ;
242 , 160 Join trees: the ways 10 tables can be joined up, before any swapping of inputs. × 2 9 Orientations: each of the 9 joins can swap which input is outer and which is inner. × 3 9 Algorithms: each of the 9 joins picks hash, merge, or nested loop. × 4 10 Scans: each of the 10 tables is either read sequentially or via index, index-only or bitmap scans. = 2 , 558 , 960 , 455 , 762 , 575 , 360
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 ;
1 , 490 , 850 Join trees: the ways 11 tables can be joined up, before any swapping of inputs. × 2 10 Orientations: each of the 10 joins can swap which input is outer and which is inner. × 3 10 Algorithms: each of the 10 joins picks hash, merge, or nested loop. × 4 11 Scans: each of the 11 tables is either read sequentially or via index, index-only or bitmap scans. = 378 , 099 , 722 , 048 , 923 , 238 , 400
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 ;
11 , 932 , 560 Join trees: the ways 12 tables can be joined up, before any swapping of inputs. × 2 11 Orientations: each of the 11 joins can swap which input is outer and which is inner. × 3 11 Algorithms: each of the 11 joins picks hash, merge, or nested loop. × 4 12 Scans: each of the 12 tables is either read sequentially or via index, index-only or bitmap scans. = 72 , 630 , 206 , 166 , 931 , 876 , 085 , 760 lots!
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