쿼리 옵티마이저가 답해야 하는 질문은 하나다. 원하는 결과를 무엇으로 정의한 SQL 문이 주어졌을 때, 논리적으로 동등한 수많은 물리적 실행 전략 중 어느 것을 실제로 실행할 것인가. 관계형 모델은 동일한 결과를 내는 물리적으로 구별되는 실행 계획이 많다는 것을 보장한다. 조인은 중첩 루프, 정렬-병합, 해시 조인 중 하나로 실행할 수 있다. 테이블은 순차 스캔이나 인덱스 중 하나로 접근할 수 있다. 세 테이블 조인은 결합 법칙과 교환 법칙에 따라 여러 모양으로 변형된다. Database System Concepts (Silberschatz, 7판, 16장 “Query Optimization”)는 이 문제를 두 개의 결합된 하위 문제로 정리한다. 계획 공간 열거 (어떤 동등한 계획들을 고려할 것인가)와 비용 추정 (실제로 실행하지 않고 순위를 매기기 위한 수치 모델)이 그것이다. Database Internals (Petrov, 7장)도 같은 경계를 긋는다. 항상 유익한 변환을 적용하는 규칙 기반 재작성 단계와, 비용 모델 아래에서 대안들을 탐색하는 비용 기반 단계로 구분한다.
비용 기반 최적화의 정전적 구현체는 System R 옵티마이저다. Selinger 외, “Access Path Selection in a Relational Database Management System” (SIGMOD 1979, research/dbms-papers/systemr-optimizer.md에 캡처)에 기술된 이 옵티마이저는 PostgreSQL이 거의 그대로 따르는 설계 틀을 수립했다.
테이블별 접근 경로 열거. 각 릴레이션마다 순차 스캔과 모든 적용 가능한 인덱스를 고려하고, 카탈로그 통계를 이용해 각각의 비용을 추정한다.
선택도 추정. 각 조건절에는 선택도 (통과시키는 행의 비율)가 있다. 선택도의 곱이 살아남는 행 수를 추정한다. 카디널리티 추정은 모든 하위 비용 계산을 이끈다.
동적 프로그래밍으로 조인 순서 열거.n! 개의 순서를 모두 평가하는 대신, System R은 릴레이션의 모든 부분집합에 대한 최적 계획을 아래에서 위로 구성한다. 1-테이블 최적 계획에서 시작해 2-테이블, 3-테이블, 전체 집합까지 올라간다. 핵심 가지치기 규칙은 최적성 원리다. 릴레이션 집합의 최적 계획은 그 부분집합들의 최적 계획으로 구성된다는 원리가 지수적 탐색을 2^n으로 줄인다.
“흥미로운 정렬 순서” 유지. 더 비싸지만 나중에 필요한 정렬(병합 조인 키, ORDER BY, GROUP BY) 순서대로 행을 이미 내보내는 계획은 전체적으로 더 나을 수 있다. 나중의 정렬 비용을 아끼기 때문이다. System R은 따라서 릴레이션 집합마다 단 하나의 최저 비용 계획만 유지하지 않는다. 각 흥미로운 정렬 순서마다 최저 비용 계획과 정렬 없는 최저 비용 계획을 함께 유지한다. 이것이 PostgreSQL의 pathkeys의 씨앗이다.
Selinger의 설계 공간에는 모든 비용 기반 옵티마이저가 반드시 결정해야 하는 몇 가지 선택지가 남아 있다. 이 문서가 전개되면서 주목해야 할 선택들이다.
탐색의 단위는 무엇인가? System R은 계획 자체를 직접 탐색한다. PostgreSQL은 중간 추상화를 사이에 둔다. 바로 Path다. Path는 비용과 정렬 순서만 담은 가벼운 계획 스케치로, 완전한 실행 계획보다 생성하고 버리기가 훨씬 싸다.
조인 탐색은 얼마나 철저한가? 순수 동적 프로그래밍은 릴레이션 수에 지수적이다. 큰 조인을 위한 대안 탐색 경로는 어느 엔진에나 필요하다. PostgreSQL의 경우 유전 옵티마이저 GEQO가 그 역할을 한다.
탐색 중 동등한 계획을 어떻게 가지치기하는가? 가지치기 규칙이 “거의 비슷한” 계획들이 한 레벨 위에서 경쟁을 계속할 수 있는지를 결정한다.
Berkeley POSTGRES 프로젝트는 이 설계 틀을 자체 확장과 함께 재구현했다. Fong의 석사 논문 “The Design and Implementation of the POSTGRES Query Optimizer” (UCB)는 System-R 비용 모델이 어떻게 오늘날의 src/backend/optimizer/ 트리의 직접 선조인 코드베이스에 적용되었는지를 기술한다. RelOptInfo, Path, pathkeys, add_path라는 어휘는 그 작업으로 곧장 거슬러 올라간다.
범위. 이 문서는 해당 옵티마이저의 뼈대와 지도다. 세 단계 제어 흐름, RelOptInfo/Path/Plan 구분, 아래에서 위로의 Path 생성, 최저 비용 Path 선택, Path→Plan 변환을 다룬다. 각 주요 부분의 메커니즘은 형제 문서에 위임된다. AM별 Path 생성기는 postgres-path-generation.md, 조인 순서 동적 프로그래밍과 join_search 내부는 postgres-join-ordering.md, 선택도와 비용 공식은 postgres-cost-model.md, 노드별 Path→Plan 변환 상세는 postgres-plan-creation.md, 완성된 Plan을 실행기가 어떻게 처리하는지는 postgres-executor.md에 있다.
“System R 설계 틀”과 “실제 PostgreSQL 심볼들” 사이에는 진지한 비용 기반 옵티마이저라면 거의 모두 채택하는 엔지니어링 관례가 하나의 층을 이룬다. 이 관례들을 먼저 이름 붙여 두면, 다음 절의 PostgreSQL 심볼들이 발명품이 아닌 알려진 패턴의 구체적 사례로 읽힌다.
옵티마이저는 거의 예외 없이 단계별로 구성된다. 재작성/정규화 단계는 비용 비교 없이 항상 유익한 변환을 적용한다. 중첩된 AND/OR 평탄화, 상수 표현식 폴딩, 단순 서브쿼리를 부모 쪽으로 끌어올려 같은 탐색에 참여시키기, 조건절을 스캔 쪽으로 밀어 내리기가 이에 해당한다. 비용 기반 탐색 단계는 진정으로 대안이 되는 물리적 전략들을 열거하고 순위를 매긴다. 마지막으로 방출 단계는 단 하나의 승자를 실행 엔진이 소비하는 형태로 구체화한다. 이 단계들을 혼용하는 것은 버그의 고전적 원인이다. “재작성”이지만 때로만 유익한 변환은 비용 기반 단계에 속한다.
모든 후보에 완전한 실행 연산자 트리를 생성하는 것은 대부분의 후보가 버려질 때 낭비다. 표준적인 해결책은 두 수준 표현이다. 탐색에 필요한 정보(추정 비용, 출력 카디널리티, 출력 정렬 순서, 필요한 파라미터)만 담고 실행 세부 사항을 생략하는 싸고 계획 전용인 노드, 그리고 선택된 계획에 대해서만 한 번 만들어지는 무거운 실행 노드로 구성된다. SQL Server의 옵티마이저에는 Group/GroupExpression 메모가 있다. Calcite에는 RelTrait을 가진 RelNode가 있다. PostgreSQL에는 Path 대 Plan이 있다. 규율은 동일하다. 싸구려 것 위에서 탐색하고, 비싼 것은 한 번만 만든다.
동적 프로그래밍 탐색에는 “이 릴레이션 집합을 생성하는 모든 방법”을 축적하고 승자를 기록해서 상위 레벨이 재사용할 수 있는 장소가 필요하다. 관례는 릴레이션 집합마다 하나의 구조다. System R의 “best plans” 테이블 항목, 캐스케이드 방식 옵티마이저의 메모 그룹이 그 예다. 이 구조는 후보 계획 목록과 최저 비용 계획에 대한 캐시된 포인터를 소유한다. 결정적으로, 논리적으로 구별되는 릴레이션 집합 하나당 정확히 하나의 컨테이너가 존재한다. 같은 집합에 대한 서로 다른 유도 경로로 도달한 계획들이 한 곳에서 경쟁하도록 하기 위해서다.
탐색이 릴레이션 집합마다 단 하나의 최저 비용 계획만 유지하면, 상위에서 정렬을 절약해 주는 정렬 순서를 가진 계획들을 버리게 된다. 보편적인 개선은 소비자에게 중요한 모든 차원을 따라 가지치기하는 것이다. 각각의 구별되는 물리적 속성 조합(정렬 순서, 그리고 PostgreSQL에서는 파라미터화도 포함)마다 최저 비용 계획을 유지한다. 어떤 살아남은 계획이 비용면에서 적어도 동등하고 동시에 모든 물리적 속성에서도 적어도 동등할 때만 계획이 버려진다. 이것이 일반화된 “흥미로운 정렬 순서”다.
동적 프로그래밍 조인 탐색은 시간과 공간 모두 O(2^n)이다. 릴레이션 십여 개에는 괜찮지만 오십 개에는 파국적이다. 따라서 모든 동적 프로그래밍 옵티마이저는 임계값을 넘으면 최적성을 포기하고 처리 가능성을 택하는 휴리스틱 탐색(탐욕적, 무작위, 또는 유전적)과 짝을 이룬다. 옵티마이저는 릴레이션 수에 따라 전략을 선택한다.
PostgreSQL 옵티마이저를 이해하는 가장 유용한 심상은 세 함수로 이루어진 스택이다. 각 함수가 하나의 논리 레이어를 처리하고 나머지를 안쪽으로 위임한다. planmain.c의 파일 주석은 역할 분담을 정확히 명시한다. planner.c는 “서브셀렉트, 상속, 집계, 그룹핑 등”을 담당하고, planmain.c는 이 기능들이 “제거된” 기본 조인 연산 계획 수립을 위한 핵심 코드라고 설명한다.
flowchart TB
P["planner / standard_planner<br/>(문장별 진입점; PlannerGlobal 설정)"]
SQP["subquery_planner<br/>(Query 레벨별 호출: 끌어올리기, 정규화,<br/>상수 폴딩, 외부 조인 축소)"]
GP["grouping_planner<br/>(상위 연산: 집합 연산, GROUP/집계, 윈도우,<br/>DISTINCT, ORDER BY, LIMIT, ModifyTable)"]
QP["query_planner<br/>(스캔+조인 핵심 설정: 베이스 릴레이션, EC,<br/>조건식 분배, pathkeys)"]
MOR["make_one_rel<br/>(모든 스캔+조인 Path를 아래에서 위로 생성)"]
CP["create_plan<br/>(최저 비용 Path 하나를 Plan으로 변환)"]
P --> SQP
SQP --> GP
GP --> QP
QP --> MOR
MOR -.->|"최저 비용 Path를 가진<br/>최종 joinrel 반환"| GP
GP -.->|"UPPERREL_FINAL에<br/>상위 Path 적층"| SQP
SQP -.->|"PlannerInfo root 반환"| P
P --> CP
CP -.->|"PlannedStmt"| P
그림 1 — 세 단계로 중첩된 계획 수립 과정과 방출. planner가 외부 진입점이다. Query 레벨당 subquery_planner를 한 번 호출하고(서브 Query는 재귀), 이것이 상위 연산을 위해 grouping_planner를 호출하며, 다시 스캔·조인 핵심부를 위해 query_planner/make_one_rel을 호출한다. Path가 올라오면, 전체 Path 트리가 완성된 후에야 planner가 create_plan을 한 번 호출해 실행 가능한 Plan을 방출한다.
외부 진입점은 얇다. planner는 단지 훅 래퍼일 뿐이다. 실제 작업은 standard_planner에서 시작한다. 이 함수는 호출별 PlannerGlobal을 설정하고, 병렬 처리 가능 여부를 결정하며, tuple_fraction (호출자가 결과를 얼마나 소비할 가능성이 있는지)을 도출하고, subquery_planner를 호출한다. 계획 수립이 끝나면 Path→Plan 변환을 수행한다.
세 가지를 주목할 점이 있다. 첫째, 계획 수립과 방출이 명확히 분리된다. 전체 탐색이 경쟁하는 Path들로 가득 찬 RelOptInfo (final_rel)를 만들고, create_plan은 단 하나의 승자를 받아 한 번만 실행된다. 둘째, 승자는 get_cheapest_fractional_path가 선택하며 tuple_fraction을 반영한다. 결과의 일부만 가져오는 커서는 전체적으로 더 저렴한 계획보다 빠르게 시작하는 계획을 선호할 수 있다. 셋째, final_rel은 조인 탐색에서 직접 가져오는 것이 아니라 상위 릴레이션 레지스트리(UPPERREL_FINAL)에서 꺼낸다. 상위 릴레이션은 grouping_planner가 조인 이후 연산을 쌓는 곳이다.
subquery_planner는 Query 노드마다 한 번 호출되고 서브 Query가 있으면 재귀한다. 이것이 재작성/정규화 단계다. 여기서 모든 것은 비용 기반 선택이 아니라 무조건적 또는 지역 휴리스틱에 따라 적용되는 변환이다. 옵티마이저 README는 수행하는 작업을 정확히 나열한다.
-subquery_planner()
pull up sublinks and subqueries from rangetable, if possible
canonicalize qual ...
simplify constant expressions
process sublinks
convert Vars of outer query levels into Params
소스 관점에서, subquery_planner는 새로운 PlannerInfo (옵티마이저 전체에서 root로 불리는 쿼리별 계획 컨텍스트)를 할당한다. 서브링크와 단순 서브쿼리를 부모 jointree로 끌어올린다. 대상 목록과 조건식에 preprocess_expression을 실행한다(조인 별칭 Var 평탄화, 조건식을 CNF 유사 형태로 정규화, 상수 폴딩). 증명 가능하게 안전한 경우 외부 조인을 내부 조인으로 축소하고, 불필요한 RTE_RESULT 릴레이션을 제거한다. 그런 다음 상위 플래너에 넘기고 마무리한다.
/* Make sure we've identified the cheapest Path for the final rel. */
set_cheapest(final_rel);
return root;
끌어올리기, 조건식 정규화, 상수 폴딩의 메커니즘은 전처리 문서의 주제다. 여기서 핵심 사실은 경계다. grouping_planner가 실행될 시점에는, 이 레벨의 Query가 부모 조인 탐색에 참여할 수 있는 서브쿼리들이 이미 그렇게 처리된 상태로 정규화되어 있다. 조건식은 비용 기반 탐색이 정확하게 배치할 수 있는 표준 형태다.
grouping_planner는 스캔·조인 핵심부 위에 위치한 모든 것을 계획한다. 집합 연산(UNION/INTERSECT/EXCEPT), 그룹핑과 집계, 윈도우 함수, DISTINCT, ORDER BY, LIMIT/OFFSET, 그리고 SELECT가 아닌 문에서는 ModifyTable 노드가 여기에 속한다. 구조는 파이프라인이다. query_planner에서 최적의 스캔/조인 Path들을 받고, 쿼리에 필요한 각 상위 연산마다 새로운 상위 RelOptInfo를 만든다. 이 RelOptInfo의 Path들은 하위 Path들에 해당 연산의 Path 노드를 쌓은 것이다.
// ... DISTINCT, ORDER BY, LIMIT, ModifyTable each stack their own paths ...
current_rel = create_<op>_paths(root, current_rel, ...) 형태가 반복된다. 이것이 상위 플래너의 관용구다. 각 단계가 이전 릴레이션의 Path들을 소비하고 하나의 논리 연산을 추가한 새 릴레이션을 만든다. 각 단계가 add_path로 Path의 집합을 유지하기 때문에, 예를 들어 플래너는 GROUP BY의 해시 집계 구현과 정렬 후 그룹 구현 모두를 함께 유지했다가 최종 ORDER BY 단계에서 전체적으로 어느 쪽이 더 저렴한지 결정할 수 있다. 정렬 기반 그룹화는 나중의 정렬을 피할 수 있기 때문이다. 각 create_*_paths 빌더의 세부 사항은 계획 생성과 비용 문서에 속한다. 여기서 중요한 사실은 grouping_planner가 논리적 SQL 절이 상위 릴레이션 체인 위에서 쌓인 물리적 Path 대안들로 변하는 곳이라는 점이다. 체인은 UPPERREL_FINAL에서 끝난다.
query_planner (planmain.c)는 System-R 핵심부의 심장이다. 단 하나의 최적 Path를 선택하지 않는다. 그럴 수 없다. 위에 있는 grouping_planner가 아직 정렬/그룹/limit 결정을 내리지 않았고, 이 결정들이 어떤 스캔/조인 Path가 전체적으로 최선인지에 영향을 주기 때문이다. 대신 살아남은 모든 Path를 가진 최종 조인 RelOptInfo를 반환하고 호출자가 선택하게 한다. 자체적인 역할은 비용 기반 탐색을 설정하는 데 필요한 모든 것이다.
if (!final_rel ||!final_rel->cheapest_total_path || ...)
elog(ERROR, "failed to construct the join relation");
return final_rel;
이 순서는 의미가 있다. README의 “EquivalenceClasses와 PathKeys 처리 순서”를 반영한다. deconstruct_jointree가 조건식을 스캔하고 병합 가능한 등치 절(a = b)로부터 EquivalenceClass를 구성한다. 더 이상 병합이 불가능해진 후에야 (EC들이 “canonical”한 상태가 됨) qp_callback이 쿼리의 ORDER BY/GROUP BY에 대한 canonicalPathKey를 구성한다. PathKey는 Path 생성 전에 canonical해야 한다. 같은 정렬 순서를 가진 두 Path가 동일한 pathkey 리스트를 포인터로 비교할 수 있어야 하기 때문이다. query_planner 상단에는 단순 SELECT expr 경우(하나의 RTE_RESULT)에 대한 빠른 경로도 있다. 하나의 GroupResultPath를 만들고 전체 기계 없이 반환한다.
**RelOptInfo**는 플래너가 추론하는 하나의 릴레이션을 나타낸다. 베이스 릴레이션(테이블, FROM 절의 서브쿼리, FROM 절의 함수) 또는 조인 릴레이션(베이스 릴레이션들의 조합)이 될 수 있다. README의 불변식에 따르면, 구별되는 베이스 릴레이션 집합마다 정확히 하나의 RelOptInfo가 존재한다. (A⋈B)⋈C로 만들어지든 A⋈(B⋈C)로 만들어지든, 조인 {A B C}의 RelOptInfo는 하나다. 이 대안적 유도 방법들은 같은RelOptInfo 안에서 경쟁하는 서로 다른 Path들이다. 이 구조체는 후보 Path들과 캐시된 승자들을 담는다.
List *indexlist; /* IndexOptInfo list, for index paths */
BlockNumber pages;
Cardinality tuples; /* size estimates from pg_class */
PlannerInfo *subroot; /* if a subquery: its own planner context */
// ... condensed ...
} RelOptInfo;
**Path**는 부모 RelOptInfo의 행을 생성하는 하나의 방법이다. 의도적으로 가볍게 설계되었다. 공통 설계 절에서 언급한 계획 전용 스케치다. 기본 구조체는 탐색에 필요한 것만 담는다.
// struct Path — src/include/nodes/pathnodes.h
typedefstruct Path
{
NodeTag type;
NodeTag pathtype; /* tag identifying scan/join method */
RelOptInfo *parent; /* the relation this path can build */
PathTarget *pathtarget; /* list of Vars/Exprs, cost, width */
ParamPathInfo *param_info; /* parameterization info, or NULL */
bool parallel_aware;
bool parallel_safe;
int parallel_workers;
Cardinality rows; /* estimated number of result tuples */
int disabled_nodes;/* count of disabled-by-GUC nodes */
Cost startup_cost; /* cost before fetching any tuples */
Cost total_cost; /* total cost, all tuples fetched */
List *pathkeys; /* sort ordering of path's output */
} Path;
README는 Plan과의 관계를 정확히 기술한다. “Path 트리와 Plan 트리는 거의 일대일 대응이지만, Path 노드는 계획 수립 중에 필요하지 않을 정보를 생략하고, 실행기에서 필요하지 않을 계획 수립에 필요한 정보를 포함한다.” pathtype은 create_plan이 어떤 실행 노드를 만들지 알려주는 NodeTag (T_SeqScan, T_NestLoop, T_HashJoin, …)다. 조인 Path는 트리다. {A B C}에 대한 HashPath는 두 입력에 대한 좌우 서브Path를 가지며, 최종 Plan과 거울처럼 대응한다.
**Plan**은 실행기가 소비하는 실행 가능한 연산자 노드다. 문장마다 하나의 Plan 트리가 있으며, 승자 Path로부터 한 번 만들어진다. 이 구분은 형식적인 것이 아니다. 단일 joinrel의 pathlist는 탐색 중에 수십 개의 경쟁하는 Path를 담을 수 있지만, 그 중 하나만 Plan이 된다. 탐색 중에 Plan 대신 Path를 생성하는 것이 O(2^n) 열거를 감당 가능하게 만든다.
flowchart LR
subgraph ROI["RelOptInfo {A B}"]
direction TB
PL["pathlist:"]
P1["HashPath (cost 120)"]
P2["MergePath (cost 140, x 기준 정렬)"]
P3["NestPath (cost 900)"]
CT["cheapest_total_path → P1"]
end
P1 -.->|"add_path에서 살아남음"| keep1["유지"]
P2 -.->|"더 좋은 정렬 순서로 유지"| keep2["유지"]
P3 -.->|"지배됨 → 가지치기"| drop["버려짐"]
그림 2 — 릴레이션 집합마다 하나의 RelOptInfo, 그 안에서 경쟁하는 여러 Path. add_path는 비용/정렬 순서/파라미터화 조합의 틈새에서 최저 비용인 Path는 유지하고 지배된 것들은 가지치기한다. MergePath는 HashPath보다 비싸지만 x에 대한 정렬 순서가 상위에서 정렬을 절약할 수 있어서 살아남는다. set_cheapest가 이후 포인터들(cheapest_total_path 등)을 캐시한다. 최종 승자만 Plan이 된다.
set_rel_pathlist는 rel->rtekind / relkind에 따라 적절한 빌더로 전환한다. 일반 테이블에는 set_plain_rel_pathlist (순차 스캔 + 인덱스 Path + 비트맵 Path), 외부 테이블에는 set_foreign_pathlist, FROM 절의 함수에는 set_function_pathlist, 서브쿼리에는 set_subquery_pathlist (실제로는 set_rel_size 중에 실행) 등이 있다. 이 빌더들의 내용 (순차 스캔 Path의 비용 계산 방법, 인덱스 Path 선택 방법)은 postgres-path-generation.md와 postgres-cost-model.md의 주제다. 여기서 핵심 사실은 set_rel_pathlist가 모든 베이스 릴레이션의 끝에서 하는 일이다.
/* Now find the cheapest of the paths for this rel */
set_cheapest(rel);
모든 베이스 릴레이션은 조인 Path가 만들어지기 전에 완결된다. 최저 비용 Path가 캐시된다. 그런 다음 make_rel_from_joinlist가 조인 탐색을 이끈다. joinlist를 initial_rels 목록으로 변환하고(서브리스트로 재귀, FULL JOIN과 collapse-limit에 의해 차단된 조인은 중첩 유지), 릴레이션 수에 따라 디스패치한다.
flowchart BT
A["{A}"]
B["{B}"]
C["{C}"]
AB["{A B}"]
BC["{B C}"]
AC["{A C}"]
ABC["{A B C}"]
A --> AB
B --> AB
B --> BC
C --> BC
A --> AC
C --> AC
AB --> ABC
BC --> ABC
AC --> ABC
그림 3 — 동적 프로그래밍 조인 탐색, 아래에서 위로. 레벨 1은 베이스 릴레이션이다. join_search_one_level이 모든 2-항목 joinrel을 구성하고, 이어서 아래 레벨에서 모든 3-항목 joinrel을, 단일 최상위 릴레이션까지 구성한다. 각 joinrel은 그것을 포함하는 릴레이션이 만들어지기 전에 set_cheapest로 완결된다. README가 설명하는 성질이다. “주어진 릴레이션에 대한 모든 Path를 완성한 후에야 그 릴레이션을 포함하는 릴레이션에 대한 Path를 구성한다.” 열거 규칙 (어떤 쌍, 좌/우/부시, 외부 조인 재정렬의 적법성)은 postgres-join-ordering.md에 있다.
README는 이 순서가 중요한 이유를 설명한다. 모든 포함된 릴레이션이 먼저 완결되기 때문에, 플래너는 “상위 레벨 릴레이션이 알아야 하기 전에 각 릴레이션의 가장 저렴한 Path를 신뢰할 수 있게 식별할 수 있다”고 기술한다. 또한 “어떤 상위 레벨 조인 Path가 이미 해당 Path를 참조하고 있는지 걱정하지 않고, 같은 릴레이션에 대한 더 나은 Path를 찾았을 때 안전하게 Path를 버릴 수 있다”고 한다. 이것이 메모리 관리 보장으로 구체화된 최적성 원리다.
두 함수가 가지치기 규율을 강제한다. add_path는 후보 Path가 생성될 때마다 호출된다. 새 Path를 릴레이션의 pathlist에 삽입하고 이제 지배된 Path들을 제거한다. 새 Path 자체가 지배된 경우 거부할 수도 있다. 지배는 다차원적이다. Path가 다른 Path를 지배하려면 관련 비용 지표에서 비용이 같거나 적어야 하고, 정렬 순서(pathkeys)에서 나쁘지 않아야 하며, 파라미터화가 더 많지 않아야 한다. 그림 2의 MergePath가 더 저렴한 HashPath에도 살아남는 이유가 바로 이것이다. 정렬 순서가 해시 Path가 지는 차원이기 때문이다.
릴레이션에 대한 모든 Path가 추가되면 set_cheapest가 살아남은 pathlist를 한 번 순회하고 승자들을 RelOptInfo에 캐시한다.
동점 처리에 주목할 점이 있다. 비파라미터화 Path 두 개의 비용이 같을 때, set_cheapest는 정렬이 더 좋은 것을 유지한다. 정렬 순서를 일급 속성으로 보존하는 것이다. 결과가 상위 레벨(그리고 최종적으로는 상단의 get_cheapest_fractional_path)이 읽는 cheapest_total_path, cheapest_startup_path, cheapest_parameterized_paths다. compare_path_costs 뒤의 비용 공식은 postgres-cost-model.md의 주제다. 여기서 핵심 사실은 가지치기가 탐색 중에 계속 발생하고(add_path), 승자가 틈새별로 캐시된다는 점이다(set_cheapest).
create_scan_plan은 Path→Plan 변환을 구체적으로 보여준다. 부모 RelOptInfo에서 제한 절을 꺼내고(baserestrictinfo, 또는 인덱스 스캔의 경우 인덱스의 indrestrictinfo), Path가 파라미터화되어 있으면 파라미터화된 조인 절을 추가하며, 출력 tlist를 결정하고, 실행 가능한 스캔 노드를 만든다.
if (best_path->param_info) /* parameterized: add join clauses */
scan_clauses =list_concat_copy(scan_clauses,
best_path->param_info->ppi_clauses);
// ... choose tlist (physical vs. needed), build the scan Plan node ...
NestPath가 NestLoop으로 변하는 방법, 파라미터화된 스캔이 nestloop params를 연결하는 방법, 유사상수 조건에 게이팅 Result 노드가 삽입되는 방법 같은 노드별 빌더 본문은 postgres-plan-creation.md의 주제다. 여기서 핵심 사실은 create_plan이 결정론적인 구조 순회라는 점이다. 비용 결정은 탐색이 끝난 시점에 이미 완료되어 있다. 방출된 Plan 트리가 postgres-executor.md에서 다루는 것이다.
flowchart TB
BP["best_path (승자 Path 트리)"]
CPR["create_plan_recurse<br/>(pathtype에 따라 분기)"]
SCAN["create_scan_plan<br/>(SeqScan, IndexScan, ...)"]
JOIN["create_join_plan<br/>(NestLoop, MergeJoin, HashJoin)"]
OTHER["create_append/sort/agg/limit/...plan"]
PLAN["Plan 트리 (실행 가능)"]
BP --> CPR
CPR --> SCAN
CPR --> JOIN
CPR --> OTHER
CPR -.->|"서브Path로 먼저 재귀"| CPR
SCAN --> PLAN
JOIN --> PLAN
OTHER --> PLAN
그림 4 — create_plan이 하나의 승자 Path 트리를 위에서 아래로 구조적으로 순회한다. create_plan_recurse가 pathtype에 따라 분기하며 각 부모 노드를 만들기 전에 자식 서브Path로 재귀한다. 따라서 실행 가능한 Plan 트리는 단 하나의 선택된 Path 트리로부터 아래에서 위로 조립된다. 여기서는 비용 계산이 없다. 탐색은 끝났다.
옵티마이저는 방대하다(여기서 인용하는 여섯 파일의 총계는 약 29,000줄). 하지만 뼈대, 즉 진입점, 세 단계, Path 생성, 가지치기, 방출은 안정적인 함수들의 작은 집합이다. 위의 그림들이 추적하는 호출 흐름에 따라 아래에 그룹화했다. AM별 Path 빌더, 조인 열거 규칙, 비용 공식, 노드별 Path→Plan 본문은 형제 문서에 있다. 다음은 이것들을 묶는 골격이다.
standard_planner — planner 훅 래퍼 뒤의 실제 진입점. 호출별 PlannerGlobal을 구성하고, cursorOptions에서 tuple_fraction을 계산하며, 최상위 Query의 subquery_planner를 호출한 후 단 한 번의 방출을 수행한다. fetch_upper_rel(root, UPPERREL_FINAL, NULL) → get_cheapest_fractional_path → create_plan. 이후(set_plan_references, PlannedStmt 구성)는 탐색이 아닌 후처리다.
get_cheapest_fractional_path — 최종 릴레이션의 pathlist에서 승자를 선택하며 tuple_fraction을 반영한다. 호출자가 결과의 일부만 가져올 때 (a DECLARE CURSOR, a LIMIT) 전체적으로 더 저렴한 계획보다 빠르게 시작하는 계획이 이길 수 있다. 탐색이 cheapest_total_path와 함께 cheapest_startup_path를 유지하는 이유다.
subquery_planner — Query 노드마다 호출되고 서브 Query가 있으면 재귀한다. PlannerInfo(root)를 할당하고, 서브링크와 단순 서브쿼리를 끌어올리며(pull_up_sublinks, pull_up_subqueries), 대상 목록과 조건식에 preprocess_expression을 실행하고, 외부 조인을 축소하며(reduce_outer_joins), 불필요한 결과 RTE를 제거한 후 grouping_planner를 호출하고 SS_charge_for_initplans + set_cheapest(final_rel)로 마무리한다. 끌어올리기와 조건식 정규화의 메커니즘은 PostgreSQL 전처리 자료에 속한다. 경계 사실은 비용 기반 작업이 시작되기 전에 Query가 정규화된다는 점이다.
grouping_planner — 스캔/조인 핵심부 위의 모든 것을 계획한다. query_planner를 호출해 current_rel(최적의 스캔/조인 Path들)을 얻고, 최종 PathTarget을 구성하며, 새로운 상위 릴레이션으로 상위 연산을 쌓는다. create_grouping_paths (GROUP BY / 집계, 해시 방식과 정렬 방식 모두), create_window_paths (윈도우 함수), create_distinct_paths (DISTINCT), create_ordered_paths (최종 ORDER BY), LIMIT, DML의 경우 ModifyTable Path. current_rel = create_<op>_paths(root, current_rel, ...) 관용구가 일관된 흐름이다. 각 단계가 릴레이션의 pathlist를 소비하고 하나의 연산이 더 쌓인 새 릴레이션을 방출하며, UPPERREL_FINAL에서 끝난다.
query_planner (planmain.c) — 비용 기반 탐색을 설정하지만 단일 Path를 선택하지 않는다. 베이스 릴레이션 RelOptInfo들을 구성하고(add_base_rels_to_query), 조건식을 분배하며 EquivalenceClass들을 구성하고(deconstruct_jointree, reconsider_outer_join_clauses, generate_base_implied_equalities), EC들이 확정된 후에만 qp_callback을 호출해 canonicalPathKey를 구성하며, 최종적으로 make_one_rel을 호출한다. EC-before-pathkeys 순서는 README의 “EquivalenceClasses와 PathKeys 처리 순서”에 의해 규정된다.
make_one_rel (allpaths.c) — 두 단계 생성기. set_base_rel_sizes → set_base_rel_pathlists(모든 테이블별 접근 Path) → make_rel_from_joinlist(모든 조인 Path). all_query_rels를 커버하는 단일 최상위 joinrel을 반환한다.
set_base_rel_pathlists / set_rel_pathlist — 베이스 릴레이션들을 순회하고 각각을 rtekind/relkind에 따라 적절한 빌더로 디스패치한다(set_plain_rel_pathlist, set_foreign_pathlist, set_function_pathlist, …). set_rel_pathlist는 모든 베이스 릴레이션 끝에 set_rel_pathlist_hook 확장 지점, 선택적 generate_useful_gather_paths(병렬), 그리고 set_cheapest(rel)을 호출한다. 따라서 모든 베이스 릴레이션은 어떤 조인도 그것을 소비하기 전에 완결된다.
make_rel_from_joinlist — joinlist를 initial_rels로 변환하고 릴레이션 수에 따라 디스패치한다. 단일 항목은 직접 반환하고, 그렇지 않으면 join_search_hook을 반영하거나, enable_geqo && levels_needed >= geqo_threshold이면 geqo로, 그렇지 않으면 standard_join_search로 넘긴다.
standard_join_search — System-R 동적 프로그램. join_rel_level[]을 할당하고 레벨 1을 initial_rels로 초기화하며, 레벨 2부터 levels_needed까지 각 레벨에서 join_search_one_level(root, lev)를 호출하고, 이어서 generate_partitionwise_join_paths, 선택적 generate_useful_gather_paths, 각 방금 만들어진 joinrel마다 set_cheapest를 실행한다. 레벨별 루프가 모든 포함된 릴레이션이 그것을 포함하는 릴레이션보다 먼저 완결됨을 보장한다. 최적성 원리 메모리 보장이다. join_search_one_level 안의 열거 규칙은 postgres-join-ordering.md에 있다.
add_path — 생성된 Path마다 호출된다. Path를 릴레이션의 pathlist에 삽입하고 지금 지배하는 Path들을 제거한다(또는 신참이 지배되면 거부한다). 지배는 다차원적이다. 비용 지표에서 같거나 적고 pathkeys에서 나쁘지 않으며 파라미터화가 더 많지 않아야 한다. 따라서 비용은 더 비싸지만 정렬이 더 좋은 Path가 살아남는다.
add_path_precheck — 빌더가 어차피 버릴 Path를 구성하는 데 노력을 낭비하기 전에 호출하는 저렴한 사전 검사.
set_cheapest — 모든 Path가 추가된 후, 살아남은 pathlist를 한 번 순회하고 비파라미터화 Path들 사이에서 비용이 같은 경우 정렬 순서 동점 처리와 함께 cheapest_startup_path, cheapest_total_path, cheapest_parameterized_paths를 캐시한다.
create_plan — 선택된 Path를 받아 한 번 실행된다. create_plan_recurse(root, best_path, CP_EXACT_TLIST)를 호출하고, 최상위 tlist에 쿼리의 출력 컬럼 이름을 붙이며 initPlan들을 첨부한다.
create_plan_recurse — best_path->pathtype에 따라 분기하고 create_scan_plan(모든 스캔 태그), create_join_plan(NestLoop / MergeJoin / HashJoin), create_append_plan, 상위 노드 빌더(Result, Sort, Agg, Limit, ModifyTable, …)로 디스패치하며 서브Path로 먼저 재귀한다.
create_scan_plan — 스캔에 대한 구체적인 Path→Plan 변환. 부모 릴레이션에서 제한 절을 꺼내고(baserestrictinfo, 또는 인덱스의 indrestrictinfo), 파라미터화된 경우 ppi_clauses를 추가하며, 출력 tlist를 선택하고, 실행 가능한 스캔 노드를 만든다. 노드별 본문은 postgres-plan-creation.md이며, 여기서 핵심 사실은 비용 결정이 이 시점에서는 없다는 것이다. 순회는 순수하게 구조적이다.
아래의 모든 확인은 브랜치 REL_18_STABLE, 커밋 273fe94852b3a7e34fd171e8abdf1481beb302fa (PostgreSQL 18.x, 2026-06-05 커밋)의 /data/hgryoo/references/postgres를 기준으로 수행했다.
standard_planner가 세 개의 별도 문장으로 탐색과 방출을 분리한다.planner.c 456–459번째 줄에서 검증. final_rel = fetch_upper_rel(root, UPPERREL_FINAL, NULL), best_path = get_cheapest_fractional_path(final_rel, tuple_fraction), top_plan = create_plan(root, best_path). Path 탐색과 단일 create_plan 호출이 텍스트 상으로 분리되어 있다. 방출은 하나의 승자를 소비한다.
subquery_planner가 grouping_planner를 호출한 후 최종 상위 릴레이션에 set_cheapest를 호출한다.subquery_planner (planner.c 669번째 줄)를 읽어 검증. grouping_planner 이후 UPPERREL_FINAL을 꺼내고, init-plan 비용을 부과하며, root를 반환하기 전에 set_cheapest(final_rel)을 호출한다. 이 레벨의 Path 선택이 캐시된 cheapest 포인터로 호출자에게 위임됨을 확인한다.
make_one_rel이 진정으로 두 번의 패스다.allpaths.c 171번째 줄에서 검증. set_base_rel_sizes 다음 set_base_rel_pathlists 다음 make_rel_from_joinlist, 반환값에 Assert(bms_equal(rel->relids, root->all_query_rels))가 뒤따른다. 모든 베이스 릴레이션 접근 Path는 조인 Path가 만들어지기 전에 존재한다.
동적 프로그래밍 루프가 다음 레벨을 구성하기 전에 각 레벨을 완결한다.standard_join_search (allpaths.c 3457번째 줄)를 읽어 검증. for (lev = 2; lev <= levels_needed; lev++) 루프가 join_search_one_level을 호출하고, joinrel마다 generate_partitionwise_join_paths, generate_useful_gather_paths(최상위 릴레이션 제외), set_cheapest를 실행한다. README가 설명하는 최적성 원리 메모리 보장이다.
README가 Path↔Plan 대응을 명시적으로 기술한다.src/backend/optimizer/README 23번째 줄에서 검증. “Path 트리와 Plan 트리는 거의 일대일 대응이지만, Path 노드는 계획 수립 중에 필요하지 않을 정보를 생략하고, 실행기에서 필요하지 않을 계획 수립에 필요한 정보를 포함한다.” 이것이 §“PostgreSQL의 구현”의 RelOptInfo/Path/Plan 구조에 대한 근거다.
EC-before-PathKey 순서는 의도된 것이며 우발적인 것이 아니다. README의 “EquivalenceClasses와 PathKeys 처리 순서” (1026번째 줄)에서 검증. EC는 deconstruct_jointree / reconsider_outer_join_clauses 중에 구성된다. 더 이상 병합이 불가능해진 후에만 “canonical”이 되어 PathKey들이 구성된다. query_planner가 generate_base_implied_equalities이후에qp_callback을 호출하는 이유다.
struct Path는 계획 수립에 관련된 필드만 담고 실행 세부 사항은 없다.pathnodes.h 1753번째 줄에서 검증. 기본 구조체는 pathtype, parent, pathtarget, param_info, 병렬 플래그, rows, disabled_nodes, startup_cost, total_cost, pathkeys를 담으며 실행기 상태는 없다. RelOptInfo (883번째 줄)는 본문에서 인용한 pathlist, partial_pathlist, 네 개의 cheapest_* 슬롯을 담는다.
disabled_nodes 대 add_path / set_cheapest에서의 레거시 disable_cost.Path 구조체 (1753번째 줄)는 정수 disabled_nodes 카운트를 담으며, compare_path_costs_fuzzily가 비용보다 먼저 이 값을 고려한다. add_path / set_cheapest 내에서 disabled_nodes, startup_cost, total_cost 사이의 정확한 동점 처리 순서는 여기서 완전히 추적하지 않았다. 조사 경로: pathnode.c의 compare_path_costs_fuzzily와 compare_path_costs를 읽고 disabled_nodes가 엄격하게 우선임을 확인한다. (postgres-cost-model.md에 속함.)
상위 릴레이션 파라미터화.UPPERREL_* 릴레이션이 파라미터화된 Path를 담는지 여부는 검증하지 않았다. 본문은 파라미터화 속성이 스캔/조인 릴레이션에만 해당한다고 본다. 조사 경로: planner.c의 create_*_paths에서 상위 Path에 대한 param_info 사용을 grep한다.
create_plan_recurse에 도달하는 pathtype 태그의 전체 집합. 본문은 주요 경우들을 나열한다. create_plan_recurse의 전체 switch (createplan.c 388번째 줄)에는 더 많은 경우가 있다(예: T_TidScan, T_TableFuncScan, T_NamedTuplestoreScan, T_CustomScan). 완전한 열거는 postgres-plan-creation.md로 위임한다.
System R / Selinger (SIGMOD 1979).Access Path Selection in a Relational Database Management System은 이 옵티마이저의 직접 선조다. 릴레이션 부분집합에 대한 아래에서 위로의 동적 프로그래밍, 흥미로운 정렬 순서, 카탈로그 통계 비용 모델이 핵심이다. research/dbms-papers/systemr-optimizer.md에 캡처되어 있다. PostgreSQL의 Path, pathkeys, add_path, standard_join_search는 한 줄 한 줄 그 후손이다. 하나의 구조적 추가가 있다. 탐색과 실행 계획 사이에 명시적인 Path 추상화를 삽입한 것이다.
Fong, The Design and Implementation of the POSTGRES Query Optimizer (UCB 석사 논문). System-R 비용 모델이 어떻게 Berkeley POSTGRES 코드베이스에 적용되었는지 기술한다. 오늘날의 src/backend/optimizer/의 선조가 그 코드베이스다. RelOptInfo, Path, RestrictInfo라는 명명 계보가 여기서 나온다. 집중적으로 읽으면 현재의 어떤 동작이 원래 POSTGRES에서 온 것이고 어떤 것이 나중에 추가된 것인지 파악할 수 있다.
Cascades / Volcano (Graefe). 아래에서 위로의 동적 프로그래밍에 대한 지배적 대안이다. 메모의 동치 그룹에 대한 하향식, 메모이제이션, 규칙 기반 탐색으로, SQL Server와 Apache Calcite에서 사용된다. PostgreSQL의 RelOptInfo는 메모 그룹의 유사체다. 하지만 탐색은 변환 규칙이 아닌 아래에서 위로의 동적 프로그래밍이다. 나란히 비교하면 PostgreSQL이 변환 규칙 엔진을 갖지 않음으로써 무엇을 얻고 잃는지 명확해진다. 새로운 대수적 재작성을 추가하기 어렵지만 탐색이 더 단순하고 예측 가능하다.
GEQO — 대형 조인 탈출구인 유전 알고리즘.geqo_threshold (기본값 12) 이상에서 PostgreSQL은 철저한 동적 프로그래밍을 포기하고 유전 알고리즘(geqo)을 사용한다. 고전적 비교 대상은 무작위 조인 열거 문헌(Ioannidis & Kang, 시뮬레이티드 어닐링 / 반복 개선)이다. postgres-join-ordering.md의 전용 주석이 교차 지점에서의 계획 품질 대 계획 수립 시간을 측정해야 한다.
적응형 / 학습된 쿼리 최적화. 현대 연구(Bao, Neo, Balsa; Spark/Presto의 적응형 실행)는 정적 비용 모델을 런타임 피드백이나 학습된 비용 추정기로 대체하거나 보완한다. PostgreSQL의 옵티마이저는 완전히 정적이다. 실행 전에 하나의 계획을 확정한다. Path/비용 분리가 정확히 학습된 비용 추정기가 주입될 이음새다. postgres-cost-model.md가 완성되면 이것이 자연스러운 프론티어 주석이 된다.