Database Query Optimizer 완전 가이드 2025: Volcano, Cascades, Cost-Based, Cardinality Estimation — PostgreSQL/MySQL 실전 분석

들어가며: SQL 한 줄의 마법

같은 쿼리, 1000배 차이

다음 쿼리를 보자:

SELECT u.name, o.total
FROM users u JOIN orders o ON u.id = o.user_id
WHERE u.country = 'KR' AND o.created_at > '2025-01-01';

이 한 줄짜리 SQL은 최소 수십 가지 방법으로 실행될 수 있다:

1. users를 먼저 스캔 → filter → orders와 nested loop join
2. orders를 먼저 스캔 → filter → users와 hash join
3. 양쪽 인덱스 사용 → merge join
4. country 인덱스 + date 인덱스 조합...

각 방식의 성능 차이는 수백~수천 배일 수 있다. 같은 쿼리, 같은 데이터, 완전히 다른 실행 시간.

그 선택을 하는 주인공이 query optimizer다. 당신이 SQL을 입력하면, 옵티마이저는:

1. 쿼리를 관계 대수로 변환
2. 가능한 실행 계획들을 생성
3. 각 계획의 비용을 추정
4. 가장 싼 것을 선택

이 글은 이 전 과정을 해부한다. Volcano에서 Cascades까지, cost-based optimization의 원리부터 현대 DB의 실전 구현까지.

왜 이걸 알아야 하는가?

• 느린 쿼리 디버깅: EXPLAIN 결과를 정확히 해석하려면 옵티마이저를 알아야 한다.
• 인덱스 설계: 옵티마이저가 어떻게 선택하는지 알면 인덱스가 왜 "안 쓰이는지" 안다.
• 통계 관리: 왜 ANALYZE가 필요한지, 통계가 어떻게 성능을 좌우하는지.
• DB 간 차이: PostgreSQL, MySQL, Oracle의 옵티마이저는 서로 크게 다르다. 이식할 때 중요.
• 최신 NewSQL: TiDB, CockroachDB의 옵티마이저는 어떻게 다른가?

1. 옵티마이저의 세 가지 단계

1단계: Parsing

SQL 텍스트를 AST (Abstract Syntax Tree) 로 변환한다.

SELECT * FROM t WHERE id = 5
        ↓
Select
├── Projection: *
├── From: t
└── Where: Equal(id, 5)

parsing 단계에선 주로 문법 검사만 한다. 이후 catalog 검증(테이블/컬럼 존재 여부)도 한다.

2단계: Rewriting / Logical Optimization

AST를 관계 대수(Relational Algebra) 로 변환하고, 논리적 변환을 적용한다:

• Predicate pushdown: WHERE 조건을 최대한 안쪽으로.
• Projection pushdown: 필요한 컬럼만 읽기.
• Constant folding: 1 + 2를 3으로.
• Subquery unnesting: 서브쿼리를 조인으로 변환.
• View expansion: 뷰를 원래 쿼리로 확장.

이 단계는 의미를 바꾸지 않는 변환들이다.

3단계: Physical Optimization / Cost-Based

가능한 물리적 실행 계획들을 생성하고, 비용을 추정해 가장 싼 것을 고른다. 이 단계가 옵티마이저의 진짜 핵심이다.

• 어떤 access method 쓸까? (full scan, index scan, index only scan)
• 어떤 join 알고리즘? (nested loop, hash join, merge join)
• 어떤 join 순서?
• 어디서 정렬할까?

2. 관계 대수와 논리적 최적화

관계 대수 기본

관계 대수는 집합 이론에 기반한 쿼리 언어의 수학적 모델이다:

• σ (selection): WHERE (행 필터링).
• π (projection): SELECT 컬럼 (열 선택).
• ⋈ (join): 테이블 결합.
• ∪ (union), ∩ (intersection), - (difference).
• γ (group): GROUP BY.

SQL:

SELECT name FROM users WHERE age > 30

관계 대수:

π_name(σ_age>30(users))

대수적 동등 변환

