(KO) PostgreSQL 비용 모델 — 페이지/CPU 비용과 경로 비교

학술적 배경
DBMS 공통 설계 패턴
PostgreSQL의 구현
소스 코드 가이드
소스 검증 (2026-06-05 기준)
PostgreSQL 너머 — 비교 설계와 연구 프론티어
출처

학술적 배경

관계형 쿼리는 일반적으로 동등한 물리적 실행 계획을 천문학적 수로 가진다. 각 테이블은 순차 스캔이나 여러 인덱스 스캔으로 접근할 수 있고, 각 릴레이션 쌍은 중첩 루프·병합·해시 중 하나로 조인할 수 있으며, 조인 순서 자체가 순열 문제다. 옵티마이저는 어느 것이 가장 빠른지 실행해 볼 수 없다. 따라서 **비용 모델(cost model)**이 필요하다. 비용 모델은 후보 물리 연산자 트리를 받아 실행 비용을 추정하는 숫자를 반환하는 함수다. “계획 A가 계획 B보다 낫나?”라는 질문을 “cost(A) < cost(B)인가?”로 환원해준다. 비용 모델 덕분에 최적화는 측정 불가능한 공간에 대한 탐색이 아니라 스칼라값 공간에 대한 탐색이 된다.

정석적인 정식화는 Selinger et al.의 Access Path Selection in a Relational Database Management System (SIGMOD 1979 — System R 옵티마이저 논문, dbms-papers/systemr-optimizer.md 참고)이다. System R은 이후 모든 비용 기반 옵티마이저가 계승한 세 가지 아이디어를 도입했다.

I/O와 CPU를 결합한 비용 지표. Selinger의 비용은 COST = PAGE FETCHES + W * (RSI calls)다. 페이지 페치(I/O 항)에 “RSI 호출(RSI calls)” 횟수에 가중치 W를 곱한 값(CPU 항)을 더한다. 핵심 통찰은 계획 비용이 단일 차원이 아니라는 점이다. 페이지를 덜 건드리지만 튜플당 조건을 더 많이 평가하는 계획이 유리할 수도, 불리할 수도 있다. 가중치 W가 두 항의 균형을 결정한다. PostgreSQL의 다섯 가지 비용 GUC는 이 아이디어를 일반화한 것이다. 순차 대 랜덤 페이지 페치, 그리고 튜플·인덱스 튜플·연산자 CPU에 별도의 가중치를 부여한다.
통계 기반 선택도(selectivity). 계획 비용을 구하려면 연산자 간에 흐르는 행 수를 알아야 하고, 그것은 조건의 선택도에 달려 있다. System R은 카탈로그 통계(카디널리티, 인덱스 값 개수)를 보유하고 이로부터 *선택도 인수(selectivity factor)*를 도출했다. 통계가 없는 경우 하드코딩된 추측값(예: 비인덱스 컬럼 동등 조건은 1/10)을 사용했다. 행 수 추정과 비용 추정은 따라서 서로 연결된 두 하위 시스템이다. 선택도 기계가 행 수를 비용 기계에 공급한다.
동적 프로그래밍 조인 열거의 가지치기 키로서의 비용. System R은 릴레이션 부분집합별로 최저 비용 계획만 유지하면서 조인 순서를 상향식으로 구성했다. 단, 나중의 정렬 단계를 절약할 수 있는 계획은 “흥미로운 정렬 순서(interesting order)” 예외로 남겼다. 비용이 이 가지치기의 비교 키다. 같은 릴레이션에서 같은 출력 순서를 내면서 더 비싼 계획은 버릴 수 있다.

이 문서는 비용 모델 자체에 집중한다. 물리 연산자를 숫자로 매핑하는 함수다. 행 수를 공급하는 선택도 기계는 postgres-extended-statistics.md가, 비용을 가지치기 키로 소비하는 조인 열거 탐색은 postgres-join-ordering.md가, 비용 계산 대상인 후보 Path 객체 생성은 postgres-path-generation.md가 담당한다. 이 문서는 세 문서의 중심에 있는 채점 함수만 다룬다.

교과서 정식화에서 충분히 강조하지 않지만 모든 실제 엔진이 직면하는 미묘한 점이 있다. 비용은 단일 숫자가 아니라 (startup, total) 쌍이다. 첫 번째 행을 생성하는 비용과 모든 행을 생성하는 비용은 다르다. LIMIT가 있을 때, 그리고 파이프라인 부모 노드가 자식 노드가 언제 처음 결과를 내는지 신경 쓸 때 이 차이가 중요하다. 정렬은 전체 입력을 소비하기 전에 아무것도 출력할 수 없으므로 startup이 높다. 반면 순차 스캔은 첫 번째 튜플을 거의 즉시 출력할 수 있어 startup이 0에 가깝다. 총 비용만 채점하는 옵티마이저는 LIMIT 1 쿼리를 체계적으로 잘못 판단한다. PostgreSQL은 모든 경로에 두 숫자를 모두 보유한다.

DBMS 공통 설계 패턴

Selinger는 골격을 제시했다. 비용 지표, 통계 기반 행 수, 가지치기 키로서의 비용. 이 절에서는 프로덕션 비용 모델이 그 위에 쌓는 엔지니어링 관례를 정리한다. 1979년 논문이 암묵적으로 남겨둔 패턴들이다. 다음 절 ## PostgreSQL의 구현에서 다루는 PostgreSQL의 구체적인 설정값은 이 공유 설계 공간의 한 점이다.

추상적 비용 단위, 밀리초가 아니라

비용 모델은 실제 벽시계 시간을 예측하지 않는다. 시간과 단조적으로(monotonically) 대응하는 무차원 점수를 예측한다. 관례는 하나의 연산을 단위로 삼는 것이다. 거의 항상 순차 페이지 페치 한 번을 1.0으로 설정하고 나머지를 모두 그 비율로 표현한다. 랜덤 페이지 페치는 순차 페치보다 몇 배 비싸고, 튜플 하나를 처리하는 CPU 비용은 페이지 페치 비용의 작은 분수다. 이 비율은 설정값이지 자연 상수가 아니다. 하드웨어에 따라 달라진다(SSD에서 랜덤 페치는 회전 디스크보다 훨씬 저렴하다). 모델이 보장해야 하는 것은 계획들의 상대적 순위가 맞는 것뿐이다.

두 가지 비용 항: 페이지 I/O와 CPU

Selinger를 따라, 모든 연산자의 비용은 페이지 접근 항(읽고 쓰는 페이지 수 × 페이지당 비용)과 CPU 항(처리한 튜플 수 × 튜플당 비용 + 평가한 조건 연산자 수 × 연산자당 비용)으로 분해된다. 순차 스캔은 페이지 I/O 지배형이고, 메모리 내 정렬은 CPU 지배형이며, 외부 정렬은 두 항을 모두 부담한다. 항을 분리해두는 덕분에 하드웨어 유형이 달라질 때 GUC 하나만 조정해도 모델 전체의 비중을 바꿀 수 있다.

Startup 비용 대 Total 비용

모든 연산자는 startup_cost(첫 출력 튜플 전까지의 작업 비용)와 total_cost(startup에 모든 튜플을 생성하는 실행 비용을 더한 값)로 채점된다. 이 분리는 실질적인 의미가 있다. total_cost에서 지는 경로도 LIMIT 아래에서는 최선일 수 있다. 실행 비용의 일부만 실제로 지불하기 때문이다. 경로 보관 로직은 두 값을 부분 순서로 취급해야 한다. 경로는 두 축 모두(와 출력 순서, 매개변수화)에서 열등할 때만 지배된다. 그래서 옵티마이저는 릴레이션당 단일 최저 비용 경로가 아니라 여러 경로를 유지한다.

I/O 항의 캐싱 효과

