(KO) PostgreSQL 플래너 Prep — 서브쿼리 끌어올리기, 조건식 정규화, 집합 연산

목차

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

학술적 배경

파싱·재작성 단계와 비용 기반 경로 생성 단계 사이에서 쿼리 옵티마이저는 정규화(normalization) 라고 부르는 작업을 수행한다. 이 작업은 최적화가 아니라 쿼리 트리를 균일하고 납작한 형태로 만드는 일이다. 그래야 뒤따르는 비용 기반 탐색이 균일한 문제를 보고 더 넓은 계획 공간을 탐색할 수 있다. PostgreSQL은 이를 prep 단계라 부르며, optimizer/prep/ 아래의 네 파일이 구현한다. 이 문서는 네 가지 prep 작업을 다룬다. 서브쿼리·SubLink 끌어올리기, 조건식 정규화, 타깃 리스트 전처리, 집합 연산 계획이다. subquery_planner와 grouping_planner 드라이버, 그리고 조인 탐색·경로 생성 기계는 형제 문서 postgres-planner-overview.md와 postgres-path-generation.md에 위임한다.

prep를 관통하는 이론 실이 세 가닥 있다.

1. 쿼리 비중첩(unnesting)과 비상관화(decorrelation). 1982년 Kim의 “On Optimizing an SQL-like Nested Query”와 System R 옵티마이저 계보(Selinger et al. 1979, dbms-papers/systemr-optimizer.md)까지 거슬러 올라가는 고전적 결과다. 중첩 서브쿼리 — 상관된 EXISTS, IN/= ANY — 는 의미상 조인이지만, 비용 기반 조인 옵티마이저는 자신이 납작한 릴레이션 집합에서 볼 수 있는 조인만 재순서화하고 메서드를 바꿀 수 있다. 서브쿼리가 WHERE 조건절 안에 숨어 있는 한 옵티마이저는 그것을 행마다 상관 서브플랜으로 평가할 수밖에 없다. 비중첩은 WHERE x IN (SELECT y FROM t)를 세미조인(semijoin) 으로 재작성하고 WHERE NOT EXISTS (...)를 안티조인(antijoin) 으로 재작성해 내부 릴레이션을 조인 재순서화·해시·병합 메서드에 노출시킨다. Database System Concepts(Silberschatz 외)의 쿼리 최적화 장은 이를 “중첩 서브쿼리를 조인으로 변환하기”로 정리하고, 세미조인이 IN/EXISTS의 중복·NULL 의미를 보존하는 정확한 관계 대수 연산자임을 지적한다.

2. 뷰·서브쿼리 병합(merging). FROM 절 서브쿼리 — SELECT * FROM (SELECT ... FROM t WHERE ...) s WHERE ... — 가 그룹핑·집계·DISTINCT·LIMIT을 포함하지 않으면 부모 쿼리에 병합(merge) 할 수 있다. 서브쿼리의 범위 테이블 항목이 부모 것이 되고, 조건절이 부모 조건절이 되며, 출력 컬럼이 인라인으로 치환된다. 이는 뷰 인라이닝과 동일한 연산이다. 병합 이후 병합된 릴레이션은 부모의 단일 전역 조인 탐색에 참여한다. 대가는 장부 관리다. 서브쿼리 출력을 참조했던 모든 Var를 하위 표현식으로 교체하고 범위 테이블 인덱스를 오프셋해야 한다.

3. Boolean 정규화. WHERE 절은 Boolean 표현식 트리이며, 그 트리가 최대한 많은 최상위 AND 구조를 노출할수록 옵티마이저에 유리하다. 최상위 AND 결합소는 각각 독립적으로 밀어 내릴 수 있고 독립적으로 인덱스를 쓸 수 있기 때문이다. 교과서 정규 형태는 CNF(conjunctive normal form, AND-of-ORs)다. NOT를 리프까지 밀어 내리는 드모르간 변환과 OR를 AND 위로 분배하는 변환으로 도달한다. PostgreSQL은 의도적으로 완전 CNF 직전에서 멈춘다. 분배 단계가 절 크기에 지수적으로 팽창할 수 있기 때문이다. 대신 NOT를 밀어 내리고 역 OR 분배 법칙으로 OR 안의 공통 결합소를 인수분해한다.

통합 원칙: prep는 소량의 선제적 재작성으로 훨씬 큰 하위 최적화 기회를 만든다. 이 단계들은 비용을 따지지 않는다. 안전 전제조건이 성립할 때 무조건 적용되는 휴리스틱 재작성이다.

DBMS 공통 설계 패턴

모든 본격적인 관계형 옵티마이저는 PostgreSQL의 prep 단계와 유사한 것을 포함한다. 중첩 서브쿼리, 뷰 병합, Boolean 정규화, 집합 연산이라는 문제는 SQL에 내재하기 때문이다.

서브쿼리 비중첩 — 변환 카탈로그

성숙한 옵티마이저(Oracle, SQL Server, DB2)는 서브쿼리 모양별로 키를 갖는 비중첩 변환 카탈로그를 유지한다. IN/= ANY → 세미조인, NOT IN/<> ALL → 안티조인(악명 높은 NULL 복잡성 포함), 상관 EXISTS → 세미조인, SELECT 목록의 스칼라 서브쿼리 → 아우터 조인 또는 LATERAL이 그것이다. 변환에는 정확성 사이드 컨디션 이 붙는다. 핵심은 3값 논리(NULL)와 중복 의미론이다. 끌어올리기는 결합적 WHERE/ON의 최상위 레벨에서만 건전하다. 서브쿼리의 진리값이 OR나 NOT을 통해 흐를 수 있는 곳에서는 “행 없음”(FALSE)과 “NULL 행”(UNKNOWN)의 구별이 관찰 가능해져 납작한 세미조인이 이를 재현할 수 없다.

장벽 목록으로 제어하는 평탄화

