query planner(optimizer) 는 어떻게 동작할까?

똑같은 결과를 내는 query 하나에도 실행 경로는 수십 개. table 을 통째로 읽을지, index 를 탈지, 어떤 순서로 join 할지 — 그걸 고르는 게 query planner(optimizer). planner 는 동등한 plan 후보들 중 "가장 싼" 것 하나를 골라 실행한다. 문제는 "싸다" 의 기준이 추정치라는 것. 추정이 틀어지면 0.5ms 짜리 query 가 30 초가 된다. 이 가이드는 planner 의 pipeline, cost model, 통계, cardinality 추정, scan·join 선택, 그리고 EXPLAIN 으로 그 판단을 들여다보는 법을 정리한다.

Pipeline — query 가 plan 이 되기까지

SQL 텍스트
   ↓ parse        문법 검사 → 파스 트리 (별도 가이드 참조)
   ↓ rewrite      view 펼치기, subquery flattening, 상수 접기
   ↓ plan/optimize  동등한 물리 plan 후보 생성 → 비용 추정 → 최저 선택
   ↓ execute      선택된 plan 을 실제로 돌림
   결과 row

Parse 는 텍스트를 트리로 바꾸는 단계 — SQL 문법 자체의 처리는 how-sql-parsing-works 가이드에서 다룬다. 여기서는 그 뒤, rewrite → plan → execute 에 집중한다.

Rewrite 단계는 의미를 바꾸지 않는 변환이다. view 는 정의 query 로 치환되고, 일부 subquery 는 join 으로 평탄화되며, WHERE 1=1 같은 상수 조건은 미리 접힌다. planner 는 이 정리된 query 를 받아 본격적인 최적화에 들어간다.

Logical plan vs Physical plan

Logical plan 은 무엇을 하는지 — "이 두 table 을 join 하고 이 조건으로 거른다". 연산의 의미만 담는다. Physical plan 은 어떻게 하는지 — "hash join 으로, table A 는 seq scan, table B 는 index scan". 같은 logical plan 하나에서 물리적 실행법은 여러 개 나온다.

Logical:  σ(status='paid')  orders ⋈ users
                              user_id

같은 logical plan → 가능한 physical plan 후보:
  A) Seq Scan(orders) ⋈hash Seq Scan(users)
  B) Index Scan(orders) ⋈nestloop Index Scan(users)
  C) Seq Scan(users) ⋈merge Index Scan(orders)
  ... 더 많음

planner 의 일 = 후보들에 비용을 매기고 최저 하나 선택.

후보 수는 join table 이 늘수록 폭발한다 (n 개 table 의 join 순서만 해도 조합이 기하급수적). 그래서 planner 는 동적 계획법(PostgreSQL 의 dynamic programming join search) 이나 휴리스틱(table 이 많으면 genetic algorithm) 으로 탐색 공간을 줄인다.

Cost-based optimization — 비용 숫자 매기기

대부분의 현대 RDBMS 는 cost-based optimizer (CBO). 각 plan 에 하나의 숫자(cost) 를 부여하고 최소값을 고른다. cost 는 시간(ms) 이 아니라 추상 단위 — "이 작업이 page 한 장을 순차로 읽는 비용의 몇 배냐" 를 나타낸다.

PostgreSQL 의 cost 파라미터 (기본값):

seq_page_cost     = 1.0    순차로 page 1 장 읽기 (기준 단위)
random_page_cost  = 4.0    무작위 위치 page 1 장 읽기 (HDD 가정)
cpu_tuple_cost    = 0.01   row 1 개 처리
cpu_index_tuple_cost = 0.005  index entry 1 개 처리
cpu_operator_cost = 0.0025 연산자/함수 1 회

대략적인 plan cost =
  (읽는 page 수 × page_cost)
+ (처리하는 row 수 × cpu_tuple_cost)
+ (index entry 수 × cpu_index_tuple_cost)
+ ...

핵심은 random_page_cost 가 seq_page_cost 의 4 배라는 가정이다. index scan 은 row 를 무작위 위치에서 fetch 하니 page 당 비용이 비싸고, seq scan 은 디스크를 순차로 훑으니 page 당 싸다. 그래서 매치되는 row 가 많으면 "비싼 random read 를 여러 번" 보다 "싼 seq read 로 전부" 가 더 싸진다 — planner 가 index 를 무시하는 핵심 이유다.

