(KO) PostgreSQL 경로 생성 — 스캔·조인 경로 빌더, add_path 지배 가지치기, Pathkeys

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

학술적 배경

비용 기반 옵티마이저(cost-based optimizer)가 후보 전략들을 순위 매기려면 먼저 각 릴레이션에 대한 물리적 접근 전략을 열거해야 한다. System R 옵티마이저(Selinger et al., “Access Path Selection in a Relational Database Management System,” SIGMOD 1979, research/dbms-papers/systemr-optimizer.md 참고)는 이 열거 단위를 **접근 경로(access path)**라 명명했다. 기본 릴레이션에 대한 접근 경로란 스캔 방법·적용 가능한 조건 술어·출력 정렬 순서의 특정 조합이다. 조인 경로는 외부 경로와 내부 경로를 특정 조인 알고리즘으로 결합한 것이다. System R의 핵심 통찰은 경로가 생성과 폐기 비용이 낮다는 점이다. 수천 개의 후보를 평가하지만 실행 가능한 계획(plan)으로 실체화되는 것은 최종 승자 하나뿐이다.

Database Internals (Petrov, ch. 7)은 이 과정을 **계획 공간 열거(plan-space enumeration)**로 정의한다. 옵티마이저는 후보 전략들을 아래에서 위로 격자 형태로 쌓아올리며, 각 수준에서 파레토 최적 전선(Pareto-optimal frontier)만 남긴다. 파레토 지배 기준은 “모든 관련 차원에서 다른 후보에 열등하지 않은 경우만 살아남는다”는 것이다. 이 가지치기 규칙이 검색을 현실적인 규모로 유지하게 해준다.

접근 경로 시스템이 반드시 다루어야 할 두 가지 차원이 있다.

단일 테이블에 대한 물리적 접근 전략. 힙(heap) 릴레이션의 경우 순차 스캔, 인덱스 스캔(적용 가능한 인덱스별 하나씩), 인덱스 온리 스캔(index-only scan), 비트맵 인덱스 스캔(여러 인덱스를 AND/OR로 결합 가능), TID 스캔이 선택지다. 각각 시작 비용·총 비용·출력 정렬 순서가 다르다.
정렬 순서를 일급(first-class) 속성으로 취급. 경쟁 후보보다 비용이 더 들더라도 조인 키나 ORDER BY 컬럼 기준으로 미리 정렬된 행을 출력하는 계획이 전체적으로 더 유리할 수 있다. 하류(downstream) 정렬 단계를 제거할 수 있기 때문이다. System R은 이를 **흥미로운 정렬 순서(interesting sort order)**라 부르며, 비정렬 최저 비용 경로 외에 각 흥미로운 정렬 순서별 최저 비용 경로를 명시적으로 유지한다. 이것이 PostgreSQL의 pathkeys 개념의 씨앗이다.

접근 경로 계층은 두 가지 인접 관심사 사이에 위치한다. 한쪽은 비용 추정(costsize.c, postgres-cost-model.md)이고, 다른 쪽은 조인 순서 열거(joinpath.c, joinrels.c, postgres-join-ordering.md)다. 이 문서는 스캔 수준 빌더, add_path, pathkeys 시스템만 다룬다.

DBMS 공통 설계 패턴

지배 가지치기를 갖춘 릴레이션별 후보 목록

모든 비용 기반 옵티마이저는 릴레이션별로 후보 목록을 관리한다. 새 후보가 도착할 때마다 목록을 훑어 새 후보가 기존 항목을 지배하는지, 또는 기존 항목이 새 후보를 지배하는지 확인한다. “지배한다”는 것은 모든 관련 차원에서 동등하거나 우월하다는 뜻이다. 지배당한 쪽은 즉시 폐기된다.

지배 판단에 사용되는 차원은 엔진마다 다르다. 비용(시작 비용과 총 비용), 출력 정렬 순서, 필요한 외부 릴레이션(매개변수화), 행 수, 그리고 현대 엔진에서는 병렬 안전성도 포함된다. 차원이 넓을수록 더 많은 후보가 살아남지만(모든 축에서 지배하기가 어렵기 때문), 그만큼 탐색이 더 철저해진다.

스캔 경로 생성과 조인 경로 생성의 분리

거의 모든 진지한 옵티마이저는 기본 릴레이션 스캔을 조인 순서와 별개의 하위 문제로 처리한다. 기본 릴레이션 경로를 먼저 완전히 생성하고 가지치기한 뒤, 조인 경로가 그 승자들을 조합하는 방식이다. 이 분리가 깔끔한 이유는 기본 릴레이션 경로가 조인 순서에 의존하지 않기 때문이다. 단, 매개변수화 경로(다른 릴레이션에서 값을 참조하는 인덱스 스캔)는 예외적으로 어떤 외부 릴레이션이 사용 가능한지에 의존한다.

인덱스 경로 생성: 조건 절을 인덱스 컬럼에 매칭

인덱스 경로 생성은 접근 경로 열거에서 가장 복잡한 부분이다. 표준적인 구현 패턴은 세 단계로 구성된다.

WHERE/ON 조건을 인덱스 컬럼에 매칭. col OP constant 형태(또는 매개변수화 경로의 경우 col OP col2)의 조건은, 연산자 OP가 해당 인덱스의 연산자 클래스에 속하는 경우 인덱스 컬럼 col을 활용할 수 있다. 실제로 인덱스가 행을 걸러내려면 조건이 인덱스 키 컬럼 접두사(prefix)와 매칭되어야 한다.
일반 스캔·인덱스 온리 스캔·비트맵 스캔 간 선택. 일반 인덱스 스캔은 인덱스 리프 항목을 따라가며 인덱스 순서대로 힙 페이지를 하나씩 가져온다. 인덱스 온리 스캔은 필요한 컬럼이 모두 인덱스에 포함된 경우 힙을 전혀 방문하지 않고 읽는다. 비트맵 스캔은 먼저 매칭되는 모든 TID를 비트맵으로 수집한 뒤 물리적 순서로 힙 페이지를 가져온다. 많은 행이 매칭되고 선택도(selectivity)가 중간 수준일 때 더 유리한 전략이다. 엔진은 보통 세 가지 변형을 모두 생성하고 비용 모델이 선택하도록 한다.
부분 인덱스와 EquivalenceClass 파생 조건 처리. 부분 인덱스(정의에 WHERE 조건이 있는 인덱스)는 쿼리의 조건이 해당 인덱스 조건을 함의할 때만 유용하다. EquivalenceClass 파생 조건(예: a = b이고 b = 5이면 a = 5를 생성할 수 있음)은 원본 쿼리에 명시되지 않은 추가 인덱스 경로를 열어줄 수 있다.