평탄화 결정은 보편적으로 장벽 조건으로 제어된다. 서브쿼리가 집계·GROUP BY·DISTINCT·LIMIT/OFFSET·집합 연산·윈도잉·FOR UPDATE를 갖지 않을 때만 병합 가능하다. 이 특성들은 부모의 납작한 관계 대수에 녹일 수 없는 카디널리티 변경 또는 순서 민감 경계를 의미한다. 모든 엔진에 is_simple_subquery에 상응하는 게이트가 있다.

부정 밀어 내리기와 제한적 정규화

어떤 프로덕션 엔진도 무조건 완전 CNF/DNF를 강제하지 않는다. 분배 단계가 최악의 경우 절 크기에 지수적이기 때문이다. 일반적인 타협은 다음과 같다. (a) 중첩된 동일 연산자 Boolean(AND-under-AND, OR-under-OR)을 N항 노드로 평탄화한다. (b) NOT을 드모르간과 연산자 부정(NOT (a < b) → a >= b)으로 리프까지 밀어 내린다. (c) 역 OR 분배 법칙 같은 저비용·제한적 인수분해를 적용한다. 이렇게 하면 최상위 결합소를 노출하면서 절 크기를 작게 유지한다.

계획 서브트리로서의 집합 연산

UNION, INTERSECT, EXCEPT는 독립적으로 계획한 리프 쿼리 위에 물리 연산자 소형 트리를 올리는 방식으로 계획된다. UNION ALL은 순수 결합(Append), UNION (distinct)은 중복 제거(정렬+유니크 또는 해시 집계)를 추가한다. INTERSECT/EXCEPT는 정렬·해시 기반 집합 연산자 또는 그룹 집계 재작성으로 구현된다. 리프 쿼리는 최적화 장벽이지만 엔진은 흥미로운 정렬 순서를 하향 전파해 병합 기반 부모가 이미 정렬된 자식을 요청할 수 있게 한다.

flowchart TD
  A["Parse/rewrite output<br/>Query tree (may be nested)"] --> B["Prep phase<br/>(optimizer/prep/*)"]
  B --> C["SubLink pull-up<br/>ANY/EXISTS to semi/anti-join"]
  B --> D["Subquery flatten<br/>merge FROM-subquery into parent"]
  B --> E["Qual canonicalize<br/>NOT push-down + OR factoring"]
  B --> F["Targetlist prep<br/>expand INSERT, add junk cols"]
  B --> G["Set-op planning<br/>UNION/INTERSECT/EXCEPT tree"]
  C --> H["Flat jointree + flat WHERE<br/>fed to join search"]
  D --> H
  E --> H
  H --> I["Path generation<br/>(postgres-path-generation.md)"]
  G --> I

PostgreSQL의 구현

PostgreSQL의 prep는 subquery_planner(planner.c) 안에서 이전 재작성의 출력을 다음 재작성이 보도록 고정된 순서로 실행된다. 이 문서와 관련한 드라이버 시퀀스는 다음과 같다.

// subquery_planner — src/backend/optimizer/plan/planner.c
replace_empty_jointree(parse);          // FROM-less query gets RTE_RESULT
if (parse->hasSubLinks)
    pull_up_sublinks(root);             // ANY/EXISTS -> semi/anti-join
preprocess_function_rtes(root);         // inline SRFs into subqueries
parse = root->parse = expand_virtual_generated_columns(root);
pull_up_subqueries(root);               // merge FROM-subqueries into parent
if (parse->setOperations)
    flatten_simple_union_all(root);     // UNION ALL -> appendrel
// ... later ...
reduce_outer_joins(root);               // strength-reduce OJs to inner
remove_useless_result_rtes(root);

조건식 정규화(canonicalize_qual)와 타깃 리스트 전처리(preprocess_targetlist)는 grouping_planner/preprocess_expression에서 더 아래쪽에 호출된다. plan_set_operations는 집합 연산 쿼리의 진입점이다. 순서는 의미를 갖는다. SubLink 끌어올리기가 서브쿼리 끌어올리기 전에 실행되어, 병합으로 노출된 서브쿼리가 자신의 SubLink를 자신이 끌어올릴 때 처리받을 수 있다. flatten_simple_union_all은 UNION ALL 리프에 끌어올리기가 적용되어야 하므로 pull_up_subqueries 이후에 실행된다.

SubLink 끌어올리기 — ANY/EXISTS가 조인이 된다

pull_up_sublinks는 조인트리를 순회하며 각 WHERE/ON 조건절에서 명시적 AND 구조를 재귀적으로 따라가 변환 가능한 SubLink 노드를 찾는다. 재귀는 의도적으로 첫 번째 비-AND 항목에서 멈춘다. 이것이 “결합적 WHERE의 최상위 레벨에서만”이라는 건전성 규칙을 코드로 표현한 것이다.

// pull_up_sublinks_qual_recurse — src/backend/optimizer/prep/prepjointree.c
if (sublink->subLinkType == ANY_SUBLINK)
{
    if ((j = convert_ANY_sublink_to_join(root, sublink,
                                         available_rels1)) != NULL)
    {
        /* insert the new join node into the join tree */
        j->larg = *jtlink1;
        *jtlink1 = (Node *) j;
        j->rarg = pull_up_sublinks_jointree_recurse(root, j->rarg,
                                                    &child_rels);
        j->quals = pull_up_sublinks_qual_recurse(root, j->quals,
                                                 &j->larg, available_rels1,
                                                 &j->rarg, child_rels);
        return NULL;            /* qual replaced by the join; TRUE remains */
    }
    ...
}
else if (sublink->subLinkType == EXISTS_SUBLINK)
{
    if ((j = convert_EXISTS_sublink_to_join(root, sublink, false,
                                            available_rels1)) != NULL)
    { ... }
}

실제 재작성(convert_ANY_sublink_to_join, convert_EXISTS_sublink_to_join)은 plan/subselect.c에 있다. prep의 역할은 변환 가능한 위치를 찾아 JoinExpr(JOIN_SEMI, 또는 EXISTS가 NOT 아래에 있으면 JOIN_ANTI)를 만들고 조인트리에 이어 붙이고 조건절 위치를 NULL로 반환해 상수 TRUE로 접는 것이다. available_rels 인수는 SubLink가 참조할 수 있는 릴레이션 집합을 전달한다. 아우터 조인의 null 불허 쪽을 참조하는 SubLink는 변환할 수 없다. 이 때문에 두 링크 슬롯(jtlink1/jtlink2)이 재귀를 통해 스레드된다.