인덱스 스캔이 k개의 튜플을 가져올 때 단순한 페이지 수는 k번의 힙 페이지 페치다. 그러나 테이블이 메모리보다 크면 같은 페이지를 다시 읽을 수 있고, 메모리보다 작으면 페이지가 캐시에 남는다. 실제 비용 모델은 버퍼 모델을 통합한다. 가장 고전적인 것이 Mackert-Lohman의 유한-LRU 공식이다. 가용 캐시 대비 워킹셋 크기를 감안해 실제로 읽게 될 고유 페이지 수를 추정한다. 이를 무시하면 캐시에 올라있는 테이블의 선택적 인덱스 스캔 비용을 체계적으로 과대 계산한다.

인덱스 순서와 힙 순서 간 상관관계

인덱스 스캔이 인덱스 키 순서로 TID를 반환하면 힙 페이지도 그 순서로 접근하게 된다. 힙이 같은 방식으로 물리적으로 정렬되어 있다면(상관관계 높음 — 예: 직후에 CLUSTER 수행) 힙 페치 대부분은 순차로 이루어져 저렴하다. 인덱스 순서와 힙 순서가 무관하다면(상관관계 0) 힙 페치는 모두 랜덤 접근이 된다. 두 경우에 같은 페이지당 비용을 부과하면 기본값 기준 4배 차이로 인덱스 스캔 가격을 잘못 책정한다. 관례는 두 경계를 모두 계산하고 상관관계의 함수로 보간하는 것이다.

탐색 가지치기를 위한 2단계 조인 비용 계산

조인 비용 추정은 비용이 크다. 조인 조건을 검사하고, 선택도 통계를 조회하고, 경우에 따라 부분 정렬 비용도 계산해야 한다. 그런데 조인 열거 탐색은 후보 조인을 대량으로 제안하고 대부분은 가지치기된다. 관례는 2단계 분할이다. 값싼 initial_cost_* 패스는 입력 경로만으로 비용의 하한값을 계산하고(조건 검사 없음), 하한값 비교에서 살아남은 경로만 비싼 final_cost_* 패스를 받는다. 이 구조가 옵티마이저 자체의 실행 시간을 제한한다.

이론 ↔ PostgreSQL 매핑

다음 절에서 PostgreSQL 심볼 이름을 만나기 전에, 각 개념이 어떤 종류의 것인지 미리 파악해두면 좋다.

이론 / 관례	PostgreSQL 이름
페이지 페치 단위 = 1.0	`seq_page_cost` GUC (`DEFAULT_SEQ_PAGE_COST` = 1.0)
순차 대비 랜덤 페치 배수	`random_page_cost` (기본값 4.0)
튜플당 CPU 가중치 (`W`)	`cpu_tuple_cost` (0.01)
인덱스 튜플당 CPU 가중치	`cpu_index_tuple_cost` (0.005)
연산자당 CPU 가중치	`cpu_operator_cost` (0.0025)
(startup, total) 비용 쌍	`Path.startup_cost`, `Path.total_cost`
순차 스캔 비용	`cost_seqscan`
인덱스 스캔 비용	`cost_index` (+ AM의 `amcostestimate`)
Mackert-Lohman 버퍼 모델	`index_pages_fetched`
상관관계 보간	`cost_index` 내 `csquared` 항
정렬 비용	`cost_sort` → `cost_tuplesort`
중첩 루프 2단계 비용	`initial_cost_nestloop` / `final_cost_nestloop`
해시 조인 2단계 비용	`initial_cost_hashjoin` / `final_cost_hashjoin`
`pg_proc.procost`에서 오는 조건 CPU 요금	`cost_qual_eval` → `add_function_cost`
행 수 이음새 (선택도)	`set_baserel_size_estimates` → `clauselist_selectivity`
행 추정 건전성 클램프	`clamp_row_est`

PostgreSQL의 구현

PostgreSQL 비용 모델은 거의 전부 src/backend/optimizer/path/costsize.c 한 파일에 들어 있다. Selinger 모델을 다섯 가지 설계 결정으로 구체화한 형태다.

다섯 개의 조정 가능한 비용 파라미터. 모두 전역 double 값이며 기본값이 문서화되어 있고, I/O와 CPU 항을 순차 페이지 페치 하나에 대한 비율로 표현한다.
모든 Path는 (startup_cost, total_cost)를 보유한다. PG 17부터 기존의 disable_cost 가산 방식을 대체하는 disabled_nodes 카운트와 rows 추정값도 함께 가진다. cost_* 함수들이 이 세 필드를 채운다.
물리 연산자별 cost_<node> 함수. 각 함수는 이미 비용이 계산된 자식 경로를 받아 자신의 페이지와 CPU 항을 더해 이 노드의 비용을 생성한다.
조인에 대한 2단계 분할 (initial_cost_* / final_cost_*). 조인 탐색이 값비싼 조건 검사 전에 저렴한 하한값으로 가지치기할 수 있다.
선택도 기계와의 깔끔한 이음새. 비용 함수는 rows를 이미 추정된 입력으로 받는다(set_baserel_size_estimates 및 관련 함수에서 공급, 내부적으로 clauselist_selectivity를 호출). 조건 복잡도는 cost_qual_eval로 튜플당 CPU 요금으로 변환된다.

다섯 가지 비용 파라미터

파일 헤더에 파라미터와 그 의미가 문서화되어 있다. 변수는 cost.h의 DEFAULT_* 매크로로 초기화된 단순 전역 변수다.

// cost parameter globals — src/backend/optimizer/path/costsize.c
double    seq_page_cost = DEFAULT_SEQ_PAGE_COST;        /* 1.0  */
double    random_page_cost = DEFAULT_RANDOM_PAGE_COST;  /* 4.0  */
double    cpu_tuple_cost = DEFAULT_CPU_TUPLE_COST;      /* 0.01 */
double    cpu_index_tuple_cost = DEFAULT_CPU_INDEX_TUPLE_COST; /* 0.005 */
double    cpu_operator_cost = DEFAULT_CPU_OPERATOR_COST;       /* 0.0025 */
double    parallel_tuple_cost = DEFAULT_PARALLEL_TUPLE_COST;   /* 0.1  */
double    parallel_setup_cost = DEFAULT_PARALLEL_SETUP_COST;   /* 1000 */

int      effective_cache_size = DEFAULT_EFFECTIVE_CACHE_SIZE; /* 524288 pages */

기본값은 상당한 버퍼 캐시를 갖춘 회전 디스크 하드웨어 모델을 전제로 한다. 헤더 주석은 관계를 명시적으로 서술한다. seq_page_cost는 보통 random_page_cost보다 상당히 작다. 순차 읽기는 미리 읽기(readahead)와 탐색 회피 덕분에 이득을 보기 때문이다. CPU 가중치는 페이지 페치보다 두 자릿수 작다. 튜플 처리는 디스크에서 페이지를 가져오는 것보다 훨씬 저렴하다. 그래서 대부분의 스캔에서 I/O가 비용을 지배한다. effective_cache_size는 메모리 할당이 아니다. 비용 모델이 쿼리에 사용 가능한 OS+공유 버퍼 캐시 양을 추정하는 값으로, index_pages_fetched에서만 사용된다. 일곱 값 모두 세션별 설정이 가능하고, seq_page_cost/random_page_cost는 테이블스페이스별로도 설정 가능하다(get_tablespace_page_costs로 조회).

enable_* GUC(enable_seqscan, enable_indexscan 등)는 이런 의미의 파라미터가 아니다. 하나를 off로 설정해도 경로가 제거되지 않는다. 대신 해당 경로의 disabled_nodes 카운트에 1을 더한다. 비활성화된 경로는 활성화된 대안이 없을 때만 선택된다. 거대한 disable_cost (1e10)를 total에 더하던 기존 방식을 대체한 것이다.

flowchart TB
  subgraph PARAMS["다섯 가지 비용 파라미터 (순차 페이지 페치 1회 대비 비율)"]
    SPC["seq_page_cost = 1.0<br/>(단위)"]
    RPC["random_page_cost = 4.0<br/>(탐색 페널티)"]
    CTC["cpu_tuple_cost = 0.01"]
    CITC["cpu_index_tuple_cost = 0.005"]
    COC["cpu_operator_cost = 0.0025"]
  end
  subgraph TERMS["모든 연산자의 비용"]
    IO["페이지 접근 항<br/>페이지 수 x {seq|random}_page_cost"]
    CPU["CPU 항<br/>튜플 수 x cpu_tuple_cost<br/>+ 연산자 수 x cpu_operator_cost"]
  end
  SPC --> IO
  RPC --> IO
  CTC --> CPU
  CITC --> CPU
  COC --> CPU
  IO --> PAIR["Path.total_cost = startup_cost + run_cost"]
  CPU --> PAIR

