CS학습2026.10.069 min read

Query Optimizer: 통계와 비용 모델로 가장 싸 보이는 실행 계획을 고르는 구성요소

쿼리 옵티마이저(Query Optimizer)는 SQL을 같은 결과를 내는 여러 실행 계획(execution plan) 후보로 바꾼 뒤, 통계 정보와 비용 모델(cost model)로 가장 저렴한 계획을 선택하는 DBMS 구성요소다. 이 글은 PostgreSQL을 기준으로 스캔 방식과 조인 방식의 선택 원리, EXPLAIN으로 계획을 읽는 방법, 통계가 틀

By 송민성

1. 개념

쿼리 옵티마이저(Query Optimizer)는 SQL 문이 "무엇을 원하는가"만 선언하면, "어떻게 가져올 것인가"를 DBMS가 대신 결정하게 해 주는 구성요소다. SQL은 선언형(declarative) 언어이므로 인덱스를 쓸지, 어떤 순서로 테이블을 조인할지는 쿼리에 적혀 있지 않다. 옵티마이저가 이 부분을 채운다.

옵티마이저의 출력물은 실행 계획(execution plan) 이다. 실행 계획은 스캔, 조인, 정렬, 집계 같은 연산자(operator)가 트리 형태로 연결된 구조다.

PostgreSQL의 처리 흐름은 대략 다음과 같다.

파서(Parser): SQL 문자열을 구문 트리로 변환
재작성기(Rewriter): 뷰 전개, 규칙 적용
플래너/옵티마이저(Planner/Optimizer): 후보 계획 생성 및 비용 비교
실행기(Executor): 선택된 계획을 실제로 수행

2. 왜 사용하는가

같은 결과를 내는 실행 방법은 수없이 많고, 비용 차이는 수십~수천 배까지 날 수 있다. 예를 들어 WHERE status = 'PAID' 조건이 전체의 0.1%만 걸러낸다면 인덱스 스캔이 유리하지만, 전체의 60%에 해당한다면 순차 스캔(sequential scan)이 더 빠를 수 있다. 이 판단은 데이터 분포에 따라 달라지므로 개발자가 쿼리마다 손으로 지정하기 어렵다.

옵티마이저가 있으면 데이터가 늘거나 분포가 바뀌어도 SQL을 고치지 않고 계획이 자동으로 적응한다. 대신 개발자는 옵티마이저가 어떤 근거로 판단하는지 알아야, 느린 쿼리가 나왔을 때 원인을 추적할 수 있다.

3. 동작 원리

3.1 비용 기반 최적화(Cost-Based Optimization, CBO)

PostgreSQL은 비용 기반 옵티마이저다. 후보 계획마다 추정 비용을 계산하고 가장 작은 것을 고른다. 비용은 실제 시간(ms)이 아니라 임의 단위이며, 기본 설정값은 다음과 같은 상대 비율을 가진다.

파라미터	기본값	의미
seq_page_cost	1.0	순차적으로 페이지 하나를 읽는 비용
random_page_cost	4.0	임의 접근으로 페이지 하나를 읽는 비용
cpu_tuple_cost	0.01	행 하나를 처리하는 CPU 비용
cpu_index_tuple_cost	0.005	인덱스 항목 하나를 처리하는 비용
cpu_operator_cost	0.0025	연산자/함수 한 번 실행하는 비용

3.2 통계 정보와 선택도(selectivity)

비용을 계산하려면 조건을 만족하는 행 수, 즉 카디널리티(cardinality)를 추정해야 한다. 옵티마이저는 ANALYZE가 수집해 pg_statistic(조회용 뷰는 pg_stats)에 저장한 통계를 사용한다.

n_distinct: 서로 다른 값의 개수(추정)
most_common_vals / most_common_freqs: 최빈값과 그 비율
histogram_bounds: 최빈값을 제외한 값 분포의 히스토그램
correlation: 물리적 저장 순서와 값 순서의 상관관계

선택도(selectivity)는 조건을 통과하는 행의 비율이다. 추정 행 수는 전체 행 수 × 선택도로 계산한다. 여러 조건이 있을 때는 기본적으로 컬럼이 서로 독립이라고 가정해 선택도를 곱한다. 이 가정이 깨지면 추정이 크게 틀어진다.

3.3 후보 계획 탐색

스캔 방식

순차 스캔(Seq Scan): 테이블 전체를 읽는다.
인덱스 스캔(Index Scan): 인덱스로 위치를 찾고 테이블 행을 읽는다.
인덱스 전용 스캔(Index Only Scan): 인덱스만으로 결과를 만든다. 가시성 맵(visibility map)이 최신이어야 효과가 크다.
비트맵 스캔(Bitmap Heap Scan): 인덱스로 대상 페이지 집합을 만든 뒤 페이지 순서대로 읽는다.

조인 방식