flowchart TD
  A["WHERE x IN (SELECT y FROM t)"] --> B{"ANY_SUBLINK at<br/>top of conjunctive WHERE?"}
  B -->|yes, refs available_rels| C["convert_ANY_sublink_to_join<br/>build JOIN_SEMI"]
  B -->|no / under OR or NOT| D["leave as correlated SubPlan"]
  C --> E["splice JoinExpr into jointree<br/>larg = old tree, rarg = sub rel"]
  E --> F["qual position returns NULL<br/>(constant TRUE)"]
  F --> G["semijoin now visible to<br/>join-order search"]

서브쿼리 평탄화 — FROM 서브쿼리 병합

pull_up_subqueries는 조인트리를 재귀적으로 순회한다. 각 RangeTblRef에서 해당 RTE가 is_simple_subquery를 통과하는 RTE_SUBQUERY인지 확인하고 그렇다면 pull_up_simple_subquery로 병합한다. 게이트는 실격 특성의 긴 목록이다.

// is_simple_subquery — src/backend/optimizer/prep/prepjointree.c
if (subquery->setOperations)
    return false;               /* setops handled by another path */
if (subquery->hasAggs ||
    subquery->hasWindowFuncs ||
    subquery->hasTargetSRFs ||
    subquery->groupClause ||
    subquery->groupingSets ||
    subquery->havingQual ||
    subquery->sortClause ||
    subquery->distinctClause ||
    subquery->limitOffset ||
    subquery->limitCount ||
    subquery->hasForUpdate ||
    subquery->cteList)
    return false;               /* any of these makes it an opt barrier */
if (rte->security_barrier)
    return false;               /* would leak rows past the barrier */

게이트를 통과하면 pull_up_simple_subquery는 자식 PlannerInfo를 만들고 복사된 서브쿼리에 초기 서브쿼리-플래너 단계를 실행하고 범위 테이블 인덱스를 부모 쪽으로 오프셋하고 — 핵심 단계 — 서브쿼리 출력 컬럼을 참조했던 부모 Var를 대응 서브쿼리 타깃 리스트 표현식으로 치환한다(pullup_replace_vars). 끌어올릴 수 없는 서브쿼리는 RTE_SUBQUERY로 남아 나중에 SubqueryScan 경로가 된다. 최적화 장벽이지만 올바른 장벽이다.

같은 재귀에 세 가지 형제 끌어올리기가 있다. 단순 UNION ALL 서브쿼리는 appendrel이 되고(pull_up_simple_union_all), 단일 행 VALUES는 RESULT가 되며(pull_up_simple_values), 인라인 가능한 집합 반환 함수 RTE는 서브쿼리가 된 뒤 다음 패스에서 끌어올려진다.

이 디스패치는 pull_up_subqueries_recurse 상단에서 RTE 종류 테스트의 연속으로 이루어진다. prep가 릴레이션의 운명을 결정하는 단일 지점이다.

// pull_up_subqueries_recurse — src/backend/optimizer/prep/prepjointree.c
if (rte->rtekind == RTE_SUBQUERY &&
    is_simple_subquery(root, rte->subquery, rte, lowest_outer_join) &&
    (containing_appendrel == NULL ||
     is_safe_append_member(rte->subquery)))
    return pull_up_simple_subquery(root, jtnode, rte,
                                   lowest_outer_join, containing_appendrel);
if (rte->rtekind == RTE_SUBQUERY &&
    is_simple_union_all(rte->subquery))
    return pull_up_simple_union_all(root, jtnode, rte);
if (rte->rtekind == RTE_VALUES &&
    lowest_outer_join == NULL && containing_appendrel == NULL &&
    is_simple_values(root, rte))
    return pull_up_simple_values(root, jtnode, rte);
if (rte->rtekind == RTE_FUNCTION)
    return pull_up_constant_function(root, jtnode, rte,
                                     containing_appendrel);
/* Otherwise, do nothing at this node. */

조건식 정규화 — 제한적 정규화, 완전 CNF 아님

canonicalize_qual이 진입점이다. 헤더 주석은 이 이름이 “역사적 잔재”임을 솔직히 밝힌다. 더 이상 AND-of-ORs 정규 형태를 강제하지 않는다.

// canonicalize_qual — src/backend/optimizer/prep/prepqual.c
Expr *
canonicalize_qual(Expr *qual, bool is_check)
{
    Expr *newqual;
    if (qual == NULL)
        return NULL;
    Assert(!IsA(qual, List));   /* not implicit-AND format */
    /* Pull up redundant subclauses in OR-of-AND trees; drop NULL consts */
    newqual = find_duplicate_ors(qual, is_check);
    return newqual;
}

중첩 AND/OR 평탄화는 이제 여기서 하지 않는다. eval_const_expressions가 전체 패스에서 이미 처리한다. canonicalize_qual은 AND/OR-평탄 입력을 받아 find_duplicate_ors를 적용하는 것만 한다. find_duplicate_ors는 역 OR 분배 법칙 ((A AND B) OR (A AND C)) => (A AND (B OR C))과 최상위 NULL 상수 제거(WHERE에서 NULL::bool을 FALSE로, CHECK에서 TRUE로 처리)를 구현한다.

NOT 밀어 내리기는 eval_const_expressions에서 호출하는 헬퍼 negate_clause에 있다. 드모르간과 연산자 부정을 적용한다.

// negate_clause — src/backend/optimizer/prep/prepqual.c
case T_OpExpr:
{
    OpExpr *opexpr = (OpExpr *) node;
    Oid negator = get_negator(opexpr->opno);    /* (NOT (< A B)) => (>= A B) */
    if (negator)
    {
        OpExpr *newopexpr = makeNode(OpExpr);
        newopexpr->opno = negator;
        ...
        return (Node *) newopexpr;
    }
}
break;
case T_BoolExpr:
    switch (((BoolExpr *) node)->boolop)
    {
        case AND_EXPR:   /* (NOT (AND A B)) => (OR (NOT A) (NOT B)) */
            ...
            return (Node *) make_orclause(nargs);
        case OR_EXPR:    /* (NOT (OR A B)) => (AND (NOT A) (NOT B)) */
            ...
            return (Node *) make_andclause(nargs);
        case NOT_EXPR:   /* NOT NOT cancels */
            return (Node *) linitial(expr->args);
    }