SSD / NVMe 환경에선 random read 가 그렇게 비싸지 않다. 그래서 실무에서 random_page_cost 를 1.1 정도로 낮추면 planner 가 index 를 더 적극적으로 쓰도록 유도할 수 있다.

통계 — planner 의 눈

Cost 를 계산하려면 "이 table 에 row 가 몇 개냐", "이 column 의 distinct 값이 몇 개냐" 를 알아야 한다. 이 정보가 통계다. PostgreSQL 은 ANALYZE (또는 autovacuum 의 auto- analyze) 가 table 을 샘플링해 통계를 수집한다.

ANALYZE orders;   -- orders 의 통계 갱신

-- 수집되는 것 (pg_stats view 로 확인):
reltuples    table 의 추정 row 수
n_distinct   column 의 distinct 값 수 (또는 비율)
most_common_vals / most_common_freqs   상위 빈출 값 + 빈도 (MCV)
histogram_bounds   나머지 값의 분포 히스토그램
null_frac    NULL 비율
correlation  물리 저장 순서와 값 순서의 상관 (index scan 효율 판단)

히스토그램 은 범위 query 의 selectivity 추정에 쓰인다. column 값을 같은 빈도의 버킷으로 나눠 저장하면, WHERE age > 40 같은 조건이 전체의 몇 %를 통과하는지 버킷 위치로 추정할 수 있다. MCV(most-common-values)는 분포가 한쪽으로 쏠린 column 에서 빛난다 — 예를 들어 status 의 99% 가 'done' 이면 그 값은 MCV 에 따로 기록돼 정확한 빈도로 추정된다.

왜 stale 통계가 나쁜 plan 을 만드나: 통계는 마지막 ANALYZE 시점의 스냅샷이다. 어제 1 만 row 였던 table 에 오늘 1 천만 row 를 부었는데 ANALYZE 를 안 했다면, planner 는 여전히 1 만 row 라고 믿고 nested loop 같은 "작은 table 용" plan 을 고른다. 실제론 천만 번 loop 를 돌게 되고 query 가 멈춘 듯 느려진다.

Cardinality / Selectivity — 1 번 원인

Cardinality = 어떤 연산이 내놓을 row 수 추정. Selectivity = filter 가 통과시키는 비율 (0~1). planner 의 모든 비용 계산이 이 추정 위에 쌓인다. 그리고 나쁜 plan 의 1 번 원인은 cardinality 오추정이다.

예: orders 1,000,000 row, status 의 distinct 5 개

WHERE status = 'paid'
→ planner: selectivity ≈ 1/5 = 0.2 → 추정 200,000 row
   (균등 분포 가정. MCV 있으면 실제 빈도 사용)

WHERE user_id = 42
→ user_id distinct 100,000 개라면
   selectivity ≈ 1/100,000 → 추정 10 row → index scan 선택

문제는 여러 조건이 상관(correlated) 될 때다. planner 는 기본적으로 조건들이 독립이라 가정하고 selectivity 를 곱한다.

WHERE city = 'Seoul' AND country = 'Korea'

planner 가정: 독립 → P(Seoul) × P(Korea)
실제: Seoul 이면 거의 항상 Korea → 두 조건이 사실상 하나

→ planner 는 row 수를 심하게 과소추정
→ 너무 낙관적인 plan (nested loop) 선택 → 폭발

이걸 보정하려고 PostgreSQL 은 CREATE STATISTICS 로 multi-column(extended) statistics 를 만들 수 있다 — 상관된 column 묶음의 실제 distinct 조합 수를 따로 저장해 곱셈 가정을 깬다. 오추정이 의심되면 EXPLAIN ANALYZE 의 estimated vs actual rows 격차부터 확인하는 게 출발점이다.

Access method — table 에 닿는 방법

하나의 table 에서 row 를 가져오는 방법만도 여러 가지다. planner 는 매치 추정 row 수(selectivity) 를 보고 고른다.