Pathkeys: 정렬 순서를 정규 대수 구조로

System R의 흥미로운 정렬 순서 처리는 임시방편적이다. 미리 식별된 소수의 순서만 검사한다. 더 원칙적인 접근 방법은 정렬 순서를 *서로 같다고 증명된 표현식의 동치류(equivalence class)*를 참조하는 데이터 구조로 정규화하는 것이다. a.x = b.y (조인 조건 또는 필터)가 있다면 a.x 기준 정렬은 b.y 기준 정렬과 동일하다. 이 사실을 추적하는 엔진이라면, a.x에 대한 인덱스 스캔이 ORDER BY b.y를 추가 정렬 없이 충족시킨다는 것을 인식할 수 있다. 관련 조인 컨텍스트에서 a.x ≡ b.y이기 때문이다.

이론 ↔ PostgreSQL 매핑

이론 / 패턴	PostgreSQL 이름
릴레이션별 후보 목록	`RelOptInfo.pathlist`
추가 시 지배 가지치기	`add_path`
차원별 최저 비용 경로 캐시	`cheapest_startup_path`, `cheapest_total_path`, `cheapest_parameterized_paths`
기본 릴레이션 순차 스캔 경로	`pathtype = T_SeqScan`인 `Path`; `create_seqscan_path`로 생성
기본 릴레이션 인덱스 스캔 경로	`IndexPath`; `create_index_paths` 내부 `build_index_paths`로 생성
다중 인덱스 비트맵 스캔	`BitmapAndPath`/`BitmapOrPath`로 구성된 `BitmapHeapPath`
매개변수화 경로 (인덱스 조인 조건)	`param_info`가 NULL이 아닌 `IndexPath`
TID 스캔	`TidPath` / `TidRangePath`; `create_tidscan_paths`로 생성
병렬 스캔 조각	`RelOptInfo.partial_pathlist`의 partial path; `create_gather_path`로 수집
흥미로운 정렬 순서	`Path.pathkeys` — `PathKey` 리스트
정규 정렬 순서 표현식	`EquivalenceClass`를 참조하는 `PathKey`
동일 표현식들의 동치류	`PlannerInfo.eq_classes` 내 `EquivalenceClass`

PostgreSQL의 구현

개요: make_one_rel의 2-패스 구조

make_one_rel (allpaths.c:171)은 query_planner가 최종 조인 RelOptInfo를 생성하기 위해 호출하는 함수다. 이 함수는 엄격한 순서의 2-패스 구조를 갖는다.

// make_one_rel — src/backend/optimizer/path/allpaths.c
RelOptInfo *
make_one_rel(PlannerInfo *root, List *joinlist)
{
    /* 패스 1: 크기 추정 (매개변수화 경로 비용 계산에 필요) */
    set_base_rel_sizes(root);

    /* 비용 모델을 위한 total_table_pages 집계 */
    total_pages = 0;
    for (rti = 1; rti < root->simple_rel_array_size; rti++) { ... }
    root->total_table_pages = total_pages;

    /* 패스 2: 기본 릴레이션의 모든 스캔 경로 생성 */
    set_base_rel_pathlists(root);

    /* 조인 탐색: 최종 조인 릴레이션 생성 */
    rel = make_rel_from_joinlist(root, joinlist);
    return rel;
}

set_base_rel_sizes가 set_base_rel_pathlists보다 먼저 실행되어야 하는 이유는 다음과 같다. 매개변수화 인덱스 경로는 루프 횟수 조정 비용을 계산하기 위해 외부 릴레이션의 카디널리티 추정값이 필요하기 때문이다. make_rel_from_joinlist는 조인 순서 탐색의 진입점이며 postgres-join-ordering.md에서 다룬다.

set_base_rel_pathlists: RTE 유형별 분기

set_base_rel_pathlists (allpaths.c:333)는 root->simple_rel_array를 순회하며 기본 릴레이션마다 set_rel_pathlist를 호출한다. set_rel_pathlist (allpaths.c:469)는 RTE 종류에 따라 분기한다.

// set_rel_pathlist — src/backend/optimizer/path/allpaths.c
static void
set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
                 Index rti, RangeTblEntry *rte)
{
    if (IS_DUMMY_REL(rel))
        /* 이미 빈 릴레이션임이 증명됨, 할 일 없음 */;
    else if (rte->inh)
        set_append_rel_pathlist(root, rel, rti, rte);  /* 파티셔닝/상속 */
    else {
        switch (rel->rtekind) {
            case RTE_RELATION:
                if (rte->relkind == RELKIND_FOREIGN_TABLE)
                    set_foreign_pathlist(root, rel, rte);
                else if (rte->tablesample != NULL)
                    set_tablesample_rel_pathlist(root, rel, rte);
                else
                    set_plain_rel_pathlist(root, rel, rte);  /* 일반 힙 */
                break;
            case RTE_FUNCTION:  set_function_pathlist(...); break;
            case RTE_VALUES:    set_values_pathlist(...);   break;
            /* RTE_SUBQUERY, RTE_CTE 등은 set_rel_size 단계에서 처리 */
        }
    }
    /* 플러그인 훅: 확장 모듈이 경로를 추가/제거할 수 있음 */
    if (set_rel_pathlist_hook)
        (*set_rel_pathlist_hook)(root, rel, rti, rte);

    /* 부분 경로를 Gather 경로로 수집 (병렬 처리) */
    if (rel->reloptkind == RELOPT_BASEREL &&
        !bms_equal(rel->relids, root->all_query_rels))
        generate_useful_gather_paths(root, rel, false);

    /* cheapest 포인터를 RelOptInfo 필드에 고정 */
    set_cheapest(rel);
}

세 가지 사항을 주목할 필요가 있다. 첫째, set_rel_pathlist_hook은 커스텀 스캔 제공자(CustomPath)를 위한 확장 지점이다. 둘째, 병렬 부분 경로는 generate_useful_gather_paths가 여기서 수집한다. 이 함수는 partial_pathlist 항목들을 GatherPath 또는 GatherMergePath 노드로 감싸 메인 pathlist에 추가한다. 셋째, 모든 기본 릴레이션 분기가 끝난 후 set_cheapest가 실행되어 조인 탐색이 시작되기 전에 cheapest_total_path가 고정된다.