헤더 주석은 트레이드오프를 명시한다. 드모르간이 NOT 개수를 늘릴 수도 있지만, 최상위 AND/OR 구조를 노출하고 논리적으로 동등한 표현식이 equal()로 비교되도록 만드는 것이 노드 수 증가보다 가치 있기 때문에 무조건 적용한다.

타깃 리스트 전처리와 집합 연산

preprocess_targetlist는 파서·재작성기 타깃 리스트를 실행기를 위해 재성형한다. INSERT에서는 누락된 컬럼에 NULL을 채운 속성 순서 전체 리스트로 확장하고(expand_insert_targetlist), UPDATE에서는 타깃 컬럼 번호를 추출해 연속 resno로 재번호하며, UPDATE/DELETE/MERGE에서는 junk 컬럼을 추가한다. junk 컬럼은 행을 찾아 다시 가져오는 데 필요한 행 식별 정보(ctid/wholerow/tableoid)와 FOR UPDATE 행 마크 junk, 다른 릴레이션의 RETURNING Var를 포함한다.

plan_set_operations는 UNION/INTERSECT/EXCEPT 쿼리를 SetOperationStmt 트리를 재귀적으로 따라가(recurse_set_operations) 각 리프 서브쿼리를 subquery_planner로 독립 계획하고 UNION용 Append 경로(generate_union_paths)나 INTERSECT/EXCEPT용 SetOp 경로(generate_nonunion_paths)를 만들어 계획한다. UNION (distinct)가 병합 기반 중복 제거를 위해 이미 정렬된 자식을 요청할 수 있도록 흥미로운 정렬 순서를 parentOp 인수로 하향 전파한다.

소스 코드 가이드

이 절은 네 prep 파일과 호출 흐름으로 묶어 안정적인 심볼 이름 기준으로 정리한다. subquery_planner/grouping_planner(planner.c) 드라이버와 함께 읽으면 좋다. 그쪽은 postgres-planner-overview.md에서 다룬다.

prepjointree.c — 조인트리 재작성

파일의 공개 진입점은 모두 subquery_planner에서 고정 순서로 호출된다. replace_empty_jointree는 FROM 없는 쿼리(SELECT 1)에서 합성 RTE_RESULT를 조인트리에 삽입해 이후 코드가 빈 fromlist를 특수 처리하지 않아도 되게 한다.

• replace_empty_jointree — 초기 정규화. *RESULT* RTE 삽입. 집합 연산 최상위 레벨은 건너뜀.
• pull_up_sublinks — ANY/EXISTS → 세미/안티조인 드라이버. pull_up_sublinks_jointree_recurse(relids를 모으며 FromExpr/JoinExpr 노드 순회)와 pull_up_sublinks_qual_recurse(조건절의 명시적 AND 구조를 내려가다 각 SubLink에서 변환기 호출)를 부른다.
• convert_ANY_sublink_to_join / convert_EXISTS_sublink_to_join — 실제 재작성, plan/subselect.c에 있음(파일 교차). JoinExpr(JOIN_SEMI, NOT EXISTS면 JOIN_ANTI)를 반환하거나 이 위치에서 변환 불가면 NULL을 반환한다.

끌어올리기 위치 테스트는 (jtlink1/jtlink2) 두 링크 슬롯과 두 available_rels 집합을 재귀를 통해 스레드해, 아우터 조인의 null 불허 쪽을 참조하는 SubLink를 null 허용 쪽으로 끌어올릴 수 없다는 규칙을 인코딩한다.

서브쿼리 평탄화가 두 번째 군집이다.

• pull_up_subqueries → pull_up_subqueries_recurse — 조인트리 순회. 각 RangeTblRef에서 rte->rtekind로 디스패치. 재귀가 끌어올리기를 제한할 수 있도록 감싸는 아우터 조인을 아래로 전달하는 방식에 주목한다.

// pull_up_subqueries_recurse — src/backend/optimizer/prep/prepjointree.c
case JOIN_LEFT:
case JOIN_SEMI:
case JOIN_ANTI:
    j->larg = pull_up_subqueries_recurse(root, j->larg, j, NULL);
    j->rarg = pull_up_subqueries_recurse(root, j->rarg, j, NULL);
    break;

• is_simple_subquery — 병합 가능성 게이트(aggs/window/SRF/group/having/sort/distinct/limit/FOR UPDATE/CTE/setops 없음, security barrier 아님, LATERAL 제약, volatile tlist 함수 없음).
• pull_up_simple_subquery — 실제 병합. 자식 PlannerInfo 생성, 서브쿼리 RT 인덱스 오프셋, pullup_replace_vars* 패밀리로 부모 Var 치환.
• pull_up_simple_union_all / is_simple_union_all / is_simple_union_all_recurse — UNION ALL 서브쿼리를 appendrel로 평탄화. recurse 헬퍼는 모든 노드가 op->all인 SETOP_UNION이고 colTypes가 일치할 것을 요구한다.

// is_simple_union_all_recurse — src/backend/optimizer/prep/prepjointree.c
else if (IsA(setOp, SetOperationStmt))
{
    SetOperationStmt *op = (SetOperationStmt *) setOp;
    if (op->op != SETOP_UNION || !op->all)   /* must be UNION ALL */
        return false;
    return is_simple_union_all_recurse(op->larg, setOpQuery, colTypes) &&
        is_simple_union_all_recurse(op->rarg, setOpQuery, colTypes);
}