• Seq Scan — table 전체를 순차로 훑음. 매치 row 가 많거나(저 selectivity) table 이 작으면 가장 싸다. index 의 random fetch 보다 순차 read 가 page 당 저렴하기 때문.
• Index Scan — index 로 row pointer 를 찾고 table 에서 row 를 fetch. 매치가 적을 때(고 selectivity) 유리. 매치마다 random page read 한 번.
• Index Only Scan — 필요한 column 이 전부 index 에 있으면(covering) table 을 안 건드림. 가장 빠른 축.
• Bitmap Heap Scan — index 로 매치 page 들의 비트맵을 만든 뒤 그 page 들을 순차에 가깝게 fetch. "index 쓰기엔 매치가 좀 많고, seq scan 하기엔 좀 적은" 중간 영역에 적합. 여러 index 결합도 가능.

왜 planner 가 일부러 내 index 를 무시하나: index 가 있어도 매치 row 가 전체의 큰 비율(예 30%+) 이면, index scan 은 그만큼 random page fetch 를 반복해야 한다. 그 비용이 table 을 한 번 순차로 훑는 비용을 넘어서면 planner 는 옳게 seq scan 을 고른다. "index 를 만들었는데 왜 안 써?" 의 답은 대개 "써봤자 더 비싸서" 다.

-- 매치가 적음 → Index Scan
EXPLAIN SELECT * FROM orders WHERE user_id = 42;
  Index Scan using idx_user on orders  (cost=0.42..8.4 rows=9 ...)

-- 매치가 table 의 절반 → Seq Scan (index 무시가 정답)
EXPLAIN SELECT * FROM orders WHERE status = 'done';
  Seq Scan on orders  (cost=0..18334 rows=512000 ...)
  Filter: (status = 'done')

Index scan 효율은 통계의 correlation 에도 좌우된다 — index 순서와 물리 저장 순서가 일치하면(높은 상관) random fetch 가 사실상 순차에 가까워 더 싸다. 자세한 index 내부는 how-database-indexes-work 가이드 참조.

Join 알고리즘 — 3 가지 무기

두 table 을 합치는 방법은 세 가지가 표준이다. planner 는 양쪽 입력의 추정 크기, 정렬 여부, 가용 index 를 보고 고른다.

• Nested Loop — 바깥 table 의 각 row 마다 안쪽 table 을 조회. 안쪽에 좋은 index 가 있고 바깥이 작을 때 최고. 바깥 row 수 × 안쪽 lookup 비용. 바깥이 크면 재앙.
• Hash Join — 작은 쪽으로 메모리에 hash table 을 짓고, 큰 쪽을 흘리며 probe. equality join 에 강하고 큰 table 끼리 유리. 양쪽을 한 번씩만 읽음(빌드 + probe). hash 가 메모리(work_mem) 를 넘으면 disk 로 spill.
• Merge Join — 양쪽을 join key 로 정렬한 뒤 지퍼처럼 맞물려 합침. 양쪽이 이미 정렬돼 있거나(예 index 순) sort 비용을 감당할 만하면 유리. 대용량 정렬 입력에 강함.

비용 직관 (바깥 N row, 안쪽 M row):

Nested Loop  ≈ N × (안쪽 1 회 lookup)
             안쪽에 index 없으면 N × M → 폭발

Hash Join    ≈ N + M  (빌드 + probe, 각 1 회 스캔)
             큰 × 큰 equality join 의 기본 선택

Merge Join   ≈ N + M  + 정렬 비용(이미 정렬이면 0)
             정렬된 입력 / range 친화적

직관: 작은 ⋈ index 있는 큰 → nested loop. 큰 ⋈ 큰 equality → hash. 이미 정렬됨 → merge. cardinality 오추정으로 "작은 줄 알았던" 입력이 사실 거대하면 planner 는 nested loop 를 골랐다가 폭발한다 — 다시, 통계가 핵심이다.

EXPLAIN / EXPLAIN ANALYZE 읽기

EXPLAIN 은 planner 의 추정 plan 만 출력한다(실행 안 함).EXPLAIN ANALYZE 는 실제로 돌려 추정 vs 실제를 나란히 보여준다 — 디버깅의 핵심 도구다.

EXPLAIN ANALYZE
SELECT * FROM orders o
JOIN users u ON u.id = o.user_id
WHERE u.country = 'Korea' AND o.status = 'paid';