그림 1 — 다섯 파라미터와 두 비용 항. 모든 비용 함수는 작업을 페이지 접근 항(페이지 비용 파라미터로 가중, 테이블스페이스별 설정 가능)과 CPU 항(튜플당·연산자당 파라미터로 가중)으로 분해하고 경로의 startup/total 쌍으로 합산한다.

startup_cost 대 total_cost, 그리고 행 수 추정

모든 Path에서 비용 모델이 출력하는 필드는 세 가지다. startup_cost(첫 튜플 이전 비용), total_cost(경로를 모두 소진하는 비용), rows(추정 출력 카디널리티). 각 cost_* 함수가 따르는 관례는 startup_cost와 run_cost를 누적한 뒤 total_cost = startup_cost + run_cost로 설정하는 것이다. 첫 튜플이 나오기 전에 반드시 치러야 하는 비용(해시 테이블 구축, 전체 입력 정렬, 일회성 startup 조건 평가)은 startup_cost에 들어가고, 출력 튜플당 비용은 run_cost에 들어간다. add_path의 경로 보관 로직(postgres-path-generation.md 참고)은 이 쌍을 부분 순서로 사용한다. startup, total, 행 수와 매개변수화의 관계, pathkeys 모두에서 열등하지 않을 때만 지배된다. 그래서 startup이 높은 정렬 경로와 startup이 낮은 비정렬 경로가 공존할 수 있다.

rows 필드는 릴레이션의 사전 계산된 추정값(baserel->rows)에서, 또는 매개변수화 경로의 경우 param_info->ppi_rows에서 경로로 주입된다. 비용 함수 스스로는 기본 행 수의 선택도 추정을 실행하지 않는다. 그 작업은 이미 set_baserel_size_estimates에서 완료되었다.

cost_seqscan — 가장 단순한 사례

cost_seqscan은 페이지 + CPU 분해를 가장 명확하게 보여주는 사례다. 함수 본문 전체는 다음과 같다.

// cost_seqscan — src/backend/optimizer/path/costsize.c (condensed)
if (param_info)
    path->rows = param_info->ppi_rows;
else
    path->rows = baserel->rows;

/* fetch estimated page cost for tablespace containing table */
get_tablespace_page_costs(baserel->reltablespace, NULL, &spc_seq_page_cost);

/* disk costs */
disk_run_cost = spc_seq_page_cost * baserel->pages;

/* CPU costs */
get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
startup_cost += qpqual_cost.startup;
cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
cpu_run_cost = cpu_per_tuple * baserel->tuples;

/* tlist eval costs are paid per output row, not per tuple scanned */
startup_cost += path->pathtarget->cost.startup;
cpu_run_cost += path->pathtarget->cost.per_tuple * path->rows;

path->disabled_nodes = enable_seqscan ? 0 : 1;
path->startup_cost = startup_cost;
path->total_cost = startup_cost + cpu_run_cost + disk_run_cost;

Selinger 공식을 구체화한 코드로 읽으면 된다. 페이지 항은 spc_seq_page_cost * baserel->pages다. 선택도와 무관하게 모든 페이지를 읽는다. 순차 스캔은 페이지를 건너뛸 수 없기 때문이다. CPU 항은 (cpu_tuple_cost + qual_per_tuple) * baserel->tuples다. 필터 후 rows가 아니라 모든 튜플을 검사한다(tuples 사용에 주목). 각 튜플은 기본 튜플 비용에 WHERE 절 평가의 튜플당 비용을 더한 것을 소비한다(get_restriction_qual_cost에서 반환, 앞서 cost_qual_eval이 채운 baserel->baserestrictcost를 활용). 두 가지 세부 사항이 있다. (1) 조건의 startup 구성요소(예: 일회성 array 해시 구축)는 startup_cost에 들어가고 튜플당 루프에는 들어가지 않는다. (2) 대상 목록(target-list) 평가 비용은 출력 행(path->rows)당 부과된다. 프로젝션은 살아남은 튜플에 대해서만 발생하기 때문이다. 순차 스캔의 startup 비용은 사실상 0이다. 첫 페이지가 읽히는 즉시 첫 튜플을 출력할 수 있다.

cost_index — 위임, Mackert-Lohman, 상관관계

cost_index는 스캔 비용 함수 중 가장 풍부하며, ## DBMS 공통 설계 패턴의 모든 관례를 실제로 구현한다. 인덱스 내부 비용을 직접 계산하지 않고 접근 방법(AM)의 amcostestimate 콜백(B-트리의 경우 btcostestimate; postgres-index-am.md / postgres-nbtree.md 참고)에 위임한다. 이 콜백이 인덱스 탐색 비용, 선택도(매칭되는 힙 튜플 비율), 상관관계(인덱스 순서와 힙 순서 간 상관관계)를 반환한다.

// cost_index — src/backend/optimizer/path/costsize.c (condensed)
amcostestimate = (amcostestimate_function) index->amcostestimate;
amcostestimate(root, path, loop_count,
               &indexStartupCost, &indexTotalCost,
               &indexSelectivity, &indexCorrelation, &index_pages);

/* all costs for touching index itself included here */
startup_cost += indexStartupCost;
run_cost += indexTotalCost - indexStartupCost;

/* estimate number of main-table tuples fetched */
tuples_fetched = clamp_row_est(indexSelectivity * baserel->tuples);

어려운 부분은 힙 접근 I/O 비용이다. 버퍼 모델과 상관관계 모두에 의존하기 때문이다. PostgreSQL은 두 경계를 계산하고 보간한다. 비상관 경계(max_IO_cost)는 모든 힙 페이지 페치가 랜덤이라고 가정한다. 상관 경계(min_IO_cost)는 페치가 순차로 힙을 traversal하므로 첫 번째를 제외한 나머지는 모두 순차라고 가정한다.

// cost_index — heap-cost bounds (normal loop_count <= 1 case), costsize.c
pages_fetched = index_pages_fetched(tuples_fetched, baserel->pages,
                                    (double) index->pages, root);
/* max_IO_cost is for the perfectly uncorrelated case (csquared=0) */
max_IO_cost = pages_fetched * spc_random_page_cost;

/* min_IO_cost is for the perfectly correlated case (csquared=1) */
pages_fetched = ceil(indexSelectivity * (double) baserel->pages);
if (pages_fetched > 0)
{
    min_IO_cost = spc_random_page_cost;          /* first fetch is random */
    if (pages_fetched > 1)
        min_IO_cost += (pages_fetched - 1) * spc_seq_page_cost;  /* rest sequential */
}
else
    min_IO_cost = 0;

보간은 상관관계의 제곱으로 이루어진다.

// cost_index — correlation interpolation, costsize.c
csquared = indexCorrelation * indexCorrelation;
run_cost += max_IO_cost + csquared * (min_IO_cost - max_IO_cost);

csquared == 0(비상관)이면 실행 비용은 max_IO_cost가 되고, csquared == 1(완전 상관, 예: CLUSTER 직후)이면 min_IO_cost가 된다. 중간값은 csquared 기준으로 선형 슬라이딩한다. 제곱은 의도적이지만 인정하건대 휴리스틱한 선택이다(주석에 “XXX is that appropriate?”라고 적혀 있다). 상관관계가 높지 않으면 랜덤 접근 가정을 선호하게 만드는 효과가 있다. 이 단 하나의 항 때문에 방금 클러스터된 테이블이 플래너 관점에서 인덱스 스캔을 극적으로 저렴하게 만든다.

CPU 측면은 cost_seqscan과 유사하지만 cpu_tuple_cost + qpqual_cost.per_tuple을 전체 테이블이 아니라 tuples_fetched(인덱스가 힙 페치 단계로 실제로 반환하는 행)에만 부과한다. 선택도 이득이 페이지 항뿐 아니라 여기서도 나타난다.