중첩 루프 조인(Nested Loop Join): 바깥 행마다 안쪽을 탐색한다. 바깥 행이 적고 안쪽에 인덱스가 있을 때 유리하다.
해시 조인(Hash Join): 한쪽으로 해시 테이블을 만들고 다른 쪽이 탐색한다. 등호(=) 조인에서만 쓸 수 있다.
병합 조인(Merge Join): 양쪽을 정렬된 상태로 병합한다. 이미 정렬되어 있거나 인덱스로 정렬 순서를 얻을 수 있으면 유리하다.

조인 순서 테이블이 n개일 때 가능한 조인 순서는 매우 빠르게 늘어난다. PostgreSQL은 동적 계획법(dynamic programming) 기반으로 탐색하되, 조인 대상 개수가 geqo_threshold(기본값 12) 이상이면 유전 알고리즘 기반의 GEQO로 전환해 탐색 비용을 제한한다. 또한 join_collapse_limit, from_collapse_limit(기본값 모두 8)은 플래너가 한 번에 순서를 재배열하는 범위를 제한한다.

4. 코드 예제

실행 가능한 PostgreSQL 예제다. 주문 테이블을 만들고 분포가 치우친 컬럼에 대해 계획이 어떻게 달라지는지 확인한다.

sql

-- 1) 테이블과 데이터 준비
DROP TABLE IF EXISTS orders;
CREATE TABLE orders (
    id          bigint PRIMARY KEY,
    customer_id int  NOT NULL,
    status      text NOT NULL,
    amount      numeric(10,2) NOT NULL
);

INSERT INTO orders (id, customer_id, status, amount)
SELECT g,
       (random() * 10000)::int,
       CASE WHEN g % 1000 = 0 THEN 'REFUNDED' ELSE 'PAID' END,
       (random() * 1000)::numeric(10,2)
FROM generate_series(1, 1000000) AS g;

CREATE INDEX idx_orders_status ON orders (status);
CREATE INDEX idx_orders_customer ON orders (customer_id);

-- 2) 통계 수집 (옵티마이저가 사용할 정보)
ANALYZE orders;

-- 3) 저장된 통계 확인
SELECT attname, n_distinct, most_common_vals, most_common_freqs
FROM pg_stats
WHERE tablename = 'orders' AND attname = 'status';

-- 4) 드문 값: 인덱스 스캔 계열이 선택될 가능성이 높다
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE status = 'REFUNDED';

-- 5) 흔한 값: 순차 스캔이 선택될 가능성이 높다
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE status = 'PAID';

-- 6) 조인 방식 확인
EXPLAIN (ANALYZE)
SELECT c.customer_id, count(*), sum(o.amount)
FROM orders o
JOIN (SELECT DISTINCT customer_id FROM orders WHERE customer_id < 100) c
  ON c.customer_id = o.customer_id
GROUP BY c.customer_id;

4번 쿼리의 계획은 보통 다음과 같은 형태로 나타난다. 수치는 환경에 따라 다르다.

text

Bitmap Heap Scan on orders  (cost=... rows=1000 width=...) (actual time=... rows=1000 loops=1)
  Recheck Cond: (status = 'REFUNDED'::text)
  ->  Bitmap Index Scan on idx_orders_status  (...)

읽는 요령은 다음과 같다.

cost=시작비용..총비용: 추정 비용
rows: 추정 행 수. ANALYZE 옵션을 쓰면 actual ... rows=에 실제 행 수가 함께 나온다.
추정 rows와 실제 rows의 차이가 크면 통계 문제를 의심한다.

통계가 부족한 컬럼의 정밀도를 높이고 컬럼 간 상관관계를 알려주는 예제다.

sql

-- 특정 컬럼의 통계 목표치 상향 (기본 default_statistics_target = 100)
ALTER TABLE orders ALTER COLUMN customer_id SET STATISTICS 500;

-- 컬럼 간 의존성 통계 (PostgreSQL 10+)
CREATE STATISTICS orders_cust_status (dependencies)
ON customer_id, status FROM orders;

ANALYZE orders;

옵티마이저의 선택을 실험할 때는 세션 단위로 특정 방식을 꺼볼 수 있다. 운영 설정으로 쓰는 용도가 아니라 진단용이다.

sql

SET enable_seqscan = off;
EXPLAIN SELECT * FROM orders WHERE status = 'PAID';
RESET enable_seqscan;

5. 시간 복잡도 또는 성능 특성

옵티마이저 자체의 비용과 선택된 연산자의 비용을 나누어 봐야 한다.

연산자별 특성 (N, M은 각 입력의 행 수)

연산	대략적 비용	비고
순차 스캔	O(N)	테이블 전체 읽기
B-tree 인덱스 탐색	O(log N)	이후 결과 행 수만큼 추가 접근
중첩 루프 조인	인덱스 없을 때 O(N × M), 안쪽 인덱스 탐색 시 O(N × log M)	바깥 행 수가 핵심
해시 조인	평균 O(N + M)	해시 테이블이 work_mem을 넘으면 디스크 배치 사용
병합 조인	병합 자체는 O(N + M)	정렬이 필요하면 O(N log N + M log M) 추가

