들어가며: 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 처리.

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

퀴즈로 복습하기

**A.** **통계(statistics)**, 특히 **정확한 cardinality 추정**이다. 옵티마이저의 모든 비용 계산은 각 단계에서 나오는 예상 행 수에 기반한다. 추정이 틀리면:

1. 선택한 access method가 부적절 (큰 결과에 인덱스 스캔, 작은 결과에 full scan).

2. 조인 알고리즘 잘못 선택 (nested loop이 최악).

3. 조인 순서 잘못 → 중간 결과 폭발.

통계가 없거나 오래되면 이런 일이 반드시 일어난다. 그래서 데이터베이스 튜닝의 첫 번째 단계는 항상 **"ANALYZE를 실행했는가?"** 를 확인하는 것이다. 대량 INSERT/UPDATE 후, 새 인덱스 추가 후엔 수동 ANALYZE가 필수다.

**A.** 옵티마이저가 **인덱스 스캔을 더 선호**하게 된다. 이유:

- Index Scan은 heap에 random I/O를 발생시킨다.

- 기본값 4.0은 random I/O가 sequential의 4배 느리다는 가정 — HDD 시대 유산.

- 현대 SSD/NVMe에선 차이가 거의 없다 (1.1이 더 현실적).

이 변경 후 변화:

1. 더 많은 쿼리가 인덱스 스캔으로 전환.

2. 선택도가 낮은 (적은 행 반환) 조건에서 full scan 회피.

3. 일반적으로 전체 성능 향상, 특히 random I/O가 저렴한 환경에서.

**주의**: 이 파라미터는 옵티마이저의 **추정**을 바꿀 뿐, 실제 성능을 직접 바꾸진 않는다. 환경에 맞지 않으면 잘못된 계획으로 이어질 수 있다. SSD에선 1.1~1.5, HDD에선 4.0 유지, 네트워크 스토리지는 그 중간이 적절하다.

**A.** **문제**: 옵티마이저는 `P(A and B) = P(A) × P(B)`로 가정한다. 두 조건이 독립이면 맞지만, 실제론 **상관관계**가 있는 경우가 많다:

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

- 추정: 10% × 20% = 2%

- 실제: 10% (Seoul은 Korea에만)

- **5배 과소 추정** → 잘못된 계획.

**PostgreSQL 해결책 (10+)**: **Extended Statistics**

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

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

ANALYZE addresses;

세 가지 타입:

1. **dependencies**: 함수적 의존성 감지 (city → country).

2. **ndistinct**: 여러 컬럼의 고유 조합 수.

3. **MCV (multivariate)**: 여러 컬럼의 가장 흔한 값 조합.

이 정보로 옵티마이저는 상관관계를 고려할 수 있다. 매우 효과적이지만 추가 통계 유지 비용이 있으므로 **문제가 되는 쿼리에 선택적으로** 적용.

**A.**

**Volcano (1993)**:

- Top-down 탐색.

- Exhaustive한 계획 생성.

- Memoization 있음.

- 변환 규칙 기반.

- **한계**: 많은 조인에서 탐색 공간 폭발, property 처리 부족.

**Cascades (1995)**:

- Volcano의 개선판 (같은 저자).

- **Memo 데이터 구조**로 동등한 식들을 그룹화.

- **Physical properties 전파** (ordering, distribution).

- **Branch-and-bound pruning**.

- **Enforcer**: 필요한 속성을 제공하기 위해 Sort, Exchange 추가.

**비유**: Volcano가 "모든 계획을 만들고 골라보자"라면, Cascades는 "그룹 단위로 비교하고, 필요한 속성만 요구하며, 명백히 나쁜 건 일찍 버리자".

**사용처**: SQL Server, CockroachDB, Apache Calcite (Cascades 기반). PostgreSQL은 둘 다 아닌 자체 DP 기반. Volcano는 연구/강의에 주로 등장하고, Cascades가 실전의 표준이 되었다.

**A.** 이는 옵티마이저가 **잘못된 추정**을 했다는 신호다. 진단 순서:

**1. ANALYZE 실행 여부 확인**

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

너무 오래됐으면 수동 실행: `ANALYZE mytable;`

**2. 통계 품질 확인**

SELECT attname, n_distinct, most_common_vals, histogram_bounds

FROM pg_stats WHERE tablename = 'mytable';

- `n_distinct`가 이상하면 샘플 크기 부족 → `ALTER TABLE ... SET STATISTICS 1000`.

- MCV가 비어 있으면 데이터가 균등 분포가 아닐 수 있음.

**3. 상관 컬럼 의심**

여러 WHERE 조건이 있는데 모두 함께 나타나는 경우가 있다면 extended statistics:

CREATE STATISTICS s ON col1, col2 FROM mytable;

**4. 서브쿼리/함수 호출**

`WHERE col = get_default()` 같은 함수 호출은 선택도를 추정하지 못한다.

**5. 조인 결과 오추정**

중간 조인 결과가 이상하면 조인 참여 컬럼의 `n_distinct`가 부정확할 가능성.

**6. 힌트/재작성**

위 단계가 모두 실패하면 pg_hint_plan 확장으로 특정 계획 강제, 또는 쿼리 재작성 (예: CTE 사용, 서브쿼리 인라인).

핵심은 "통계 → 데이터 특성 → 쿼리 구조" 순서로 접근하는 것이다. 대부분의 문제는 ANALYZE 한 번으로 해결된다.

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

핵심 정리

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)](https://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/Papers/volcano-graefe.pdf)

- [The Cascades Framework for Query Optimization (Graefe, 1995)](https://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/Papers/Cascades-graefe.pdf)

- [Access Path Selection in a Relational Database Management System (Selinger et al., 1979)](https://www2.cs.duke.edu/courses/compsci516/cps216/spring03/papers/selinger-etal-1979.pdf) - System R의 고전

- [PostgreSQL Query Planner](https://www.postgresql.org/docs/current/runtime-config-query.html)

- [How PostgreSQL's Query Planner Works (Interdb)](https://www.interdb.jp/pg/pgsql03.html)

- [MySQL Query Optimization](https://dev.mysql.com/doc/refman/8.0/en/optimization.html)

- [Apache Calcite Documentation](https://calcite.apache.org/docs/)

- [CockroachDB SQL Optimizer (Cascades-based)](https://www.cockroachlabs.com/blog/building-a-sql-optimizer/)

- [Database Internals (Alex Petrov), Chapter 12](https://www.databass.dev/)

- [Use the Index, Luke!](https://use-the-index-luke.com/) - 인덱스 사용법 완전 가이드