쿼리 옵티마이저의 핵심 과제인 조인 순서 결정(join ordering)은 NP-hard 문제로 알려져 있지만, 실행 시간이라는 명확한 기준이 있어 검증이 쉽습니다. 저자는 4B 파라미터의 소형 오픈 모델을 SFT와 에이전틱 강화학습(RL)로 후훈련(post-training)하여 Postgres 기본 옵티마이저보다 빠른 쿼리 플랜을 생성하는 실험을 수행했습니다. 그 결과 조인이 많은 113개 쿼리에서 평균 44.7%의 지연 시간 감소를 달성했으며, 일부 쿼리에서는 최대 81% 빠른 플랜을 생성했습니다.
번역된 본문
쿼리 옵티마이저는 정말 얼마나 좋을까? Leis 등은 2015년에 이 정확한 질문을 던졌습니다. 그리고 10년 후 다시 같은 질문을 던졌습니다. 원래 탐구 이후 10년간 방대한 연구가 축적되었음에도 불구하고, 쿼리 옵티마이저는 여전히 개선의 여지가 많다는 것을 발견했습니다. 저는 이 사실을 처음 알았을 때 놀랐습니다. Postgres 데이터베이스는 자신의 테이블에 있는 데이터에 대해 모든 것을 알고 있어야 하지 않나요? 그게 얼마나 어려울 수 있을까요? 결론부터 말하자면: 엄청나게 어렵습니다. 실제로 쿼리 옵티마이저가 수행해야 하는 특정 작업 중 하나인 조인 순서 결정(join ordering)은 NP-hard로 알려져 있습니다. 그래서 쿼리 옵티마이저는 어렵습니다. 덜 어려운 것은 옵티마이저가 선택한 쿼리 플랜이 좋은지 나쁜지 검증하는 일입니다. 간단히 말해, 좋은 쿼리 옵티마이저는 빠르게 실행되는 플랜을 만들고, 나쁜 옵티마이저는 느린 플랜을 만듭니다. 언어 모델은 검증이 쉬운 출력을 가진 작업을 학습하는 데 특히 뛰어납니다. 최적화할 단일 축—쿼리의 실행 시간—이 존재하기 때문에, 이 문제는 모델이 더 빠른 쿼리 플랜을 생성하도록 유도하는 행동을 강화하는 것으로 아름답게 환원됩니다. 이하는 제가 수행한 실험의 분석입니다: 소형 오픈 웨이트 모델을 지도 미세조정(SFT)과 에이전틱 강화학습(RL)을 통해 Postgres의 기본 플랜을 능가하는 Postgres 쿼리 플랜을 생성하도록 후훈련할 수 있는가? 그 질문에 대한 답은 확고한 '예'입니다. 주요 성과는 다음과 같습니다: 처음에 113개 중 99개에 대해 쿼리 플랜을 생성하지 못했던 4B 모델로부터 조인이 많은 113개 쿼리에서 44.7%의 지연 시간 감소 달성; 동시 실행되는 컨테이너 간 Linux 페이지 캐시 경합 노이즈를 최소화하는 Postgres 측정 장비 구축; 본질적으로 노이즈가 많은 환경에서 RL 롤아웃을 채점하기 위한 맞춤형 GRPO 변형 설계; 두 대의 머신에 RL 분산—대여한 2x H100 노드에서 vLLM과 트레이너 실행, 제 책상에서 4개의 Postgres 컨테이너 실행; 약 500개의 GPT-6 Astra 에이전트 궤적(trajectory)에 걸친 오프-정책 증류(distillation) 수행. 처음부터 시작해 봅시다. 쿼리 옵티마이저 내부 IMDb 데이터셋의 다음 부분을 고려해 보세요: -- IMDb 타이틀(영화, 시리즈, 에피소드 등) [약 100만 행] title ( id integer PRIMARY KEY, title text, production_year integer, kind_id integer -- FK -> kind_type ) -- 영화 <> 회사 연결 테이블 [약 200만 행] 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 ) -- 회사 이름, 원산지 등 [약 10만 행] company_name ( id integer PRIMARY KEY, name text, country_code text -- '[us]', '[jp]', ... ) -- 타이틀에 대한 회사 역할 조회 테이블 [4행] company_type ( id integer PRIMARY KEY, kind text -- 'production companies', 'distributors', ... ) -- 타이틀이 무엇인지에 대한 조회 테이블 [7행] kind_type ( id integer PRIMARY KEY, kind text -- 'movie', 'tv series', 'episode', ... ) "2000년대에 가장 많은 작품을 제작한 일본 회사는 어디인가?"라는 질문에 답하려 한다고 합시다. 다음과 같은 쿼리를 작성할 수 있습니다: 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; 이 쿼리를 실행하면 2000년부터 2009년 사이에 관련된 타이틀 수와 함께 상위 10개 일본 회사가 내림차순으로 정렬되어 출력됩니다. 하지만 Postgres는 어떻게 이 결과를 얻었을까요? Postgres가 이 데이터를 가져오기 위해 거친 경로는 결코 자명한 것이 아니며, 이는 선택적 조건자(selective predicates), 즉 WHERE 절의 필터링 조건과 깊은 관련이 있습니다. 이를 설명하기 위해 일본 회사 필터나 날짜 범위 필터 없이 동일한 쿼리를 상상해 보겠습니다: 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
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: 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 t = 1 m t = 1\text{m} t = 1 m Taking into account our joins, we get the following cardinalities: ( c n ⋈ m c ) = 2 m , then ⋈ t = 2 m (cn \bowtie mc) = 2\text{m}, \text{ then } \bowtie t = 2\text{m} ( c n ⋈ m c ) = 2 m , then ⋈ t = 2 m ( t ⋈ m c ) = 2 m , then ⋈ c n = 2 m (t \bowtie mc) = 2\text{m}, \text{ then } \bowtie cn = 2\text{m} ( t ⋈ m c ) = 2 m , then ⋈ c n = 2 m 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) ( c n ′ ⋈ m c ) ≈ 100 k , then ⋈ t ′ ≈ 20 k (cn' \bowtie mc) \approx 100\text{k}, \text{ then } \bowtie\ t' \approx 20\text{k} ( c n ′ ⋈ m c ) ≈ 100 k , then ⋈ t ′ ≈ 20 k ( t ′ ⋈ m c ) ≈ 400 k , then ⋈ c n ′ ≈ 20 k (t' \bowtie mc) \approx 400\text{k}, \text{ then } \bowtie\ cn' \approx 20\text{k} ( t ′ ⋈ m c ) ≈ 400 k , then ⋈ c n ′ ≈ 20 k 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. Unfortunately, it doesn’t stop there. A combinatorial explosion Each join can use any of: Hash join Merge join Nested-loop join 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: Sequential Index Index-only Bitmap 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: 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 numb