set_plain_rel_pathlist: 세 가지 스캔 패밀리

일반 힙 테이블의 경우, set_plain_rel_pathlist (allpaths.c:768)는 정확히 세 가지 스캔 패밀리를 추가한다.

// set_plain_rel_pathlist — src/backend/optimizer/path/allpaths.c
static void
set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
{
    Relids  required_outer = rel->lateral_relids;

    /* TID 스캔 (CurrentOfExpr가 있으면 강제; 이 경우 즉시 반환) */
    if (create_tidscan_paths(root, rel))
        return;

    /* 순차 스캔 — 항상 추가 */
    add_path(rel, create_seqscan_path(root, rel, required_outer, 0));

    /* 병렬 순차 스캔 조각 */
    if (rel->consider_parallel && required_outer == NULL)
        create_plain_partial_paths(root, rel);

    /* 적용 가능한 모든 인덱스 경로 */
    create_index_paths(root, rel);
}

순차 스캔은 무조건 추가된다. 비용이 아무리 높더라도 항상 유효한 선택지이기 때문이다. create_tidscan_paths는 CurrentOfExpr(커서 위치 갱신/삭제)가 있을 때만 true를 반환하며, 이 경우 다른 경로 유형은 실행기가 처리할 수 없으므로 즉시 반환한다. 대부분의 작업은 create_index_paths에서 처리된다.

create_index_paths: 인덱스 경로 생성기

create_index_paths (indxpath.c:240)는 rel->indexlist(IndexOptInfo 구조체 리스트)를 순회하며 인덱스마다 3단계 조건 매칭 파이프라인을 실행한다.

// create_index_paths — src/backend/optimizer/path/indxpath.c
void
create_index_paths(PlannerInfo *root, RelOptInfo *rel)
{
    /* 릴레이션의 각 인덱스에 대해: */
    foreach(lc, rel->indexlist)
    {
        IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);

        /* 쿼리를 만족하지 않는 부분 인덱스는 건너뜀 */
        if (index->indpred != NIL && !index->predOK)
            continue;

        /* 1단계: WHERE/baserestrictinfo를 인덱스 컬럼에 매칭 */
        match_restriction_clauses_to_index(root, index, &rclauseset);
        get_index_paths(root, rel, index, &rclauseset, &bitindexpaths);

        /* 2단계: 조인 조건 매칭 (EC에 병합되지 않은 느슨한 조인 절) */
        match_join_clauses_to_index(root, rel, index,
                                    &jclauseset, &joinorclauses);

        /* 3단계: EC 파생 조인 조건 매칭 */
        match_eclass_clauses_to_index(root, index, &eclauseset);

        /* 2+3단계를 결합해 매개변수화 인덱스 경로 생성 */
        if (jclauseset.nonempty || eclauseset.nonempty)
            consider_index_join_clauses(root, rel, index,
                                        &rclauseset, &jclauseset,
                                        &eclauseset, &bitjoinpaths);
    }

    /* 제한 조건 비트맵을 하나의 BitmapHeapPath로 병합 */
    if (bitindexpaths != NIL) {
        bitmapqual = choose_bitmap_and(root, rel, bitindexpaths);
        bpath = create_bitmap_heap_path(root, rel, bitmapqual,
                                        rel->lateral_relids, 1.0, 0);
        add_path(rel, (Path *) bpath);
        if (rel->consider_parallel && rel->lateral_relids == NULL)
            create_partial_bitmap_paths(root, rel, bitmapqual);
    }

    /* 조인 비트맵: 고유 매개변수화별로 BitmapHeapPath 하나씩 */
    if (bitjoinpaths != NIL) { /* ... */ }
}

1단계(match_restriction_clauses_to_index)는 rel->baserestrictinfo를 순회하며 각 RestrictInfo를 인덱스 키 컬럼과 대조한다. 매칭에는 연산자가 인덱스 연산자 패밀리에 속해야 하고 인덱스 가능한 컬럼이 적절한 쪽에 있어야 한다. get_index_paths는 build_index_paths를 호출해 일반 스캔용 IndexPath(IndexScan 또는 IndexOnlyScan)를 add_path에 넘겨 추가하고, 비트맵 집계 후보 리스트에 IndexPath를 축적한다.

2단계와 3단계는 매개변수화 인덱스 경로를 찾는다. 이는 인덱스 조건이 다른 릴레이션에서 가져온 값을 참조하는 인덱스 스캔이다(예: WHERE a.x = b.y는 중첩 루프 조인에서 b.y가 외부 릴레이션으로 제공될 때 a.x 인덱스를 사용할 수 있다). 2단계는 명시적 조인 절을 매칭하고, 3단계는 쿼리의 EquivalenceClass 그래프에서 파생될 수 있는 조건을 매칭한다.

마지막 비트맵 경로 조합 단계(choose_bitmap_and)도 중요하다. 여러 인덱스가 각각 다른 부분 집합의 적격 행을 커버할 때, 그 TID 비트맵을 AND로 결합하면 가져와야 할 힙 페이지 수를 줄일 수 있다. costsize.c의 비용 모델은 결합된 비트맵 스캔이 개별 인덱스 스캔보다 저렴한지 평가한다.

그림 1 — 인덱스별 create_index_paths 조건 파이프라인

flowchart TD
  A["create_index_paths\n(rel->indexlist 루프)"]
  B["match_restriction_clauses_to_index\n(WHERE / baserestrictinfo)"]
  C["get_index_paths → build_index_paths\n(IndexPath, IndexOnlyScan, 비트맵)"]
  D["match_join_clauses_to_index\n(명시적 조인 조건)"]
  E["match_eclass_clauses_to_index\n(EC 파생 조인 조건)"]
  F["consider_index_join_clauses\n(매개변수화 IndexPath + 비트맵)"]
  G["choose_bitmap_and\n→ BitmapHeapPath (제한 조건)"]
  H["choose_bitmap_and × 매개변수화\n→ BitmapHeapPath (조인)"]

  A --> B --> C
  A --> D
  A --> E
  D & E --> F
  C -->|"bitindexpaths"| G
  F -->|"bitjoinpaths"| H