• preprocess_function_rtes — 함수 RTE를 상수 단순화하고 SRF를 인라인해(inline_set_returning_function) RTE를 서브쿼리로 변환해 다음 끌어올리기 패스가 병합할 수 있게 한다.
• flatten_simple_union_all — 최상위 동반자. 전체 쿼리가 UNION ALL이면 가장 왼쪽 리프를 appendrel 멤버로 만들고, 가장 왼쪽 RTE를 appendrel 부모로 표시하고(inh = true), parse->setOperations를 지워 쿼리가 appendrel의 일반 스캔으로 재계획되게 한다.

// flatten_simple_union_all — src/backend/optimizer/prep/prepjointree.c
childRTE = copyObject(leftmostRTE);
parse->rtable = lappend(parse->rtable, childRTE);
childRTI = list_length(parse->rtable);
((RangeTblRef *) leftmostjtnode)->rtindex = childRTI;
leftmostRTE->inh = true;                  /* now an appendrel parent */
...
parse->setOperations = NULL;              /* pretend no setops */

세 번째 군집은 아우터 조인 강도 축소다. 같은 파일에 있어 여기 포함한다.

• reduce_outer_joins — 2패스. **reduce_outer_joins_pass1**은 조인트리 노드마다 포함 relids와 하위에 아우터 조인이 있는지를 수집한다. **reduce_outer_joins_pass2**는 조건절을 검사해, 위쪽의 null 불허 조건절이 null 확장 행을 어차피 거부할 때 아우터 조인을 inner로(또는 full 조인을 left로) 변환한다. 축소된 조인은 remove_nulling_relids로 nulling-rel 참조를 제거한다.
• remove_useless_result_rtes — 위 재작성 후 불필요해진 RTE_RESULT RTE를 제거한다.

패스-2 핵심은 JOIN_LEFT를 JOIN_ANTI로 변환하고(조인 자체 조건절이 strict하고 내부 행의 후속 사용이 없을 때) JOIN_RIGHT를 arm을 바꿔 정규 JOIN_LEFT로 변환한다. pull_up_sublinks가 앞서 만든 세미/안티 조인은 의도적으로 건너뛴다. 상위 조건절이 오른쪽을 참조할 수 없기 때문이다.

// reduce_outer_joins_pass2 — src/backend/optimizer/prep/prepjointree.c
case JOIN_SEMI:
case JOIN_ANTI:
    /*
     * These could only have been introduced by pull_up_sublinks, so
     * there's no way that upper quals could refer to their righthand
     * sides, and no point in checking.
     */
    break;
...
if (jointype == JOIN_RIGHT)            /* canonicalize to LEFT by swapping */
{
    Node *tmparg = j->larg;
    j->larg = j->rarg;
    j->rarg = tmparg;
    jointype = JOIN_LEFT;
    right_state = linitial(state1->sub_states);
    left_state = lsecond(state1->sub_states);
}

prepqual.c — Boolean 정규화

• canonicalize_qual — 공개 진입점. AND/OR-평탄 입력을 받아(eval_const_expressions가 평탄화) find_duplicate_ors에 위임. is_check 플래그가 NULL 상수 처리를 WHERE 의미(NULL≈FALSE)와 CHECK 의미(NULL≈TRUE) 사이에서 전환한다.
• negate_clause — eval_const_expressions에서 호출하는 NOT 밀어 내리기 헬퍼. Const, OpExpr(연산자 부정), ScalarArrayOpExpr(= ANY ↔ <> ALL), BoolExpr(드모르간, NOT-NOT 취소), NullTest, BooleanTest를 처리한다. 더 영리한 규칙이 없으면 리터럴 make_notclause로 폴스루한다.
• find_duplicate_ors — 최상위 AND/OR 구조를 재귀적으로 따라가고 WHERE/CHECK 규칙에 따라 NULL/상수 입력을 제거하며 각 OR 목록을 process_duplicate_ors에 넘긴다.
• process_duplicate_ors — 역 OR 분배 법칙 구현. 가장 짧은 AND 자식을 참조로 선택하고 모든 OR arm에 존재하는 참조 항(“승자”)을 찾아 인수분해한다.

// process_duplicate_ors — src/backend/optimizer/prep/prepqual.c
/* Choose the shortest AND clause as the reference list */
foreach(temp, orlist)
{
    Expr *clause = (Expr *) lfirst(temp);
    if (is_andclause(clause))
    {
        int nclauses = list_length(((BoolExpr *) clause)->args);
        if (reference == NIL || nclauses < num_subclauses)
        {
            reference = ((BoolExpr *) clause)->args;
            num_subclauses = nclauses;
        }
    }
    else { reference = list_make1(clause); break; }
}

• pull_ands / pull_ors — 중첩된 동일 연산자 Boolean(AND-under-AND, OR-under-OR)을 단일 N항 arglist로 평탄화한다. 위 인수분해가 서브절을 끌어올린 뒤 평탄성을 복원하는 데 쓴다.

preptlist.c — 타깃 리스트 전처리

• preprocess_targetlist — 드라이버. 결과는 root->processed_tlist에 담긴다. commandType으로 분기한다.
  • CMD_INSERT → expand_insert_targetlist(속성 순서 리스트, 누락·삭제된 컬럼에 NULL/Const, coerce_null_to_domain으로 도메인 강제 변환).
  • CMD_UPDATE → extract_update_targetlist_colnos(타깃 컬럼 번호를 root->update_colnos로 추출, resno를 연속 번호로 재번호).
  • CMD_UPDATE/DELETE/MERGE 비상속 → add_row_identity_columns(junk ctid 등).
• junk 컬럼 추가. 드라이버는 각 PlanRowMark마다 ctid<id>(TID), wholerow<id>, tableoid<id> junk TLE를 붙이고, 다른 릴레이션의 RETURNING Var도 추가한다.

// preprocess_targetlist — src/backend/optimizer/prep/preptlist.c
if (rc->allMarkTypes & ~(1 << ROW_MARK_COPY))
{
    var = makeVar(rc->rti, SelfItemPointerAttributeNumber, TIDOID, ...);
    snprintf(resname, sizeof(resname), "ctid%u", rc->rowmarkId);
    tle = makeTargetEntry((Expr *) var, list_length(tlist) + 1,
                          pstrdup(resname), true /* resjunk */);
    tlist = lappend(tlist, tle);
}

