A small 4-billion-parameter open-weights language model, fine-tuned via supervised learning and reinforcement learning techniques, achieved a 44.7% latency reduction across 113 join-heavy queries compared to Postgres’s default query planner, according to an experiment detailed by researcher Rohan Bansal.
The model was initially unable to produce valid query plans for 99 of the test queries but, through post-training with agentic reinforcement learning (RL), learned to generate faster execution plans. The experiment demonstrates that language models can be effectively trained to optimize tasks with easily measurable outcomes—in this case, query execution time.
Query optimization presents a fundamental computational challenge. The task of determining optimal join ordering—the sequence in which database tables are combined—is mathematically known to be NP-hard. Modern database systems like Postgres use dynamic programming and genetic algorithms to prune the exponentially large search space of possible plans. A single three-table join, for example, can theoretically be executed in 4,608 different ways when accounting for join algorithms (hash, merge, nested-loop), join orientation, and table scan methods (sequential, index, index-only, bitmap).
Postgres cannot count actual row cardinalities during query planning, as doing so would require executing each potential plan—defeating the purpose of fast optimization. Instead, it relies on statistics and heuristics, including the assumption that value frequencies are uniformly distributed across joined tables. This assumption often fails in real-world data, leading to suboptimal plans.
Bansal’s approach leveraged the fact that query plan quality has a single, easily verifiable metric: execution time. The experiment involved constructing a specialized Postgres measurement environment to minimize noise from Linux page cache contention, designing a custom GRPO variant for scoring RL rollouts in noisy conditions, and distributing training across two machines—one running vLLM and the trainer on rented H100 GPUs, another running four Postgres containers.
The work built on a decade of research into query optimizer limitations, including a 2015 study by Leis et al. that revisited the question of optimizer effectiveness a decade later, finding continued room for improvement despite extensive academic research.
Key facts
- A 4B-parameter model achieved 44.7% latency reduction on 113 join-heavy queries
- The model was initially unable to produce valid plans for 99 of 113 test queries
- Join ordering optimization is mathematically NP-hard
- A single three-table join can theoretically execute 4,608 different ways
- Postgres uses statistical estimation and uniform distribution assumptions rather than exact cardinality counting