그림 1 — create_index_paths 내부의 3단계 조건 매칭 파이프라인. 외부 foreach(lc, rel->indexlist) 루프를 한 번 통과할 때마다 인덱스 하나당 1~3단계가 실행된다. 모든 인덱스에서 누적된 비트맵 경로들은 루프 종료 후 하나의 BitmapHeapPath(제한 조건) 또는 매개변수화별로 하나씩(조인)으로 조합된다.

Path 구조체: 타입 계층

모든 경로는 구체적인 스캔 또는 조인 알고리즘을 식별하는 pathtype 태그를 가진 Path 노드다. 특수화된 경로들은 첫 번째 멤버로 Path를 포함하는 표준 C 구조체 상속 패턴을 사용한다.

// Path (기본) — src/include/nodes/pathnodes.h
typedef struct Path {
    NodeTag     type;
    NodeTag     pathtype;       /* T_SeqScan, T_IndexScan, T_NestLoop 등 */
    RelOptInfo *parent;         /* 이 경로가 생성하는 릴레이션 */
    PathTarget *pathtarget;     /* 출력 컬럼 목록 */
    ParamPathInfo *param_info;  /* NULL = 비매개변수화 */
    bool        parallel_aware;
    bool        parallel_safe;
    int         parallel_workers;
    Cardinality rows;
    int         disabled_nodes; /* GUC로 비활성화된 계획 노드 수 */
    Cost        startup_cost;
    Cost        total_cost;
    List       *pathkeys;       /* 정렬 순서: PathKey 리스트 */
} Path;

// IndexPath — src/include/nodes/pathnodes.h
typedef struct IndexPath {
    Path        path;           /* pathtype = T_IndexScan 또는 T_IndexOnlyScan */
    IndexOptInfo *indexinfo;
    List       *indexclauses;   /* IndexClause 리스트 */
    List       *indexorderbys;  /* 인덱스 AM이 사용할 수 있는 ORDER BY 표현식 */
    ScanDirection indexscandir;
    Cost        indextotalcost;
    Selectivity indexselectivity;
} IndexPath;

// BitmapHeapPath — src/include/nodes/pathnodes.h
typedef struct BitmapHeapPath {
    Path        path;           /* pathtype = T_BitmapHeapScan; pathkeys = NIL */
    Path       *bitmapqual;     /* IndexPath, BitmapAndPath, 또는 BitmapOrPath */
} BitmapHeapPath;

disabled_nodes 필드는 최근 PG 릴리스에서 추가된 것으로, 경로 트리에서 GUC로 비활성화된 계획 유형을 사용하는 노드의 수를 센다(예: enable_seqscan = off). add_path는 disabled_nodes를 비용보다 높은 차원의 비용 요소로 취급한다. 비활성화된 노드가 적은 경로는 추정 비용에 상관없이 더 많은 노드를 쓰는 경로를 항상 이긴다. enable_seqscan = off가 실제로 작동하는 방식이 바로 이것이다. 순차 스캔 경로가 pathlist에서 제거되는 것이 아니라, disabled_nodes 페널티가 붙어 add_path 비교에서 탈락한다.

조인 경로들은 JoinPath 구조체(Path에 외부/내부 서브 경로와 조인 타입을 추가)를 포함하며, 각 알고리즘별 특수화가 있다.

// NestPath / MergePath / HashPath — src/include/nodes/pathnodes.h
typedef struct NestPath  { JoinPath jpath; } NestPath;

typedef struct MergePath {
    JoinPath jpath;
    List    *path_mergeclauses;
    List    *outersortkeys;     /* NIL = 외부 경로가 이미 정렬됨 */
    List    *innersortkeys;     /* NIL = 내부 경로가 이미 정렬됨 */
    int      outer_presorted_keys;  /* 증분 정렬 적합성 판단용 */
    bool     skip_mark_restore;
    bool     materialize_inner;
} MergePath;

typedef struct HashPath {
    JoinPath jpath;
    List    *path_hashclauses;
    int      num_batches;
    Cardinality inner_rows_total;
} HashPath;

add_path: 지배 가지치기 규칙

add_path (pathnode.c:464)는 새 후보 경로가 생성될 때마다 호출된다. rel->pathlist의 모든 기존 경로를 순회하며 파레토 지배 검사를 수행한다. 새 경로가 비용·pathkeys·매개변수화·행 수·병렬 안전성 모든 차원에서 기존 경로보다 동등하거나 우월하고 적어도 하나에서 엄격히 우월하면 기존 경로가 지배당한 것이다.

// add_path — src/backend/optimizer/util/pathnode.c
void
add_path(RelOptInfo *parent_rel, Path *new_path)
{
    bool accept_new = true;
    /* 매개변수화 경로는 NIL pathkeys로 취급 —
       정렬 순서 기준으로는 이길 수 없고, 비용으로만 경쟁 */
    new_path_pathkeys = new_path->param_info ? NIL : new_path->pathkeys;

    foreach(p1, parent_rel->pathlist) {
        Path *old_path = (Path *) lfirst(p1);
        bool  remove_old = false;

        costcmp = compare_path_costs_fuzzily(new_path, old_path, STD_FUZZ_FACTOR);
        /* 비용이 양방향으로 다르면 둘 다 유지 (지배 없음) */
        if (costcmp != COSTS_DIFFERENT) {
            keyscmp = compare_pathkeys(new_path_pathkeys, old_path_pathkeys);
            if (keyscmp != PATHKEYS_DIFFERENT) {
                outercmp = bms_subset_compare(PATH_REQ_OUTER(new_path),
                                              PATH_REQ_OUTER(old_path));
                /* costcmp, keyscmp, outercmp, rows, parallel_safe의
                   모든 조합을 검사해 remove_old 또는 accept_new=false 설정 */
            }
        }
        if (remove_old) { /* pathlist에서 old 제거, IndexPath가 아니면 pfree */ }
        else if (new_path->total_cost >= old_path->total_cost) insert_at++;
        if (!accept_new) break;
    }
    if (accept_new)
        parent_rel->pathlist = list_insert_nth(parent_rel->pathlist,
                                               insert_at, new_path);
    else
        if (!IsA(new_path, IndexPath)) pfree(new_path);
}

add_path에 내재된 세 가지 설계 선택을 짚어볼 필요가 있다.