플래닝 비용 조인 순서 탐색은 테이블 수가 늘수록 급격히 비싸진다. 그래서 join_collapse_limit과 GEQO 같은 제한 장치가 있다. 단순한 OLTP 쿼리에서는 플래닝 시간이 무시할 만하지만, 조인이 많은 쿼리에서는 플래닝 시간 자체가 병목이 될 수 있다. EXPLAIN (ANALYZE) 출력 끝의 Planning Time과 Execution Time으로 구분해 확인한다.

추정 오차의 영향 추정 행 수가 실제와 크게 다르면 비용이 낮다고 믿은 계획이 실제로는 훨씬 느릴 수 있다. 예를 들어 1건으로 추정해 중첩 루프를 골랐는데 실제로 수십만 건이면, 안쪽 탐색이 수십만 번 반복된다.

6. 실무 사용 사례

느린 쿼리 진단: EXPLAIN (ANALYZE, BUFFERS)로 추정 행 수와 실제 행 수를 비교하고, 오차가 가장 먼저 커지는 노드를 찾는다. 그 노드의 조건이나 통계가 원인인 경우가 많다.
인덱스 설계 검증: 인덱스를 만들었는데 쓰이지 않는다면 선택도가 낮거나, 컬럼에 함수가 적용됐거나(WHERE lower(email) = ...), 타입이 맞지 않는 경우를 확인한다. 함수 조건에는 표현식 인덱스(expression index)로 대응한다.
대량 적재 후 통계 갱신: 배치로 데이터를 대량 적재한 직후에는 autovacuum의 자동 ANALYZE가 도달하기 전에 쿼리가 실행될 수 있다. 적재 후 명시적으로 ANALYZE를 실행한다.
페이징 쿼리 점검: ORDER BY ... LIMIT은 옵티마이저가 정렬 순서를 제공하는 인덱스를 선택하면 빨라지고, 그렇지 않으면 전체 정렬이 일어난다. 계획에서 Sort 노드의 유무를 확인한다.
SSD 환경 튜닝: random_page_cost 기본값 4.0은 HDD를 가정한 값에 가깝다. SSD 환경에서는 이 값을 낮추는 경우가 많다. 다만 변경 전후로 주요 쿼리의 계획을 비교해야 한다.

7. 주의할 점

EXPLAIN과 EXPLAIN ANALYZE의 차이: EXPLAIN은 계획만 보여주고 실행하지 않는다. EXPLAIN ANALYZE는 쿼리를 실제로 실행한다. INSERT, UPDATE, DELETE에 쓰면 데이터가 실제로 변경되므로 트랜잭션으로 감싸고 롤백한다.

sql

BEGIN;
EXPLAIN (ANALYZE) UPDATE orders SET amount = amount + 1 WHERE customer_id = 1;
ROLLBACK;

통계가 오래되면 계획이 나빠진다. 데이터 분포가 크게 바뀌었다면 ANALYZE를 먼저 의심한다.
컬럼 독립 가정의 한계: city = 'Seoul' AND zipcode = '04524'처럼 강하게 연관된 조건은 선택도를 과도하게 낮게 추정한다. 확장 통계(CREATE STATISTICS)로 완화할 수 있다.
**enable_* 설정은 진단용**: enable_seqscan = off는 순차 스캔을 금지하는 것이 아니라 비용을 매우 크게 만들어 회피하게 하는 방식이다. 운영 환경에 전역으로 적용하면 다른 쿼리가 나빠질 수 있다.
플랜 캐시 주의: 프리페어드 스테이트먼트(prepared statement)는 여러 번 실행 후 파라미터와 무관한 범용 계획(generic plan)을 쓸 수 있다. 값에 따라 분포 차이가 크면 특정 파라미터에서 느려질 수 있으며, plan_cache_mode 설정으로 조절한다.
비용 수치를 시간으로 읽지 않는다. cost는 상대 비교용 단위이며 ms가 아니다.

8. 핵심 정리

옵티마이저는 SQL을 실행 계획으로 바꾸는 구성요소이며, PostgreSQL은 비용 기반으로 후보 계획 중 추정 비용이 가장 낮은 것을 고른다.
비용 추정의 핵심 입력은 ANALYZE가 수집한 통계와 선택도다. 통계가 틀리면 계획도 틀린다.
스캔 방식(순차, 인덱스, 비트맵)과 조인 방식(중첩 루프, 해시, 병합), 조인 순서가 선택 대상이다.
튜닝은 EXPLAIN (ANALYZE, BUFFERS)에서 추정 행 수와 실제 행 수의 차이를 찾는 것에서 시작한다.
해결 수단은 순서대로 통계 갱신, 통계 목표치 조정이나 확장 통계, 인덱스 설계, 쿼리 재작성이며, enable_* 설정은 진단용으로만 쓴다.