관계 대수는 변환 규칙이 있다. 예를 들어:

• Selection 분배: σ_p∧q(R) = σ_p(σ_q(R))
• Selection push through join: σ_p(R ⋈ S) = σ_p(R) ⋈ S (p가 R의 컬럼만 사용할 때)
• Projection push through selection: π_A(σ_p(R)) = π_A(σ_p(π_A∪필요컬럼(R)))
• Join 교환: R ⋈ S = S ⋈ R
• Join 결합: (R ⋈ S) ⋈ T = R ⋈ (S ⋈ T)

이 규칙들을 적용하면 같은 결과를 내는 다른 쿼리가 된다.

Predicate Pushdown 예시

SELECT u.name, o.total
FROM users u JOIN orders o ON u.id = o.user_id
WHERE u.country = 'KR';

초기 계획:

π_{name,total}(σ_{country='KR'}(users ⋈ orders))

users와 orders를 먼저 조인하고 나서 country 필터링 → 비효율.

Predicate pushdown 적용:

π_{name,total}(σ_{country='KR'}(users) ⋈ orders)

users에서 KR만 먼저 필터링하고 orders와 조인 → 훨씬 효율.

현대 옵티마이저는 이런 변환을 수백 가지 자동 적용한다.

Projection Pushdown

SELECT name FROM users JOIN orders ON users.id = orders.user_id;

초기 계획: users와 orders의 모든 컬럼을 가져와서 조인 후 name만 뽑기.

최적화: 조인 전에 users에서 (id, name), orders에서 user_id만 가져오기. 네트워크와 메모리 대폭 절약.

Subquery Unnesting

SELECT * FROM orders
WHERE user_id IN (SELECT id FROM users WHERE country = 'KR');

이 쿼리는 두 가지 방식으로 실행될 수 있다:

1. Correlated: orders의 각 행마다 서브쿼리 실행 → N번의 users 스캔 → 매우 느림.
2. Unnested: 조인으로 변환.

-- 옵티마이저가 이렇게 변환
SELECT o.* FROM orders o JOIN users u ON o.user_id = u.id
WHERE u.country = 'KR';

좋은 옵티마이저는 이런 변환을 자동으로 한다. 나쁜 옵티마이저(또는 오래된 것)는 correlated execution을 그대로 실행해서 극도로 느린 결과가 나온다.

3. 물리 연산자: 실행의 기본 단위

Access Method: 테이블 읽기

Sequential Scan (Full Table Scan):

[Page 1][Page 2][Page 3]...
   ↓       ↓       ↓
모든 행을 순차적으로 읽음

• 큰 테이블 + 조건 없음: 빠름 (순차 I/O).
• 작은 결과 + 조건 있음: 느림 (모든 행을 버려야 함).

Index Scan:

B-Tree
   ↓ (조건에 맞는 키 찾기)
Heap → 해당 행 읽기

• 작은 결과: 매우 빠름.
• 큰 결과 (선택도 높음): random I/O 많아서 느림.
• 보통 전체의 10% 이상을 반환하면 full scan이 더 빠르다.

Index Only Scan:

B-Tree
   ↓ (인덱스만으로 답변)
Heap 접근 없음

필요한 모든 컬럼이 인덱스에 있으면 heap을 건드리지 않는다. 가장 빠른 접근 방식.

Bitmap Index Scan:

Index 1 → bitmap 1
Index 2 → bitmap 2
  ↓
AND/OR 결합
  ↓
Heap scan (정렬된 순서)

여러 인덱스의 결과를 결합. 순차 접근 패턴으로 random I/O를 줄인다.

Join Algorithms

Nested Loop Join (NLJ):

for r in R:
    for s in S:
        if r.key == s.key:
            output(r, s)

• 복잡도: O(|R| × |S|).
• 인덱스가 있으면: O(|R| × log|S|).
• 작은 outer + 인덱스 있는 inner에 최적.

Hash Join:

# Build phase
hash_table = {}
for r in R:
    hash_table[r.key] = r