index_pages_fetched는 Mackert-Lohman 유한-LRU 버퍼 모델이다. 가져올 튜플 수, 테이블 페이지 수, effective_cache_size의 비례 배분 몫이 주어지면, 실제로 읽게 될 고유 페이지 수를 추정한다. 작은 테이블에서 많은 튜플을 가져올 때 캐시에 남은 페이지를 다시 히트한다는 사실을 반영한다.

// index_pages_fetched — Mackert & Lohman 1989, costsize.c (core)
T = (pages > 1) ? (double) pages : 1.0;          /* # pages in table */
total_pages = root->total_table_pages + index_pages;
b = (double) effective_cache_size * T / total_pages;  /* pro-rated cache share */
/* ... force b positive and integral ... */
if (T <= b)                                       /* table fits in cache share */
{
    pages_fetched = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched);
    if (pages_fetched >= T)
        pages_fetched = T;                        /* never more than all pages */
}
/* ... T > b cases use the piecewise formula ... */

2TN/(2T+N) 형태가 점근선이다. 튜플 수가 적을 때는 ≈ N(각 튜플마다 새 페이지)이고, 튜플이 늘어날수록 T에서 포화된다(모든 페이지를 읽은 것). 이것이 캐싱 효과 관례를 구체화한 것이며, 선택적 인덱스 스캔에 행당 랜덤 페이지 비용이 부과되지 않는 단 하나의 이유다.

flowchart TB
  START["cost_index(path, loop_count)"]
  AM["amcostestimate (btcostestimate)<br/>=> indexStartupCost, indexTotalCost,<br/>indexSelectivity, indexCorrelation"]
  TF["tuples_fetched = selectivity x baserel.tuples"]
  ML["index_pages_fetched<br/>(Mackert-Lohman: effective_cache_size 몫 기반<br/>고유 힙 페이지 수)"]
  MAX["max_IO_cost = pages x random_page_cost<br/>(비상관 경계)"]
  MIN["min_IO_cost = random + (pages-1) x seq<br/>(상관 경계)"]
  INTERP["csquared = correlation^2<br/>run_cost += max + csquared x (min - max)"]
  CPU["+ (cpu_tuple_cost + qual) x tuples_fetched<br/>+ tlist cost x rows"]
  OUT["path.startup_cost / path.total_cost"]
  START --> AM --> TF --> ML
  ML --> MAX
  ML --> MIN
  MAX --> INTERP
  MIN --> INTERP
  INTERP --> CPU --> OUT

그림 2 — cost_index 데이터 흐름. AM 콜백이 선택도와 상관관계를 제공한다. Mackert-Lohman이 가져올 튜플 수를 고유 힙 페이지 수로 변환한다. 두 I/O 경계를 계산해 상관관계 제곱으로 보간한다. CPU 항을 페치된 튜플에 더한다. 인덱스 내부 비용은 AM에 위임된 블랙박스다.

cost_qual_eval — 조건 CPU 이음새

스캔 비용의 qual_per_tuple 요금은 어디서 오는가? cost_qual_eval은 조건 표현식 트리를 순회해 (startup, per_tuple) QualCost를 합산한다. 드라이버는 묵시적 AND 절 목록을 순회하며 각각을 처리한다.

// cost_qual_eval — src/backend/optimizer/path/costsize.c
void
cost_qual_eval(QualCost *cost, List *quals, PlannerInfo *root)
{
    cost_qual_eval_context context;
    context.root = root;
    context.total.startup = 0;
    context.total.per_tuple = 0;
    foreach(l, quals)
        cost_qual_eval_walker((Node *) lfirst(l), &context);
    *cost = context.total;
}

walker는 RestrictInfo 노드에 결과를 캐시한다(eval_cost, 센티넬 startup < 0 = 아직 미계산). 같은 절을 참조하는 여러 경로가 있어도 두 번 비용을 계산하지 않는다. 각 함수/연산자 노드는 add_function_cost로 위임한다. 이것이 플래너에서 pg_proc으로의 다리다. procost * cpu_operator_cost를 부과하거나 지원 함수(prosupport)에 더 정교한 추정을 요청한다. (add_function_cost는 pg_proc 행을 읽어야 하므로 카탈로그 접근 레이어인 plancat.c에 있다.)

// add_function_cost — src/backend/optimizer/util/plancat.c (tail)
/* No support function, or it failed, so rely on procost */
cost->per_tuple += procform->procost * cpu_operator_cost;

이것이 System R의 W * (RSI calls) 항을 다듬은 것이다. 균일한 튜플당 요금 대신, 각 조건의 CPU 비용은 해당 함수의 선언된 비용이다(기본값 procost = 1, 즉 연산자 하나당 cpu_operator_cost 하나). 비싼 함수(예: COST 100으로 선언된 PL/pgSQL 함수)는 그에 비례해 요금이 부과된다. 조건 순서와 비싼 함수의 배치가 계획 비용을 바꿀 수 있는 이유다.

같은 기계가 clauses.c에서도 사용된다. 플래너가 파라미터가 두 번 이상 나타나는 SQL 함수를 인라인할지 결정할 때, cost_qual_eval을 “이것이 비싼가?” 판단 게이트로 사용한다. “10개 이상의 연산자”보다 비싸면 비용이 큰 하위 표현식 복제를 피한다.

// inline_function expensiveness gate — src/backend/optimizer/util/clauses.c
cost_qual_eval(&eval_cost, list_make1(param), NULL);
if (eval_cost.startup + eval_cost.per_tuple > 10 * cpu_operator_cost)
    goto fail;   /* don't inline; would duplicate an expensive expression */

cost_qual_eval은 비용 모델 구성요소일 뿐 아니라 표현식 트리 변환이 재사용하는 결정 오라클이기도 하다.

cost_sort — 대표적인 고-startup 연산자

정렬은 높은 startup_cost, 낮은 run_cost 연산자의 교과서적 예다. 첫 번째 튜플을 출력하기 전에 전체 입력을 읽고 정렬해야 한다. 그 후 출력은 저렴하다. cost_sort는 얇은 래퍼다. 입력 경로 비용을 startup에 더하고 나서 cost_tuplesort에 모델을 위임한다.

// cost_sort — src/backend/optimizer/path/costsize.c
void
cost_sort(Path *path, PlannerInfo *root, List *pathkeys, int input_disabled_nodes,
          Cost input_cost, double tuples, int width, Cost comparison_cost,
          int sort_mem, double limit_tuples)
{
    Cost startup_cost, run_cost;
    cost_tuplesort(&startup_cost, &run_cost,
                   tuples, width, comparison_cost, sort_mem, limit_tuples);
    startup_cost += input_cost;        /* must consume all input first */
    path->rows = tuples;
    path->disabled_nodes = input_disabled_nodes + (enable_sort ? 0 : 1);
    path->startup_cost = startup_cost;
    path->total_cost = startup_cost + run_cost;
}

cost_tuplesort는 데이터가 sort_mem(work_mem)에 맞는지에 따라 분기한다. 메모리 내 경우는 고전적인 비교 정렬 비용인 comparison_cost * N * log2(N)이고 전부 startup에 부과된다. 외부 경우는 병합 패스를 위한 페이지 I/O를 더한다.

// cost_tuplesort — src/backend/optimizer/path/costsize.c (condensed)
comparison_cost += 2.0 * cpu_operator_cost;     /* default per-comparison cost */

if (output_bytes > sort_mem_bytes)
{
    /* disk-based merge sort */
    double npages = ceil(input_bytes / BLCKSZ);
    double nruns = input_bytes / sort_mem_bytes;
    double mergeorder = tuplesort_merge_order(sort_mem_bytes);
    double log_runs, npageaccesses;

    *startup_cost = comparison_cost * tuples * LOG2(tuples);   /* N log2 N comparisons */

    if (nruns > mergeorder)
        log_runs = ceil(log(nruns) / log(mergeorder));
    else
        log_runs = 1.0;
    npageaccesses = 2.0 * npages * log_runs;
    /* Assume 3/4ths of accesses are sequential, 1/4th are not */
    *startup_cost += npageaccesses * (seq_page_cost * 0.75 + random_page_cost * 0.25);
}
else
{
    /* plain in-memory quicksort */
    *startup_cost = comparison_cost * tuples * LOG2(tuples);
}