첫째, 매개변수화 경로는 NIL pathkeys로 처리된다는 점이다. 매개변수화 경로가 정렬 순서 기준으로 이길 수 있다면, 덜 매개변수화된 경로가 단순히 경쟁 상대가 정렬되어 있다는 이유로 폐기될 수 있다. 그러면 조인 토폴로지가 바뀔 때 비매개변수화 선택지가 사라지는 문제가 생긴다. 매개변수화 경로를 비정렬로 취급하면 살아남는 수가 제한되어 pathlist가 관리 가능한 크기로 유지된다.

둘째, 비용 비교에 퍼지(fuzz) 처리를 한다는 점이다. compare_path_costs_fuzzily는 작은 퍼지 계수(STD_FUZZ_FACTOR = 1.01)를 사용해 1% 미만의 차이는 동일 비용으로 처리한다. 이는 플랫폼별 부동소수점 반올림 오차로 인해 의도치 않게 다른 계획이 생성되는 것을 방지한다.

셋째, IndexPath 노드는 절대 pfree되지 않는다는 점이다. IndexPath 객체는 독립 경로로도, BitmapHeapPath의 자식으로도 참조될 수 있다. 따라서 add_path는 IndexPath를 거부할 때 pfree를 건너뛰어 이미 해당 포인터를 가진 BitmapHeapPath의 댕글링 포인터(dangling pointer) 문제를 방지한다.

set_cheapest: 승자 고정

릴레이션의 모든 경로에 add_path 처리가 끝난 후, set_cheapest (pathnode.c:272)는 살아남은 pathlist를 훑어 RelOptInfo에 네 개의 포인터를 고정한다.

// set_cheapest — src/backend/optimizer/util/pathnode.c
void
set_cheapest(RelOptInfo *parent_rel)
{
    /* pathlist 순회 (disabled_nodes 기준, 그 다음 total_cost 기준 정렬됨) */
    foreach(p, parent_rel->pathlist) {
        Path *path = (Path *) lfirst(p);
        if (path->param_info) {
            parameterized_paths = lappend(parameterized_paths, path);
            /* (최소 매개변수화 기준, 그 다음 비용 기준으로) best_param_path 추적 */
        } else {
            /* cheapest_startup_path와 cheapest_total_path 갱신 */
        }
    }
    /* 비매개변수화 경로가 없으면 최선의 매개변수화 경로를 cheapest_total로 사용 */
    parent_rel->cheapest_startup_path = cheapest_startup_path;
    parent_rel->cheapest_total_path   = cheapest_total_path;
    parent_rel->cheapest_unique_path  = NULL;   /* 필요 시 계산됨 */
    parent_rel->cheapest_parameterized_paths = parameterized_paths;
}

cheapest_parameterized_paths가 단일 포인터가 아닌 리스트인 이유는 다음과 같다. 서로 다른 외부 릴레이션 매개변수화는 비교 불가능하기 때문이다. {A}로 매개변수화된 경로와 {B}로 매개변수화된 경로는 어느 쪽도 다른 쪽의 부분집합이 아니므로 둘 다 유지된다. 조인 경로 빌더들은 현재 고려 중인 외부 릴레이션에 맞는 항목을 이 리스트에서 선택한다.

Pathkeys: 정규 정렬 순서

PathKey (pathnodes.h:1595)는 경로 출력 순서의 하나의 정렬 키를 나타낸다.

// PathKey — src/include/nodes/pathnodes.h
typedef struct PathKey {
    NodeTag         type;
    EquivalenceClass *pk_eclass;   /* 정렬 표현식을 포함하는 EC */
    Oid              pk_opfamily;  /* 순서를 정의하는 btree 연산자 패밀리 */
    CompareType      pk_cmptype;   /* 오름차순 또는 내림차순 */
    bool             pk_nulls_first;
} PathKey;

핵심 통찰은 pk_eclass가 EquivalenceClass — 옵티마이저가 쿼리 컨텍스트에서 서로 동일함을 증명한 표현식들의 집합 — 라는 점이다. a.x = b.y가 조인 조건이라면 a.x와 b.y 모두 같은 EC에 속하므로, 해당 EC를 참조하는 PathKey는 두 표현식 중 어느 것을 기준으로 정렬해도 동일한 순서를 나타낸다. make_canonical_pathkey가 각 EC마다 정규화된 공유 인스턴스를 반환하기 때문에, a.x의 인덱스 스캔과 b.y의 인덱스 스캔은 포인터가 동일한 PathKey 노드를 가진다. 결과적으로 compare_pathkeys는 키 하나당 O(1) 포인터 비교로 일치 여부를 판단할 수 있다.

// make_canonical_pathkey — src/backend/optimizer/path/pathkeys.c
PathKey *
make_canonical_pathkey(PlannerInfo *root,
                       EquivalenceClass *eclass, Oid opfamily,
                       CompareType cmptype, bool nulls_first)
{
    /* ec_merged 링크를 따라 정규 EC로 이동 */
    while (eclass->ec_merged) eclass = eclass->ec_merged;

    /* 일치하는 정규 PathKey가 있으면 반환 */
    foreach(lc, root->canon_pathkeys) {
        pk = (PathKey *) lfirst(lc);
        if (eclass == pk->pk_eclass && opfamily == pk->pk_opfamily &&
            cmptype == pk->pk_cmptype && nulls_first == pk->pk_nulls_first)
            return pk;
    }
    /* planner_cxt에 새 정규 PathKey 할당 */
    pk = makeNode(PathKey); /* ... 필드 채움 ... */
    root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
    return pk;
}

이 정규화 덕분에 pathkeys_contained_in (pathkeys.c:343)은 표현식 트리 깊은 비교 없이 포인터 동등성(pointer equality)으로 O(n) 리스트 비교를 수행해 한 경로의 정렬 순서가 다른 요건을 충족하는지 판단할 수 있다.

그림 2 — PathKey 정규화와 EC 기반 정렬 순서 매칭

flowchart LR
  subgraph EC["EquivalenceClass {a.x, b.y}"]
    AX["a.x"]
    BY["b.y"]
  end
  PK["PathKey\npk_eclass → EC\npk_opfamily = int4_ops\npk_cmptype = ASC"]
  IX["IndexPath on a.x\npathkeys = [PK]"]
  IY["IndexPath on b.y\npathkeys = [PK]"]
  MJ["MergePath\noutersortkeys = [PK]\ninnersortkeys = [PK]"]
  OB["ORDER BY a.x\nrequired_pathkeys = [PK]"]

  EC --> PK
  PK --> IX
  PK --> IY
  PK --> MJ
  PK --> OB