# Probe phase
for s in S:
    if s.key in hash_table:
        output(hash_table[s.key], s)

• 복잡도: O(|R| + |S|).
• 메모리 필요.
• 큰 테이블 + 인덱스 없음에 최적.
• Parallel 친화적.

Sort-Merge Join:

sort(R, by=key)
sort(S, by=key)

i, j = 0, 0
while i < len(R) and j < len(S):
    if R[i].key == S[j].key:
        output(R[i], S[j])
        # 중복 처리
    elif R[i].key < S[j].key:
        i += 1
    else:
        j += 1

• 복잡도: O(|R| log|R| + |S| log|S|).
• 이미 정렬되어 있으면: O(|R| + |S|).
• ORDER BY나 인덱스로 이미 정렬된 경우에 최적.
• Range join 지원.

선택의 기준

어떤 조인을 고를까? 옵티마이저는 비용 함수로 비교한다:

• NLJ cost: |R| × cost_per_probe
• Hash join cost: |R| × hash_cost + |S| × probe_cost + build_memory
• Merge join cost: sort(R) + sort(S) + scan(R) + scan(S)

여기서 핵심은 |R|, |S|를 모른다는 것이다. 옵티마이저는 이를 추정해야 한다.

4. Cost-Based Optimization: 비용의 수학

비용 함수

각 물리 연산자는 비용 공식을 가진다:

Sequential Scan:

cost = seq_page_cost × num_pages + cpu_tuple_cost × num_tuples

Index Scan:

cost = random_page_cost × (index_pages + heap_pages) 
     + cpu_index_tuple_cost × num_matched 
     + cpu_tuple_cost × num_matched

파라미터의 의미

PostgreSQL의 기본값:

seq_page_cost = 1.0          # 순차 디스크 페이지 I/O
random_page_cost = 4.0       # 랜덤 디스크 페이지 I/O
cpu_tuple_cost = 0.01        # 행 처리 CPU 비용
cpu_index_tuple_cost = 0.005 # 인덱스 엔트리 처리
cpu_operator_cost = 0.0025   # 연산자 실행 (=, <, ...)

이 값들은 상대적이다. seq_page_cost = 1.0은 단지 기준일 뿐이다.

SSD 시대의 조정

HDD 시대엔 random I/O가 sequential I/O보다 훨씬 느렸다 (~100배). 그래서 random_page_cost = 4.0으로 설정되어 있다. 하지만 SSD에선 차이가 작다. NVMe는 거의 같다.

# SSD 환경에선
random_page_cost = 1.1

이 하나의 변경만으로도 옵티마이저가 인덱스를 더 많이 사용하게 된다.

effective_cache_size

effective_cache_size = 4GB

이 파라미터는 "OS page cache + PostgreSQL shared buffers에 몇 MB가 캐시될 수 있는가"를 알려준다. 옵티마이저는 이 값을 참고해 인덱스 스캔의 예상 I/O를 조정한다. 크면 인덱스 선호, 작으면 full scan 선호.

Join Cost 예시

SELECT * FROM A JOIN B ON A.id = B.a_id

A: 10,000행, B: 100,000행, B에 a_id 인덱스 있음.

NLJ (A outer):

10,000 × (index_lookup_cost + matched_rows_cost)
≈ 10,000 × (4 + 0.01 × 10)  (각 A 행마다 평균 10 매치)
≈ 40,000 + 1000 = 41,000

Hash Join (B as build):

build: 100,000 × cpu_tuple_cost = 1,000
probe: 10,000 × (hash_cost + matched_cost) ≈ 10,000 × 0.02 = 200
total: 1,200

Hash가 훨씬 싸다. 옵티마이저는 hash join을 선택한다.

주의: 비용은 상대적 비교용이지 절대 시간이 아니다. "cost=1,000"이 "1초"가 아니다. 같은 쿼리 내에서 대안들의 순위를 매기는 용도다.

5. Cardinality Estimation: 옵티마이저의 생명

"얼마나 많은 행이 나올까?"