QUERY PLAN
─────────────────────────────────────────────────────────────────
Hash Join  (cost=33.50..2150.75 rows=120 width=88)
           (actual time=0.42..58.3 rows=48000 loops=1)
  Hash Cond: (o.user_id = u.id)
  ->  Seq Scan on orders o  (cost=0..1800 rows=50000 width=72)
        (actual time=0.01..21.4 rows=50000 loops=1)
        Filter: (status = 'paid')
  ->  Hash  (cost=20..20 rows=800 width=16)
        ->  Index Scan using idx_country on users u
              (cost=0.3..20 rows=800 ...)
              (actual time=0.03..2.1 rows=790 loops=1)

Planning Time: 0.31 ms
Execution Time: 71.9 ms

읽는 순서와 포인트:

• 안쪽(들여쓰기 깊은 곳)부터 바깥으로 읽는다. 위 예는 orders seq scan + users index scan → hash join 으로 결합.
• cost=시작..총 — 첫 row 까지 비용 .. 전체 완료 비용 (추상 단위). actual time=시작..총 은 실제 ms.
• 가장 중요: rows=120 (추정) vs actual ... rows=48000. 400 배 오추정. planner 는 join 결과를 120 row 로 보고 plan 을 짰지만 실제는 4 만 8 천. correlated 조건의 곱셈 가정이 무너진 전형적 사례.
• loops=N — nested loop 안쪽에서 N 번 반복됐다는 뜻. actual time 은 loop 1 회 평균이므로 총 시간은 time × loops.
• cost 가 큰데 time 은 작거나(또는 반대) 하면 추정이 현실과 어긋난 신호. 추가 옵션: EXPLAIN (ANALYZE, BUFFERS) 로 실제 page 읽기까지 본다.

실무 진단법: estimated vs actual rows 의 격차가 가장 큰 node 를 찾아라. 거기가 오추정의 진원지이고, 잘못된 join 선택과 폭발의 원인일 확률이 높다.

Plan 캐싱 / Prepared statement

같은 query 를 반복하면 매번 plan 을 새로 짜는 게 낭비다. prepared statement 는 plan 을 재사용한다. PostgreSQL 은 두 모드를 오간다:

• Custom plan — 매 실행마다 실제 파라미터 값으로 다시 최적화. 값에 따라 최적 plan 이 달라지는 경우 유리(예 어떤 값은 희귀, 어떤 값은 흔함).
• Generic plan — 파라미터를 평균 selectivity 로 가정해 한 번만 짜고 재사용. 계획 시간을 아낌. PostgreSQL 은 처음 몇 회 custom 비용을 보고 generic 이 비슷하게 싸면 generic 으로 고정한다.

함정: 데이터 분포가 한쪽으로 쏠린 column 에 generic plan 이 박히면, 희귀 값엔 좋지만 흔한 값엔 끔찍한 plan 이 재사용될 수 있다. plan_cache_mode 로 강제 전환 가능.

참고 자료

• PostgreSQL — Using EXPLAIN — postgresql.org
• PostgreSQL — Planner Cost Constants — postgresql.org
• PostgreSQL — Row Estimation Examples — postgresql.org
• Use The Index, Luke — Markus Winand — use-the-index-luke.com

실용 요약

• planner 의 일 = 동등한 물리 plan 후보 중 cost 가 최저인 하나를 고르는 것. cost 는 시간이 아니라 추상 단위.
• 큰 변경(대량 INSERT / 삭제 / 새 column 분포) 후엔 반드시 ANALYZE. stale 통계가 나쁜 plan 의 흔한 뿌리.
• 나쁜 plan 의 1 번 원인은 cardinality 오추정. correlated column 은 CREATE STATISTICS 로 보정.
• 매치가 많으면 planner 가 index 를 무시하고 seq scan 을 고르는 게 정답이다. random fetch 가 순차 read 보다 비싸서.
• join 직관 — 작은 ⋈ index 큰 = nested loop, 큰 ⋈ 큰 = hash, 정렬됨 = merge.
• EXPLAIN ANALYZE 에서 estimated vs actual rows 격차가 가장 큰 node 를 찾아라 — 거기가 문제의 진원지.
• planner 와 무작정 싸우지 말 것(index 힌트 강제 등). 대개 통계를 고치거나 query 를 다시 쓰는 게 정도. 관련 — how-database-indexes- work, how-sql-parsing-works.