그림 2 — a.x 또는 b.y를 정렬 출력으로 하는 모든 Path 노드가 하나의 정규 PathKey를 공유한다. 병합 조인과 ORDER BY가 동일한 PathKey 포인터를 참조하므로 pathkeys_contained_in은 키 하나당 O(1) 포인터 비교로 이들을 매칭한다.

Append 경로와 파티셔닝 테이블 경로

파티셔닝 테이블과 상속 계층의 경우, set_append_rel_pathlist (allpaths.c:1251)는 각 자식 릴레이션에 재귀적으로 set_rel_pathlist를 호출한 뒤 결과를 AppendPath 또는 MergeAppendPath로 조합한다. MergeAppendPath는 모든 자식이 동일한 정렬 순서로 출력할 때(예: 각 자식에 매칭되는 인덱스가 있을 때) 사용된다. 이 경우 최상위 정렬을 피할 수 있다. 파티션 키와 일치하는 ORDER BY가 있으면 플래너는 파티션별 인덱스 스캔에 MergeAppend를 사용해 정렬을 생략할 수 있다. 이것이 파티션별 연산의 핵심 최적화다.

파티션 가지치기는 경로 생성 이전에 set_rel_size 단계에서 발생한다. 쿼리 필터와 범위가 겹치지 않는 파티션들은 더미 릴레이션으로 표시된다. set_append_rel_pathlist가 자식들을 순회할 때 더미 릴레이션은 건너뛰므로, 가지치기된 파티션에는 경로가 전혀 생성되지 않는다.

Foreign 경로와 커스텀 스캔 경로

set_foreign_pathlist (allpaths.c:938)는 FDW의 GetForeignPaths 콜백을 호출하고, 콜백은 create_foreignscan_path(pathnode.c)를 사용해 ForeignPath 노드를 생성한다. FDW는 제출할 경로 수를 스스로 결정하며 경로마다 add_path를 호출한다. FDW 훅 패턴은 코어 스캔 빌더와 동일한 add_path API를 사용한다. 즉, 커스텀 경로들이 힙 스캔 및 인덱스 스캔 경로들과 동일한 pathlist에서 직접 경쟁한다.

커스텀 스캔 제공자(set_rel_pathlist_hook)도 동일한 메커니즘을 사용한다. CustomPath에는 methods 포인터가 있고, create_plan이 그 PlanCustomPath 콜백을 호출해 실행 가능한 CustomScan 노드를 생성한다.

소스 코드 가이드

allpaths.c — make_one_rel과 RTE별 분기

make_one_rel — 기본 릴레이션과 조인 경로 생성의 최상위 진입점. 크기 추정 패스를 먼저 실행하고 경로 생성 패스를 이어서 실행. 조인 순서 탐색을 위해 make_rel_from_joinlist를 호출.
set_base_rel_sizes — 기본 릴레이션 첫 번째 패스: 릴레이션별 set_rel_size를 호출해 rows, pages, consider_parallel을 채움.
set_base_rel_pathlists — 두 번째 패스: 기본 릴레이션별 set_rel_pathlist를 호출.
set_rel_pathlist — rtekind/relkind에 따라 적절한 경로 빌더로 분기. 끝에서 set_rel_pathlist_hook, generate_useful_gather_paths, set_cheapest를 호출.
set_plain_rel_pathlist — 일반 힙 테이블용: TID 스캔, 순차 스캔, 병렬 순차 스캔, 인덱스 경로 추가.
create_plain_partial_paths — 병렬 워커 수에 맞는 partial 순차 스캔 경로를 rel->partial_pathlist에 추가.
set_append_rel_pathlist — 파티셔닝/상속 테이블용: 자식별 재귀 호출 후 AppendPath/MergeAppendPath 조합.
set_foreign_pathlist — FDW GetForeignPaths 콜백 호출.
set_subquery_pathlist — 서브쿼리 RTE용: 재귀적으로 계획된 서브쿼리에서 푸시다운 안전 계획을 선택하고 조건 푸시다운 적용.

indxpath.c — 인덱스 경로 생성

create_index_paths — rel->indexlist 외부 루프 진입점. 3단계 조건 매칭을 조율하고 비트맵 경로를 조합.
get_index_paths — 하나의 인덱스와 하나의 조건 집합을 받아 스캔 방향을 결정하고 정방향·역방향 스캔마다 build_index_paths를 호출.
build_index_paths — IndexPath(IndexScan 또는 IndexOnlyScan)를 생성해 add_path에 전달하고, 비트맵 후보 목록에 IndexPath를 축적.
match_restriction_clauses_to_index — rel->baserestrictinfo를 인덱스 키 컬럼에 매칭. IndexClauseSet을 채움.
match_join_clauses_to_index — rel->joininfo(느슨한 조인 절)를 인덱스 키 컬럼에 매칭. 별도의 IndexClauseSet을 채움.
match_eclass_clauses_to_index — 이 릴레이션 컬럼을 참조하는 EquivalenceClass마다 인덱스 가능한 조인 조건을 생성. eclauseset을 채움.
consider_index_join_clauses — 2+3단계에서 파생된 고유 매개변수화별로 build_index_paths를 호출해 매개변수화 IndexPath 노드를 생성.

pathnode.c — 경로 생성자와 가지치기

set_cheapest — 모든 경로가 추가된 후 pathlist를 훑어 cheapest_startup_path, cheapest_total_path, cheapest_parameterized_paths를 설정.
add_path — 지배 가지치기. 새 경로를 삽입하거나 폐기. 정렬된 삽입 순서(disabled_nodes 기준, 그 다음 total_cost 기준)로 탐색을 빠르게 함.
add_partial_path — partial_pathlist(병렬 조각)에 같은 가지치기를 적용.
create_seqscan_path — pathtype = T_SeqScan인 일반 Path 노드 생성. 비용은 cost_seqscan에서 계산.
create_nestloop_path — 외부 경로와 내부 경로를 입력으로 받는 NestPath 생성. 비용은 cost_nestloop.
create_mergejoin_path — 두 입력의 정렬 요건을 계산하는 MergePath 생성. 비용은 cost_mergejoin.
create_hashjoin_path — HashPath 생성. 비용은 cost_hashjoin.
create_gather_path — 병렬 실행 시 partial 경로를 GatherPath로 감쌈. 비용은 cost_gather.

pathkeys.c — 정규 정렬 순서 추적