옵티마이저의 모든 비용 계산은 **각 연산자의 결과 행 수(cardinality)**에 의존한다. 추정이 틀리면 전체 계획이 틀린다.

SELECT * FROM users WHERE country = 'KR' AND age > 30;

질문:

• 전체 users 수: 100만
• country='KR'의 선택도: 20% → 20만
• age > 30의 선택도: 40% → 40만
• 둘 다 만족: ?

선택도 독립 가정: 20% × 40% = 8% → 8만 행 추정.

이 추정이 실제(예: 5만 행)와 비슷하면 좋은 계획. 완전히 틀리면(예: 50만 행) 재앙.

통계: 옵티마이저의 감각

통계가 정확해야 추정도 정확하다. PostgreSQL의 pg_statistic에 저장되는 정보:

1. n_distinct: 컬럼의 고유값 수.
2. null_frac: NULL 비율.
3. most_common_vals (MCV): 가장 자주 나오는 값들.
4. most_common_freqs: MCV들의 빈도.
5. histogram_bounds: 값 분포 히스토그램 (균등 버킷).
6. correlation: 물리 순서와 논리 순서의 상관관계.

히스토그램

컬럼 age의 히스토그램 (100개 버킷)
[0-5][5-12][12-20][20-25][25-28]...[70-120]
 5%   5%     5%     5%      5%       5%

각 버킷은 전체의 균등 비율(예: 1%)을 담는다. 버킷 범위가 좁을수록 값이 밀집된 구간.

쿼리 WHERE age > 30:

• 30 이상 버킷이 몇 개인가?
• 각 버킷은 전체의 1%.
• 추정: 버킷수 × 1% × 총행수.

MCV (Most Common Values)

값이 매우 편중된 경우 (예: status 컬럼의 90%가 'active'):

• MCV: ['active', 'inactive', 'pending']
• MCV freqs: [0.9, 0.08, 0.02]

WHERE status = 'active' → 추정: 0.9 × 총행수.

MCV에 없는 값은 히스토그램으로 추정.

선택도 계산의 함정

함정 1: 독립 가정의 오류

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

옵티마이저: P(city='Seoul') × P(country='Korea') = 0.1 × 0.2 = 0.02

실제: P(city='Seoul' AND country='Korea') = 0.1 (Seoul은 Korea에만 있음)

5배 차이. 잘못된 계획으로 이어진다.

해결: 확장 통계(Extended Statistics). PostgreSQL 10+에서:

CREATE STATISTICS ON (city, country) FROM addresses;
ANALYZE addresses;

이제 옵티마이저가 두 컬럼의 상관관계를 안다.

함정 2: LIKE 패턴

WHERE name LIKE 'A%'

선택도 추정이 어렵다. 옵티마이저는 MCV와 히스토그램으로 시도하지만 종종 틀린다.

함정 3: 조인 결과 추정

SELECT * FROM A JOIN B ON A.key = B.key

결과 행 수 추정:

|R ⋈ S| ≈ |R| × |S| / max(n_distinct(A.key), n_distinct(B.key))

이 공식은 "균등 분포" 가정에 기반한다. 실제론 치우쳐 있으면 오차가 크다.

ANALYZE의 중요성

통계는 ANALYZE 명령으로 업데이트된다:

ANALYZE users;  -- 특정 테이블
ANALYZE;        -- 전체

PostgreSQL은 autovacuum이 주기적으로 ANALYZE를 실행한다. 그러나:

• 대량 INSERT/UPDATE 후엔 수동 ANALYZE 권장.
• 통계가 오래되면 옵티마이저가 잘못된 계획을 고른다.
• 새 테이블에 ANALYZE 없이 대량 조회하면 끔찍한 계획이 나올 수 있다.

6. Volcano Optimizer

Goetz Graefe의 혁신

1993년 Goetz Graefe가 발표한 Volcano Optimizer는 현대 query optimizer의 시작점이다. 핵심 아이디어:

"변환 규칙의 집합으로 모든 가능한 계획을 생성하고, 가장 싼 것을 고른다."

Operator Tree