/* small per-extracted-tuple charge; NOT cpu_tuple_cost — Sort does no qual/projection */
*run_cost = cpu_operator_cost * tuples;

주목할 모델링 선택이 세 가지다. (1) 정렬 비용 전체가 startup이다. run 비용은 출력 튜플당 토큰 cpu_operator_cost에 불과하다. Sort 노드는 조건 검사나 프로젝션을 하지 않으므로 플래너가 의도적으로 일반 노드의 cpu_tuple_cost보다 낮게 부과한다. (2) 외부 경우는 병합 패스 전체에 걸쳐 2 * npages * log_runs번의 페이지 접근에 75% 순차/25% 랜덤 비율을 적용한다. 상수에 내장된 명시적 캐싱/지역성 가정이다. (3) 유효한 LIMIT(limit_tuples로 전달)가 있으면 모델을 N * log2(K) 비교의 bounded heap sort로 전환한다. 거대한 입력에 대한 ORDER BY ... LIMIT 10이 전체 정렬보다 훨씬 저렴하게 계산되는 이유다. startup_cost 기계가 제 역할을 하는 지점이다. 정렬의 높은 startup이 작은 LIMIT 아래에서 플래너가 이미 정렬된 인덱스 경로를 선호하도록 유도한다.

2단계 조인 분할

조인 비용 계산에서 initial_cost_* / final_cost_* 관례가 나타난다. initial_cost_nestloop은 입력 경로 비용만으로 하한값을 생성한다. 조인 조건을 검사하지 않는다(주석에 명시). 중간 값을 JoinCostWorkspace에 저장한다. 조인 탐색은 이 하한값을 지금까지 찾은 최선 경로와 비교한다. 살아남은 경로만 final_cost_nestloop을 받는다. 이 단계에서 비용이 큰 조건 평가와 최종 행 수 추정을 수행한다.

// initial_cost_nestloop — src/backend/optimizer/path/costsize.c (condensed)
disabled_nodes = enable_nestloop ? 0 : 1;
disabled_nodes += inner_path->disabled_nodes + outer_path->disabled_nodes;

cost_rescan(root, inner_path, &inner_rescan_start_cost, &inner_rescan_total_cost);

/* must pay both children's startup before first tuple */
startup_cost += outer_path->startup_cost + inner_path->startup_cost;
run_cost += outer_path->total_cost - outer_path->startup_cost;
if (outer_path_rows > 1)
    run_cost += (outer_path_rows - 1) * inner_rescan_start_cost;

inner_run_cost = inner_path->total_cost - inner_path->startup_cost;
/* ... for SEMI/ANTI/unique, defer to final; else scan whole inner per outer row ... */
else
{
    run_cost += inner_run_cost;
    if (outer_path_rows > 1)
        run_cost += (outer_path_rows - 1) * inner_rescan_run_cost;
}
workspace->run_cost = run_cost;   /* private data for final_cost_nestloop */

중첩 루프 형태는 교과서 그대로다. 내부 경로가 외부 행마다 한 번씩 (재)스캔된다. 지배적인 run_cost 항은 첫 번째 inner_run_cost 위에 (outer_rows - 1) * inner_rescan_run_cost다. Startup은 두 자식의 startup 합이다. 어느 자식도 자신의 startup을 치르기 전에는 튜플을 내놓지 않기 때문이다. SEMI/ANTI/inner-unique 경우(첫 번째 매치 후 조기 종료)는 조인 조건이 필요하므로 final에 위임된다.

final_cost_nestloop은 실제 튜플 수와 CPU 요금을 계산한다.

// final_cost_nestloop — src/backend/optimizer/path/costsize.c (normal-case tail)
ntuples = outer_path_rows * inner_path_rows;       /* tuples *processed* */

cost_qual_eval(&restrict_qual_cost, path->jpath.joinrestrictinfo, root);
startup_cost += restrict_qual_cost.startup;
cpu_per_tuple = cpu_tuple_cost + restrict_qual_cost.per_tuple;
run_cost += cpu_per_tuple * ntuples;

/* tlist eval costs are paid per output row, not per tuple scanned */
startup_cost += path->jpath.path.pathtarget->cost.startup;
run_cost += path->jpath.path.pathtarget->cost.per_tuple * path->jpath.path.rows;

ntuples는 출력 행 수가 아니라 검사한 후보 쌍 수(outer_rows * inner_rows)다. CPU 요금은 모든 조건 평가에 부과되고, 대상 목록 비용은 훨씬 적은 path.rows 출력에 부과된다. 조인에 System R 비용 지표를 적용한 것이다. 자식들의 실행 비용에서 페이지 비용은 initial 단계에서 이미 반영되었고, 이 단계는 비교당 CPU 항을 더한다.

cost_hashjoin — 다른 조인 형태

해시 조인의 2단계 분할은 initial_cost_hashjoin / final_cost_hashjoin에 있다. initial 단계는 해시 구축 비용을 startup으로 부과한다(내부 행당 컬럼별 해시 함수 하나 + 테이블 삽입의 cpu_tuple_cost). 핵심으로 **배치(batching)**를 모델링한다. 내부 릴레이션이 hash_mem에 맞지 않으면 executor가 디스크로 spill한다. 따라서 spill된 페이지당 seq_page_cost를 추가한다.

// initial_cost_hashjoin — src/backend/optimizer/path/costsize.c (condensed)
startup_cost += outer_path->startup_cost;
run_cost += outer_path->total_cost - outer_path->startup_cost;
startup_cost += inner_path->total_cost;      /* must build hash from whole inner */

/* hash build: one cpu_operator_cost per column hash + cpu_tuple_cost insert */
startup_cost += (cpu_operator_cost * num_hashclauses + cpu_tuple_cost) * inner_path_rows;
run_cost += cpu_operator_cost * num_hashclauses * outer_path_rows;   /* probe hashing */

ExecChooseHashTableSize(inner_path_rows_total, inner_path->pathtarget->width,
                        true, parallel_hash, outer_path->parallel_workers,
                        &space_allowed, &numbuckets, &numbatches, &num_skew_mcvs);
if (numbatches > 1)            /* inner doesn't fit -> spill both sides to disk */
{
    double outerpages = page_size(outer_path_rows, outer_path->pathtarget->width);
    double innerpages = page_size(inner_path_rows, inner_path->pathtarget->width);
    startup_cost += seq_page_cost * innerpages;            /* write inner */
    run_cost += seq_page_cost * (innerpages + 2 * outerpages);  /* re-read */
}

final_cost_hashjoin은 추정된 내부 버킷 크기(외부 행이 프로브하는 버킷에 내부 행이 몇 개 들어가는지)를 사용해 프로브 비용을 부과한다. 해시 코드 불일치가 비교를 조기에 종료한다는 점을 반영해 조건 평가 요금을 절반으로 줄인다.

// final_cost_hashjoin — src/backend/optimizer/path/costsize.c (normal-case core)
/* comparisons = outer_rows x (inner_rows x bucketsize); halve for hash-mismatch skip */
startup_cost += hash_qual_cost.startup;
run_cost += hash_qual_cost.per_tuple * outer_path_rows *
    clamp_row_est(inner_path_rows * innerbucketsize) * 0.5;

hashjointuples = approx_tuple_count(root, &path->jpath, hashclauses);

/* per surviving join tuple: cpu_tuple_cost + other (qp) quals */
startup_cost += qp_qual_cost.startup;
cpu_per_tuple = cpu_tuple_cost + qp_qual_cost.per_tuple;
run_cost += cpu_per_tuple * hashjointuples;