make_canonical_pathkey — 주어진 (EC, opfamily, cmptype, nulls_first) 조합에 해당하는 고유한 PathKey를 반환하거나 생성. root->canon_pathkeys에 저장.
pathkeys_contained_in — pathkeys 리스트 keys1이 keys2의 접두사이거나 동일한지 검사. 정렬이 불필요한지 판단에 사용.
build_join_pathkeys — 외부 경로의 pathkeys와 조인 후 사용 가능한 EC로부터 조인 경로의 pathkeys를 파생.
make_pathkeys_for_sortclauses — SQL ORDER BY / GROUP BY 절 리스트를 정규 PathKey 노드로 변환해 필요 순서로 사용.

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

심볼	파일	행
`make_one_rel`	`src/backend/optimizer/path/allpaths.c`	171
`set_base_rel_sizes`	`src/backend/optimizer/path/allpaths.c`	290
`set_base_rel_pathlists`	`src/backend/optimizer/path/allpaths.c`	333
`set_rel_pathlist`	`src/backend/optimizer/path/allpaths.c`	469
`set_plain_rel_pathlist`	`src/backend/optimizer/path/allpaths.c`	768
`create_plain_partial_paths`	`src/backend/optimizer/path/allpaths.c`	806
`set_foreign_pathlist`	`src/backend/optimizer/path/allpaths.c`	938
`set_append_rel_pathlist`	`src/backend/optimizer/path/allpaths.c`	1251
`set_subquery_pathlist`	`src/backend/optimizer/path/allpaths.c`	2529
`create_index_paths`	`src/backend/optimizer/path/indxpath.c`	240
`get_index_paths`	`src/backend/optimizer/path/indxpath.c`	716
`build_index_paths`	`src/backend/optimizer/path/indxpath.c`	810
`match_restriction_clauses_to_index`	`src/backend/optimizer/path/indxpath.c`	2466
`match_join_clauses_to_index`	`src/backend/optimizer/path/indxpath.c`	2482
`match_eclass_clauses_to_index`	`src/backend/optimizer/path/indxpath.c`	2516
`set_cheapest`	`src/backend/optimizer/util/pathnode.c`	272
`add_path`	`src/backend/optimizer/util/pathnode.c`	464
`add_partial_path`	`src/backend/optimizer/util/pathnode.c`	798
`create_seqscan_path`	`src/backend/optimizer/util/pathnode.c`	986
`create_nestloop_path`	`src/backend/optimizer/util/pathnode.c`	2671
`create_mergejoin_path`	`src/backend/optimizer/util/pathnode.c`	2768
`create_hashjoin_path`	`src/backend/optimizer/util/pathnode.c`	2836
`create_gather_path`	`src/backend/optimizer/util/pathnode.c`	2180
`make_canonical_pathkey`	`src/backend/optimizer/path/pathkeys.c`	56
`pathkeys_contained_in`	`src/backend/optimizer/path/pathkeys.c`	343
`build_join_pathkeys`	`src/backend/optimizer/path/pathkeys.c`	1295
`make_pathkeys_for_sortclauses`	`src/backend/optimizer/path/pathkeys.c`	1336
`RelOptInfo` (구조체)	`src/include/nodes/pathnodes.h`	883
`Path` (구조체)	`src/include/nodes/pathnodes.h`	1753
`IndexPath` (구조체)	`src/include/nodes/pathnodes.h`	1842
`BitmapHeapPath` (구조체)	`src/include/nodes/pathnodes.h`	1917
`EquivalenceClass` (구조체)	`src/include/nodes/pathnodes.h`	1442
`PathKey` (구조체)	`src/include/nodes/pathnodes.h`	1595
`NestPath` (구조체)	`src/include/nodes/pathnodes.h`	2225
`MergePath` (구조체)	`src/include/nodes/pathnodes.h`	2271
`HashPath` (구조체)	`src/include/nodes/pathnodes.h`	2292

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

검증된 사실

make_one_rel은 크기 추정 패스 이전에 경로 패스를 실행하지 않는다. allpaths.c:171~232를 직접 읽어 확인했다. set_base_rel_sizes가 set_base_rel_pathlists보다 먼저 무조건 호출되고, total_table_pages 집계 루프가 그 사이에 실행된다. 이 순서는 매개변수화 경로의 비용이 외부 릴레이션 카디널리티에 의존하기 때문에 필수다.
set_rel_pathlist_hook은 내장 빌더 호출 후, set_cheapest 호출 전에 실행된다. allpaths.c:540~562에서 확인했다. 훅 호출과 generate_useful_gather_paths 호출이 모두 set_cheapest(rel) 앞에 있다는 점이다. 커스텀 스캔 제공자는 cheapest 포인터가 고정되기 전에 pathlist를 수정할 수 있다.
add_path는 IndexPath 노드를 절대 pfree하지 않는다. pathnode.c(약 650행)에서 if (!IsA(old_path, IndexPath)) pfree(old_path) 코드를 확인했다. 주석에 IndexPath 객체가 BitmapHeapPath 자식과 공유된다는 이유가 설명되어 있다.
disabled_nodes는 비용보다 높은 차원의 비용 요소다. add_path 코드를 읽어 확인했다. insert_at 로직이 total_cost 비교 이전에 new_path->disabled_nodes > old_path->disabled_nodes를 기본 정렬 키로 사용한다. enable_seqscan = off는 순차 스캔 경로를 탐색에서 제거하지 않는다. 다만 활성화된 대안이 있는 경우 반드시 지도록 보장한다.
매개변수화 경로는 add_path에서 NIL pathkeys로 처리된다. pathnode.c:506에서 new_path_pathkeys = new_path->param_info ? NIL : new_path->pathkeys 코드를 확인했다. 주석에 설계 근거가 설명되어 있다.
make_canonical_pathkey는 조회 전에 ec_merged 링크를 추적해 정규 EC를 찾는다. pathkeys.c:56~104에서 확인했다. 두 EC가 병합된 후에도(전이적 동등 관계 발견 시) 병합 전에 생성된 PathKey 노드들이 여전히 동일한 정규 EC로 올바르게 해석된다.
create_index_paths는 predOK 플래그가 false인 부분 인덱스를 건너뛴다. indxpath.c:268의 if (index->indpred != NIL && !index->predOK) continue 코드를 확인했다. predOK는 set_plain_rel_pathlist 호출 전 set_plain_rel_size 내부의 check_index_predicates가 설정한다. 이 함수는 쿼리의 baserestrictinfo가 부분 인덱스 조건을 함의하는지 검사한다.