쿼리는 logical operator의 트리로 표현된다:

Join
├── Scan(A)
└── Scan(B)

옵티마이저의 목표는 이를 physical operator의 트리로 변환하면서 비용을 최소화하는 것:

HashJoin
├── SeqScan(A)
└── IndexScan(B)

Transformation Rules

Volcano는 변환 규칙들의 집합으로 탐색한다:

• Logical → Logical: Join commutativity, associativity.
• Logical → Physical: Join → HashJoin, Join → NestedLoopJoin 등.
• Enforcer: 정렬이 필요하면 Sort 추가.

Top-down 탐색

Volcano는 탐색을 top-down으로 진행한다:

1. 루트 연산자부터 시작.
2. 각 연산자에 가능한 물리 구현을 나열.
3. 자식들도 재귀적으로 최적화.
4. 모든 하위 트리의 비용을 계산 후 최적 선택.

Memoization

같은 하위 문제를 여러 번 만나면 재계산하면 비싸다. Volcano는 memoization(계산 결과 캐싱)을 사용한다. 같은 하위 식은 한 번만 최적화.

문제점

Volcano는 훌륭하지만 몇 가지 한계가 있었다:

1. Exhaustive search: 모든 계획을 생성하려 해서 조인 수가 많으면 폭발.
2. Top-down의 비효율: 상위에서 결정이 하위로 전파되며 여러 번 재방문.

이를 개선한 것이 Cascades다.

7. Cascades Optimizer

Graefe의 차기작

Cascades (1995)도 Goetz Graefe의 작품이다. SQL Server, CockroachDB, Apache Calcite, Greenplum의 옵티마이저가 모두 Cascades 기반.

주요 개선

1. Unified logical/physical transformations: 규칙을 통일된 방식으로 표현.
2. Memoization 구조 개선: "memo" 데이터 구조로 중복 최적화 방지.
3. Property propagation: 정렬, 분포 같은 속성을 전파.
4. Branch-and-bound pruning: 명백히 나쁜 계획은 일찍 포기.

Memo 구조

Memo는 동등한 식들의 그룹 집합이다:

Group 1: σ_p(R)
Group 2: σ_p(R) ⋈ S, (R ⋈ S with σ_p pushed)
Group 3: A ⋈ B, B ⋈ A (commutativity)

각 group은 동일한 결과를 내는 여러 표현 방식을 담는다. 옵티마이저는 group 수준에서 비용 비교.

Property

Physical Properties는 계획이 가지는 특성이다:

• Ordering: 결과가 정렬되어 있는가?
• Distribution: 분산 DB에서 데이터가 어떻게 파티션되어 있나?
• Uniqueness: 결과에 중복이 없는가?

부모 연산자가 특정 property를 요구하면(예: Merge Join이 정렬된 입력 요구), 자식이 그걸 제공하거나 enforcer를 추가한다(Sort).

Pruning

탐색이 폭발하는 걸 막기 위해 pruning:

• 이미 찾은 최적 비용보다 높은 하위 문제는 스킵.
• Branch-and-bound 알고리즘.

Cascades 기반 옵티마이저들

• SQL Server: 자체 Cascades 기반 구현.
• PostgreSQL: Cascades 아님 (dynamic programming 기반).
• CockroachDB: Cascades 기반.
• Apache Calcite: Cascades 기반, Hive/Flink/Beam에서 사용.
• Presto/Trino: Calcite 영감 + 자체 구현.

8. PostgreSQL의 옵티마이저

구조

PostgreSQL은 Volcano/Cascades보다 조금 다른 접근을 쓴다:

• Rewriting → Logical plan
• Plan generation: Dynamic programming + Genetic algorithm.
• Cost estimation: 이산 비용 함수.
• Plan selection: 가장 싼 것.

Dynamic Programming Join Ordering

조인 순서 결정에 Dynamic Programming (DP) 를 쓴다. 각 부분집합의 최적 조인을 구하고 조합한다.