• get_plan_rowmark — RT 인덱스로 PlanRowMark를 조회하는 헬퍼.

prepunion.c — 집합 연산 계획

• plan_set_operations — 집합 연산 쿼리 진입점. 가장 왼쪽 리프(출력 컬럼 이름용)를 찾은 뒤 generate_recursion_path(재귀 WITH RECURSIVE UNION) 또는 **recurse_set_operations**로 분기.
• recurse_set_operations — 디스패처. 리프 RangeTblRef는 리프 서브쿼리에서 subquery_planner를 트리거(최적화 장벽). SetOperationStmt는 generate_union_paths 또는 generate_nonunion_paths로 분기. parentOp 인수가 흥미로운 정렬 순서를 하향 전파.
• generate_union_paths — UNION/UNION ALL용. 동일한 자식 UNION 노드 병합(plan_union_children), Append tlist 생성(generate_append_tlist), 자식 경로 생성, Append 경로 생성. distinct UNION에는 정렬+유니크와/또는 해시-집계 중복 제거 추가.
• generate_nonunion_paths — INTERSECT/EXCEPT용. 양쪽 arm 재귀, SetOp tlist 생성, groupList 계산, 정렬/해시 가능성 확인. 비-EXCEPT의 경우 더 작은 릴레이션을 앞에 놓기 위해 입력을 교환. 데이터타입이 정렬과 해시 모두 지원하지 않으면 오류.
• generate_setop_tlist / generate_append_tlist / generate_setop_grouplist — 자식 컬럼 타입이 집합 연산 출력 타입과 다를 때 타입 강제 변환 삽입을 포함하는 tlist/group-clause 생성.

INTERSECT/EXCEPT에서 입력이 선택되고 필요에 따라 교환된 뒤, 결과 RelOptInfo가 UPPERREL_SETOP에 생성되고 연산자와 all 플래그에서 SetOpCmd가 선택된다. 해시 계획은 가장 저렴한 자식 경로 위의 SetOp이다.

// generate_nonunion_paths — src/backend/optimizer/prep/prepunion.c
switch (op->op)
{
    case SETOP_INTERSECT:
        cmd = op->all ? SETOPCMD_INTERSECT_ALL : SETOPCMD_INTERSECT;
        break;
    case SETOP_EXCEPT:
        cmd = op->all ? SETOPCMD_EXCEPT_ALL : SETOPCMD_EXCEPT;
        break;
}
if (can_hash)
{
    path = (Path *) create_setop_path(root, result_rel, lpath, rpath,
                                      cmd, SETOP_HASHED, groupList,
                                      dNumGroups, dNumOutputRows);
    add_path(result_rel, path);
}

입력 교환 휴리스틱(INTERSECT는 더 작은 릴레이션 먼저, EXCEPT는 왼쪽 입력 고정)은 해시 테이블 크기와 왼쪽 입력 비어있음 빠른 경로를 예측 가능하게 만드는 prep 단계의 계획 형태 결정이다.

flowchart TD
  A["plan_set_operations"] --> B{"hasRecursion?"}
  B -->|yes| C["generate_recursion_path<br/>RecursiveUnion"]
  B -->|no| D["recurse_set_operations"]
  D --> E{"node kind"}
  E -->|RangeTblRef leaf| F["subquery_planner<br/>(barrier, build_simple_rel)"]
  E -->|UNION SetOpStmt| G["generate_union_paths<br/>Append + dedup"]
  E -->|INTERSECT/EXCEPT| H["generate_nonunion_paths<br/>SetOp sort/hash"]
  G --> I["root->processed_tlist"]
  H --> I
  C --> I

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

심볼	파일	줄
replace_empty_jointree	optimizer/prep/prepjointree.c	410
pull_up_sublinks	optimizer/prep/prepjointree.c	468
pull_up_sublinks_qual_recurse	optimizer/prep/prepjointree.c	652
preprocess_function_rtes	optimizer/prep/prepjointree.c	914
pull_up_subqueries	optimizer/prep/prepjointree.c	1102
pull_up_subqueries_recurse	optimizer/prep/prepjointree.c	1146
pull_up_simple_subquery	optimizer/prep/prepjointree.c	1291
pull_up_simple_union_all	optimizer/prep/prepjointree.c	1636
is_simple_subquery	optimizer/prep/prepjointree.c	1826
is_simple_union_all	optimizer/prep/prepjointree.c	2234
is_simple_union_all_recurse	optimizer/prep/prepjointree.c	2262
flatten_simple_union_all	optimizer/prep/prepjointree.c	3002
reduce_outer_joins	optimizer/prep/prepjointree.c	3121
reduce_outer_joins_pass1	optimizer/prep/prepjointree.c	3194
remove_useless_result_rtes	optimizer/prep/prepjointree.c	3615
negate_clause	optimizer/prep/prepqual.c	73
canonicalize_qual	optimizer/prep/prepqual.c	293
pull_ands	optimizer/prep/prepqual.c	323
pull_ors	optimizer/prep/prepqual.c	349
find_duplicate_ors	optimizer/prep/prepqual.c	406
process_duplicate_ors	optimizer/prep/prepqual.c	517
preprocess_targetlist	optimizer/prep/preptlist.c	64
extract_update_targetlist_colnos	optimizer/prep/preptlist.c	348
expand_insert_targetlist	optimizer/prep/preptlist.c	382
get_plan_rowmark	optimizer/prep/preptlist.c	526
plan_set_operations	optimizer/prep/prepunion.c	93
recurse_set_operations	optimizer/prep/prepunion.c	209
generate_recursion_path	optimizer/prep/prepunion.c	357
generate_union_paths	optimizer/prep/prepunion.c	676
generate_nonunion_paths	optimizer/prep/prepunion.c	998
generate_setop_tlist	optimizer/prep/prepunion.c	1357
generate_append_tlist	optimizer/prep/prepunion.c	1485
convert_ANY_sublink_to_join	optimizer/plan/subselect.c	1333
convert_EXISTS_sublink_to_join	optimizer/plan/subselect.c	1450
subquery_planner (드라이버)	optimizer/plan/planner.c	~700

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