중첩 루프와의 대비가 비용 모델의 존재 이유를 잘 보여준다. 해시 조인은 비용을 startup에 앞당기고(테이블 구축) 이후 프로브를 저렴하게 처리한다. 중첩 루프의 outer * inner 비교 횟수가 폭발하는 대규모 동등 조인에서 유리하다. 반면 구축 비용을 회수할 틈이 없는 좁은 LIMIT 아래에서는 불리하다. 프로브 비용을 결정하는 bucketsize와 mcvfreq 추정은 선택도 기계에서 온다(estimate_hash_bucket_stats, estimate_multivariate_bucketsize). 버킷 크기의 확장 통계 처리는 postgres-extended-statistics.md가 담당한다.

행 수 추정 이음새

비용 함수는 행 수를 입력으로 받는다. 직접 추정하지 않는다. 추정은 앞서 set_baserel_size_estimates에서 이루어진다. 이것이 선택도 하위 시스템(clauselist_selectivity, 궁극적으로 selfuncs.c의 연산자별 추정 함수)으로의 이음새다.

// set_baserel_size_estimates — src/backend/optimizer/path/costsize.c
nrows = rel->tuples *
    clauselist_selectivity(root, rel->baserestrictinfo, 0, JOIN_INNER, NULL);
rel->rows = clamp_row_est(nrows);
cost_qual_eval(&rel->baserestrictcost, rel->baserestrictinfo, root);
set_rel_width(root, rel);

비용 모델에는 두 가지 출력이 공급된다. rel->rows(비용 함수가 읽는 필터 후 카디널리티)와 rel->baserestrictcost(나중에 cost_seqscan에 전달하는 조건 CPU 비용). 모든 행 수 추정은 clamp_row_est를 통과한다. 최솟값을 1.0으로 강제하고, 정수로 반올림하며, double 오버플로를 막는 캡을 씌운다. 작지만 중요한 보호 장치다. 0-행 추정은 하류 비용 보간에서 0 나눗셈을 일으키고, 무한 추정은 add_path를 망가뜨린다. selfuncs.c의 선택도 함수(히스토그램/MCV 조회, System R 폴백 상수)는 postgres-extended-statistics.md가 담당한다. 이 문서에서는 rel->rows를 주어진 값으로 취급한다.

flowchart LR
  STATS["pg_statistic<br/>(히스토그램, MCV, ndistinct, 상관관계)"]
  CLS["clauselist_selectivity<br/>(selfuncs.c)"]
  SBSE["set_baserel_size_estimates<br/>rel.rows = tuples x selectivity<br/>rel.baserestrictcost = cost_qual_eval(...)"]
  COST["cost_seqscan / cost_index / cost_*<br/>rel.rows + baserestrictcost 읽기"]
  ADD["add_path<br/>(startup/total/순서 부분 순서로 보관)"]
  STATS --> CLS --> SBSE --> COST --> ADD

그림 3 — 행 수 추정 이음새. 통계가 선택도를 결정하고, 선택도가 rel->rows를 설정한다. 비용 함수는 해당 카디널리티와 사전 계산된 조건 비용을 소비한다. 비용 모델과 선택도 모델은 서로 연결되어 있지만 명확히 분리된다. 비용 함수는 기본 행을 위해 clauselist_selectivity를 직접 호출하지 않는다.

소스 코드 가이드

심볼 이름에 닻을 내리고 줄 번호에 의존하지 말 것. PostgreSQL 소스는 릴리스 간 이동한다. 함수나 구조체 이름이 안정적인 핸들이다. git grep -n '<symbol>' src/backend/optimizer/로 현재 위치를 찾을 수 있다. 아래 위치 힌트 표의 줄 번호는 커밋 273fe94 (REL_18_STABLE) 기준 빠른 참고용이다.

비용 파라미터와 클램프 (`costsize.c` 상단)

seq_page_cost / random_page_cost / cpu_tuple_cost / cpu_index_tuple_cost / cpu_operator_cost — 다섯 가지 조정 가능한 비용 GUC. cost.h의 DEFAULT_* 매크로로 초기화.
parallel_tuple_cost / parallel_setup_cost / effective_cache_size — 병렬 통신 가중치와 버퍼 모델 캐시 크기.
disable_cost (1e10) — 레거시 가산값. 경로별 disabled_nodes 카운터(enable_* GUC가 증가)로 대부분 대체됨.
clamp_row_est — 행 수 추정을 [1, 1e100] 범위의 정수로 강제. 모든 비용 보간 전 범용 건전성 보호.
clamp_width_est / clamp_cardinality_to_long — 튜플 너비와 long 변환을 위한 동반 클램프.

스캔 비용 함수

cost_seqscan — 페이지 항 spc_seq_page_cost * pages + CPU 항 (cpu_tuple_cost + qual) * tuples; startup 사실상 0.
cost_index — 인덱스 내부 비용을 amcostestimate에 위임. index_pages_fetched로 힙 I/O 계산. csquared(correlation²)로 min_IO_cost / max_IO_cost 보간.
index_pages_fetched — Mackert & Lohman (1989) 유한-LRU 버퍼 모델. 비례 배분된 effective_cache_size 기준 페치될 고유 힙 페이지 수.
cost_samplescan / cost_bitmap_heap_scan / cost_tidscan — 형제 스캔 비용 함수(bitmap·TID 스캔은 postgres-scan-nodes.md 참조).
extract_nonindex_conditions — 어떤 제한 절이 qpqual(CPU 부과)이 되는지, 어떤 것이 인덱스 내부에서 처리되는지 결정.

정렬과 물질화

cost_sort — 래퍼: 입력 비용을 startup에 추가 후 cost_tuplesort 호출.
cost_tuplesort — 메모리 내 comparison_cost * N * log2(N). 외부 병합은 2 * npages * log_runs번의 페이지 접근 75% 순차/25% 랜덤 추가. LIMIT 아래에서 N * log2(K) bounded.
cost_incremental_sort — 접두사 정렬 입력을 기준으로 추정 그룹별 cost_tuplesort.
cost_material / cost_memoize_rescan — 물질화와 Memoize 재스캔 캐시.

조인 비용 함수 (2단계)

initial_cost_nestloop / final_cost_nestloop — 하한값(조건 검사 없음) 후 최종. 외부 행마다 내부 한 번 재스캔. SEMI/ANTI/unique 조기 종료는 final에 위임.
initial_cost_mergejoin / final_cost_mergejoin — 병합 조인. cost_sort로 필요한 정렬 비용 계산. cached_scansel이 병합 스캔 선택도 캐시.
initial_cost_hashjoin / final_cost_hashjoin — 구축 비용을 startup으로. 배치 spill에 seq_page_cost. 프로브 비용에 내부 bucketsize.
cost_gather / cost_gather_merge — 병렬 리더/워커 gather. parallel_setup_cost + parallel_tuple_cost 추가.
cost_rescan — 조인 내부 측을 재실행하는 비용.
approx_tuple_count / has_indexed_join_quals — 조인 튜플 수와 인덱스 조건 감지 헬퍼.

조건 CPU 비용

cost_qual_eval / cost_qual_eval_node — 절 목록/단일 노드의 QualCost 합산. RestrictInfo.eval_cost에 캐시.
cost_qual_eval_walker — 재귀 walker. 노드 유형별 요금 부과 (FuncExpr, OpExpr, ScalarArrayOpExpr, Aggref 등).
add_function_cost (plancat.c) — pg_proc.procost와 prosupport 지원 함수로의 다리. procost * cpu_operator_cost 부과.
get_restriction_qual_cost — baserel->baserestrictcost 반환(매개변수화 경로의 push-down 절 비용 포함).

행 수 추정 이음새

set_baserel_size_estimates — rel->rows = tuples * selectivity; rel->baserestrictcost = cost_qual_eval(baserestrictinfo); set_rel_width.
get_parameterized_baserel_size / calc_joinrel_size_estimate / set_joinrel_size_estimates — 매개변수화 및 조인 카디널리티.
clauselist_selectivity (selfuncs.c) — 이음새가 호출하는 선택도 진입점. postgres-extended-statistics.md 담당.

크기/병렬 헬퍼