• 복잡도: O(3^n) 정도.
• n ≤ 12: DP로 정확한 최적.
• n > 12: geqo_threshold 초과 → Genetic Algorithm으로 전환.

Genetic Algorithm (GEQO)

많은 테이블의 조인(예: 15개)에서는 DP가 너무 느리므로:

1. 무작위 조인 순서 생성.
2. "적합도" (예상 비용) 평가.
3. 좋은 것을 교차/변이.
4. 여러 세대 진화.
5. 가장 좋은 것 선택.

정확한 최적은 아니지만 합리적인 해를 빠르게 찾는다. geqo = on (기본).

Generic vs Custom Plan

PostgreSQL은 prepared statement에 대해 특별한 동작을 한다:

• Custom plan: 매 실행마다 파라미터 기반 최적화.
• Generic plan: 한 번만 최적화, 이후 재사용.

PostgreSQL은 처음 몇 번은 custom, 이후 generic이 더 싸면 generic으로 전환. 이로 인해 "처음엔 빠르다가 갑자기 느려지는" 현상이 발생할 수 있다.

EXPLAIN

옵티마이저의 결정을 보려면 EXPLAIN:

EXPLAIN (ANALYZE, BUFFERS, VERBOSE) 
SELECT u.name, o.total 
FROM users u JOIN orders o ON u.id = o.user_id
WHERE u.country = 'KR';

Hash Join  (cost=10.00..250.00 rows=500 width=64) (actual time=0.1..5.0 rows=487 loops=1)
  Hash Cond: (o.user_id = u.id)
  Buffers: shared hit=234
  ->  Seq Scan on orders o  (cost=0.00..150.00 rows=10000 width=16)
  ->  Hash  (cost=8.00..8.00 rows=100 width=56)
        ->  Index Scan using idx_users_country on users u
              Index Cond: (country = 'KR')

해석:

• cost: 추정 비용 (시작_비용..전체_비용).
• rows: 추정 행 수.
• actual: 실제 실행 시 측정값.
• loops: 이 노드가 실행된 횟수.

추정 rows vs actual rows 차이가 크면 통계 문제. ANALYZE 필요.

9. MySQL의 옵티마이저

역사

MySQL의 옵티마이저는 오랫동안 heuristics 기반이었다:

• 항상 테이블을 고정 순서로 조인 (왼쪽 깊은 트리).
• 인덱스 사용 여부를 규칙으로 결정.

5.6 이후 cost-based optimizer를 도입하고 지속적으로 개선 중이다.

Histograms

MySQL 8.0부터 히스토그램 지원:

ANALYZE TABLE users UPDATE HISTOGRAM ON country WITH 100 BUCKETS;

PostgreSQL보다 늦게 추가되었지만 효과적이다.

Optimizer Hints

MySQL은 옵티마이저에게 힌트를 줄 수 있다:

SELECT /*+ INDEX(users idx_country) */ *
FROM users WHERE country = 'KR';

이는 "country 인덱스 써"라는 지시다. PostgreSQL은 힌트를 공식 지원하지 않는다 (철학적 차이).

ICP (Index Condition Pushdown)

MySQL의 유용한 기능. WHERE 조건 중 일부를 인덱스 수준에서 평가:

SELECT * FROM users WHERE country = 'KR' AND age > 30;

인덱스 (country, age)가 있으면:

1. 일반적: country='KR' 인덱스 매치 → 행 fetch → age 검사.
2. ICP: country='KR' 인덱스 매치 → age 조건을 인덱스 수준에서 체크 → 통과한 것만 fetch.

random I/O를 크게 줄인다.

Join Buffer (Block Nested Loop)

인덱스가 없을 때 MySQL의 기본 조인은 Block Nested Loop:

join_buffer_size 만큼 outer의 여러 행을 메모리에 모음
  ↓
inner table을 한 번 스캔하면서 각 outer 블록과 매치
  ↓
I/O 줄임

Hash join은 MySQL 8.0.18부터 추가되었다. 이전엔 block NLJ가 유일한 대안이었다.

10. 옵티마이저의 한계와 실전 기법