REL_18_STABLE 작업 트리 커밋 273fe94(/data/hgryoo/references/postgres, PG 18.x)를 기준으로 검증했다. 수행한 확인 사항은 다음과 같다.

• 드라이버 순서. planner.c의 subquery_planner는 순서대로 호출한다. replace_empty_jointree(748줄), pull_up_sublinks(757줄, parse->hasSubLinks로 조건부), preprocess_function_rtes(765줄), expand_virtual_generated_columns(773줄), pull_up_subqueries(779줄), flatten_simple_union_all(788줄, parse->setOperations로 조건부), reduce_outer_joins(1260줄), remove_useless_result_rtes(1269줄), preprocess_targetlist(1809줄). grep으로 확인. 각 호출 위치의 소스 내 주석이 §PostgreSQL의 구현에 인용한 순서 이유를 명시한다.

• canonicalize_qual이 더 이상 CNF를 강제하지 않음. 헤더 주석(279–283줄)은 정규 형태 동작이 “이론적 순수성이 실제 유용성보다 컸다”는 이유로 제거되었다고 명시한다. 본문은 find_duplicate_ors만 호출한다. 평탄화가 eval_const_expressions로 이동했음을 헤더 주석(14–17줄)으로 확인했다.

• SubLink 변환기가 파일 교차. convert_ANY_sublink_to_join과 convert_EXISTS_sublink_to_join은 prepjointree.c가 아닌 plan/subselect.c(1333줄, 1450줄)에 정의되어 있다. prep는 위치를 찾고 반환된 JoinExpr를 이어 붙이기만 한다. 옵티마이저 트리 전체에 대한 grep으로 이 경계를 확인했다.

• is_simple_subquery 게이트 목록. 실격 필드 전체(hasAggs, hasWindowFuncs, hasTargetSRFs, groupClause, groupingSets, havingQual, sortClause, distinctClause, limitOffset, limitCount, hasForUpdate, cteList, setOperations, security_barrier, LATERAL 참조, volatile tlist)가 함수(1841–1946줄)에 그대로 있음. 발췌 소스와 일치.

• flatten_simple_union_all 사이드 이펙트. leftmostRTE->inh = true와 parse->setOperations = NULL(3055줄, 3070줄) 설정 확인. 소스 내 주석이 pull_up_simple_subquery Assert가 setOperations를 먼저 지워야 하는 이유임을 명시.

• junk 컬럼 이름. preprocess_targetlist가 rc->rowmarkId로 키를 삼아 ctid%u(249줄), wholerow%u(263줄), tableoid%u(280줄)라는 resjunk TLE를 만든다. 발췌 소스와 일치.

• 범위 밖 심볼. 경로 생성 세부 사항(build_setop_child_paths, create_append_path, EquivalenceClass 설정, make_pathkeys_for_sortclauses)은 호출 대상으로만 이름을 언급하며 내부는 postgres-path-generation.md에 속한다. subquery_planner와 grouping_planner 본문은 postgres-planner-overview.md에 속한다. 위치 힌트 테이블의 줄 번호는 이 updated: 날짜 범위에 한정되며 시간이 지나면 달라질 수 있다. 심볼 이름이 영속적인 기준점이다.

PostgreSQL 너머 — 비교 설계와 연구 동향

PostgreSQL의 prep 단계는 쿼리 비중첩과 정규화에 관한 훨씬 넓은 연구·공학 문헌의 실용적 부분집합이다.

비중첩 — PostgreSQL과 완전 분류 체계 비교

PostgreSQL은 정확히 두 가지 SubLink 모양을 조인으로 비중첩한다. ANY/IN을 세미조인으로, EXISTS를 세미/안티조인으로 변환하며, 이는 결합적 WHERE/ON의 최상위 레벨에서만 이루어진다. Kim(1982), Ganski & Wong(1987, Kim의 COUNT 버그 수정), 그리고 이후 Neumann & Kemper, “Unnesting Arbitrary Queries” (BTW 2015) 의 “완전” 비중첩 작업은 엄밀히 더 넓은 공간을 기술한다. SELECT 목록의 스칼라 서브쿼리, OR 아래 서브쿼리, 분리 조건절 안의 서브쿼리 같은 임의의 상관 서브쿼리도 의존 조인(d-join) 연산자를 도입하고 의존성을 대수적으로 아래로 밀어 사라지게 만들어 비중첩할 수 있다. 결과 계획에는 상관 실행이 전혀 없다. HyPer와 DuckDB는 이 일반 알고리즘을 구현한다. PostgreSQL은 그렇지 않다. PostgreSQL의 스칼라 서브쿼리와 OR 아래 서브쿼리는 행마다 평가되는 상관 SubPlan으로 남는다(Materialize/Memoize 노드를 통해 캐시될 수 있다. postgres-path-generation.md 참조). 이는 올바르지만 큰 입력에서 비상관 조인보다 수 배 느릴 수 있다.

PostgreSQL이 그 지점에서 멈추는 이유는 §DBMS 공통 설계 패턴에서 논의한 3값 논리 건전성 경계다. 서브쿼리의 진리값이 NOT이나 OR를 통해 흐를 수 있으면 FALSE와 UNKNOWN의 구별이 관찰 가능해지고 납작한 세미조인이 이를 재현할 수 없다. 일반 알고리즘은 세미조인으로 접지 않고 명시적 (안티)의존 조인을 유지하며 대수 레벨에서 NULL을 다룸으로써 이를 우회한다.

매직 집합 / 측방 정보 전달

비상관화의 병렬 계보인 매직 집합(Bancilhon 외 1986; Mumick 외 1990, “Magic is Relevant”) 은 상관 서브쿼리를 재작성해 상관 값을 보조 “매직” 릴레이션으로 모은 뒤 조인해 서브쿼리의 평가를 관련 파라미터 바인딩으로만 제한한다. SQL Server와 DB2는 특정 상관 집계에 매직 집합 재작성을 사용한다. PostgreSQL에는 매직 집합 기계가 없다. 가장 가까운 유사체는 파라미터화된 경로와 Memoize 노드로, 파라미터 값별로 상관 서브플랜 결과를 캐시한다.

