옵티마이저Query Optimizer
SQL 문 하나에 가능한 실행 계획(접근 경로 · 조인 순서 · 조인 방식)을 늘어놓고, 통계로 추정한 행 수와 비용 식으로 가장 싼 계획을 고르는 DBMS 구성 요소다.
1요약
- 옵티마이저는 SQL 처리에서 파서 다음 · 실행기 앞에 놓이며, 1979년 IBM System R 이 보인 비용 기반 최적화(Selinger 1979)가 지금 PostgreSQL 플래너 · Oracle CBO · MySQL 옵티마이저의 뼈대다 — 이 위에서 접근 경로 · 조인 순서 · 조인 방식 선택이 돈다.
- 같은 결과를 내는 계획끼리도 비용이 자릿수로 갈리는데, 실제 데이터로 만든 조인 질의 113개에서 DBMS 들의 카디널리티 추정은 최대 1억 배까지 작게 빗나갔다(Leis 2015 3.2절 · 그림 3).
- 「질의가 갑자기 느려졌다」는 추정 행 수와 실제 행 수가 맞는가로 가른다 — 10배 넘게 어긋나면 통계를, 맞는데 느리면 비용 상수 · 색인 · 질의 꼴을 본다.
2등장 배경
표가 셋이고 표마다 읽는 방법이 셋인 질의만 해도 조인 순서 3! = 6가지에 경로 조합이 곱해져 후보 계획이 백 개를 넘는다. 데이터가 바뀌면 가장 빠른 계획도 바뀌므로 프로그래머가 순서와 색인을 문장에 박아 둘 수 없다. System R 은 그래서 사용자가 저장 방식 · 색인 · 조인 순서를 적지 않고, 옵티마이저가 둘 다 고르게 했다(Selinger 1979 1절).
1979년 IBM San Jose 연구소의 Selinger 등은 비용 = 페이지 읽기 + W × RSI 호출(돌려준 투플 수) 식, 표 행 수 NCARD · 페이지 수 TCARD · 색인 키 수 ICARD 통계, 통계가 없을 때의 선택도 기본값(같음 1/10 · 범위 1/3 · BETWEEN 1/4), 표 부분 집합을 키워 가는 동적 계획법을 냈다(Selinger 1979 4 · 5절 · 표 1). 반면 Oracle 의 규칙 기반 옵티마이저(RBO)는 접근 경로 15개에 순위를 매겨, 15위 전체 스캔이 더 빨라도 색인이 있으면 색인을 골랐다(Oracle9i 8장). Oracle 은 10g Release 1 에서 RBO 지원을 끊고 CBO 를 기본으로 했다(Oracle 10g 업그레이드 안내서 5장).
2015년 Leis 등은 비용 모델보다 카디널리티 추정이 질의 성능을 훨씬 크게 가른다는 것을 113개 질의로 보였다(Leis 2015 초록). 그래서 오늘 옵티마이저를 다루는 일의 중심은 비용 식이 아니라 통계 수집 · 추정 대조 · 계획 고정이다.
3쉽게 이해하기 — 내비게이션의 길 고르기
운전자 김 씨는 차에 타서 「역까지 가 줘」라고만 말한다. 내비 앱은 교통 정보 서버에서 어제 모은 막힘 정보를 받아 고속도로 · 국도 · 골목길마다 걸릴 시간을 더하고, 가장 짧은 고속도로를 고른다. 그런데 오늘 고속도로에 공사가 있어 18분이라던 길이 60분 걸린다. 내비가 정보를 새로 받자 국도 25분이 가장 짧아져 길을 바꾼다.
그림 1 · 김 씨는 목적지만 말하고, 내비가 교통 정보로 길마다 시간을 셈해 가장 짧은 길을 고른다 — SQL 은 결과만 말하고 계획은 옵티마이저가 정한다.
그림 2 · 내비가 틀리는 까닭은 계산이 아니라 어제 정보이고, 옵티마이저도 오래된 통계의 행 수로 셈해 계획을 잘못 고른다 — 정보를 새로 받으면 같은 목적지에 다른 길이 나온다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 「역까지 가 줘」 | SQL 문(선언형) | 얻을 결과만 정하고 읽는 방법은 적지 않는다 |
| 내비 앱 | 옵티마이저 | 후보 계획을 늘어놓고 가장 싼 것을 고른다 |
| 교통 정보 서버 | 통계 카탈로그 | 열마다 자주 나오는 값 · 분포 · 서로 다른 값 수를 담는다 |
| 고속도로 · 국도 · 골목길 | 실행 계획 후보 | 접근 경로 · 조인 순서 · 조인 방식의 조합 |
| 길마다 걸릴 시간 | 비용 추정 | 읽을 페이지 · 행 수에 비용 상수를 곱해 더한다 |
| 고른 길로 달리는 차 | 실행기 | 고른 계획을 그대로 실행한다 |
| 정보 새로 받기 | ANALYZE | 표본을 다시 읽어 통계를 고친다 |
| 늘 다니던 길로만 가기 | 힌트 · 계획 고정 | 사람이 정한 계획을 옵티마이저 판단보다 앞세운다 |
⚠ 비유가 맞지 않는 곳: 내비는 달리는 중에 길을 바꾸지만, 대부분의 DBMS 옵티마이저는 실행 전에 계획을 한 번 정하고 실행 중에는 바꾸지 않는다. 또 내비의 시간은 분 단위 실측이지만 옵티마이저 비용은 「순차 페이지 1회 = 1」로 잡은 상대 값이다.
4구조 — 탐색기 · 추정기 · 비용 모델
옵티마이저는 후보를 늘어놓는 계획 탐색기, 행 수를 추정하는 카디널리티 추정기, 비용을 매기는 비용 모델 셋과 그 입력인 통계로 나뉜다(Leis 2015 그림 1).
그림 3 · 비용 모델이 받는 행 수는 통계에서 추정기가 만든 값이라, 계획의 질은 비용 식보다 통계와 추정의 정확도가 정한다.
| 요소 | 역할 | 값 | 근거 |
|---|---|---|---|
| 계획 탐색기 | 접근 경로 · 조인 순서 · 조인 방식 후보를 열거 | 표 n개 = 순서 n! · 동적 계획법은 부분 집합 2^n개 × 관심 순서 수만 저장 | Selinger 1979 5절 |
| 카디널리티 추정기 | 조건마다 선택도 F 를 구해 행 수 추정 | AND = F1 × F2(독립 가정) · 통계 없음 = 같음 1/10 · 범위 1/3 | Selinger 1979 표 1 |
| 통계 카탈로그 | 열 분포 요약 | MCV · 히스토그램 · n_ | PostgreSQL 14.2.1 |
| 비용 모델 | 경로마다 비용 계산 | seq_ | PostgreSQL 19.7.2 |
| 접근 경로 | 표 하나를 읽는 방법 | 전체 스캔 · 색인 스캔 · 비트맵 힙 스캔 | PostgreSQL 51.5.1 · 14.1.1 |
| 조인 방식 | 두 입력을 잇는 방법 | 중첩 루프 · 병합 조인 · 해시 조인 | PostgreSQL 51.5.1 |
| 힌트 · 계획 고정 | 사람이 후보를 좁히거나 검증된 계획만 허용 | MySQL / · Oracle SQL 계획 기준선 | MySQL 10.9.3 · Oracle 19c 28장 |
탐색기는 표 하나씩 가장 싼 경로를 구한 뒤 표 둘 · 셋으로 부분 집합을 키우며, 결과 정렬이 GROUP BY · ORDER BY · 조인 열에 쓰이는 관심 순서(interesting order) 계획은 더 비싸도 남긴다(Selinger 1979 4 · 5절). 조인 조건이 없는 곱(Cartesian product)은 조인 순서의 가능한 한 뒤로 미룬다(Selinger 1979 5절).
🔑 규칙 기반은 경로의 「종류」로 순위를 매기고, 비용 기반은 그 경로가 읽을 「행 수」로 값을 매긴다.
5동작 — 오래된 통계로 고른 조인 계획
설명용 가정 값 — 주문 표 orders(800,000행 · 10,000페이지 · status 색인)와 고객 표 customers(20,000행 · 250페이지 · id 기본 키)에 PostgreSQL 18 기본 비용 상수를 넣어 원문 식으로 셈했다.
SELECT o.id, c.name
FROM orders o JOIN customers c ON c.id = o.customer_id
WHERE o.status = 'HOLD' AND c.grade = 'VIP';
- 파서가 문장을 질의 트리로 바꾸고, 옵티마이저가 카탈로그에서 두 표의 행 수 · 페이지 수를 읽는다.
- 선택도 — pg_stats 의 MCV 에서 status = 'HOLD' 빈도 0.0025 → 800,000 × 0.0025 = 2,000행, grade = 'VIP' 빈도 0.05 → 1,000행으로 추정한다(PostgreSQL 69.1 MCV 식).
- orders 접근 경로 — 전체 스캔 = 10,000 × 1.0 + 800,000 × 0.01 + 800,000 × 0.0025 = 20,000(PostgreSQL 14.1.1 식). 색인 경로 ≈ 2,000 × (4.0 + 0.005 + 0.01 + 0.0025) = 8,035 이므로 색인을 고른다.
- customers 접근 경로 — 전체 스캔 = 250 + 20,000 × 0.0125 = 500.
- 조인 순서 · 방식 — 조인 행 수 = 2,000 × 1,000 / max(20,000, 20,000) = 100(PostgreSQL 69.1 eqjoinsel 식). 중첩 루프는 orders 행마다 기본 키 탐색이 붙어 약 16,000, customers 1,000행으로 해시 표를 만드는 해시 조인은 약 8,550 이라 해시 조인을 고른다.
- 그 사이 배치가 46,000건을 HOLD 로 바꿨다. 자동 분석 문턱 50 + 0.1 × 800,000 = 80,050건(PostgreSQL 19.10.1)에 못 미쳐 통계는 그대로였고,
EXPLAIN ANALYZE는 색인 경로 노드에 rows=2000 · actual rows=48000 을 보인다 — 실제 비용은 약 48,000 × 4.0175 = 192,840 이다. ANALYZE orders뒤 HOLD 빈도가 0.06 이 되어 추정이 48,000행으로 바뀌고, 색인 경로 192,840 > 전체 스캔 20,000 이므로 전체 스캔 + 해시 조인(조인 행 추정 2,400)으로 다시 고른다.
그림 4 · 통계가 2,000행이라 말해 고른 색인 경로가 실제로는 48,000행을 읽어 비용 약 192,840 이 되고, ANALYZE 뒤 같은 문장이 전체 스캔 20,000 으로 바뀐다.
그림 5 · 색인 경로 비용은 읽을 행 수에 비례하고 전체 스캔은 고정이라 약 4,978행에서 두 선이 만나며, 추정 행 수가 그 앞인지 뒤인지가 접근 경로를 정한다.
⚠ 그림 5 의 색인 경로 식(행 수 × 4.0175)은 행마다 다른 페이지를 무작위로 한 번 읽는다고 본 단순화다. PostgreSQL 은 색인 페이지 · 물리 순서 상관 · 캐시를 셈에 넣고 중간 선택도에서는 비트맵 힙 스캔을 고르므로(14.1.1) 실제 손익분기는 이 값과 다르다.
🔑 같은 SQL · 같은 색인에서 계획이 바뀌었다면 데이터보다 통계가 먼저 바뀐 것이다 — 옵티마이저는 표가 아니라 통계를 읽는다.
6비교 — 규칙 기반 · 비용 기반 · 계획 고정
| 기준 | 규칙 기반(RBO) | 비용 기반(CBO) | 계획 고정(힌트 · 기준선) |
|---|---|---|---|
| 고르는 근거 | 경로 종류의 순위 15개(Oracle9i 8장) | 통계로 추정한 비용 | 사람이 적은 지시 · 검증된 계획 목록 |
| 통계 | 쓰지 않음 | 필수(ANALYZE) | 고정할 때의 통계만 반영 |
| 데이터가 바뀌면 | 계획 그대로 · 전체 스캔이 빨라도 색인 | 통계 갱신 뒤 계획이 바뀜 | 계획 그대로 · 새 계획은 검증 뒤 허용(Oracle 19c 28장) |
| 실패 꼴 | 결과가 큰 조건에도 색인 고집 | 과소 추정으로 중첩 루프 선택(Leis 2015 4.1절) | 분포가 바뀌어도 옛 계획 유지 |
| 현재 | Oracle 10g Release 1 지원 중단 | PostgreSQL · Oracle · MySQL 기본 | Oracle SQL 계획 관리 · MySQL /*+ … */ · PostgreSQL enable_* 설정(19.7.1) |
분석기본은 비용 기반에 두고, 추정 오류가 되풀이되는 소수 문장만 계획 고정으로 묶는다. 기준선은 색인 삭제처럼 되돌릴 수 없는 변경에는 소용없고(Oracle 19c 28장) 고정은 추정 오류를 고치지 않으므로, 통계 갱신 · 확장 통계로 추정을 먼저 바로잡는다.
7실무 진단 — 추정 행 수 어긋남 가르기
분석EXPLAIN ANALYZE 로 노드마다 추정 rows 와 실제 rows 를 대조하고, 가장 아래에서 처음 어긋난 노드의 표 통계부터 본다. 위 노드의 행 수는 아래 노드 추정에 선택도를 곱해 만들므로(Selinger 1979 5절 N 식) 아래 오류가 위로 커지고, 성능은 비용 모델보다 카디널리티 오류가 더 크게 가른다(Leis 2015 초록).
| # | 증상 | 의심 원인 | 단계 | 확인 명령 | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | 대량 변경 뒤 갑자기 느림 | 통계 오래됨 · 자동 분석 문턱 미달 | 통계 | SELECT n_mod_since_analyze, last_autoanalyze FROM pg_stat_all_tables WHERE relname = 'orders' | n_ANALYZE(27.2.19 · 19.10.1) |
| 2 | 두 조건 AND 에서 추정 1행 · 실제 수천 행 | 상관된 열을 독립으로 곱함 | 추정 | CREATE STATISTICS st_rb (dependencies) ON region, branch FROM shops 뒤 EXPLAIN 재비교 | 종속 계수가 1.0 에 가까우면 유지 · 같음 · IN 조건에만 쓰임(14.2.2.1) |
| 3 | 특정 값만 느림 | 값이 MCV 목록 밖 · 분포 치우침 | 통계 | SELECT most_common_vals, most_common_freqs FROM pg_stats WHERE tablename = 'orders' AND attname = 'status' | 값이 목록에 없으면 ALTER TABLE … SET STATISTICS 로 항목 수를 기본 100 보다 늘림(14.2.1) |
| 4 | 준비 문장만 가끔 느림 | 값과 무관한 일반 계획 재사용 | 탐색 | EXPLAIN (GENERIC_PLAN) … 과 값을 넣은 EXPLAIN 비교 | 두 계획이 다르면 plan_cache_mode = force_custom_plan(EXPLAIN · 19.7.4) |
| 5 | 추정은 맞는데 느림 | 비용 상수가 실제 저장 장치 · 캐시와 안 맞음 | 비용 | SHOW random_page_cost | 데이터가 메모리에 다 올라오면 낮춤 검토 · seq_ |
순서는 실제 rows 대조 → 통계 시각 → 분포 · 상관 → 비용 상수다. 통계를 고치기 전에 힌트로 계획을 누르면 다음 데이터 변화에서 같은 오류가 다른 문장에 다시 나온다.
8시험 대비
www.q-net.or.kr시험에서는 규칙 기반과 비용 기반 옵티마이저의 차이를 묻는 비교형, 비용 기반 옵티마이저가 통계에서 실행 계획을 고르는 과정을 묻는 동작 · 절차 설명형이 나올 수 있다. 비교형은 그림 5 의 손익분기로 「규칙은 행 수를 모른다」를 보이고, 절차형은 그림 3 구성도에 선택도 · 비용 식 하나씩을 붙인다.
- 개요 — 정의 · 파서와 실행기 사이의 위치 · Selinger 1979 비용 식(페이지 읽기 + W × RSI 호출)
- 구성 — 그림 3 구성도: 계획 탐색기 · 카디널리티 추정기 · 비용 모델 · 통계 카탈로그
- RBO 와 CBO 비교 — 표: 고르는 근거 · 통계 · 데이터 변화 · 실패 꼴 · 현재(Oracle 10g 지원 중단)
- 계획 선택 절차 — 선택도 F → 행 수 → 경로 비용 수치 예(전체 20,000 대 색인 8,035) + 그림 5 손익분기 그래프
- 통계 부정확 대응 — 추정 · 실제 rows 대조 · ANALYZE · 확장 통계 · 히스토그램 항목 수 · 힌트 · 계획 기준선
- 결론 — 추정 오류가 비용 모델보다 크다는 실험(Leis 2015) · 통계 먼저, 고정은 소수 문장만
꼭 쓸 키워드
비용 기반 최적화규칙 기반 최적화선택도카디널리티히스토그램MCV동적 계획법관심 순서힌트SQL 계획 기준선
차이를 내는 한 가지는 손익분기 숫자다 — 전체 스캔 20,000 과 색인 경로 행당 4.0175 를 놓고 약 4,978행에서 계획이 바뀐다는 계산을 그림 5 와 함께 쓰면 「통계가 왜 계획을 정하는가」가 식으로 보인다.
9오해와 사실
- 오해옵티마이저는 늘 가장 빠른 계획을 고른다.사실옵티마이저는 추정 비용이 가장 낮은 계획을 고르며, Selinger 등도 예측 비용이 절대값으로는 자주 틀리고 순서만 대개 맞는다고 적었다(Selinger 1979 7절).
- 오해색인이 있으면 색인 경로가 늘 이긴다.사실행이 많이 걸리는 조건에서는 전체 스캔이 싸고, PostgreSQL 은 unique1 < 7000 처럼 행의 70% 가 걸리는 조건에서 색인이 있어도 전체 스캔을 고른다(14.1.1).
- 오해ANALYZE 는 표 전체를 읽어 정확한 통계를 만든다.사실ANALYZE 는 무작위 표본을 읽으며(69.1), 갓 갱신한 통계도 근사값이다(14.2).
10핵심 정리
| 구분 | 맡는 일 | 입력 | 출력 | 확인 명령 | 대표 값 |
|---|---|---|---|---|---|
| 계획 탐색기 | 후보 열거 · 최저 비용 선택 | 질의 트리 | 실행 계획 | EXPLAIN | 동적 계획법 · 관심 순서 |
| 카디널리티 추정 | 행 수 추정 | 선택도 · 행 수 | 노드별 rows | EXPLAIN ANALYZE | AND = 곱 · 통계 없음 1/10 |
| 통계 | 열 분포 요약 | 표 표본 | MCV · 히스토그램 · n_ | pg_stats | 항목 기본 100개 |
| 비용 모델 | 경로 비용 계산 | 페이지 · 행 수 | cost | SHOW random_page_cost | 1.0 · 4.0 · 0.01 · 0.0025 |
| 접근 경로 | 표 하나 읽기 | 조건 · 색인 | Seq · Index · Bitmap 스캔 | EXPLAIN | 손익분기 행 수 |
| 조인 방식 | 두 입력 결합 | 두 경로의 결과 | 중첩 루프 · 병합 · 해시 | EXPLAIN | 작은 쪽으로 해시 표 |
| 계획 고정 | 후보 제한 · 검증된 계획만 허용 | 힌트 · 기준선 | 허용 계획 | MySQL SHOW WARNINGS | /*+ … */ · SQL 계획 기준선 |
11참고 문헌
- 먼저 볼 문헌
- ★ Access Path Selection in a Relational Database Management System (Proc. ACM SIGMOD 1979 pp. 23-34) — 비용 식 · 선택도 기본값(표 1) · 관심 순서 · 조인 순서 동적 계획법을 원문으로 볼 때
- ★ How Good Are Query Optimizers, Really? (PVLDB 9(3) pp. 204-215) — 카디널리티 추정 오류가 비용 모델보다 성능을 크게 가른다는 실험을 볼 때
- ★ PostgreSQL 18 Documentation 14.2 Statistics Used by the Planner — MCV · 히스토그램 · 확장 통계(열 상관)를 볼 때
- ★ PostgreSQL 18 Documentation 14.1 Using EXPLAIN — 비용 숫자 읽는 법과 추정 rows · 실제 rows 대조를 볼 때
- 본문 근거
- PostgreSQL 18 Documentation 69.1 Row Estimation Examples — PostgreSQL Global Development Group · 2026-11 ·
www.postgresql.org/docs/current/row-estimation-examples.html· 확인 2026-11-04 - PostgreSQL 18 Documentation 19.7 Query Planning — PostgreSQL Global Development Group · 2026-11 ·
www.postgresql.org/docs/current/runtime-config-query.html· 확인 2026-11-04 - PostgreSQL 18 Documentation 51.5 Planner/Optimizer — PostgreSQL Global Development Group · 2026-11 ·
www.postgresql.org/docs/current/planner-optimizer.html· 확인 2026-11-04 - PostgreSQL 18 Documentation 19.10.1 Automatic Vacuuming — PostgreSQL Global Development Group · 2026-11 ·
www.postgresql.org/docs/current/runtime-config-vacuum.html· 확인 2026-11-04 - PostgreSQL 18 Documentation 27.2.19 pg_stat_all_tables — PostgreSQL Global Development Group · 2026-11 ·
www.postgresql.org/docs/current/monitoring-stats.html· 확인 2026-11-04 - PostgreSQL 18 Documentation EXPLAIN — PostgreSQL Global Development Group · 2026-11 ·
www.postgresql.org/docs/current/sql-explain.html· 확인 2026-11-04 - Oracle9i Database Performance Tuning Guide and Reference Release 2 (9.2) Chapter 8 Using the Rule-Based Optimizer — Oracle · 2002-10 ·
docs.oracle.com/cd/B10500_01/server.920/a96533/rbo.htm· 확인 2026-11-04 - Oracle Database Upgrade Guide 10g Release 1 (10.1) Chapter 5 Compatibility and Interoperability — Oracle · 2003-12 ·
docs.oracle.com/cd/B13789_01/server.101/b10763/compat.htm· 확인 2026-11-04 - Oracle Database 19c SQL Tuning Guide 28 Overview of SQL Plan Management — Oracle · 2026-11 ·
docs.oracle.com/en/database/oracle/oracle-database/19/tgsql/overview-of-sql-plan-management.html· 확인 2026-11-04 - MySQL 8.4 Reference Manual 10.9.3 Optimizer Hints — Oracle · 2026-11 ·
dev.mysql.com/doc/refman/8.4/en/optimizer-hints.html· 확인 2026-11-04