한계 1: 통계가 없거나 오래됨

증상: EXPLAIN의 rows 추정이 실제와 심하게 다름.

해결:

ANALYZE my_table;  -- PostgreSQL
ANALYZE TABLE my_table;  -- MySQL

자동 ANALYZE가 작동하는지 확인. 큰 업데이트 후엔 수동 실행.

한계 2: 조인 수 폭발

20개 테이블 조인은 옵티마이저를 질리게 한다. 시간이 기하급수적으로 늘어난다.

해결:

• View로 분해: 자주 쓰이는 조합을 뷰로.
• Subquery로 분리: 부분적으로 먼저 계산.
• PostgreSQL: join_collapse_limit, from_collapse_limit 조정.
• MySQL: optimizer_search_depth 조정.

한계 3: 상관 컬럼

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

독립 가정이 틀려 추정 오류. Extended statistics(PostgreSQL) 또는 histograms + correlation 정보 필요.

한계 4: Skewed data

특정 값이 극도로 많은 경우:

status 컬럼: 'active' 99%, 'deleted' 1%

"all-or-nothing" 쿼리에서 문제:

SELECT * FROM t WHERE status = 'deleted';

• 통계 없이: "행 수의 50%" 추정 → full scan.
• MCV로: "1%" 추정 → 인덱스 사용.

MCV가 정확하게 잡혀야 한다.

한계 5: 파라미터 의존 쿼리

PREPARE p AS SELECT * FROM t WHERE x = $1 AND y > $2;

$1 = 'rare_value'와 $1 = 'common_value'에 맞는 최적 계획이 다를 수 있다. Generic plan은 두 경우 모두에 최적일 수 없다.

해결:

• Custom plan 강제: PostgreSQL의 plan_cache_mode = force_custom_plan.
• 동적 SQL: 파라미터화 포기.

실전 기법: Query Rewriting

옵티마이저가 못 푸는 문제를 SQL 재작성으로 해결:

원본 (느림):

SELECT * FROM orders
WHERE EXISTS (
  SELECT 1 FROM users
  WHERE users.id = orders.user_id AND users.country = 'KR'
);

재작성 (빠름):

SELECT o.* FROM orders o
INNER JOIN users u ON o.user_id = u.id
WHERE u.country = 'KR';

현대 옵티마이저는 대부분 자동 변환하지만, 항상은 아니다.

실전 기법: Materialized View

자주 실행되는 비싼 쿼리를 미리 계산해서 저장:

CREATE MATERIALIZED VIEW user_order_summary AS
SELECT u.id, u.name, COUNT(o.id) as order_count, SUM(o.total) as total_spent
FROM users u LEFT JOIN orders o ON u.id = o.user_id
GROUP BY u.id, u.name;

REFRESH MATERIALIZED VIEW user_order_summary;

옵티마이저는 (PostgreSQL 기본으론) 자동 활용하지 않지만, 애플리케이션에서 직접 사용 가능.

실전 기법: Hint or Plan Pinning

마지막 수단: 특정 계획 강제.

Oracle:

SELECT /*+ INDEX(t idx_t_name) */ * FROM t WHERE name = 'foo';

PostgreSQL (pg_hint_plan 확장):

/*+ IndexScan(t idx_t_name) */
SELECT * FROM t WHERE name = 'foo';

MySQL:

SELECT * FROM t USE INDEX (idx_t_name) WHERE name = 'foo';

힌트는 유혹적이지만 위험하다. 데이터 분포가 바뀌면 더 이상 최적이 아닐 수 있다. 최후의 수단으로.

11. 분산 DB의 옵티마이저

추가 고려사항

분산 DB(CockroachDB, TiDB, Spanner)의 옵티마이저는 추가로 고려할 것들:

• 데이터 위치(locality): 어떤 노드에 어떤 데이터가 있는가.
• 네트워크 비용: 조인을 어디서 할까?
• 병렬성: 여러 노드에서 동시 실행.
• Exchange 연산자: 노드 간 데이터 이동.

Distributed Join Strategies