미해결 의문

부분 비트맵 경로 생성 조건. create_partial_bitmap_paths는 rel->consider_parallel && rel->lateral_relids == NULL일 때만 호출된다. lateral_relids == NULL 조건은 명확하다(LATERAL 참조는 기본 릴레이션 수준에서 병렬화할 수 없다). 그러나 비트맵 힙 경로의 LATERAL 참조가 부분 실행을 막는 이유가 코드에서 즉시 명확하지 않다. 조사 경로: create_partial_bitmap_paths와 create_bitmap_heap_path에서 required_outer 처리를 추적.
choose_bitmap_and 비용 모델 정확도. 이 함수는 탐욕적(greedy) 휴리스틱으로 비트맵 인덱스 경로의 최선 AND 조합을 선택한다(완전 탐색이 아님). 결합 비트맵 스캔의 비용 모델(cost_bitmap_heap_scan)은 상관된 페이지에 근사치를 적용한다. 이 근사치가 높은 상관관계를 가진 컬럼(예: 복합 인덱스 시나리오)에서도 정확한지는 미검증 상태다. 조사 경로: costsize.c의 cost_bitmap_and_node.
MergePath의 outer_presorted_keys와 증분 정렬 상호작용. outer_presorted_keys 필드는 외부 경로가 부분 정렬된 경우 증분 정렬을 가능하게 한다. 플래너는 병합 경로 생성 시 이를 설정하지만, 상위 릴레이션에서 grouping_planner가 수행하는 IncrementalSortPath 생성과의 상호작용은 미검증 상태다. 기본 릴레이션 병합 경로가 외부 입력에 IncrementalSortPath도 생성할 수 있는지, 아니면 그것이 상위 릴레이션 경로에만 해당되는지 불분명하다.

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

Cascades / Columbia / Orca 메모 아키텍처. PostgreSQL은 릴레이션별 pathlist(System R 방식)를 사용한다. 후보들은 추가 시 가지치기되고, 탐색이 위로 올라가면 구조가 소멸된다. Cascades 계열 옵티마이저(Graefe 1995; SQL Server, Orca/Greenplum에서 구현됨)는 모든 논리적·물리적 표현식을 그룹 해시 테이블인 *메모(memo)*에 유지하는 하향식 탐색과 메모이제이션(memoization)을 사용한다. 상위 수준의 비용 컨텍스트가 바뀔 때 하위 그룹을 재방문할 수 있어, 등가 논리 변환이 많은 쿼리에서 더 강력하다. 다만 메모리 오버헤드가 더 크다. add_path의 상향식 가지치기와 Cascades의 하향식 규칙 발화(rule-fire) 모델을 나란히 비교하면 이 트레이드오프를 잘 보여준다.
적응형 쿼리 처리와 재최적화. PostgreSQL의 경로 생성은 완전히 정적이다. 실행이 시작되기 전에 통계로부터 모든 비용을 추정한다. Eddies(Avnur & Hellerstein, SIGMOD 2000)나 SQL Server의 미드쿼리 계획 전환 같은 최신 연구는 실제 런타임 행 수 피드백으로 정적 탐색을 대체하거나 보강한다. PG18의 비동기 I/O(postgres-aio.md)는 정적 옵티마이저가 이미 선택한 계획의 I/O 처리량을 개선하지만, 실제 I/O 비용을 재계획에 피드백하지는 않는다.
ML 기반 카디널리티 추정과 학습된 비용 모델. create_index_paths에서 경로 선택의 정확도는 전적으로 통계 서브시스템의 카디널리티 추정에 달려 있다. 최근 연구(Kipf et al., “Learned Cardinalities,” CIDR 2019; Marcus et al., “Bao,” SIGMOD 2021)는 히스토그램 기반 추정을 쿼리 실행 피드백으로 학습된 ML 모델로 대체하거나 보강한다. PostgreSQL의 확장 통계(postgres-extended-statistics.md)는 현재 아키텍처 내에서 이 방향으로 나아가는 프로덕션 단계다.
부분 인덱스 활용 깊이. PostgreSQL의 predOK 검사는 쿼리 필터가 인덱스 조건을 함의하는지 테스트한다. 더 깊은 활용은 더 많은 부분 인덱스를 적용 가능하게 만드는 필터를 생성하는 것이다. 이는 무결성 제약 조건을 사용해 새 조건을 생성하는 “의미론적 쿼리 최적화(semantic query optimization)” 문헌의 주제와 맞닿는다. 현재 어떤 RDBMS도 이를 완전하게 구현하지 않았다.
파티션별 조인 및 집계 경로 생성. set_append_rel_pathlist는 현재 AppendPath/MergeAppendPath를 생성한다. RelOptInfo에 consider_partitionwise_join이 설정되면, joinpath.c의 조인 경로 빌더들이 파티션별 조인 경로를 생성한다(PG11에서 도입). pathkey 정규화와 파티션 키 표현식(파티션별 조인이 합법적이려면 동일한 EC에 속해야 함) 간의 상호작용은 현재도 활발히 개발 중인 영역이다.

출처

인트리 문서

src/backend/optimizer/README — 전체 옵티마이저 설계 문서. 경로/조인 트리 구성, EquivalenceClass, 외부 조인 순서, Vars/PlaceHolderVars, 옵티마이저 함수 개요를 다룸.

논문

Selinger et al., “Access Path Selection in a Relational Database Management System,” SIGMOD 1979 — System R 템플릿. knowledge/research/dbms-papers/systemr-optimizer.md에 정리됨.

교과서

Database Internals (Petrov, ch. 7) — 비용 기반 탐색, 계획 공간 열거, 파레토 최적 전선.
Database System Concepts (Silberschatz, 7e, ch. 16) — 쿼리 최적화 개요, 비용 추정, 동적 프로그래밍 조인 열거.

소스 파일

src/backend/optimizer/path/allpaths.c — make_one_rel, 모든 RTE별 경로 빌더
src/backend/optimizer/path/indxpath.c — 인덱스 경로 생성 파이프라인
src/backend/optimizer/path/pathkeys.c — 정규 pathkey 구성 및 비교
src/backend/optimizer/util/pathnode.c — add_path, set_cheapest, 모든 경로 생성자
src/include/nodes/pathnodes.h — RelOptInfo, Path, IndexPath, BitmapHeapPath, EquivalenceClass, PathKey, 조인 경로 구조체