relation_byte_size — tuples * (MAXALIGN(width) + MAXALIGN(header)).
page_size — ceil(relation_byte_size / BLCKSZ).
get_parallel_divisor — 워커당 작업 비율. 리더 참여 모델링(리더는 1 - 0.3 * workers 기여).

위치 힌트 (2026-06-05, REL_18 273fe94 기준)

심볼	파일	줄
`clamp_row_est`	`src/backend/optimizer/path/costsize.c`	213
`cost_seqscan`	`src/backend/optimizer/path/costsize.c`	295
`cost_gather`	`src/backend/optimizer/path/costsize.c`	446
`cost_index`	`src/backend/optimizer/path/costsize.c`	560
`index_pages_fetched`	`src/backend/optimizer/path/costsize.c`	908
`cost_tuplesort`	`src/backend/optimizer/path/costsize.c`	1898
`cost_sort`	`src/backend/optimizer/path/costsize.c`	2144
`initial_cost_nestloop`	`src/backend/optimizer/path/costsize.c`	3267
`final_cost_nestloop`	`src/backend/optimizer/path/costsize.c`	3349
`initial_cost_hashjoin`	`src/backend/optimizer/path/costsize.c`	4160
`final_cost_hashjoin`	`src/backend/optimizer/path/costsize.c`	4275
`cost_qual_eval`	`src/backend/optimizer/path/costsize.c`	4756
`cost_qual_eval_walker`	`src/backend/optimizer/path/costsize.c`	4796
`get_restriction_qual_cost`	`src/backend/optimizer/path/costsize.c`	5072
`set_baserel_size_estimates`	`src/backend/optimizer/path/costsize.c`	5349
`relation_byte_size`	`src/backend/optimizer/path/costsize.c`	6453
`get_parallel_divisor`	`src/backend/optimizer/path/costsize.c`	6474
`add_function_cost`	`src/backend/optimizer/util/plancat.c`	2125
`cost_qual_eval` (인라인 게이트)	`src/backend/optimizer/util/clauses.c`	4831
`DEFAULT_SEQ_PAGE_COST` …	`src/include/optimizer/cost.h`	24

소스 검증 (2026-06-05 기준)

/data/hgryoo/references/postgres, REL_18_STABLE, 커밋 273fe94852b3a7e34fd171e8abdf1481beb302fa 기준으로 검증했다.

다섯 가지 비용 파라미터와 기본값. cost.h에 DEFAULT_SEQ_PAGE_COST 1.0, DEFAULT_RANDOM_PAGE_COST 4.0, DEFAULT_CPU_TUPLE_COST 0.01, DEFAULT_CPU_INDEX_TUPLE_COST 0.005, DEFAULT_CPU_OPERATOR_COST 0.0025, DEFAULT_PARALLEL_TUPLE_COST 0.1, DEFAULT_PARALLEL_SETUP_COST 1000.0, DEFAULT_EFFECTIVE_CACHE_SIZE 524288이 정의되어 있다. costsize.c의 전역 변수들이 이 값으로 초기화된다. grep -n DEFAULT_ src/include/optimizer/cost.h로 확인.
cost_seqscan 페이지 + CPU 분해. disk_run_cost = spc_seq_page_cost * baserel->pages와 cpu_run_cost = (cpu_tuple_cost + qpqual_cost.per_tuple) * baserel->tuples, total_cost = startup_cost + cpu_run_cost + disk_run_cost 확인. CPU 항은 baserel->tuples(필터 전), tlist 비용은 path->rows(필터 후) 사용. 함수 본문 전체를 읽어 검증.
cost_index 위임과 보간. amcostestimate 콜백이 indexSelectivity와 indexCorrelation을 공급하고, csquared = indexCorrelation * indexCorrelation, run_cost += max_IO_cost + csquared * (min_IO_cost - max_IO_cost) 확인. loop_count > 1 분기(반복 인덱스 스캔)와 인덱스 전용 스캔 allvisfrac 감소가 설명대로 존재.
Mackert-Lohman. index_pages_fetched의 헤더 주석에 “Mackert and Lohman, Index Scans Using a Finite LRU Buffer, ACM TODS Vol. 14 No. 3, 1989”가 인용되어 있고 b를 비례 배분된 effective_cache_size 몫으로 사용하는 2TNs/(2T+Ns) 분할 공식을 구현한다. 확인.
cost_tuplesort 모델. 메모리 내 퀵소트 comparison_cost * tuples * LOG2(tuples)가 startup에 부과됨, 외부 병합이 npageaccesses * (seq_page_cost * 0.75 + random_page_cost * 0.25) 추가, run 비용이 cpu_operator_cost * tuples(cpu_tuple_cost가 아님 — Sort 노드는 조건/프로젝션 없음을 주석이 설명) 확인. comparison_cost += 2.0 * cpu_operator_cost 기본값. 확인.
2단계 조인. initial_cost_nestloop과 initial_cost_hashjoin이 JoinCostWorkspace를 채우고 조건 검사를 명시적으로 연기함(“CPU costs left for later”). final_cost_nestloop / final_cost_hashjoin이 joinrestrictinfo / hashclauses로 cost_qual_eval을 호출. hashjoin 배치 분기(numbatches > 1)가 spill된 페이지당 seq_page_cost를 부과. 확인.
cost_qual_eval → add_function_cost. walker가 RestrictInfo.eval_cost에 캐시(센티넬 startup < 0)하고, add_function_cost(clauses.c가 아닌 plancat.c)가 prosupport 함수가 없을 때 procform->procost * cpu_operator_cost를 부과. clauses.c의 4831행은 inline_function의 “10개 초과 연산자” 비용 게이트이고 정의가 아님. grep -n cost_qual_eval src/backend/optimizer/util/clauses.c로 확인.
행 수 추정 이음새. set_baserel_size_estimates가 rel->rows = clamp_row_est(rel->tuples * clauselist_selectivity(...))를 계산하고 cost_qual_eval로 rel->baserestrictcost를 설정. clauselist_selectivity는 selfuncs에 선언되어 통계 하위 시스템의 경계다. 확인.
REL_18 사항 준수. disabled_nodes(PG 17부터 enable_* GUC가 증가하는 경로별 카운터)가 레거시 disable_cost 가산 방식 대신 전반적으로 사용됨. estimate_multivariate_bucketsize(확장 통계 버킷 크기 조정, PG 17+)가 final_cost_hashjoin에서 호출됨. 17 이전 구성 요소는 단언하지 않음.

PostgreSQL 너머 — 비교 설계와 연구 프론티어

PostgreSQL 비용 모델은 1979년 System R 설계의 충실하고 보수적인 계승자다. 다른 엔진과 연구 문헌과 비교하면 어떤 선택이 보편적이고 어떤 것이 맥락 의존적인지 명확해진다.

디스크 시대 상수 문제. PostgreSQL의 기본값(random_page_cost = 4.0)은 회전 디스크 물리를 반영한다. 랜덤 탐색이 순차 읽기 약 4회 분량이다. NVMe SSD에서 이 비율은 1.1–1.5에 가깝고, 완전히 캐시된 워킹셋에서는 사실상 1.0이다. 모델이 단위 없는 값이고 파라미터가 노출되어 있으므로, 표준적인 대처는 재조정이다. random_page_cost를 낮추면 인덱스 스캔이 더 매력적으로 보인다. 프로덕션에서 가장 흔한 비용 모델 조정이다. 더 깊은 비판은 하나의 random_page_cost로는 처음 몇 페이지는 캐시(저렴)되어 있고 나머지는 디스크(비쌈)에 있는 스토리지 계층을 표현할 수 없다는 점이다. effective_cache_size와 Mackert-Lohman 모델이 PostgreSQL의 부분적 답변이지만, 이 둘은 학습된 릴레이션별 히트율이 아니라 테이블당 균일한 캐시 몫을 가정한다.