Broadcast Join: 작은 테이블을 모든 노드에 복제.

Small table → broadcast → 각 노드에서 local join

Shuffle Join (Hash Redistribution): 조인 키 해시로 노드에 재분배.

Both tables → 조인 키 해시 → 같은 키가 같은 노드로

Collocated Join: 두 테이블이 이미 같은 키로 파티션되어 있으면 로컬에서 바로.

옵티마이저는 이들의 비용을 비교해 선택한다.

TiDB의 옵티마이저

TiDB는 Cost-Based + Rule-Based 하이브리드:

• Rule-based: 항상 적용되는 변환 (predicate pushdown 등).
• Cost-based: 계획 선택에 cardinality + 비용 모델.
• Statistics: 히스토그램 + Count-Min Sketch for skew 처리.

분산 환경의 추가 복잡도를 극복하기 위해 많은 연구가 진행 중이다.

퀴즈로 복습하기

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

CREATE STATISTICS stat_addr (dependencies) ON city, country FROM addresses;
CREATE STATISTICS stat_addr_ndist (ndistinct) ON city, country FROM addresses;
ANALYZE addresses;

SELECT last_analyze, last_autoanalyze FROM pg_stat_user_tables WHERE relname='mytable';

SELECT attname, n_distinct, most_common_vals, histogram_bounds
FROM pg_stats WHERE tablename = 'mytable';

CREATE STATISTICS s ON col1, col2 FROM mytable;

마치며: 옵티마이저는 협력자다

핵심 정리

1. 옵티마이저는 통계에 의존한다. ANALYZE를 소홀히 하지 마라.
2. Cost 기반이다. 비용 파라미터는 환경에 맞춰 튜닝.
3. Cardinality estimation이 생명이다. 상관 컬럼엔 extended statistics.
4. EXPLAIN을 읽어라. estimated vs actual의 차이가 진단의 시작.
5. 조인 순서는 옵티마이저의 어려운 과제. 테이블 수가 많으면 힌트나 재작성 고려.
6. Cascades가 현대의 표준이지만 PostgreSQL은 자체 DP.
7. 힌트는 최후의 수단. 통계와 구조부터 고쳐라.

옵티마이저와의 협력

옵티마이저를 적이 아니라 협력자로 생각하자:

• 통계를 주어라: ANALYZE, extended statistics.
• 명확한 쿼리를 써라: 옵티마이저가 이해하기 쉬운 SQL.
• 인덱스를 제공하라: 필요한 access path 확보.
• 측정하라: EXPLAIN ANALYZE로 현실을 확인.
• 신뢰하라, 그러나 검증하라: 대부분의 경우 옵티마이저가 맞다.

마지막 교훈

옵티마이저는 수십 년간의 연구와 수만 명의 엔지니어가 쏟아부은 결과다. 그것을 이기려 들지 말자. 대신 옵티마이저가 올바른 결정을 내리게 도와주자. 정확한 통계, 적절한 인덱스, 명료한 쿼리. 이 셋이 모이면 SQL은 마법처럼 빠르게 돈다.

다음에 느린 쿼리를 만나면, 먼저 물어보자:

• "통계는 최신인가?"
• "옵티마이저가 본 cardinality가 실제와 맞는가?"
• "내가 제공한 인덱스와 통계로 최적화할 수 있는 구조인가?"

답이 "그렇다"라면, 옵티마이저는 거의 항상 올바른 답을 준다.

참고 자료

• The Volcano Optimizer Generator (Graefe, 1993)
• The Cascades Framework for Query Optimization (Graefe, 1995)
• Access Path Selection in a Relational Database Management System (Selinger et al., 1979) - System R의 고전
• PostgreSQL Query Planner
• How PostgreSQL's Query Planner Works (Interdb)
• MySQL Query Optimization
• Apache Calcite Documentation
• CockroachDB SQL Optimizer (Cascades-based)
• Database Internals (Alex Petrov), Chapter 12
• Use the Index, Luke! - 인덱스 사용법 완전 가이드