(KO) PostgreSQL 조인 순서 결정 — 동적 프로그래밍 탐색과 GEQO 폴백
목차
- 학술적 배경
- DBMS 공통 설계 패턴
- PostgreSQL의 구현
- 소스 코드 가이드
- 소스 검증 (2026-06-05 기준)
- PostgreSQL 너머 — 비교 설계와 연구 프론티어
- 출처
학술적 배경
섹션 제목: “학술적 배경”두 개를 초과하는 릴레이션을 조인하는 쿼리에서 옵티마이저는 두 가지 결정을 내려야 한다. 첫 번째는 릴레이션을 어떤 순서로 조인할 것인가다. ((A ⋈ B) ⋈ C), (A ⋈ (B ⋈ C)), ((A ⋈ C) ⋈ B) 등 다양한 조합이 가능하다. 두 번째는 순서가 고정된 상태에서 각 조인을 어떤 물리 알고리즘(중첩 루프, 정렬 병합, 해시)으로 수행하고 각 기본 릴레이션을 어떤 접근 경로(순차 스캔, 인덱스 스캔, 비트맵 스캔)로 읽을 것인가다. 이 문서는 첫 번째 결정인 조인 열거(join enumeration)를 다루며, 두 번째 결정은 위임된 하위 문제로 다룬다(자세한 내용은 postgres-path-generation.md와 postgres-cost-model.md 참고).
조인 순서가 지배적인 비용 결정 요인인 이유는 순서 경우의 수가 조합론적으로 폭발하는 반면, 각 순서에 대한 계산량은 상대적으로 제한되어 있기 때문이다. n개 릴레이션에 대한 조인 트리 수는 좌편향과 부시 형태, 그리고 각 조인의 양방향을 모두 세면 다음과 같다.
(2(n-1))! / (n-1)!
n=2이면 2, n=3이면 12, n=4이면 120, n=5이면 1680이고 이후 초지수적으로 증가한다. 좌편향 트리만 고려해도 n!가지 순서가 존재한다. 어떤 엔진도 n이 큰 경우 모든 트리의 비용을 계산할 수 없으므로, 모든 옵티마이저는 탐색 공간을 가지치기하거나 휴리스틱으로 탐색해야 한다. 어떤 순서를 선택하느냐는 결과에 막대한 영향을 미친다. 나쁜 순서는 좋은 순서라면 완전히 피할 수 있었을 거대한 중간 결과를 만들어내기 때문이다.
이론적 기반은 Selinger et al., Access Path Selection in a Relational Database Management System (SIGMOD 1979 — System R 옵티마이저 논문, knowledge/research/dbms-papers/systemr-optimizer.md 참고)이다. PostgreSQL이 하는 모든 것의 근간이 되는 두 가지 아이디어가 이 논문에 담겨 있다.
-
규칙 기반이 아닌 비용 기반. System R은 모든 후보 계획에 수치 비용을 부여한다. 카탈로그 통계(카디널리티, 선택도)에서 계산한 예상 페이지 페치와 CPU 명령어의 가중 합이다. 최솟값을 선택한다. 논문이 소개한 선택도 인수(selectivity factor)와 비용 공식은 PostgreSQL 비용 모델에 그대로 반영되어 있다.
-
릴레이션 부분 집합에 대한 동적 프로그래밍. System R은 전체 트리를 열거하는 대신 부분 집합 크기 순으로 바텀업 방식으로 답을 구성한다. 먼저 각 단일 릴레이션의 최적 접근 방법을 찾고, 모든 쌍의 최적 2방향 조인을, 모든 3-튜플의 최적 3방향 조인을 구하는 방식으로 이미 계산된 부분 집합의 최적 계획을 재사용한다. 핵심 통찰은 **최적성 원리(principle of optimality)**다. 릴레이션 집합 S를 조인하는 가장 저렴한 계획은 반드시 S의 어떤 부분 집합에서 산출한 가장 저렴한 계획 위에 구축되어야 한다. 옵티마이저는 릴레이션 부분 집합마다 가장 저렴한 계획들만 유지하면 충분하다. 이것이 **메모(memo)**다. 결과적으로
(2(n-1))!/(n-1)!의 트리 공간이 대략2^n개 부분 집합으로 축소되고, 각 부분 집합은 제한된 횟수만 비용이 계산된다.
폭발 규모를 구체적으로 살펴보면, 5방향 조인 A⋈B⋈C⋈D⋈E에는 1680개의 서로 다른 조인 트리(부시 형태, 양방향 포함)가 있지만 {A,B,C,D,E}의 비어 있지 않은 부분 집합은 2^5 - 1 = 31개에 불과하다. 2개 이상 원소를 가진 부분 집합(조인 릴레이션)은 그 중 26개다. DP는 이 26개 릴레이션 각각을 한 번씩 비용 계산하고, 이미 비용 계산된 두 하위 릴레이션으로 분할하는 소수의 방법을 고려한다. 점근적 차이가 핵심이다. 트리 수는 Θ(4^n / n^{1.5}), 부분 집합 수는 2^n이다. geqo_threshold = 12일 때 2^12 = 4096개 부분 집합은 여전히 처리 가능하지만, 12개 릴레이션에 대한 트리 수는 천문학적으로 크다. 임계값이 이 위치에 설정된 이유가 바로 이것이다.
Selinger의 System R은 좌편향 트리만 유지하고 비흥미로운 순서를 가지치기해 완전성과 처리 가능성을 절충했다. 논문은 또한 **흥미로운 정렬 순서(interesting order)**를 도입했다. 나중 연산자(병합 조인, ORDER BY, GROUP BY)에 유용한 순서로 출력을 생성하는 하위 계획은, 가장 저렴하지 않더라도 보유한다. 제공하는 정렬이 나중의 정렬을 절약해줄 수 있기 때문이다. “가장 저렴하다”는 것이 단일 스칼라가 아니라 출력 정렬과 매개변수화에 따라 달라진다는 이 미묘함이, PostgreSQL이 릴레이션당 경로 하나가 아닌 비지배 경로 집합을 유지하는 이유다. 자세한 내용은 postgres-path-generation.md에 있다.
흥미로운 정렬 순서 아이디어를 한 번 더 살펴볼 가치가 있다. “가장 저렴한 계획”이 스칼라가 아닌 이유를 이해하는 데 핵심이기 때문이다. Selinger는 나중 병합 조인이 필요로 하는 컬럼 기준으로 정렬된 {A,B} 릴레이션을 생성하는 하위 계획은, {A,B}에 대한 더 저렴한 비정렬 계획이 존재하더라도 보유할 가치가 있다고 관찰했다. 이미 제공하는 정렬이 나중 병합 조인의 정렬 비용을 절약해줄 수 있고, 그 절감이 선행 비용 프리미엄을 초과할 수 있다. 따라서 옵티마이저는 릴레이션 집합당 가장 저렴한 계획 하나가 아니라 (비용, 출력 순서)에 대한 **파레토 프론티어(Pareto frontier)**를 유지해야 한다. 현대 PostgreSQL에서는 (비용, 출력 순서, 매개변수화)에 대한 프론티어를 유지한다. 조인 탐색 코드가 반복적으로 set_cheapest(다음 레벨 구축을 위한 스칼라 승자 선택)를 호출하면서도 전체 pathlist(프론티어 보존)를 유지하는 이유가 여기에 있다. 구축을 위한 스칼라 승자와 보존을 위한 프론티어 — 이 구분이 구현 전반에 걸쳐 반복된다.
DP 접근 방식에는 잘 알려진 실패 모드가 하나 있다. 2^n 자체가 수십 개 릴레이션을 넘어서면 처리 불가능해지고, 상수 인수(각 부분 집합이 많은 후보 조인과 경로를 생성함)가 그 훨씬 이전에 문제가 된다. 대규모 조인 문제에서 문헌은 무작위/휴리스틱 탐색으로 방향을 전환한다. 반복 개선, 시뮬레이티드 어닐링, 그리고 조인 순서를 “투어”(순회 외판원 문제에 비유)로 취급하고 더 낮은 비용을 향해 투어 집단을 진화시키는 유전 알고리즘이 그 예다. PostgreSQL은 이 두 체제 설계를 정확하게 구현한다. 작은 문제는 완전 DP, 임계값을 넘으면 유전 알고리즘(GEQO)이다.
DBMS 공통 설계 패턴
섹션 제목: “DBMS 공통 설계 패턴”이론이 뼈대를 확정한다. 릴레이션 부분 집합에 대한 비용 기반 DP와 대규모 문제를 위한 휴리스틱 탈출구다. 이 절에서는 프로덕션 옵티마이저들이 이를 구현할 때 공유하는 엔지니어링 관례를 정리한다. PostgreSQL의 구체적인 코드가 알려진 설계 공간에서 하나의 지점으로 읽힐 수 있도록 맥락을 제공한다.
1. 릴레이션 집합을 키로 하는 메모. 모든 DP 옵티마이저는 기본 릴레이션 집합을 그 집합을 생성하는 최적 계획들에 매핑하는 테이블이 필요하다. 집합이 키인 이유는 논리 수준에서 조인이 교환적·결합적이기 때문이다. (A ⋈ B) ⋈ C와 (B ⋈ C) ⋈ A는 동일한 릴레이션 {A,B,C}을 생성하므로 하나의 메모 항목으로 합쳐져야 하고, 두 구축 경로는 같은 항목에서 경쟁해야 한다. 엔진이 이것을 “메모”(Cascades/SQL Server/Calcite), “그룹의 MEMO 구조”, 또는 PostgreSQL처럼 Relids 비트맵셋을 키로 하는 RelOptInfo 노드의 join_rel_list/join_rel_hash라 부르든 역할은 동일하다. relid 집합으로 탐색 또는 생성하고, 기존 노드에 후보 계획을 추가한다.
교과서가 대충 넘어가지만 모든 구현이 반드시 다뤄야 하는 미묘함이 있다. 릴레이션 집합에 대한 메모 항목은 계획 하나가 아니라 비지배 계획의 작은 집합을 담는다. 전체 비용이 더 비싸더라도 나중 연산자가 필요로 하는 정렬 순서로 출력을 제공하는 계획(Selinger의 “흥미로운 정렬 순서”)은 보유할 가치가 있다. 또는 매개변수화 중첩 루프의 내측이 될 수 있도록 매개변수화된 계획도 마찬가지다. 따라서 “relid 집합으로 탐색·생성” 다음에는 “이 후보를 보유 집합에 병합하되, 지배하는 것은 버리고 지배당하면 자신을 버린다”가 따라온다. PostgreSQL이 add_path라 부르는 파레토 프론티어 유지 방식이다. relid 집합은 메모 키고, 보유된 경로 집합이 메모 값이다.
2. 레벨 단위 구축(DP 순서). 바텀업 변형(“Selinger 스타일 DP”)은 부분 집합 크기 순으로 반복한다. 크기 1 릴레이션에서 크기 2 조인을 구축하고, {크기 1 ⋈ 크기 2}에서 크기 3을 구축하는 방식이다. 크기 k 조인을 구축할 때 그것이 구축될 수 있는 더 작은 모든 부분 집합의 최적 계획이 이미 계산되어 있음을 보장한다. PostgreSQL은 이를 레벨 인덱스를 가진 명시적 배열 join_rel_level[k]로 구체화한다.
3. 트리 형태: 좌편향 대 부시. 좌편향 트리는 항상 누적된 결과를 단일 기본 릴레이션과 조인한다. 부시 트리는 두 복합 중간 결과를 조인할 수 있다. 좌편향은 탐색 공간이 작고 중첩 루프에서 파이프라인이 잘 작동한다. 부시는 스타/스노우플레이크 스키마에서 극적으로 저렴하고, 아우터 조인 순서 제약에서 유일하게 합법적인 형태일 수 있다. System R 같은 초기 옵티마이저는 좌편향만 탐색했다. PostgreSQL을 포함한 현대 옵티마이저는 부시 트리도 탐색하지만, 폭발을 제한하기 위해 실제로 조인 절을 공유하는 쌍으로 부시 조인을 가지치기한다.
4. 연결된 부분 그래프 가지치기. 조인 절로 연결되지 않은 쌍(카테시안 곱)의 비용을 계산하는 것은 거의 항상 낭비다. 따라서 열거자는 조인 술어로 연결된 쌍, 즉 노드가 릴레이션이고 에지가 조인 절인 조인 그래프에서 인접한 쌍을 선호한다. 카테시안 조인은 절로 연결된 계획이 존재하지 않을 때 최후 수단으로만 생성된다.
5. 의미론에 의한 조인 순서 제약. 이너 조인은 자유롭게 교환하고 결합할 수 있지만, 아우터 조인, 세미/안티 조인(IN/EXISTS), LATERAL 참조는 순서 제약을 부과한다. 일부 릴레이션은 다른 것보다 먼저 조인되어야 하거나, 아우터 조인을 넘어 재순서화될 수 없다. 제안된 모든 쌍을 정확성 검사(join_is_legal)로 검증해야 하고, 제약으로 인해 좌편향이 불합법적일 때 열거자는 부시 계획을 생성할 의지가 있어야 한다.
6. 대형 N 탈출구. 2^n과 그 상수 인수가 결국 지배하기 때문에, 옵티마이저는 완전 탐색에 상한을 두고 큰 조인 문제에는 휴리스틱으로 전환한다. 탐욕적 좌편향(“최소 선택도 우선”), 무작위 재시작, 시뮬레이티드 어닐링, 또는 유전 알고리즘이 그 예다. 상한은 보통 FROM 목록 항목 수에 대한 조정 가능한 임계값이다.
7. 대칭성 활용. 논리 조인이 교환적이므로, 열거자가 (R, S)와 (S, R) 모두를 별개의 순서 탐색 이벤트로 고려하면 작업의 절반을 낭비한다. 표준 기법은 조인 릴레이션 생성자를 대칭으로 만들어 — 비순서쌍이 주어지면 내부적으로 두 방향 모두를 물리적 대안으로 시도 — 열거자가 각 비순서쌍을 한 번씩 방문하게 하는 것이다. PostgreSQL은 두 가지 모두 적용한다. make_join_rel(x, y)은 “x,y와 y,x 두 경우를 모두 처리”하고, join_search_one_level은 대칭 레벨(level == 2와 부시 k == other_level 경우)에서 이미 고려된 쌍을 건너뛰는 first_rel 인덱스를 사용한다. 결과적으로 순서 탐색은 비순서쌍을 열거하지만 경로 탐색은 여전히 어느 쪽이 외부인지 선택할 수 있다.
8. 비용 모델 결합. 열거자의 품질은 add_path의 지배 테스트를 구동하는 카디널리티·비용 추정치에 달려 있다. 중간 조인에 대한 행 수 추정이 잘못되면 전파된다. 잘못된 하위 계획이 가장 저렴해 보이고, 이것이 다음 레벨의 구축 블록이 된다. 이것이 모든 Selinger 스타일 옵티마이저가 공유하는 아킬레스건이며, 아래 “너머” 절이 실행 중에 순서를 재검토하는 적응형·학습 접근 방식에 공간을 할애하는 이유다. DP 기계 자체는 정확하다. 입력값이 취약한 부분이다.
flowchart TD
J["make_rel_from_joinlist<br/>levels_needed = #jointree items"] --> Q{"enable_geqo AND<br/>levels_needed >= geqo_threshold?"}
Q -- "no (small)" --> DP["standard_join_search<br/>exhaustive DP"]
Q -- "yes (large)" --> GEQO["geqo<br/>genetic search"]
DP --> L["join_rel_level[1..n]<br/>filled level by level"]
GEQO --> P["pool of join-order tours<br/>evolved over generations"]
L --> TOP["top-level RelOptInfo<br/>cheapest_total_path"]
P --> TOP
PostgreSQL의 구현
섹션 제목: “PostgreSQL의 구현”PostgreSQL은 Selinger 스타일 DP를 충실하고 현대적으로 구현하며, 설정 가능한 임계값에서 유전 알고리즘 폴백을 갖추고 있다. 전체 조인 탐색 서브시스템은 make_rel_from_joinlist(allpaths.c)라는 함수 하나에서 시작된다. 플래너가 FROM 절을 조인 목록(joinlist) — RangeTblRef 리프와 서브 목록의 중첩 목록 — 으로 평탄화한 후 이 함수를 호출한다(deconstruct_jointree가 조인 목록을 생성하는 방법은 postgres-planner-overview.md 참고).
진입점은 항목 수를 세고 분기한다.
// make_rel_from_joinlist — src/backend/optimizer/path/allpaths.clevels_needed = list_length(joinlist);// ... build initial_rels (one RelOptInfo per joinlist child, recursing// into sub-lists) ...if (levels_needed == 1) return (RelOptInfo *) linitial(initial_rels);else{ root->initial_rels = initial_rels; if (join_search_hook) return (*join_search_hook) (root, levels_needed, initial_rels); else if (enable_geqo && levels_needed >= geqo_threshold) return geqo(root, levels_needed, initial_rels); else return standard_join_search(root, levels_needed, initial_rels);}levels_needed는 독립적인 조인트리 항목의 수다. 명시적 JOIN 구문과 평탄화된 서브셀렉트가 항목을 묶을 수 있으므로 원시 테이블 수와 다를 수 있다. 세 갈래 분기가 설계의 핵심을 간결하게 보여준다. 로드 가능한 익스텐션(join_search_hook, 예: pg_hint_plan)이 탐색 전체를 대체할 수 있고, 그렇지 않으면 geqo_threshold GUC(기본값 12)가 대규모 문제에는 유전 탐색을, 나머지에는 완전 DP를 선택한다.
DP 메모. 이것이 완전 탐색이 아니라 동적 프로그래밍인 이유는 root->join_rel_level이라는 레벨 인덱스 List * 배열 때문이다. PlannerInfo에 이렇게 문서화되어 있다.
// PlannerInfo — src/include/nodes/pathnodes.h/* * When doing a dynamic-programming-style join search, join_rel_level[k] * is a list of all the join-relations of k items ... * join_cur_level is the current level. New join-relation RelOptInfos are * automatically added to the join_rel_level[join_cur_level] list. * join_rel_level is NULL if not in use. */List **join_rel_level pg_node_attr(read_write_ignore);int join_cur_level;조인 릴레이션의 고유성은 구축 방법이 아니라 relid 집합으로 결정된다. build_join_rel(make_join_rel에서 호출)은 join_rel_hash를 탐색하거나 새 항목을 생성한다. {A,B,C}를 생성하는 첫 번째 구축 경로가 RelOptInfo를 할당하고, 같은 집합을 생성하는 이후의 모든 경로는 기존 노드를 찾아 경로를 추가하기만 한다. 이것이 메모다. join_search_one_level은 새로 구축된 조인 릴레이션을 join_rel_level[join_cur_level]에 몇 쌍이 구축했는지와 무관하게 한 번만 추가한다.
standard_join_search — 레벨 루프. 레벨 1은 초기 릴레이션으로 시드(seed)되고, 이후 각 레벨은 join_search_one_level로 구축되며, 각 새 조인 릴레이션은 set_cheapest로 마무리된다.
// standard_join_search — src/backend/optimizer/path/allpaths.croot->join_rel_level = (List **) palloc0((levels_needed + 1) * sizeof(List *));root->join_rel_level[1] = initial_rels;
for (lev = 2; lev <= levels_needed; lev++){ join_search_one_level(root, lev); foreach(lc, root->join_rel_level[lev]) { rel = (RelOptInfo *) lfirst(lc); generate_partitionwise_join_paths(root, rel); if (!bms_equal(rel->relids, root->all_query_rels)) generate_useful_gather_paths(root, rel, false); set_cheapest(rel); }}// final level must contain exactly one rel — the whole joinAssert(list_length(root->join_rel_level[levels_needed]) == 1);rel = (RelOptInfo *) linitial(root->join_rel_level[levels_needed]);마지막 레벨에는 릴레이션이 정확히 하나(전체 조인)여야 하고, 그것의 cheapest_total_path가 선택된 계획이 된다. set_cheapest는 릴레이션당 pathlist(비지배 경로 집합, add_path가 유지)를 다음 레벨이 구축에 사용할 cheapest-startup과 cheapest-total 승자로 압축한다.
join_search_one_level — 열거자. 이것이 전략의 핵심이다. 목표 level에서 세 가지 구축 방법을 고려한다.
- 좌/우 편향 조인 — 각
(level-1)-릴레이션을 조인 절을 공유하는 초기(단일) 릴레이션과 조인. 좌편향 뼈대다. - 부시 조인 —
2 <= k <= level-2범위에서 각k-릴레이션을(level-k)-릴레이션과 조인. 관련 조인 절이나 순서 제약이 연결하는 경우에만. - 최후 수단 카테시안 — 어느 쪽도 이 레벨에서 조인 릴레이션을 생성하지 못했다면, 절 없는 조인을 강제해 탐색이 막히지 않게 한다.
// join_search_one_level — src/backend/optimizer/path/joinrels.cforeach(r, joinrels[level - 1]){ RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
if (old_rel->joininfo != NIL || old_rel->has_eclass_joins || has_join_restriction(root, old_rel)) { int first_rel; if (level == 2) /* avoid considering the same pair twice */ first_rel = foreach_current_index(r) + 1; else first_rel = 0; make_rels_by_clause_joins(root, old_rel, joinrels[1], first_rel); } else make_rels_by_clauseless_joins(root, old_rel, joinrels[1]);}level == 2에서의 first_rel 기법은 대칭성을 이용한다. 레벨 2에서 (a)를 (b)와 조인하는 것은 (b)를 (a)와 조인하는 것과 같은 문제이므로, 현재 것 이후의 릴레이션만 본다. 부시 루프는 k를 2에서 중간점까지 순회하고(make_join_rel(x,y)가 두 방향을 이미 처리하므로), 관련 절이나 제약이 있는 !bms_overlap(서로소 relid 집합) 쌍만 조인한다.
// join_search_one_level (bushy section) — joinrels.cfor (k = 2;; k++){ int other_level = level - k; if (k > other_level) break; /* only go to the halfway point */ foreach(r, joinrels[k]) { /* ... skip rels with no join clause and no restriction ... */ for_each_from(r2, joinrels[other_level], first_rel) { RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2); if (!bms_overlap(old_rel->relids, new_rel->relids)) { if (have_relevant_joinclause(root, old_rel, new_rel) || have_join_order_restriction(root, old_rel, new_rel)) (void) make_join_rel(root, old_rel, new_rel); } } }}make_join_rel — 합법성, 메모, 경로. 모든 후보 쌍은 make_join_rel을 거친다. relid 합집합을 계산하고, join_is_legal(아우터/세미 조인 또는 LATERAL 제약이 금지하는 순서 거부 — 불합법 쌍에는 NULL 반환)을 확인하고, 메모 RelOptInfo를 탐색·구축하고, populate_joinrel_with_paths를 호출한다.
// make_join_rel — src/backend/optimizer/path/joinrels.cjoinrelids = bms_union(rel1->relids, rel2->relids);if (!join_is_legal(root, rel1, rel2, joinrelids, &sjinfo, &reversed)) return NULL; /* invalid join order */joinrelids = add_outer_joins_to_relids(root, joinrelids, sjinfo, &pushed_down_joins);if (reversed) { /* swap rel1/rel2 to match sjinfo */ }if (sjinfo == NULL) { sjinfo = &sjinfo_data; init_dummy_sjinfo(...); }joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo, pushed_down_joins, &restrictlist);if (is_dummy_rel(joinrel)) return joinrel; /* provably empty */populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo, restrictlist);return joinrel;populate_joinrel_with_paths는 조인 유형에 따라 분기하고, 합법적인 각 (외부, 내부) 방향마다 add_paths_to_joinrel을 한 번씩 호출한다. 예를 들어 일반 이너 조인이면 (rel1 외부, rel2 내부)와 (rel2 외부, rel1 내부) 두 방향을 시도한다. 중첩 루프와 해시 조인은 비용이 대칭이 아니기 때문이다(내측은 재스캔·해시됨). 조인 순서 탐색이 조인 방법 및 경로 탐색에 위임하는 지점이다. add_paths_to_joinrel이 sort_inner_and_outer, match_unsorted_outer, hash_inner_and_outer를 순서대로 호출해 수행하며, 자세한 내용은 postgres-path-generation.md와 postgres-cost-model.md에 있다.
flowchart TD
S1["join_search_one_level(level)"] --> A["left/right-sided:<br/>make_rels_by_clause_joins<br/>(level-1) x initial rels"]
S1 --> B["bushy: k x (level-k)<br/>with relevant clause only"]
S1 --> C{"joinrels[level] empty?"}
C -- yes --> D["last-ditch:<br/>make_rels_by_clauseless_joins"]
A --> MJ["make_join_rel(rel1, rel2)"]
B --> MJ
D --> MJ
MJ --> LEG{"join_is_legal?"}
LEG -- no --> X["return NULL"]
LEG -- yes --> BJR["build_join_rel<br/>find-or-create by relids = memo"]
BJR --> PP["populate_joinrel_with_paths"]
PP --> APJ["add_paths_to_joinrel<br/>sort-merge / nestloop / hash"]
레벨 단위 추적 예시. 4-항목 쿼리 SELECT ... FROM a, b, c, d WHERE a.x=b.x AND b.y=c.y AND c.z=d.z — 체인 조인 그래프 a—b—c—d를 살펴보자. levels_needed = 4로 임계값 미만이므로 standard_join_search가 실행된다. DP 배열은 다음과 같이 채워진다.
| 레벨 | join_rel_level[k] 내용 | 구축 방법 |
|---|---|---|
| 1 | {a}, {b}, {c}, {d} | initial_rels 시드 |
| 2 | {a,b}, {b,c}, {c,d} | 절 조인. {a,c}, {a,d}, {b,d}는 조인 절 없어 건너뜀 |
| 3 | {a,b,c}, {b,c,d} | {a,b}⋈c, c⋈{a,b}; {b,c}⋈a, {b,c}⋈d; {c,d}⋈b |
| 4 | {a,b,c,d} | {a,b,c}⋈d (좌편향) 및 {a,b}⋈{c,d} (부시) |
핵심은 레벨 4다. 최종 릴레이션 {a,b,c,d}는 두 가지 구축 경로로 도달한다. make_rels_by_clause_joins의 좌편향 {a,b,c}⋈d와, 부시 루프의 k=2, other_level=2 분기의 {a,b}⋈{c,d}다. 두 경로 모두 make_join_rel을 호출하고, build_join_rel이 relid 집합 {a,b,c,d}로 키를 잡은 동일한 RelOptInfo에 해소한다. 두 경로 모두 단일 pathlist에 경로를 기여하고, set_cheapest가 모든 경로 중 전역 승자를 선택한다. 열거자가 릴레이션을 조합하는 방법을 얼마나 많이 찾든 릴레이션은 하나의 노드로 비용이 계산된다. 이것이 동적 프로그래밍 메모가 수행하는 역할이다. 레벨 2에서의 누락도 눈여겨볼 지점이다. {a,c}, {a,d}, {b,d}는 연결하는 조인 절이 없어 결코 구축되지 않는다. 연결된 부분 그래프 가지치기가 이 작은 문제에서도 카테시안 중간 결과의 비용 계산을 방지한다.
합법성 검사와 아우터 조인. 이너 조인은 자유롭게 교환·결합되지만, 아우터 조인, 세미/안티 조인, LATERAL 참조가 등장하는 순간 대부분의 순서가 불합법이 된다. 아우터 조인을 넘어 릴레이션을 재순서화하면 어떤 행이 null 확장되는지가 바뀌고, LATERAL 서브쿼리는 참조하는 릴레이션 이후에 조인되어야 한다. make_join_rel은 모든 쌍에서 작업 시작 전에 join_is_legal을 확인하고, 불합법 쌍에는 NULL을 반환해 그 쌍의 RelOptInfo나 경로가 생성되지 않게 한다.
// make_join_rel — src/backend/optimizer/path/joinrels.cAssert(!bms_overlap(rel1->relids, rel2->relids));joinrelids = bms_union(rel1->relids, rel2->relids);if (!join_is_legal(root, rel1, rel2, joinrelids, &sjinfo, &reversed)){ bms_free(joinrelids); return NULL; /* invalid join order — drop it */}join_is_legal은 root->join_info_list(합법적인 피연산자 범위를 인코딩하는 min_lefthand/min_righthand relid 집합을 가진 비이너 조인당 하나의 SpecialJoinInfo)와 LATERAL 부기를 참조한다. 두 출력값이 make_join_rel의 나머지를 조정한다. *sjinfo_p는 매칭된 조인의 SpecialJoinInfo이거나 일반 이너 조인이면 NULL(이 경우 init_dummy_sjinfo가 선택도 코드를 위한 최소한의 것을 만든다), *reversed_p는 두 입력을 조인의 구문론적 LHS/RHS에 맞추기 위해 스왑해야 하는지 여부다. 이 제약들이 열거자가 부시 트리를 구축해야 하는 이유이기도 하다. 일부 중간 레벨에서 합법적인 좌편향 순서가 없고 더 높은 레벨에서 부시 조합만 성공하는 쿼리가 있다. join_search_one_level의 elog(ERROR, "failed to build any %d-way joins", level)이 root->join_info_list != NIL일 때 의도적으로 억제되는 이유가 바로 이것이다. 특수 조인이 있을 때 빈 레벨은 합법적이고 회복 가능한 상태일 수 있다.
순서 탐색이 끝나고 경로 탐색이 시작되는 지점. make_join_rel이 (외부, 내부) 방향을 고정하면, add_paths_to_joinrel은 고정된 순서로 경로 빌더를 실행한다. 소스의 번호 매기기는 두 탐색 사이의 계약이므로 인용할 가치가 있다. 조인 순서 레이어는 이것을 전혀 보지 못하고, 결과 pathlist만 본다.
// add_paths_to_joinrel — src/backend/optimizer/path/joinpath.c/* 1. mergejoin with both relations explicitly sorted */if (mergejoin_allowed) sort_inner_and_outer(root, joinrel, outerrel, innerrel, jointype, &extra);/* 2. nestloops + mergejoins where the outer is already ordered */if (mergejoin_allowed) match_unsorted_outer(root, joinrel, outerrel, innerrel, jointype, &extra);/* 4. hash join (both sides hashed) */if (enable_hashjoin || jointype == JOIN_FULL) hash_inner_and_outer(root, joinrel, outerrel, innerrel, jointype, &extra);/* 5/6. FDW join pushdown and the set_join_pathlist_hook extension seam */각 빌더는 initial_cost_* 추정으로 후보를 검사하는 try_*_path 헬퍼로 끝나고, 생존하면 add_path를 호출해 joinrel->pathlist에 삽입한다. add_path는 비지배 경로 집합(cheapest-total과 유용한 정렬 순서 또는 더 저렴한 매개변수화를 가진 것들)을 유지하는 파레토 필터다. 이 빌더들의 전체 내용은 postgres-path-generation.md의 주제다. 여기서 요점은 조인 순서가 그것들을 비용이 매겨진 경로를 반환하는 블랙박스로 취급한다는 것이다.
GEQO 체제. levels_needed >= geqo_threshold이면 DP 대신 geqo()가 실행된다. “게놈”이 투어 — 릴레이션 인덱스의 순열 — 이고, 적합도(fitness)가 계획 비용인 교과서적 세대 유전 알고리즘이다. 드라이버 루프는 간결하다.
// geqo — src/backend/optimizer/geqo/geqo_main.cpool_size = gimme_pool_size(number_of_rels);number_generations = gimme_number_generations(pool_size);pool = alloc_pool(root, pool_size, number_of_rels);random_init_pool(root, pool);sort_pool(root, pool); /* sort by fitness once; kids replace worst */
for (generation = 0; generation < number_generations; generation++){ geqo_selection(root, momma, daddy, pool, Geqo_selection_bias); /* default build: edge recombination crossover (ERX) */ gimme_edge_table(root, momma->string, daddy->string, pool->string_length, edge_table); kid = momma; edge_failures += gimme_tour(root, edge_table, kid->string, pool->string_length); kid->worth = geqo_eval(root, kid->string, pool->string_length); spread_chromo(root, kid, pool); /* reinsert kid by fitness rank */}best_tour = (Gene *) pool->data[0].string;best_rel = gimme_tree(root, best_tour, pool->string_length);세 가지 설계 포인트가 중요하다. 첫째, 풀은 한 번 정렬되고 이후 각 자식은 spread_chromo로 적합도 순위에 삽입되어 최악의 개체를 밀어낸다. Whitley의 Genitor에서 적용한 준정상 상태(steady-state) 방식이다. 둘째, 적합도는 실제 계획 비용이다. geqo_eval은 실제로 투어의 조인 릴레이션을 구축하고 cheapest_total_path->total_cost를 읽는다. GEQO는 DP와 동일한 경로에 비용을 매기되, 훨씬 적은 수의 순서에 대해서만 수행한다. 셋째, 탐색은 geqo_seed로 시드되므로 시드를 고정하지 않으면 출력이 비결정론적이다. 2^n 벽을 탈출하는 데 따르는 운영상의 대가다.
클럼프 병합 gimme_tree는 임의의 순열이 합법적인 계획을 산출할 수 있게 해주는 장치다. 투어 순서대로 맹목적으로 조인하는 대신(아우터 조인이나 LATERAL 제약을 위반할 수 있음), 각 릴레이션은 desirable_join하는 첫 번째 기존 클럼프에 조인되고, 불합법/바람직하지 않은 조인은 연기된다. 남은 클럼프는 마지막에 강제 조인된다. 동일한 make_join_rel을 거치므로 완전 탐색이 따르는 모든 합법성·비용 규칙이 여기서도 적용된다.
flowchart TD
INIT["alloc_pool + random_init_pool<br/>sort_pool by fitness"] --> GEN{"generation < number_generations?"}
GEN -- yes --> SEL["geqo_selection<br/>pick momma + daddy by linear bias"]
SEL --> XOVER["recombination (ERX)<br/>crossover -> kid tour"]
XOVER --> EVAL["geqo_eval -> gimme_tree<br/>fitness = cheapest_total_path cost"]
EVAL --> SPREAD["spread_chromo<br/>reinsert kid, drop worst"]
SPREAD --> GEN
GEN -- no --> BEST["gimme_tree(best_tour)<br/>return cheapest join rel"]
유전 루프와 DP 루프는 호출자 관점에서 교환 가능하다. 두 방식 모두 initial_rels를 소비하고 cheapest_total_path를 가진 단일 최상위 RelOptInfo를 반환한다. 차이는 커버리지뿐이다. DP는 비용 모델 내에서 전역 최적을 보장하고, GEQO는 공간을 샘플링해 샘플한 것 중 최선을 반환한다. make_rel_from_joinlist가 단일 if로 두 방식(그리고 훅)을 선택할 수 있는 이유가 이 대체 가능성이다.
소스 코드 가이드
섹션 제목: “소스 코드 가이드”이 절에서는 플래너의 위임에서 유전 폴백까지 심볼 단위로 호출 체인을 추적한다. 심볼 이름을 기준으로 삼는다. 마지막 표의 줄 번호는 updated: 날짜 기준의 힌트다.
진입점과 분기 (allpaths.c)
섹션 제목: “진입점과 분기 (allpaths.c)”- **
make_one_rel**은 플래너의 접근 경로 생성 최상위 함수다. 기본 릴레이션 경로를 설정(set_base_rel_pathlists)하고make_rel_from_joinlist를 호출해 조인 트리를 구축한다. (postgres-path-generation.md에 자세히 설명됨.) - **
make_rel_from_joinlist**는 조인 목록을 재귀 순회해initial_rels를 구축한 뒤,levels_needed에 따라 분기한다.join_search_hook오버라이드,enable_geqo && levels_needed >= geqo_threshold이면geqo, 그 외에는standard_join_search를 선택한다. 조인트리 항목이 하나면 탐색 없이 즉시 반환한다. join_search_hook(join_search_hook_type전역)은 익스텐션이 탐색 전체를 대체할 수 있는 심(seam)이다.pg_hint_plan이 사용하는 이음새다.
완전 DP (allpaths.c + joinrels.c)
섹션 제목: “완전 DP (allpaths.c + joinrels.c)”- **
standard_join_search**는root->join_rel_level을 할당하고, 레벨 1을initial_rels로 시드한 뒤,lev를 2에서levels_needed까지 순회하며join_search_one_level을 호출하고 각 새 조인 릴레이션을generate_partitionwise_join_paths,generate_useful_gather_paths,set_cheapest로 마무리한다. 최상위 레벨에 릴레이션이 하나임을 단언하고 반환한다. - **
join_search_one_level**은 열거자다. 좌/우 편향 조인을 위해joinrels[level-1]을 스캔하고,joinrels[k] x joinrels[level-k]에 대한 부시 이중 루프를 실행하며, 레벨이 비어 있는 경우에만 최후 수단 카테시안 폴백을 재실행한다. 새로 구축된 조인 릴레이션이 올바른 목록에 배치되도록root->join_cur_level을 설정한다. - **
make_rels_by_clause_joins**는old_rel을other_rels(초기 릴레이션)의 각 멤버 중 서로소이고 관련 조인 절이나have_join_order_restriction으로 연결된 것과 조인한다. - **
make_rels_by_clauseless_joins**는old_rel을 서로소 멤버 모두와 무조건 조인한다. 사용 가능한 조인 절이 없는 릴레이션과 최후 수단 패스에 사용된다. has_join_restriction/have_relevant_joinclause/ **have_join_order_restriction**은 어떤 쌍의 비용을 계산할 가치가 있는지 결정하는 조인 그래프 인접 테스트다(joininfo.c에 정의됨).
조인 릴레이션 구축과 메모 (joinrels.c)
섹션 제목: “조인 릴레이션 구축과 메모 (joinrels.c)”- **
make_join_rel**은 “이 두 릴레이션의 조인을 구축”하는 보편적 진입점이다. relid를bms_union으로 합치고,join_is_legal을 확인하고,add_outer_joins_to_relids로 아우터 조인 relid를 접어 넣고,build_join_rel로RelOptInfo를 탐색·구축하고, 경로를 채운다. 불합법 쌍에는NULL을 반환한다. - **
join_is_legal**은 제안된 조인이 아우터 조인, 세미/안티 조인, LATERAL 순서 제약을 따르는지 확인하고,SpecialJoinInfo와 입력 스왑 여부를 보고한다. - **
init_dummy_sjinfo**는 일반 이너 조인(원래는 없음)을 위한 최소한의SpecialJoinInfo를 만들어 선택도 코드가 무엇이 조인되는지 알 수 있게 한다. build_join_rel(relnode.c)은 relid 집합을 키로join_rel_hash를 탐색·생성한다. 이것이 DP 메모다. 어떤 relid 집합의 첫 번째 호출자가 할당하고, 이후 호출자는 기존 노드를 재사용해 경로를 추가한다.- **
populate_joinrel_with_paths**는sjinfo->jointype에 따라 분기하고, 합법적인 각 방향마다add_paths_to_joinrel을 호출하며, 한 쪽이 증명 가능하게 비어 있거나 상수 거짓 제약이 적용되면 조인 릴레이션을 더미로 표시한다.
고정된 쌍에 대한 경로 열거 (joinpath.c)
섹션 제목: “고정된 쌍에 대한 경로 열거 (joinpath.c)”조인 방법 탐색으로, 순서 쌍이 고정되면 호출된다. postgres-path-generation.md에 속하지만 체인을 완성하기 위해 이름을 나열한다.
- **
add_paths_to_joinrel**은JoinPathExtraData(병합 절 목록, inner-unique 플래그,param_source_rels)를 계산하고 네 경로 빌더를 순서대로 실행한다.sort_inner_and_outer(양쪽 정렬 병합 조인),match_unsorted_outer(중첩 루프 + 이미 정렬된 외부 병합 조인),hash_inner_and_outer(해시 조인), 그리고 FDW와set_join_pathlist_hook익스텐션 훅이다. - **
sort_inner_and_outer**는 cheapest-total 입력에서 후보 선행 pathkey별로 명시적 정렬 병합 조인 경로를 구축한다. - **
match_unsorted_outer**는 중첩 루프 경로(및 순서 있는 외부 병합 조인)를 구축한다.nestjoinOK/useallclauses조인 유형 분기가 여기에 있다. - **
hash_inner_and_outer**는 제한 목록에서 해시 가능한 절을 스캔하고 cheapest-startup과 cheapest-total 외부를 cheapest-total 내부와 조합해 해시 조인 경로를 구축한다. try_nestloop_path/try_mergejoin_path/ **try_hashjoin_path**는 비용-유지 헬퍼다. 각각initial_cost_*검사를 수행하고,required_outer를 계산하고,add_path를 호출해 파레토 비교에서 살아남으면 경로를 조인 릴레이션의 pathlist에 삽입한다.
유전 폴백 (geqo_main.c + geqo_eval.c)
섹션 제목: “유전 폴백 (geqo_main.c + geqo_eval.c)”- **
geqo**는 GA 드라이버다. 풀 크기(gimme_pool_size)와 세대 수(gimme_number_generations)를 결정하고, 풀을 무작위 초기화해 적합도 기준으로 정렬한 뒤 루프를 실행한다.geqo_selection이 두 부모를 선택하고, 재조합 연산자(기본값 ERX)가kid투어를 생성하고,geqo_eval이 kid를 평가하고,spread_chromo가 재삽입한다. 모든 세대를 마친 뒤 최선 투어로gimme_tree를 호출해 반환한다. - **
gimme_pool_size**는 기본값으로 풀 크기를2^(nr_rel+1)로,[10*Geqo_effort, 50*Geqo_effort]로 클램핑한다(즉 10–100에서 50–500 개체). - **
gimme_number_generations**는 기본값으로 세대 수를 풀 크기로 설정한다. - **
geqo_eval**은 적합도 함수다. 비공개 메모리 컨텍스트와 임시join_rel_hash를 열고,join_rel_list를 저장 후 나중에 잘라내어(반복 평가가 메모 항목을 누적하지 않도록)gimme_tree를 호출하고, 결과cheapest_total_path->total_cost를 반환한다(투어에서 합법적 계획이 나오지 않으면DBL_MAX). - **
gimme_tree**는 클럼프 병합 휴리스틱으로 유전자 투어를 조인 릴레이션으로 변환한다. 투어 순서의 각 릴레이션은desirable_join할 수 있는 첫 번째 기존 “클럼프”에merge_clump로 흡수된다. 불합법/바람직하지 않은 조인은 연기되고, 남은 클럼프는 마지막에 강제 조인된다. 완전 탐색과 동일한make_join_rel을 호출하므로 GEQO도 올바른 부시 계획을 생성할 수 있다. - **
merge_clump**는 클럼프를 재귀적으로 첫 번째 조인 가능한 클럼프에 흡수하고, 형성된 각 조인 릴레이션에set_cheapest를 재실행하며, 더 큰 클럼프를 앞에 유지한다.force=true이면 합법적인 어느 곳에나 조인한다(카테시안 허용). - **
desirable_join**은 클럼프 휴리스틱이다. 관련 조인 절이나 조인 순서 제약이 있으면 조인하고, 그렇지 않으면 연기한다.
초독에서 놓치기 쉬운 점이 하나 있다. GEQO는 수천 번의 적합도 평가에 걸쳐 공유 옵티마이저 상태를 오염시키면 안 된다. geqo_eval은 모든 gimme_tree 호출을 상태 저장·복원으로 감싼다. list_length(root->join_rel_list)와 root->join_rel_hash를 기록하고, 일회용 AllocSetContext 내부에서 실행하고, 완료 후 조인 릴레이션 목록을 저장된 길이로 list_truncate하고, 해시 포인터를 복원하고, 컨텍스트를 삭제한다. 이 없이는 평가된 각 투어가 조인 릴레이션을 전역 메모에 누적시키고 다음 투어가 낡은 항목을 “발견”하게 된다. standard_join_search 헤더 주석이 플러그인 작성자에게 “standard_join_search() 호출 중 함수들이 root->join_rel_list와 root->join_rel_hash를 수정한다”고 경고하며 저장·복원 예시로 geqo_eval()을 언급하는 이유가 이것이다. GEQO는 여러 조인 탐색을 실행하려는 모든 훅의 사내 선례다.
위치 힌트 (2026-06-05 기준, REL_18 273fe94)
섹션 제목: “위치 힌트 (2026-06-05 기준, REL_18 273fe94)”| 심볼 | 파일 | 줄 번호 |
|---|---|---|
make_one_rel | src/backend/optimizer/path/allpaths.c | 171 |
make_rel_from_joinlist | src/backend/optimizer/path/allpaths.c | 3352 |
join_search_hook (전역) | src/backend/optimizer/path/allpaths.c | 88 |
standard_join_search | src/backend/optimizer/path/allpaths.c | 3457 |
join_search_one_level | src/backend/optimizer/path/joinrels.c | 73 |
make_rels_by_clause_joins | src/backend/optimizer/path/joinrels.c | 280 |
make_rels_by_clauseless_joins | src/backend/optimizer/path/joinrels.c | 314 |
join_is_legal | src/backend/optimizer/path/joinrels.c | 350 |
init_dummy_sjinfo | src/backend/optimizer/path/joinrels.c | 661 |
make_join_rel | src/backend/optimizer/path/joinrels.c | 696 |
add_outer_joins_to_relids | src/backend/optimizer/path/joinrels.c | 793 |
populate_joinrel_with_paths | src/backend/optimizer/path/joinrels.c | 885 |
add_paths_to_joinrel | src/backend/optimizer/path/joinpath.c | 124 |
try_nestloop_path | src/backend/optimizer/path/joinpath.c | 831 |
try_mergejoin_path | src/backend/optimizer/path/joinpath.c | 1029 |
try_hashjoin_path | src/backend/optimizer/path/joinpath.c | 1222 |
sort_inner_and_outer | src/backend/optimizer/path/joinpath.c | 1357 |
match_unsorted_outer | src/backend/optimizer/path/joinpath.c | 1812 |
hash_inner_and_outer | src/backend/optimizer/path/joinpath.c | 2220 |
select_mergejoin_clauses | src/backend/optimizer/path/joinpath.c | 2501 |
geqo | src/backend/optimizer/geqo/geqo_main.c | 72 |
gimme_pool_size | src/backend/optimizer/geqo/geqo_main.c | 320 |
gimme_number_generations | src/backend/optimizer/geqo/geqo_main.c | 352 |
geqo_eval | src/backend/optimizer/geqo/geqo_eval.c | 57 |
gimme_tree | src/backend/optimizer/geqo/geqo_eval.c | 163 |
merge_clump | src/backend/optimizer/geqo/geqo_eval.c | 238 |
desirable_join | src/backend/optimizer/geqo/geqo_eval.c | 325 |
geqo_threshold (GUC) | src/backend/utils/misc/guc_tables.c | 2223 |
join_rel_level 필드 | src/include/nodes/pathnodes.h | 315 |
소스 검증 (2026-06-05 기준)
섹션 제목: “소스 검증 (2026-06-05 기준)”아래 모든 확인은 커밋 273fe94852b3a7e34fd171e8abdf1481beb302fa(PG 18.x)의 REL_18_STABLE 작업 트리를 기준으로 했다.
- 분기 임계값과 분기.
make_rel_from_joinlist(allpaths.c)에는 인용한 세 갈래 분기가 그대로 있다.join_search_hook, 그 다음enable_geqo && levels_needed >= geqo_threshold→geqo, 아니면standard_join_search. 3400–3424줄을 읽어 확인. geqo_threshold기본값은 12.guc_tables.c에&geqo_threshold, 12, 2, INT_MAX(기본값 12, 최솟값 2)가 선언되어 있다. 동반하는DEFAULT_GEQO_EFFORT 5는src/include/optimizer/geqo.h에 있다. 풀 크기는 50–500/바닥 10–100으로,gimme_pool_size주석의50 to 500 individuals/10 to 100 individuals와 일치한다.join_rel_level이 DP 배열. 필드와 주석이pathnodes.h의PlannerInfo에 존재하고(read_write_ignore),standard_join_search는palloc0((levels_needed + 1) * sizeof(List *))로 할당하고,[1] = initial_rels로 시드하고, 반환 전에 다시 null로 만든다. 확인됨.- 탐색·생성을 통한 메모.
make_join_rel은build_join_rel(root, joinrelids, ...)를 호출한다. relid 집합 탐색·생성 의미론(및 “많은 쌍으로 도달하는 동일 조인 릴레이션” 메모이제이션)은joinrels.c의make_rels_by_clause_joins헤더 주석에 “레벨 2 이상에서는 동일한 조인 릴레이션을 여러 방식으로 생성한다 … join_rel_level 메커니즘 … 각 새 조인 릴레이션이 목록에 한 번만 추가되도록 자동으로 보장한다”고 명시되어 있다. 확인됨. - 부시 루프 경계. 부시
for (k = 2;; k++)루프는k > other_level(중간점)에서 중단되고,have_relevant_joinclause또는have_join_order_restriction이 있는 서로소 쌍에만make_join_rel을 호출한다. joinrels.c 148–198줄에서 확인됨. - 최후 수단 카테시안.
if (joinrels[level] == NIL)블록이make_rels_by_clauseless_joins를 재실행하고, 이후elog(ERROR, "failed to build any %d-way joins", level)은 특수 조인이 없고 LATERAL RTE가 없을 때만 실행된다. 확인됨. - GEQO가
make_join_rel재사용.geqo_eval.c의merge_clump는make_join_rel(root, old_clump->joinrel, new_clump->joinrel)을 호출한다. 즉 유전 경로와 완전 경로가 동일한 조인 릴레이션 구축·경로 생성 기계를 공유한다. geqo_eval.c 260–262줄에서 확인됨. - GEQO 메모 위생.
geqo_eval은list_length(root->join_rel_list)와root->join_rel_hash를 저장하고, 해시를 null로 만들고, 비공개AllocSetContextCreate("GEQO", ...)에서gimme_tree를 실행한 뒤,join_rel_list를list_truncate로 복원하고 해시와 컨텍스트를 삭제한다. geqo_eval.c 95–131줄에서 확인됨. - 기본 재조합 연산자.
geqo.h의#error가드는 ERX/PMX/CX/PX/OX1/OX2 중 하나를 요구한다. 기본 빌드는ERX(에지 재조합 교차)를 정의하고,geqo()의 세대 루프에서#if defined (ERX)분기가 실행된다. CX 전용geqo_mutation인클루드는#if defined(CX)로 가드된다. 확인됨. - 대칭성 처리.
make_rels_by_clause_joins는level == 2에서만foreach_current_index(r) + 1의first_rel로 호출되고, 부시 루프도k == other_level일 때만 같은 오프셋을 사용한다. 두 경우 모두make_join_rel헤더 주석(“x,y와 y,x를 모두 처리”)과join_search_one_level블록 주석에 명시된 대칭성을 반영한다. 확인됨. add_paths_to_joinrel단계 순서. 번호 붙은 주석1.(sort_inner_and_outer),2.(match_unsorted_outer), 비활성화된3.,4.(hash_inner_and_outer),5.(FDW),6.(set_join_pathlist_hook)이 joinpath.c에 그대로 있다. 단계 3(match_unsorted_inner)은#ifdef NOT_USED내부에 있다. joinpath.c 278–345줄에서 확인됨.- REL_18 범위 가드. XLOG2 rmgr 또는
B_DATACHECKSUMSWORKER_*심볼이 없다. 조인 탐색 코드는 코어(src/backend/optimizer/...)이고 contrib이 아니다. 헤더 주석은 여전히Copyright (c) 1996-2025로 REL_18 소스 그대로다.
이 확인들은 문서의 핵심 주장을 검증한다. make_rel_from_joinlist의 단일 분기가 join_rel_level을 바텀업으로 채우는 완전 DP와 조인 순서 투어를 샘플링하는 유전 탐색 중 하나를 선택하고, 두 방식 모두 동일한 make_join_rel → build_join_rel(메모) → add_paths_to_joinrel(경로 탐색) 파이프라인을 거친다. geqo_threshold GUC가 두 체제 경계를 이동하는 유일한 손잡이다.
PostgreSQL 너머 — 비교 설계와 연구 프론티어
섹션 제목: “PostgreSQL 너머 — 비교 설계와 연구 프론티어”PostgreSQL의 조인 열거자는 넓은 설계 공간의 잘 알려진 한 지점에 있다. 대안들을 살펴보면 PostgreSQL이 왜 그런 선택을 했는지, 그리고 현재 연구가 어디에 있는지가 명확해진다.
1. 하향식(Cascades) 대 상향식(Selinger). PostgreSQL은 확고하게 상향식 DP다. 크기 2 조인을 구축하고, 크기 3을 구축하는 방식이다. 주요 현대적 대안은 Graefe의 Volcano/Cascades 옵티마이저(SQL Server와 Apache Calcite가 사용)의 하향식, 변환 기반 프레임워크다. Cascades는 검색 공간을 동치 그룹의 Memo로 표현하고 변환 규칙(조인 교환성, 결합성, 연산자 치환)을 목표 지향 탐색과 분기 한정(branch-and-bound) 가지치기 및 메모이제이션으로 지연 적용한다. 비용 한계를 초과하면 그룹 탐색을 중단할 수 있다. 절충점은 명확하다. Cascades는 더 확장 가능(새 연산자 = 새 규칙)하고 더 공격적으로 가지치기하지만 더 무거운 기계다. Selinger 스타일 DP는 더 단순하고, 그 체제 내에서 완전하고, 추론하기 쉽다. PostgreSQL의 “놀라움 없음” 철학에 맞다. 두 방식 모두 릴레이션 집합으로 키를 잡은 메모 아이디어를 공유한다. PostgreSQL의 join_rel_hash는 규칙 엔진 없는 간소화된 메모다.
2. DPccp 계통 — 연결된 부분 그래프만 열거. Selinger DP의 고전적인 학술적 개선은 DPsize / DPsub / DPccp(Moerkotte & Neumann, “Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees”, VLDB 2006)다. DPccp는 조인 그래프의 **연결된 부분 그래프와 그 여집합 쌍(csg-cmp-pairs)**을 각각 한 번씩만 방문하는 순서로 열거한다. 부시 트리 탐색에서 고려하는 조인 쌍 수가 증명 가능한 최적이다. PostgreSQL의 join_search_one_level은 더 거친 근사다. 레벨 단위로 반복하고 have_relevant_joinclause로 연결되지 않은 쌍을 건너뛰지만, 엄밀한 csg-cmp-쌍 열거를 구현하지 않으므로 일부 절 없는 경우에서 “중복 작업”을 감수한다(소스 주석이 공개적으로 인정). 이것은 알려진 격차다. 복잡한 조인 술어를 처리하는 하이퍼그래프 확장 DPhyp가 PostgreSQL이 채택하지 않은 최신 기술이다.
3. 임계값 문제와 GEQO의 연식. PostgreSQL이 geqo_threshold = 12에서 유전 알고리즘으로 전환하는 것은 실용적이지만 투박하다. 유전 알고리즘은 최적성 보장을 제공하지 않고 결과가 geqo_seed 값에 따라 비결정론적이어서, 안정적인 계획을 기대하는 사용자를 당황하게 만든다. 현대 시스템은 완전 DP를 훨씬 더 멀리 밀어붙이는 경우가 많고(DPhyp는 20–25개 릴레이션을 편안하게 처리), 하드 컷오프보다 적응형/비용 한정 방식을 사용하기도 한다. GEQO는 본질적으로 1990년대 코드다(Utesch 기여, Whitley의 Genitor에서 적용). 결정론적 계획이 필요한 경우 geqo_threshold를 높이거나 GEQO를 완전히 비활성화하는 것이 일반적인 운영 조언이며, 더 긴 계획 시간을 감수한다. GEQO를 더 현대적인 휴리스틱이나 더 나은 DP 알고리즘으로 교체하자는 커뮤니티 논의가 반복되지만, 완전 경로의 O(2^n) 상수 인수가 실제 장애물이다.
GEQO가 무엇을 보장하고 무엇을 보장하지 않는지 정확하게 짚는 것이 중요하다. spread_chromo가 최악을 제거하는(전 세대 교체가 아닌) 준정상 상태 재삽입, 기본값 에지 재조합 교차(ERX, 두 부모의 인접 정보를 보존하는 경향이 있어 투어 유사 게놈에 적합), Geqo_selection_bias로 조정하는 선택 압력을 갖춘 세대 유전 알고리즘이다. 이 중 어느 것도 전역 최적을 보장하지 않는다. 풀 크기(2^(nr_rel+1)을 [10..50] * Geqo_effort로 클램핑)와 세대 수(기본값 풀 크기)는 “충분히 좋고 충분히 빠르게”를 위한 휴리스틱이지 수렴 증명을 위한 것이 아니다. 실제로 GEQO 계획은 보통 최적 대비 작은 인수 내에 있지만, 시드에 따른 분산은 실재하고, 합법적 계획을 gimme_tree가 복구하지 못한 하나의 불량 평가가 DBL_MAX를 반환해 유전자 풀에서 탈락한다. 솔직한 요약은 GEQO가 DP의 비용 모델 내 최적성 보장을 처리 가능성으로 교환하며, geqo_threshold GUC가 그 교환이 시작되는 시점을 조정하는 사용자 손잡이라는 것이다.
4. 적응형·학습 쿼리 최적화. 전체 Selinger 체계에 대한 가장 깊은 비판은 실행 전에 추정된 카디널리티에 기반해 단일 계획을 확정한다는 것이다. 카디널리티 추정 오차는 조인 트리를 따라 곱셈적으로 복합되므로, 나쁜 추정에 대한 “최적” 계획은 임의로 나빠질 수 있다. 두 연구 방향이 이에 응답한다.
- 적응형 쿼리 처리 — 예를 들어 Eddies(Avnur & Hellerstein,
knowledge/research/dbms-papers/eddies.md참고)는 고정된 조인 순서를 완전히 포기하고, 관찰된 선택도에 반응해 실행 중에 효과적인 순서가 바뀔 수 있도록 각 튜플을 연산자 사이에서 동적으로 라우팅한다. PostgreSQL에는 이런 종류가 없다. 순서는 계획 시에 확정된다. - 학습 옵티마이저 — 최근 시스템들(Neo, Bao, 더 넓은 “ML for query optimization” 계통)은 강화 학습이나 학습된 비용 모델로 조인 순서를 선택하고, 실행 피드백에서 개선될 정책으로 열거자 출력을 취급한다. 이것들은 대체로 연구/익스텐션 영역에 머물러 있다. PostgreSQL 코어는 분석적 비용 모델을 유지하지만,
join_search_hook이 이런 시스템이 연결할 정확한 이음새다.
5. PostgreSQL이 올바르게 한 것. 연식에도 불구하고 설계에는 지속적인 미덕이 있다. 탐색·생성 메모는 정확하고 단순하다. 절 연결성 가지치기를 갖춘 부시 탐색은 중요한 경우(스타 스키마, 강제 부시 아우터 조인)를 전체 DPccp 복잡성 없이 처리한다. 깔끔한 join_search_hook/set_join_pathlist_hook 이음새는 pg_hint_plan과 실험적 옵티마이저가 플래너를 포크하지 않고도 개입할 수 있게 한다. 두 체제 구조 — 가능하면 완전, 불가능하면 휴리스틱 — 는 Selinger의 논문이 사십 년 전에 예상한 형태 그대로다.
- Selinger, P. G., Astrahan, M. M., Chamberlin, D. D., Lorie, R. A., &
Price, T. G. (1979). Access Path Selection in a Relational Database
Management System. SIGMOD. 비용 기반 바텀업 DP 조인 순서 결정, 흥미로운 정렬 순서, 선택도 기반 비용 추정의 기원.
로컬 캡처:
knowledge/research/dbms-papers/systemr-optimizer.md. - Avnur, R. & Hellerstein, J. M. (2000). Eddies: Continuously Adaptive
Query Processing. SIGMOD. 고정된 Selinger 순서에 대한 적응형 순서 결정의 대조점. 로컬 캡처:
knowledge/research/dbms-papers/eddies.md. - Moerkotte, G. & Neumann, T. (2006). Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees (DPccp), VLDB; 그리고 DPhyp (2008). PostgreSQL이 근사하는 최적 연결 부분 그래프 열거. (참고 문헌. 로컬 캡처 없음.)
- PostgreSQL REL_18_STABLE 소스 (커밋
273fe94):src/backend/optimizer/path/allpaths.c—make_rel_from_joinlist,standard_join_search,make_one_rel.src/backend/optimizer/path/joinrels.c—join_search_one_level,make_join_rel,make_rels_by_clause_joins,populate_joinrel_with_paths.src/backend/optimizer/path/joinpath.c—add_paths_to_joinrel과 정렬/중첩루프/해시 경로 빌더.src/backend/optimizer/geqo/geqo_main.c,src/backend/optimizer/geqo/geqo_eval.c— 유전 폴백.src/backend/optimizer/README— 조인 탐색, 매개변수화 경로, param_source_rels 휴리스틱에 대한 플래너 자체 서술.src/include/nodes/pathnodes.h—PlannerInfo.join_rel_level,RelOptInfo.src/include/optimizer/geqo.h,src/backend/utils/misc/guc_tables.c— GEQO 기본값과geqo_thresholdGUC.
- 이 KB 내 교차 참조:
postgres-planner-overview.md(조인 목록이 생성되는 방법과 옵티마이저가 플래너에 맞는 방법),postgres-path-generation.md(이 문서가 위임하는 쌍당 경로 탐색),postgres-cost-model.md(add_path를 구동하는 비용 함수),postgres-executor.md(선택된 조인 계획이 실행되는 방법).