보정된 비용 단위 대 추상 비용 단위. 일부 엔진은 비용 단위를 실제 하드웨어에 보정한다. DB2와 초기 System R 후계자들은 I/O/CPU 가중치를 설정하는 하드웨어 특성 분석을 실행했다. Microsoft SQL Server의 비용 단위는 기준 기계에서의 초 단위다. PostgreSQL은 의도적으로 추상 단위를 유지한다. 비용은 무차원이며 시간과 단조적이기만 하면 된다. 트레이드오프가 있다. 추상 단위는 절댓값 모델 오류에 단순하고 견고하지만, “이 쿼리는 2초 걸릴까?”라는 질문에는 답할 수 없고 계획 간 비교만이 숫자의 유일한 유효한 용도가 된다.

카디널리티 추정이 주된 오류 원인이다. 주목할 만한 연구 — Leis et al., How Good Are Query Optimizers, Really? (VLDB 2015) — 는 조인이 많은 쿼리에서 비용 모델 자체의 오류가 카디널리티 추정 오류에 비해 훨씬 작다는 것을 경험적으로 보였다. 행 수가 틀리면(조인 트리를 거치면서 오류가 곱셈으로 누적된다), 비용 함수의 정밀도는 무관해진다. 논문의 단호한 결론은 좋은 옵티마이저는 정교한 비용 함수보다 정확한 카디널리티 추정이 훨씬 더 필요하다는 것이다. PostgreSQL의 비교적 단순한 비용 산술은 이런 관점에서 올바른 수준의 투자이며, 레버리지는 selfuncs.c와 확장 통계(postgres-extended-statistics.md)에 있다.

학습 및 적응형 비용 모델. 연구 최전선은 비용 함수를 수작업 상수에서 학습된 모델로 옮긴다. Neo (Marcus et al., VLDB 2019)와 Bao는 실행 피드백에서 비용/지연 예측기를 학습한다. 학습된 카디널리티 추정기(MSCN, DeepDB, NeuroCard)는 히스토그램 파이프라인을 대체한다. 적응형 쿼리 처리(예: 고전적 eddies, SCOPE와 Spark의 AQE 같은 시스템의 런타임 재최적화)는 실행 중 중간 카디널리티를 측정하고 재계획해 추정 오류를 우회한다. PostgreSQL 코어에는 이런 것이 없다. 비용 모델은 계획 시간에 고정된다. 단, prosupport 메커니즘(add_function_cost가 지원 함수를 참조)은 작은 확장성 훅이고, pg_hint_plan이나 적응형 통계 패치 같은 확장들이 그 공간을 탐색한다. 정적 모델을 지지하는 보수적 논거는 계획 안정성과 설명 가능성이다. 고정된 비용 함수는 관리자가 EXPLAIN으로 추론할 수 있는 재현 가능한 계획을 생성한다.

벡터화·컬럼형 엔진은 CPU 항을 재조정한다. PostgreSQL의 cpu_tuple_cost/cpu_operator_cost는 행 단위(row-at-a-time) Volcano 실행기(postgres-executor.md)를 가정한다. 컬럼형/벡터화 엔진(DuckDB, ClickHouse, Vectorwise)은 배치를 처리하고 연산자를 SIMD 벡터화한다. 따라서 튜플당 CPU 상수가 훨씬 낮고 스캔 대 해시 조인의 상대적 비용이 달라진다. 튜플 단위 인터프리터용으로 조정된 비용 모델은 벡터화 엔진의 CPU 바운드 연산자를 체계적으로 과대 계산한다. 이런 엔진들이 PostgreSQL 비용 모델을 이식하지 않고 자체 비용 모델을 도입하는 이유 중 하나다. 모델은 스토리지 하드웨어만이 아니라 자신이 채점하는 실행기 아키텍처와도 연결되어 있다.

단순함을 유지해 올바른 것들. 2단계 조인 분할(initial_cost_* / final_cost_*)은 조인 탐색이 조합적으로 폭발하는 상황에서 옵티마이저 런타임을 제한하는 진정으로 좋은 엔지니어링 패턴이다. 많은 학습/적응형 시스템도 탐색을 실용적으로 만들기 위한 동등한 저렴한-하한값 메커니즘이 여전히 필요하다. 그리고 add_path가 부분 순서로 취급하는 깔끔한 (startup, total) 쌍은 플랫-비용 모델이 틀리게 되는 LIMIT-인식 계획에 올바른 기본 요소다.

출처

코드 (REL_18_STABLE, 커밋 273fe94, 2026-06-05 기준):
- src/backend/optimizer/path/costsize.c — 비용 모델: cost_seqscan, cost_index, index_pages_fetched, cost_sort / cost_tuplesort, initial_cost_nestloop / final_cost_nestloop, initial_cost_hashjoin / final_cost_hashjoin, cost_gather, cost_qual_eval, get_restriction_qual_cost, set_baserel_size_estimates, clamp_row_est, relation_byte_size, get_parallel_divisor, 다섯 가지 비용 파라미터 전역 변수.
- src/backend/optimizer/util/clauses.c — inline_function의 cost_qual_eval “10개 연산자” 비용 게이트(clauses.c 이음새).
- src/backend/optimizer/util/plancat.c — add_function_cost. pg_proc.procost / prosupport로의 다리.
- src/include/optimizer/cost.h — DEFAULT_* 비용 파라미터 매크로.
- src/include/nodes/pathnodes.h — Path (startup_cost, total_cost, rows, disabled_nodes), QualCost, JoinCostWorkspace.
이론: Selinger, Astrahan, Chamberlin, Lorie, Price, Access Path Selection in a Relational Database Management System, SIGMOD 1979 — knowledge/research/dbms-papers/systemr-optimizer.md 참고 (비용 지표, 선택도 인수, 가지치기 키로서의 비용). Mackert & Lohman, Index Scans Using a Finite LRU Buffer: A Validated I/O Model, ACM TODS 14(3), 1989 (index_pages_fetched 공식).
비교 / 프론티어: Leis et al., How Good Are Query Optimizers, Really?, VLDB 2015 (카디널리티 대 비용 오류); Marcus et al., Neo: A Learned Query Optimizer, VLDB 2019 (학습된 비용). Hellerstein, Stonebraker & Hamilton, Architecture of a Database System, 2007 — knowledge/research/dbms-papers/fntdb07-architecture.md.
관련 KB 문서: postgres-path-generation.md (Path 객체 생성과 add_path의 보관 방식), postgres-join-ordering.md (비용을 가지치기 키로 소비하는 열거 탐색), postgres-extended-statistics.md (clauselist_selectivity 뒤의 선택도/카디널리티 하위 시스템), postgres-planner-overview.md (플래너에서 비용 계산의 위치), postgres-executor.md (CPU 가중치가 모델링하는 Volcano 실행기), postgres-scan-nodes.md, postgres-index-am.md, postgres-nbtree.md (amcostestimate 피호출자).

(KO) PostgreSQL 비용 모델 — 페이지/CPU 비용과 경로 비교

학술적 배경

DBMS 공통 설계 패턴

추상적 비용 단위, 밀리초가 아니라

두 가지 비용 항: 페이지 I/O와 CPU

Startup 비용 대 Total 비용

I/O 항의 캐싱 효과

인덱스 순서와 힙 순서 간 상관관계

탐색 가지치기를 위한 2단계 조인 비용 계산

이론 ↔ PostgreSQL 매핑

PostgreSQL의 구현

다섯 가지 비용 파라미터

startup_cost 대 total_cost, 그리고 행 수 추정

cost_seqscan — 가장 단순한 사례

cost_index — 위임, Mackert-Lohman, 상관관계

cost_qual_eval — 조건 CPU 이음새

cost_sort — 대표적인 고-startup 연산자

2단계 조인 분할

cost_hashjoin — 다른 조인 형태

행 수 추정 이음새

소스 코드 가이드

비용 파라미터와 클램프 (costsize.c 상단)

스캔 비용 함수

정렬과 물질화

조인 비용 함수 (2단계)

조건 CPU 비용

행 수 추정 이음새

크기/병렬 헬퍼

위치 힌트 (2026-06-05, REL_18 273fe94 기준)

소스 검증 (2026-06-05 기준)

PostgreSQL 너머 — 비교 설계와 연구 프론티어

출처

비용 파라미터와 클램프 (`costsize.c` 상단)