정규화 — 제한적 vs. 완전 CNF

PostgreSQL이 CNF를 강제하지 않겠다는 의도적 결정(canonicalize_qual의 “역사적 잔재 이름” 주석)은 이제 통상적인 입장이다. 초기 System R과 학술 옵티마이저는 CNF나 DNF로 정규화했다. 분배 단계의 지수적 팽창(n개의 2항 AND로 이루어진 OR가 2ⁿ개의 절로 분배됨)이 기계 생성 SQL에서 감당 불가하게 만들었다. 현대 엔진은 제한적 정규화와 목표 지향 인수분해를 택한다. PostgreSQL의 process_duplicate_ors에 있는 역 OR 분배 법칙 인수분해는 문서화되어 있다는 점(헤더 주석이 이를 필요로 하는 TPC 벤치마크 쿼리를 인용)에서 특이하며, 손으로 작성한 쿼리가 아닌 생성된 SQL에서 동기를 얻은 최적화의 좋은 사례다. Selinger 시대 비용 기반 탐색은 정규화된 조건절을 입력으로 가정했다. PostgreSQL의 prep는 CNF 비용을 치르지 않고 그 전제조건을 제공하는 층이다.

집합 연산 — SetOp 노드 vs. 그룹 집계

PostgreSQL은 INTERSECT/EXCEPT를 전용 SetOp 실행 노드(정렬 또는 해시 기반)로 계획한다. 일부 교과서에서 제안하듯 HAVING count(...) 조건절을 가진 그룹 집계로 재작성하지 않는다. PG 18 라인은 이 영역을 현대화했다. 역사적인 플래그 컬럼 표현(각 행에 출처를 태그하는 합성 resjunk 컬럼)이 제거되었다. recurse_set_operations에 남아 있는 “XXX Now that there are no flag columns” 주석이 소스에 그 흔적을 남기고 있다. 이 분야의 연구 최전선은 구체화 뷰와 스트리밍을 위한 증분 집합 연산이다. INTERSECT/EXCEPT를 삽입·삭제 아래에서 유지해야 하는 문제로, 여기서 다루는 배치 플래너 범위 밖이다.

연구 최전선

• 비용 기반 비중첩 결정. PostgreSQL은 안전할 때 무조건 끌어올린다. “상관으로 남기기 vs. 비상관화”를 비용으로 따지지 않는다. 일부 형태(고도로 선택적인 상관 EXISTS와 작은 외부 테이블)에서는 상관 형태가 더 빠를 수 있다. 비용 기반 비중첩(DB2와 학술 연구에서 탐구됨)은 PostgreSQL이 채택하지 않은 최전선이다.
• 서브쿼리 캐싱. Memoize 노드(PG 14 이상)는 옵티마이저가 비상관화할 수 없는 상관 서브플랜의 격차를 줄인다. 런타임 캐시로, 계획 시간 재작성이 아니다. prep와 직교하는 기능이다.
• LATERAL을 일반적 탈출구로. PostgreSQL의 prep는 선택적으로 납작하게 만들지 않는 의존성을 표현하는 원칙적 방법으로 점점 더 LATERAL 의미론(is_simple_subquery의 lateral 제약)에 기대고 있다. 알고리즘은 아니더라도 표현에서는 일반 비중첩 작업의 의존 조인 모델에 수렴하는 방향이다.

출처

• 소스 트리. /data/hgryoo/references/postgres, REL_18_STABLE, 커밋 273fe94 (PG 18.x). 핵심 파일:

  • src/backend/optimizer/prep/prepjointree.c — SubLink 끌어올리기, 서브쿼리 평탄화, UNION ALL 평탄화, 아우터 조인 축소.
  • src/backend/optimizer/prep/prepqual.c — negate_clause, canonicalize_qual, find_duplicate_ors, process_duplicate_ors.
  • src/backend/optimizer/prep/preptlist.c — preprocess_targetlist, expand_insert_targetlist, junk 컬럼 추가.
  • src/backend/optimizer/prep/prepunion.c — plan_set_operations와 generate_*_paths/generate_*_tlist 패밀리.
  • src/backend/optimizer/plan/planner.c — subquery_planner 드라이버(호출 순서).
  • src/backend/optimizer/plan/subselect.c — convert_ANY_sublink_to_join, convert_EXISTS_sublink_to_join.

• 교차 참조 (이 KB).

  • postgres-planner-overview.md — subquery_planner/grouping_planner 드라이버, PlannerInfo, 전체 파이프라인.
  • postgres-path-generation.md — RelOptInfo 경로 생성, Append/SetOp/SubqueryScan 경로, 여기서 호출 대상으로 참조되는 EquivalenceClass·pathkey 기계.
  • postgres-join-ordering.md, postgres-join-nodes.md — 끌어올린 세미조인/안티조인이 진입하는 곳.
  • postgres-rewriter.md — prep가 소비하는 상위 단계(단, preprocess_targetlist는 rewriteTargetListIU와 일부 작업을 나눈다).
  • postgres-agg-sort-nodes.md — 집합 연산 중복 제거에 쓰이는 Sort/Unique/Agg 노드.

• 이론 기준점 (.omc/plans/postgres-paper-bibliography.md 참조).

  • Selinger 외 1979, System R 접근 경로 선택 — knowledge/research/dbms-papers/systemr-optimizer.md (prep 정규화 출력을 소비하는 비용 기반 탐색).
  • Database System Concepts (Silberschatz 외, 7판) — knowledge/research/dbms-general/database-system-concepts.md (중첩 서브쿼리-조인 변환, 집합 연산 의미론).
  • Architecture of a Database System (Hellerstein 외 2007) — knowledge/research/dbms-papers/fntdb07-architecture.md (쿼리 재작성/옵티마이저 계층화).
  • Kim 1982; Ganski & Wong 1987; Neumann & Kemper 2015 (임의 쿼리 비중첩); Mumick 외 1990 (매직 집합) — 외부 문헌, §PostgreSQL 너머에서 비교 맥락으로 인용. 이 KB에는 없음.