(KO) PostgreSQL 조인 실행기 — 중첩 루프, 머지 조인, 해시 조인

목차

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

학술적 배경

조인(join)은 조인 조건을 만족하는 두 릴레이션의 튜플을 결합하는 연산이다. 관계 모델의 핵심 연산이며, 후보 튜플 쌍의 수가 두 입력 크기의 곱이기 때문에 쿼리 처리 비용 중 가장 많은 최적화 노력이 집중된다. 나이브한 “모든 쌍 비교”는 O(|R| × |S|)다. Database System Concepts (Silberschatz, Korth & Sudarshan, 7판, 15장 “Query Processing”, §15.5 “Join Operation”)는 물리 연산자 선택 문제를 이렇게 정의한다. 옵티마이저가 조인 순서와 어느 입력이 외부(outer) / *내부(inner)*인지 결정한 뒤, 어떤 알고리즘이 이진 조인 하나를 저렴하게 평가하는가? 교과서는 세 가지 계열을 제시하며, PostgreSQL을 포함한 모든 주류 엔진이 정확히 이 세 가지를 구현한다.

1. 중첩 루프 조인(Nested-loop join) (§15.5.1). 브루트포스 알고리즘이다. 외부 릴레이션 r의 튜플 t_r 마다 내부 릴레이션 s 전체를 스캔하여 조건 θ를 만족하는 모든 쌍 (t_r, t_s)를 출력한다. 최악의 경우 비용은 n_r × b_s + b_r 블록 전송이다. 입력에 아무런 전제 조건(정렬 순서, 인덱스, 등호 조건)이 없어도 동작하기 때문에, 비등호 조인(r.a < s.b)이나 크로스 곱의 유일한 선택지이자 범용 폴백이다. 핵심 개선은 인덱스 중첩 루프 조인 (§15.5.2)이다. 내부 릴레이션의 조인 속성에 인덱스가 있으면 내부 “스캔”이 현재 외부 튜플 값을 키로 하는 인덱스 조회로 바뀌고, 내부 비용이 b_s에서 탐색 비용 c로 줄어든다. 이 경우 가장 나쁜 알고리즘이 종종 최선이 된다.

2. 머지 조인(Merge join) (§15.5.4, “sort-merge join”). 두 입력이 조인 속성 기준으로 정렬되어 있다면, 두 커서를 조율하는 단일 패스로 충분하다. 값이 더 작은 쪽을 전진시키다 두 커서가 만나면 매칭 쌍을 출력하고 동등 그룹을 넘긴다. 정렬된 후의 비용은 b_r + b_s로 입력 크기에 선형이다. 다만 조인 키 기준으로 정렬되어 있어야 한다. 교과서가 강조하는 미묘한 점은 중복 처리다. 외부에 동일 키를 가진 튜플이 여러 개 있으면 새로운 외부 튜플마다 내부 커서를 동등 그룹의 첫 위치로 되감아야 한다. 따라서 알고리즘은 내부 위치를 마킹하고 그 위치로 복원하는 수단이 필요하다.

3. 해시 조인(Hash join) (§15.5.5). 등호 조인에 적합하다. 해시 함수 h로 두 입력을 분할한다. 조인될 튜플은 같은 파티션에 속하므로, 각 파티션에서 (더 작은) 빌드 입력으로 인메모리 해시 테이블을 구축하고 (더 큰) 탐색 (probe) 입력으로 조회하면 된다. 빌드 파티션이 메모리에 맞는 경우 비용은 3(b_r + b_s)로 선형이다. 메모리가 부족하면 GRACE / 하이브리드 해시 조인 (§15.5.5.1–15.5.5.2)이 작동한다. 빌드 릴레이션을 n개의 파티션으로 나누어 임시 파일에 쓰고, 파티션을 하나씩 독립적으로 빌드/탐색 처리하여 한 번에 메모리에 올리는 파티션이 하나뿐이도록 한다. 하이브리드 해시 조인은 분할 패스 중 첫 번째 파티션을 메모리에 유지해 디스크에 쓰지 않는 최적화를 포함한다. 해시 조인은 등호 조인에만 사용할 수 있으나 정렬이나 인덱스가 필요 없다.

교과서의 선택 요약(§15.5.6 “Complex Joins”와 비용 논의)이 옵티마이저가 인코딩하는 정신적 모델이다. 중첩 루프는 입력이 작거나 내부에 선택적 인덱스가 있을 때 유리하다. 머지 조인은 입력이 이미 정렬되어 있거나 정렬 비용이 저렴하고 출력 순서가 유용할 때 유리하다. 해시 조인은 정렬되지 않은 대규모 등호 조인 입력에서 정렬 비용을 초과하는 경우 유리하다. 실행 엔진의 역할은 세 알고리즘을 충실하게 구현하고 플래너가 선택하게 하는 것이다. 이 문서는 REL_18 소스에서 그 세 구현을 추적한다.

실행기 프레임워크(postgres-executor.md)로부터 이어받는 두 가지 속성이 세 노드 모두의 형태를 결정한다.

• Demand-pull 이터레이터 인터페이스. 각 조인은 PlanState이며 ExecProcNode가 한 번 호출될 때마다 조인된 TupleTableSlot 하나를 반환한다. lefttree(외부)와 righttree(내부)의 자식에 ExecProcNode를 호출해 입력 튜플을 끌어온다. 노드 구조체에 상태(현재 외부 튜플, 머지 페이즈, 해시 배치)가 호출 사이에 유지된다.
• 상태는 노드에, 제어는 아래로 재귀한다. 조인의 next() 한 번이 자식들의 next() 호출 연쇄로 이어지고, 조인은 두 입력 스트림을 하나의 출력 스트림으로 변환한다.

DBMS 공통 설계 패턴

교과서가 알고리즘을 제시한다면, 이 절은 프로덕션 이터레이터 엔진이 그 알고리즘을 조합 가능한 풀(pull) 노드로 구현할 때 채택하는 엔지니어링 관례를 정리한다. PostgreSQL이 다른 시스템들과 공유하는 패턴이므로, ## PostgreSQL의 구현 절에서 등장하는 심볼들이 공통 설계 공간의 한 점으로 읽힌다.

외부 입력이 드라이버, 내부 입력이 재읽기 가능 측

풀(pull) 엔진에서 두 입력의 비대칭성은 구체적이다. 외부 입력은 처음부터 끝까지 한 번 스캔된다. 내부 입력은 재읽기 가능해야 한다. 외부 튜플마다 처음부터 다시 스캔되거나(중첩 루프), 마킹된 위치로 되감기 되거나(머지 조인), 해시 테이블로 완전히 구체화된다(해시 조인). 엔진들은 내부 자식이 리스캔(rescan) / 마크-복원 (mark-restore) 프로토콜을 지원하도록 설계하고, 각 조인 유형에 어떤 물리 연산자가 내부 측에 올 수 있는지 결정한다. 비용 비대칭 때문에 조인 순서와 내부/외부 할당은 플래너의 결정이지 실행기의 결정이 아니다.

인덱스 중첩 루프를 위한 매개변수화 리스캔

인덱스 중첩 루프 조인이 빠르려면 내부 인덱스 스캔이 현재 외부 튜플의 값을 키로 사용해야 한다. 관례는 매개변수 전달 채널이다. 조인이 새 외부 튜플을 받을 때마다 관련 외부 컬럼 값을 런타임 매개변수 슬롯에 쓰고, 그 매개변수를 변경된 것으로 표시한 다음 내부 서브트리에 리스캔을 트리거한다. 내부 인덱스 스캔은 그 매개변수 슬롯에서 스캔 키를 읽으므로, 각 “리스캔”이 실제로는 신선한 인덱스 조회가 된다. 이 채널 없이는 내부가 외부 튜플마다 릴레이션 전체를 다시 읽어야 해서 인덱스가 무용해진다.

머지 조인 중복 그룹을 위한 마크와 복원

중복 키에 대한 머지 조인은 동등한 내부 튜플 그룹을 여러 외부 튜플 각각과 재조인해야 한다. 관례는 내부 스트림에 마크 / 복원 쌍을 두는 것이다. 동등 그룹의 첫 내부 튜플 위치를 마킹하고, 그룹을 통과하며 조인하다가, 다음 외부 튜플의 키가 같으면 내부 커서를 마크 위치로 복원해 전체 내부 그룹을 다시 조인한다. 액세스 메서드 수준(인덱스 스캔이 TID를 기억)이나, 최근 읽은 내부 튜플을 캐싱하는 구체화(materialize) 버퍼를 사이에 끼워 구현한다.

더 작은 측 빌드, 메모리 초과 시 스필

해시 조인의 선형 비용은 빌드 측 해시 테이블이 작업 메모리 예산에 맞을 때만 성립한다. 따라서 모든 엔진은 (1) 플래너가 더 작다고 추정한 입력으로 빌드하고, (2) 런타임에 추정이 틀렸을 때를 위한 우아한 저하(graceful degradation) 전략을 갖는다. 해시 값의 추가 비트로 두 입력을 배치로 분할하고, 하나의 배치를 메모리에 유지하면서 나머지는 임시 파일로 스필하여 배치를 순차 처리한다. 배치 수를 2의 거듭제곱으로 유지하면 배로 늘리기가 해시 비트 하나를 더 보는 것에 해당하므로, 이미 디스크에 있는 튜플을 전부 다시 읽어 재분할하지 않아도 된다. 이것이 하이브리드 해시 / GRACE 기계이며, 그 정확성은 인메모리 버킷과 온디스크 배치를 모두 같은 해시 비트로 결정한다는 불변식에 달려 있다.

공통 조인 기반 타입: 조건 분리와 외부 조인 채움

세 알고리즘 모두 외부 조인 의미론과 두 가지 조건 분리를 공유하며, 프로덕션 엔진은 이를 공통 기반으로 묶는다.

• joinqual 대 otherqual. 조인 조건은 두 튜플이 “매칭”되는지 결정한다. 외부 조인에서 외부 튜플이 만족되었는지를 판단하는 데도 이 조건을 사용한다. 기타 조건(WHERE 잔여분)은 행 출력 전에 통과해야 하지만, 매칭 여부 판단에는 포함되지 않는다. 이를 분리해야 LEFT JOIN ... ON 대 WHERE 의미론이 올바르게 처리된다.
• NULL 채움 슬롯. LEFT/RIGHT/FULL/ANTI 조인은 매칭 없는 측을 NULL로 채운 행을 출력해야 한다. 엔진은 채워질 수 있는 측을 위해 미리 상수 올-NULL 슬롯을 만들고, 외부(또는 내부) 튜플에 매치가 없을 때 투영에 대입한다.
• single_match 단락(short-circuit). 세미조인이나 플래너가 내부 측이 고유하다고 증명한 조인의 경우, 엔진은 주어진 외부 튜플에 대한 첫 번째 내부 매치 후 더 이상 스캔하지 않는다.

이론 ↔ PostgreSQL 대응표

이론 / 관례	PostgreSQL 이름
중첩 루프 next()	ExecNestLoop (nodeNestloop.c)
인덱스 NL 매개변수 채널	NestLoop.nestParams → ParamExecData 슬롯, ExecReScan(innerPlan)
머지 조인 next() 상태 기계	ExecMergeJoin (11개 EXEC_MJ_* 상태)
내부 마크 / 복원	ExecMarkPos / ExecRestrPos, mj_MarkedTupleSlot
키별 비교	MJCompare (MergeJoinClause[] + SortSupport)
해시 조인 next() 상태 기계	ExecHashJoinImpl (6개 HJ_* 상태)
빌드 측 해시 테이블	HashJoinTable (MultiExecHash / ExecHashTableInsert로 빌드)
버킷·배치 할당	ExecHashGetBucketAndBatch
버킷 탐색	ExecScanHashBucket
배치 증가 / 스필	ExecHashIncreaseNumBatches, ExecHashJoinSaveTuple, BufFile
메모리 예산 크기 결정	ExecChooseHashTableSize, get_hash_memory_limit
공유 조인 기반	JoinState (js.joinqual, js.ps.qual, js.single_match)
NULL 채움 슬롯	ExecInitNullTupleSlot → *_NullInnerTupleSlot / *_NullOuterTupleSlot
결과 투영	ExecProject(node->js.ps.ps_ProjInfo)

실행기 프레임워크(라이프사이클, ExecProcNode 디스패치, TupleTableSlot 추상화, ExecReScan)는 postgres-executor.md가 담당한다. 조인이 끌어오는 리프 입력 (순차·인덱스 스캔, 머지 조인에 입력을 공급하는 Material / Sort 노드)은 postgres-scan-nodes.md가 담당한다. 컴파일된 joinqual / otherqual / 해시-절 ExprState와 ExecQual / ExecProject는 postgres-expression-eval.md가 담당한다. 이 문서는 세 조인 노드 본체와 그것이 구동하는 해시 테이블 빌드/탐색/스필 기계를 다룬다.

PostgreSQL의 구현

PostgreSQL은 세 가지 교과서 알고리즘을 세 개의 실행기 노드 파일로 구현한다. 모두 공유 JoinState 기반 위에 구축되고, ExecProcNode 호출마다 투영된 TupleTableSlot 하나를 반환한다.

flowchart TB
  subgraph JS["JoinState (공유 기반, execnodes.h)"]
    JQ["jointype<br/>joinqual (매치 조건)<br/>ps.qual = otherqual (WHERE 잔여)<br/>single_match"]
  end
  NL["NestLoopState<br/>ExecNestLoop<br/>nl_NeedNewOuter / nl_MatchedOuter"]
  MJ["MergeJoinState<br/>ExecMergeJoin<br/>mj_JoinState (11 상태)<br/>mj_MarkedTupleSlot"]
  HJ["HashJoinState<br/>ExecHashJoinImpl<br/>hj_JoinState (6 상태)<br/>hj_HashTable"]
  JS --> NL
  JS --> MJ
  JS --> HJ
  HJ -. "inner child" .-> HASH["HashState<br/>MultiExecHash<br/>HashJoinTable (버킷 + 배치)"]

그림 1 — 세 조인 실행기와 공유 JoinState 기반. 모든 조인은 jointype, 매치 조건 joinqual, 잔여 필터 otherqual (ps.qual에 저장), single_match 단락 플래그를 가진다. 해시 조인은 특별히 내부 입력이 항상 전용 Hash 노드이며, MultiExecHash가 HashJoinTable을 빌드하고 나면 조인이 직접 탐색한다.

네 가지 설계 결정이 조인 레이어의 형태를 만든다.

1. 외부는 lefttree, 내부는 righttree. outerPlanState(node) / innerPlanState(node)가 두 자식을 읽는다. 외부는 처음부터 끝까지 한 번 풀(pull)되고, 내부는 재읽기 가능 측(리스캔, 마크/복원, 또는 해싱 대상)이다.
2. 매치/필터 분리는 기반에 있다. js.joinqual이 “매칭됨”을 결정하며 외부 조인과 안티조인 로직을 구동한다. js.ps.qual(제네릭 노드 qual)은 otherqual로, 행 출력 전에 통과해야 한다. 두 조건 모두 컴파일된 ExprState다.
3. 외부 조인은 미리 빌드된 NULL 슬롯을 사용한다. ExecInitNullTupleSlot이 채워질 측을 위한 올-NULL 가상 슬롯을 만들며, 매칭 없는 행을 투영할 때 econtext->ecxt_innertuple / ecxt_outertuple에 대입된다.
4. 해시 조인의 빌드 측은 별도 노드다. Hash 노드(nodeHash.c)는 일반 풀 노드가 아니다. ExecProcNode를 호출하면 오류가 발생하며, MultiExecProcNode로 한 번 구동되어 전체 테이블을 빌드한 다음 HashJoin 노드가 직접 탐색한다.

중첩 루프 — ExecNestLoop

ExecNestLoop는 교과서 알고리즘을 가장 직접적으로 구현한다. 루프는 두 플래그를 가진다. nl_NeedNewOuter(현재 외부 기준으로 내부가 소진됐으므로 다음 외부로 전진)와 nl_MatchedOuter(현재 외부 튜플에 내부 매치가 있었는지 — LEFT/ANTI 채움에 필요). 새 외부 튜플이 필요할 때 하나를 풀(pull)하고, 인덱스 중첩 루프의 핵심 단계인 외부 컬럼 값을 PARAM_EXEC 슬롯에 밀어 넣은 뒤 내부를 리스캔한다.

// ExecNestLoop — src/backend/executor/nodeNestloop.c (condensed)
if (node->nl_NeedNewOuter)
{
    outerTupleSlot = ExecProcNode(outerPlan);
    if (TupIsNull(outerTupleSlot))
        return NULL;                       /* outer exhausted -> join done */

    econtext->ecxt_outertuple = outerTupleSlot;
    node->nl_NeedNewOuter = false;
    node->nl_MatchedOuter = false;

    /* push outer Vars into the inner scan's PARAM_EXEC slots */
    foreach(lc, nl->nestParams)
    {
        NestLoopParam *nlp = (NestLoopParam *) lfirst(lc);
        ParamExecData *prm = &(econtext->ecxt_param_exec_vals[nlp->paramno]);

        prm->value = slot_getattr(outerTupleSlot,
                                  nlp->paramval->varattno, &(prm->isnull));
        /* Flag parameter value as changed */
        innerPlan->chgParam = bms_add_member(innerPlan->chgParam,
                                             nlp->paramno);
    }
    ExecReScan(innerPlan);                 /* now an index probe, not a re-read */
}

innerPlan->chgParam을 설정하는 것이 리스캔을 저렴하게 만드는 열쇠다. postgres-executor.md에서 설명하듯 ExecProcNode는 chgParam을 확인하고 풀(pull) 전에 ExecReScan을 호출한다. 매개변수화된 인덱스 스캔은 바로 이 ParamExecData 슬롯에서 스캔 키를 읽으므로, “리스캔”이 현재 외부 값을 키로 하는 새 인덱스 조회로 실행된다. 일반(비인덱스) 중첩 루프에서는 nestParams가 비어 있고 ExecReScan(innerPlan)이 단순히 내부 스캔을 처음부터 다시 시작한다.

이어서 본체가 다음 내부 튜플을 풀(pull)하고 조건을 검사한다.

// ExecNestLoop — inner advance and qual test (condensed)
innerTupleSlot = ExecProcNode(innerPlan);
econtext->ecxt_innertuple = innerTupleSlot;

if (TupIsNull(innerTupleSlot))
{
    node->nl_NeedNewOuter = true;
    if (!node->nl_MatchedOuter &&
        (node->js.jointype == JOIN_LEFT || node->js.jointype == JOIN_ANTI))
    {
        /* outer had no match: emit NULL-extended row if otherqual passes */
        econtext->ecxt_innertuple = node->nl_NullInnerTupleSlot;
        if (otherqual == NULL || ExecQual(otherqual, econtext))
            return ExecProject(node->js.ps.ps_ProjInfo);
    }
    continue;                              /* go get a new outer tuple */
}

if (ExecQual(joinqual, econtext))          /* match predicate */
{
    node->nl_MatchedOuter = true;
    if (node->js.jointype == JOIN_ANTI) {  /* antijoin: a match means skip */
        node->nl_NeedNewOuter = true;
        continue;
    }
    if (node->js.single_match)             /* semijoin / unique inner */
        node->nl_NeedNewOuter = true;
    if (otherqual == NULL || ExecQual(otherqual, econtext))
        return ExecProject(node->js.ps.ps_ProjInfo);   /* emit joined row */
}

세 노드 모두 공유하는 형태다. joinqual이 MatchedOuter를 결정한다. JOIN_ANTI에서는 매치 발생 시 출력을 억제하고, 내부 소진 시 NULL 채움 행을 출력한다. single_match(세미조인 또는 플래너가 내부를 고유하다고 증명한 경우)에서는 매치 하나가 다음 외부로 전진시킨다. otherqual은 ExecProject 전의 최종 필터다.

flowchart TB
  START["ExecNestLoop 호출"] --> NEED{"nl_NeedNewOuter?"}
  NEED -->|yes| OUT["ExecProcNode(outer)"]
  OUT --> OUTNULL{"outer NULL?"}
  OUTNULL -->|yes| DONE["return NULL (조인 완료)"]
  OUTNULL -->|no| PARAM["outer Var → PARAM_EXEC 주입<br/>chgParam 설정, ExecReScan(inner)"]
  PARAM --> INNER
  NEED -->|no| INNER["ExecProcNode(inner)"]
  INNER --> INNULL{"inner NULL?"}
  INNULL -->|yes| FILL["LEFT/ANTI이고 미매칭?<br/>NULL 채움 행 출력"]
  FILL --> NEED
  INNULL -->|no| JQ{"joinqual?"}
  JQ -->|no| INNER
  JQ -->|yes| OQ{"otherqual?"}
  OQ -->|no| INNER
  OQ -->|yes| EMIT["ExecProject -> 조인 행 반환"]

그림 2 — ExecNestLoop 제어 흐름. 왼쪽 외부 튜플 분기에서 매개변수화 내부 리스캔이 발생한다. 오른쪽 내부 튜플 분기에서 쌍별 조건 검사가 이루어진다. 내부 소진 시 새 외부로 전진하는 동시에, 매칭이 없던 LEFT/ANTI 외부 튜플에 NULL 채움 행을 출력하는 시점이 된다.

ExecReScanNestLoop는 의도적으로 내부 플랜을 리스캔하지 않는다. 내부 리스캔은 메인 루프 안에서 외부 튜플마다 수행되며, 여기서 리스캔하면 런타임 키가 설정된 내부 인덱스 스캔이 깨진다. 외부만 리스캔하고(외부에 chgParam이 없는 경우) 두 플래그를 초기화한다.

머지 조인 — ExecMergeJoin

머지 조인은 두 입력이 머지 키 기준으로 정렬되어 도착한다고 가정한다. 플래너가 인덱스 스캔이나 명시적 Sort 노드로 이를 보장한다. 노드는 열한 개 상태를 가진 명시적 상태 기계로 구현된다. 파일 헤더 주석이 알고리즘 골격을 제시하며, 상태들이 이에 직접 대응한다. 호출 진입부는 노드를 읽고, 튜플별 컨텍스트를 초기화하며, mj_JoinState로 디스패치한다.

// ExecMergeJoin — src/backend/executor/nodeMergejoin.c (state dispatch, condensed)
for (;;)
{
    switch (node->mj_JoinState)
    {
        case EXEC_MJ_INITIALIZE_OUTER:   /* first call: fetch first outer */
            outerTupleSlot = ExecProcNode(outerPlan);
            node->mj_OuterTupleSlot = outerTupleSlot;
            switch (MJEvalOuterValues(node)) { ... }   /* -> INITIALIZE_INNER */
            break;
        case EXEC_MJ_SKIP_TEST:          /* compare; advance the smaller side */
            compareResult = MJCompare(node);
            if (compareResult == 0) {
                if (!node->mj_SkipMarkRestore)
                    ExecMarkPos(innerPlan);             /* mark start of group */
                MarkInnerTuple(node->mj_InnerTupleSlot, node);
                node->mj_JoinState = EXEC_MJ_JOINTUPLES;
            } else if (compareResult < 0)
                node->mj_JoinState = EXEC_MJ_SKIPOUTER_ADVANCE;
            else
                node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE;
            break;
        /* ... JOINTUPLES, NEXTINNER, NEXTOUTER, TESTOUTER, ENDOUTER, ENDINNER ... */
    }
}

비교 자체는 머지 등호 연산자를 실행하는 방식이 아니다. 플래너가 leftexpr = rightexpr 절 목록과 각 절의 btree opfamily / 콜레이션 / 정렬 방향 메타데이터를 전달하면, MJExamineQuals가 각 절을 SortSupport를 가진 MergeJoinClauseData로 변환한다. MJEvalOuterValues / MJEvalInnerValues는 현재 튜플의 키 표현식을 평가하고, MJCompare가 절들을 순회하며 ApplySortComparator를 호출해 0 / <0 / >0을 반환한다.

// MJCompare — src/backend/executor/nodeMergejoin.c (condensed)
for (i = 0; i < mergestate->mj_NumClauses; i++)
{
    MergeJoinClause clause = &mergestate->mj_Clauses[i];

    if (clause->lisnull && clause->risnull) {
        nulleqnull = true;             /* NULL "=" NULL -> not a real match */
        continue;
    }
    result = ApplySortComparator(clause->ldatum, clause->lisnull,
                                 clause->rdatum, clause->risnull,
                                 &clause->ssup);
    if (result != 0)
        break;
}
/* NULL=NULL or a constant-false joinqual must not report equality */
if (result == 0 && (nulleqnull || mergestate->mj_ConstFalseJoin))
    result = 1;                        /* treat as outer > inner: advance inner */

중복 그룹 처리가 알고리즘의 핵심이다. SKIP_TEST가 동등 쌍을 발견하면 내부 위치를 마킹하고(ExecMarkPos와 mj_MarkedTupleSlot에 복사), JOINTUPLES가 쌍을 출력하며, NEXTINNER가 내부를 동등 그룹 안에서 전진시킨다. 내부 그룹이 끝나면 NEXTOUTER가 다음 외부 튜플을 가져오고, TESTOUTER가 새 외부 튜플을 마킹된 내부 튜플과 비교한다. 여전히 동등하면 외부에도 중복이 있는 것이므로 ExecRestrPos로 내부를 마크 위치로 되감아 전체 내부 그룹을 이 새 외부 튜플과 재조인한다.

// ExecMergeJoin — EXEC_MJ_TESTOUTER (condensed)
innerTupleSlot = node->mj_MarkedTupleSlot;
(void) MJEvalInnerValues(node, innerTupleSlot);
compareResult = MJCompare(node);

if (compareResult == 0)            /* new outer still equals marked inner */
{
    if (!node->mj_SkipMarkRestore)
    {
        ExecRestrPos(innerPlan);                  /* rewind inner to the mark */
        node->mj_InnerTupleSlot = innerTupleSlot;
    }
    node->mj_JoinState = EXEC_MJ_JOINTUPLES;      /* re-join the group */
}
else if (compareResult > 0)        /* new outer past the marked group */
{
    /* reload current inner and resume skipping */
    ...
    node->mj_JoinState = EXEC_MJ_SKIP_TEST;
}

플래너가 마크/복원이 불필요하다고 증명할 수 있을 때(예: 내부가 키 기준으로 고유한 경우) skip_mark_restore를 설정하면, 노드가 ExecMarkPos / ExecRestrPos 호출 전체를 건너뛴다(mj_SkipMarkRestore). 외부 조인은 doFillOuter / doFillInner 플래그와 MJFillOuter / MJFillInner 헬퍼가 처리하며, SKIP / ADVANCE / END 상태를 매칭 없이 빠져나가는 튜플마다 NULL 확장 행을 출력한다 (otherqual 통과 조건).

flowchart TB
  IO["INITIALIZE_OUTER<br/>첫 외부 튜플 fetch"] --> II["INITIALIZE_INNER<br/>첫 내부 튜플 fetch"]
  II --> ST{"SKIP_TEST<br/>MJCompare"}
  ST -->|"outer < inner"| SOA["SKIPOUTER_ADVANCE<br/>(LEFT이면 outer 채움)"]
  ST -->|"outer > inner"| SIA["SKIPINNER_ADVANCE<br/>(RIGHT이면 inner 채움)"]
  ST -->|"equal"| MARK["ExecMarkPos inner<br/>-> JOINTUPLES"]
  SOA --> ST
  SIA --> ST
  MARK --> JT["JOINTUPLES<br/>쌍 출력, joinqual+otherqual"]
  JT --> NI["NEXTINNER<br/>그룹 안에서 inner 전진"]
  NI -->|"still equal"| JT
  NI -->|"group ended"| NO["NEXTOUTER<br/>outer 전진"]
  NO --> TO{"TESTOUTER<br/>새 outer == 마크?"}
  TO -->|"equal"| RESTR["ExecRestrPos inner<br/>-> JOINTUPLES"]
  TO -->|"greater"| ST
  RESTR --> JT

그림 3 — ExecMergeJoin 상태 기계. 왼쪽 SKIP_* 상태들이 두 커서를 동기화한다. 오른쪽 JOINTUPLES/NEXTINNER/NEXTOUTER/TESTOUTER 사이클이 동등 그룹을 출력하고, SKIP_TEST에서 설정된 마크와 TESTOUTER의 ExecRestrPos로 외부 중복 키마다 동등 그룹을 재조인한다. ENDOUTER/ENDINNER 상태(미표시)는 한쪽 입력이 소진된 뒤 외부 조인 채움 행을 소진한다.

해시 조인 — ExecHashJoinImpl

해시 조인은 하이브리드 해시 알고리즘으로, 역시 상태 기계(6개 HJ_* 상태)다. 다른 두 노드와 다른 비대칭성이 하나 있다. 내부 입력이 전용 Hash 노드로, 탐색 전에 전체 해시 테이블을 미리 빌드한다. 핵심 드라이버는 ExecHashJoinImpl이며 pg_attribute_always_inline으로 표시되어 병렬 무관 ExecHashJoin과 병렬 인식 ExecParallelHashJoin 두 인스턴스로 생성된다. 컴파일러가 각 인스턴스에서 죽은 parallel 분기를 제거한다. 빌드 상태는 한 번만 실행된다.

// ExecHashJoinImpl — HJ_BUILD_HASHTABLE (condensed, serial path)
case HJ_BUILD_HASHTABLE:
    /* (optional) empty-outer short-circuit for inner joins */
    if (!HJ_FILL_INNER(node) && !parallel && ...)
    {
        node->hj_FirstOuterTupleSlot = ExecProcNode(outerNode);
        if (TupIsNull(node->hj_FirstOuterTupleSlot))
            return NULL;                      /* empty outer -> no inner join */
    }

    hashtable = ExecHashTableCreate(hashNode);
    node->hj_HashTable = hashtable;

    hashNode->hashtable = hashtable;
    (void) MultiExecProcNode((PlanState *) hashNode);   /* BUILD the table */

    if (hashtable->totalTuples == 0 && !HJ_FILL_OUTER(node))
        return NULL;                          /* empty inner -> no rows */

    node->hj_JoinState = HJ_NEED_NEW_OUTER;
    /* FALL THRU */

Hash 자식에 MultiExecProcNode를 호출하면 MultiExecHash → MultiExecPrivateHash가 실행된다. 모든 내부 튜플을 풀(pull)하고 해시 값을 계산해 테이블에 삽입하거나 배치 파일로 스필한다. 빌드 루프 자체가 분할 패스다.

// MultiExecPrivateHash — src/backend/executor/nodeHash.c (condensed)
for (;;)
{
    slot = ExecProcNode(outerNode);          /* "outer" of Hash = inner of join */
    if (TupIsNull(slot))
        break;
    econtext->ecxt_outertuple = slot;
    hashdatum = ExecEvalExprSwitchContext(node->hash_expr, econtext, &isnull);
    if (!isnull)
    {
        uint32 hashvalue = DatumGetUInt32(hashdatum);
        int bucketNumber = ExecHashGetSkewBucket(hashtable, hashvalue);
        if (bucketNumber != INVALID_SKEW_BUCKET_NO)
            ExecHashSkewTableInsert(hashtable, slot, hashvalue, bucketNumber);
        else
            ExecHashTableInsert(hashtable, slot, hashvalue);   /* normal insert */
        hashtable->totalTuples += 1;
    }
}

이후 탐색은 HJ_NEED_NEW_OUTER → HJ_SCAN_BUCKET 사이클로 진행된다. 외부 튜플을 가져와 해시 값을 계산하고, 버킷과 배치를 찾은 뒤 버킷 체인을 순회하며 해시 절을 검사한다. 전체 스필 방식의 정확성은 ExecHashGetBucketAndBatch에 달려 있다. 이 함수가 해시 값을 인메모리 버킷 인덱스(하위 비트)와 배치 인덱스(로테이션된 상위 비트)로 분리한다.

// ExecHashGetBucketAndBatch — src/backend/executor/nodeHash.c
if (nbatch > 1)
{
    *bucketno = hashvalue & (nbuckets - 1);
    *batchno = pg_rotate_right32(hashvalue,
                                 hashtable->log2_nbuckets) & (nbatch - 1);
}
else
{
    *bucketno = hashvalue & (nbuckets - 1);
    *batchno = 0;
}

// ExecScanHashBucket — src/backend/executor/nodeHash.c (condensed)
if (hashTuple != NULL)
    hashTuple = hashTuple->next.unshared;          /* continue current chain */
else
    hashTuple = hashtable->buckets.unshared[hjstate->hj_CurBucketNo];

while (hashTuple != NULL)
{
    if (hashTuple->hashvalue == hashvalue)         /* cheap pre-filter */
    {
        inntuple = ExecStoreMinimalTuple(HJTUPLE_MINTUPLE(hashTuple),
                                         hjstate->hj_HashTupleSlot, false);
        econtext->ecxt_innertuple = inntuple;
        if (ExecQualAndReset(hjclauses, econtext)) /* real equality test */
        {
            hjstate->hj_CurTuple = hashTuple;       /* remember position */
            return true;
        }
    }
    hashTuple = hashTuple->next.unshared;
}
return false;                                      /* bucket exhausted */

두 단계 검사 구조에 주목한다. 체인 해시 테이블은 각 HashJoinTuple 헤더에 전체 hashvalue를 저장하므로, ExecScanHashBucket은 해시 값이 다른 튜플의 비싼 ExecQual을 건너뛰고 해시 충돌 후보에만 해시 절 ExprState를 실행한다.

빌드/탐색과 배치 처리(디스크 스필)

빌드 측 테이블은 플래너의 행 추정치와 hash_mem 예산(get_hash_memory_limit)으로 ExecChooseHashTableSize가 초기 nbuckets와 nbatch(모두 2의 거듭제곱)를 결정해 미리 크기를 잡는다. 추정이 틀릴 수 있으므로 ExecHashTableInsert는 실제 사용 공간을 측정하고 테이블이 spaceAllowed를 초과하면 배치 수를 배로 늘린다.

// ExecHashTableInsert — src/backend/executor/nodeHash.c (condensed)
ExecHashGetBucketAndBatch(hashtable, hashvalue, &bucketno, &batchno);
if (batchno == hashtable->curbatch)
{
    /* in-memory: prepend to bucket chain */
    hashTuple = (HashJoinTuple) dense_alloc(hashtable, HJTUPLE_OVERHEAD + tuple->t_len);
    hashTuple->hashvalue = hashvalue;
    memcpy(HJTUPLE_MINTUPLE(hashTuple), tuple, tuple->t_len);
    hashTuple->next.unshared = hashtable->buckets.unshared[bucketno];
    hashtable->buckets.unshared[bucketno] = hashTuple;

    hashtable->spaceUsed += HJTUPLE_OVERHEAD + tuple->t_len;
    if (hashtable->spaceUsed + hashtable->nbuckets_optimal * sizeof(HashJoinTuple)
        > hashtable->spaceAllowed)
        ExecHashIncreaseNumBatches(hashtable);     /* over budget -> split */
}
else
{
    /* belongs to a later batch: spill to a temp file */
    Assert(batchno > hashtable->curbatch);
    ExecHashJoinSaveTuple(tuple, hashvalue,
                          &hashtable->innerBatchFile[batchno], hashtable);
}

ExecHashIncreaseNumBatches는 nbatch를 배로 늘리고, 배치별 BufFile 배열을 확장한 뒤 인메모리 튜플 전체를 순회하며 배치 번호를 재검사한다. 더 이상 curbatch에 속하지 않는 튜플들을 새 배치 파일로 플러시하고 메모리에서 해제한다. nbatch가 2의 거듭제곱이므로 배로 늘리면 해시 비트 하나가 추가로 노출되어, 인메모리 튜플의 약 절반이 이동하고 나머지는 제자리에 남는다. 스필 자체는 ExecHashJoinSaveTuple이 수행하며, 임시 BufFile을 지연 생성하고 hashvalue와 MinimalTuple을 추가한다.

// ExecHashJoinSaveTuple — src/backend/executor/nodeHashjoin.c (condensed)
if (file == NULL)
{
    MemoryContext oldctx = MemoryContextSwitchTo(hashtable->spillCxt);
    file = BufFileCreateTemp(false);
    *fileptr = file;
    MemoryContextSwitchTo(oldctx);
}
BufFileWrite(file, &hashvalue, sizeof(uint32));    /* hash, then the tuple */
BufFileWrite(file, tuple, tuple->t_len);

현재 배치의 외부 측이 소진되면 HJ_NEED_NEW_BATCH가 ExecHashJoinNewBatch를 호출한다. 완료된 외부 파일을 닫고, 다음 내부 배치 파일을 비워진 해시 테이블로 로드한 뒤 그 배치의 외부 파일을 탐색용으로 다시 연다. 배치 0은 특별하다. 그 내부 튜플들은 빌드 패스에서 이미 메모리에 있고, 외부 튜플들은 직접 외부 자식에서 읽힌다. 나중 배치에 해싱되는 외부 튜플들은 HJ_NEED_NEW_OUTER에서 즉시 외부 배치 파일로 스필된다. 이것이 하이브리드 해시 최적화다. 첫 번째 파티션은 메모리를 떠나지 않는다.

flowchart TB
  BUILD["HJ_BUILD_HASHTABLE<br/>MultiExecHash로 테이블 빌드<br/>(배치 1..n 스필 가능)"] --> NNO["HJ_NEED_NEW_OUTER<br/>외부 튜플 fetch, 해시 계산"]
  NNO -->|"outer NULL"| NNB
  NNO -->|"나중 배치 소속"| SPILL["외부 배치 파일에 저장<br/>NEED_NEW_OUTER 유지"]
  SPILL --> NNO
  NNO -->|"현재 배치"| SB["HJ_SCAN_BUCKET<br/>체인 순회, ExecScanHashBucket"]
  SB -->|"매치 + 조건 통과"| EMIT["ExecProject -> 행 반환"]
  SB -->|"매치 없음"| FOT["HJ_FILL_OUTER_TUPLE<br/>(LEFT: NULL 채움 행 출력)"]
  FOT --> NNO
  NNB["HJ_NEED_NEW_BATCH<br/>ExecHashJoinNewBatch:<br/>다음 내부 배치 파일 로드"] -->|"배치 남음"| NNO
  NNB -->|"배치 없음"| DONE["return NULL (조인 완료)"]

그림 4 — ExecHashJoinImpl 하이브리드 해시 상태 기계(직렬 경로). 빌드가 한 번 실행되고, NEED_NEW_OUTER/SCAN_BUCKET 사이클이 현재 배치를 탐색하며, NEED_NEW_BATCH가 디스크에서 스필된 다음 배치를 로드한다. 나중 배치로 해싱되는 외부 튜플들은 탐색 대신 스필된다. HJ_FILL_INNER_TUPLES(right/full 조인, 미표시)는 배치 전진 전에 매칭 없는 내부 튜플을 테이블에서 스캔한다.

소스 코드 가이드

심볼 이름을 앵커로 사용하라, 줄 번호가 아니라. 함수·구조체 이름은 릴리스를 거쳐도 안정적인 핸들이다. 현재 위치는 git grep -n '<symbol>' src/backend/executor/로 찾을 수 있다. 아래 위치 힌트 표의 줄 번호는 커밋 273fe94(REL_18_STABLE) 기준이며 참고용이다.

중첩 루프 (nodeNestloop.c)

• ExecNestLoop — next() 본체. nl_NeedNewOuter가 새 외부 fetch + nestParams 주입 + ExecReScan(innerPlan)을 구동한다. 내부 전진 단계에서 joinqual 후 otherqual을 검사하고, 내부 소진 시 nl_NullInnerTupleSlot으로 LEFT/ANTI NULL 채움을 처리한다.
• ExecInitNestLoop — NestLoopState를 빌드한다. 외부 자식 초기화 후, nestParams == NIL인 경우에만 내부에 EXEC_FLAG_REWIND를 설정한다(매개변수화된 내부는 신선한 매개변수로 리스캔되므로 REWIND가 불필요하다). single_match = inner_unique || JOIN_SEMI를 설정하고, LEFT/ANTI를 위한 null-inner 슬롯을 빌드한다.
• ExecReScanNestLoop — 외부를 리스캔하고(chgParam이 null인 경우) nl_NeedNewOuter / nl_MatchedOuter를 초기화한다. 내부는 의도적으로 리스캔하지 않는다.
• ExecEndNestLoop — 두 자식에 ExecEndNode를 재귀 호출한다.

머지 조인 (nodeMergejoin.c)

• ExecMergeJoin — 열한 개 상태 기계 (EXEC_MJ_INITIALIZE_OUTER/INNER, SKIP_TEST, SKIPOUTER_ADVANCE/SKIPINNER_ADVANCE, JOINTUPLES, NEXTINNER, NEXTOUTER, TESTOUTER, ENDOUTER/ENDINNER).
• MJExamineQuals — 플래너의 leftexpr = rightexpr 머지절 목록과 opfamily/콜레이션/방향 메타데이터를 SortSupport 비교기 (BTSORTSUPPORT_PROC 또는 BTORDER_PROC 심) 를 가진 MergeJoinClauseData[] 배열로 변환한다.
• MJEvalOuterValues / MJEvalInnerValues — 머지 키 표현식을 clause->ldatum / rdatum으로 평가한다. MJEVAL_MATCHABLE / MJEVAL_NONMATCHABLE(NULL 키) / MJEVAL_ENDOFJOIN(입력 소진 또는 조인을 끝내는 첫 컬럼 NULL)을 반환한다.
• MJCompare — ApplySortComparator로 절들을 순회한다. NULL=NULL과 mj_ConstFalseJoin은 비동등으로 처리해 내부를 전진시킨다.
• MarkInnerTuple (매크로) / ExecMarkPos / ExecRestrPos — 외부 중복 키를 동등한 내부 그룹에 재조인하는 내부 플랜의 마크/복원. mj_MarkedTupleSlot이 마킹된 튜플을 캐시한다.
• MJFillOuter / MJFillInner — 외부 조인에서 매칭 없는 외부/내부 튜플마다 NULL 확장 행을 출력한다(otherqual 통과 조건).
• ExecInitMergeJoin — MergeJoinState를 빌드한다. 키 평가가 튜플별 초기화에서 살아남도록 두 개의 추가 ExprContext(mj_OuterEContext / mj_InnerEContext)를 생성한다. skip_mark_restore가 아닌 경우 내부 자식에 EXEC_FLAG_MARK를 전달한다. Material 내부를 위해 mj_ExtraMarks를 설정한다.
• ExecReScanMergeJoin / ExecEndMergeJoin — EXEC_MJ_INITIALIZE_OUTER로 리셋, 해제.

해시 조인 (nodeHashjoin.c)

• ExecHashJoinImpl — 항상 인라인되는 6-상태 기계 (HJ_BUILD_HASHTABLE, HJ_NEED_NEW_OUTER, HJ_SCAN_BUCKET, HJ_FILL_OUTER_TUPLE, HJ_FILL_INNER_TUPLES, HJ_NEED_NEW_BATCH).
• ExecHashJoin / ExecParallelHashJoin — ExecHashJoinImpl(pstate, false/true)를 인스턴스화하는 두 개의 얇은 래퍼.
• ExecHashJoinOuterGetTuple / ExecParallelHashJoinOuterGetTuple — 다음 외부 튜플을 fetch한다. 배치 0에서는 자식 플랜에서 직접(hj_OuterHash로 해시 값 계산), 이후 배치에서는 외부 배치 BufFile에서 재생.
• ExecHashJoinNewBatch / ExecParallelHashJoinNewBatch — 다음 배치로 전진한다. 내부 파일을 테이블에 로드하고 외부 파일을 다시 연다. 배치가 남지 않으면 false를 반환한다.
• ExecHashJoinSaveTuple — hashvalue + MinimalTuple을 spillCxt의 배치별 임시 BufFile에 추가한다(지연 생성).
• ExecInitHashJoin — HashJoinState를 빌드한다. 내부 자식은 항상 Hash 노드다. hashclauses와 측별 해시 표현식을 컴파일한다.

해시 테이블 빌드/탐색/스필 (nodeHash.c)

• ExecHash — 오류를 발생시킨다. Hash 노드는 MultiExecProcNode로 구동되며 튜플별 ExecProcNode 관례를 따르지 않는다.
• MultiExecHash → MultiExecPrivateHash / MultiExecParallelHash — 모든 내부 튜플을 풀(pull)하고 해시하여 ExecHashTableInsert(또는 스큐 삽입).
• ExecHashTableCreate / ExecChooseHashTableSize — HashJoinTable을 할당한다. 행 추정치와 get_hash_memory_limit으로 nbuckets / nbatch를 결정한다. NTUP_PER_BUCKET == 1이 목표 부하 인자다.
• ExecHashTableInsert — 인메모리 삽입(dense_alloc으로 버킷 체인 앞에 추가) 또는 innerBatchFile[batchno]로 스필. 임계값 초과 시 ExecHashIncreaseNumBuckets / ExecHashIncreaseNumBatches 트리거.
• ExecHashGetBucketAndBatch — 해시 값을 버킷(하위 비트)과 배치(로테이션된 상위 비트)로 분리한다. 스필 방식이 의존하는 불변식.
• ExecHashIncreaseNumBatches — nbatch를 배로 늘리고, 인메모리 튜플을 재검사해 나중 배치 소속은 플러시한다.
• ExecScanHashBucket / ExecParallelScanHashBucket — 버킷 체인을 순회한다. hashvalue 사전 필터 후 ExecQualAndReset(hashclauses).
• ExecPrepHashTableForUnmatched / ExecScanHashTableForUnmatched — 매칭 없는 내부 튜플에 대한 right/full 조인 패스(HJ_FILL_INNER_TUPLES).
• HashJoinTableData (hashjoin.h) — nbuckets / nbatch / spaceUsed / spaceAllowed / curbatch / buckets / innerBatchFile / outerBatchFile.

공유 조인 기반 (execnodes.h)

• struct JoinState — 세 노드 모두에 임베드된 기반. jointype, joinqual, single_match. 제네릭 ps.qual이 otherqual을 담는다.
• struct NestLoopState / MergeJoinState / HashJoinState — 세 구체 상태 노드.

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

심볼	파일	줄
ExecNestLoop	nodeNestloop.c	60
ExecInitNestLoop	nodeNestloop.c	262
ExecEndNestLoop	nodeNestloop.c	361
ExecReScanNestLoop	nodeNestloop.c	381
ExecMergeJoin	nodeMergejoin.c	594
MJExamineQuals	nodeMergejoin.c	175
MJEvalOuterValues	nodeMergejoin.c	289
MJEvalInnerValues	nodeMergejoin.c	336
MJCompare	nodeMergejoin.c	386
MJFillOuter	nodeMergejoin.c	447
MJFillInner	nodeMergejoin.c	478
ExecInitMergeJoin	nodeMergejoin.c	1439
ExecEndMergeJoin	nodeMergejoin.c	1636
ExecReScanMergeJoin	nodeMergejoin.c	1652
ExecHashJoinImpl	nodeHashjoin.c	221
ExecHashJoin	nodeHashjoin.c	684
ExecParallelHashJoin	nodeHashjoin.c	700
ExecInitHashJoin	nodeHashjoin.c	716
ExecHashJoinOuterGetTuple	nodeHashjoin.c	979
ExecHashJoinNewBatch	nodeHashjoin.c	1130
ExecHashJoinSaveTuple	nodeHashjoin.c	1414
MultiExecHash	nodeHash.c	105
MultiExecPrivateHash	nodeHash.c	138
ExecHashTableCreate	nodeHash.c	446
ExecChooseHashTableSize	nodeHash.c	658
ExecHashIncreaseNumBatches	nodeHash.c	1030
ExecHashIncreaseNumBuckets	nodeHash.c	1587
ExecHashTableInsert	nodeHash.c	1749
ExecHashGetBucketAndBatch	nodeHash.c	1960
ExecScanHashBucket	nodeHash.c	1992
NTUP_PER_BUCKET (매크로)	nodeHash.c	655
HashJoinTableData	hashjoin.h	298

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

각 항목은 커밋 273fe94(REL_18_STABLE) 현재 소스의 사실로 시작한다. 다른 자료 없이도 읽을 수 있다. 마지막 문장이 검증 방법을 보여 준다.

검증된 사실

• 중첩 루프는 chgParam 경로로만 외부 Var를 PARAM_EXEC 슬롯에 밀어 넣고 내부를 리스캔한다. ExecNestLoop의 nl_NeedNewOuter 분기가 nl->nestParams를 순회하며 slot_getattr로 econtext->ecxt_param_exec_vals[paramno]에 값을 넣고, innerPlan->chgParam = bms_add_member(...)를 설정한 뒤 ExecReScan(innerPlan)을 호출한다. 2026-06-05 ExecNestLoop 열람으로 검증.

• ExecInitNestLoop은 매개변수화된 내부의 EXEC_FLAG_REWIND를 억제한다. node->nestParams == NIL인 경우에만 eflags |= EXEC_FLAG_REWIND를 설정하고, 그렇지 않으면 해제한다. ExecInitNestLoop 열람으로 검증.

• 머지 조인은 머지 등호 연산자가 아닌 SortSupport 비교기로 키를 비교한다. MJExamineQuals가 각 절의 ssup에 BTSORTSUPPORT_PROC(또는 BTORDER_PROC 심)을 로드한다. MJCompare가 ApplySortComparator를 호출한다. 머지절 연산자는 opfamily 등호 연산자(COMPARE_EQ)임이 단언된다. MJExamineQuals와 MJCompare 열람으로 검증.

• 머지 조인은 동등 그룹의 첫 내부 튜플을 마킹하고 외부 중복 키마다 복원한다. EXEC_MJ_SKIP_TEST가 동등 시 ExecMarkPos(innerPlan)을 호출하고(단, mj_SkipMarkRestore가 아닌 경우) MarkInnerTuple을 수행한다. EXEC_MJ_TESTOUTER가 여전히 동등한 새 외부 튜플에서 ExecRestrPos(innerPlan)을 호출한다. 두 상태 열람으로 검증. 내부 자식은 skip_mark_restore가 아닌 경우 EXEC_FLAG_MARK로 초기화됨 (ExecInitMergeJoin 열람).

• Hash 노드는 MultiExecProcNode로 빌드되며, ExecProcNode는 의도적으로 오류를 발생시킨다. ExecHash가 elog(ERROR, "Hash node does not support ExecProcNode call convention")을 호출한다. HJ_BUILD_HASHTABLE이 ExecHashTableCreate 후 (void) MultiExecProcNode((PlanState *) hashNode)를 호출한다. ExecHash, MultiExecHash, ExecHashJoinImpl 열람으로 검증.

• 해시 값은 버킷(하위 비트)과 배치(로테이션된 상위 비트)로 분리되며 nbatch는 2의 거듭제곱이다. ExecHashGetBucketAndBatch가 *bucketno = hashvalue & (nbuckets - 1)과 *batchno = pg_rotate_right32(hashvalue, log2_nbuckets) & (nbatch - 1)을 수행한다. ExecHashIncreaseNumBatches가 nbatch = oldnbatch * 2를 수행한다. 두 함수 열람으로 검증.

• 빌드 측 스필은 플래너 추정치만이 아닌 실측 spaceUsed로 구동된다. ExecHashTableInsert가 spaceUsed를 누적하고 spaceUsed + nbuckets_optimal * sizeof(HashJoinTuple) > spaceAllowed 조건 시 ExecHashIncreaseNumBatches를 호출한다. ExecChooseHashTableSize가 get_hash_memory_limit으로 초기 nbatch/nbuckets를 설정한다. 두 함수 열람으로 검증.

• ExecScanHashBucket은 저장된 해시 값으로 사전 필터링 후 해시 절 ExecQual을 실행한다. 각 HashJoinTuple이 hashvalue를 저장하며, 버킷 순회 시 hashTuple->hashvalue == hashvalue인 경우에만 ExecQualAndReset(hjclauses, econtext)를 실행한다. 함수 열람으로 검증.

• 세 노드 모두 동일한 joinqual/otherqual/single_match 형태를 사용한다. 각 노드가 ExecQual(joinqual, ...)로 매칭 상태를 설정하고, 그 뒤 otherqual을 거쳐 ExecProject를 호출하며, js.single_match(= inner_unique || JOIN_SEMI)로 단락한다. ExecNestLoop, EXEC_MJ_JOINTUPLES, HJ_SCAN_BUCKET의 출력 경로 열람으로 검증.

미해결 사항

1. 병렬 해시 조인의 배리어 안무는 여기서 개요만 다뤘다. PHJ_BUILD_* / PHJ_BATCH_* / PHJ_GROW_* 페이즈 기계(ExecParallelHashJoin과 MultiExecParallelHash의 Barrier 조율 공유 상태)는 요약되었으나 상태별로 추적하지 않았다. 조사 경로: nodeHashjoin.c 헤더 주석 블록과 ExecParallelHashJoinNewBatch 열람. 별도의 postgres-parallel-query.md가 적합한 후속 위치다.

2. 스큐 최적화(MCV 기반 스큐 버킷)는 이름만 언급했다. ExecHashBuildSkewHash / ExecHashGetSkewBucket / ExecHashSkewTableInsert가 가장 흔한 내부 값을 별도 스큐 해시 테이블에 유지해 편향된 외부 튜플이 스필되지 않도록 한다. 비용 모델과 num_skew_mcvs 선택은 추적하지 않았다. 조사 경로: ExecHashBuildSkewHash와 플래너의 skewTable 필드 열람.

3. Material이 머지 조인의 마크/복원 대 정렬된 인덱스 스캔과 어떻게 상호작용하는지. mj_ExtraMarks는 REWIND 없는 Material 내부에만 설정된다. 인덱스 스캔은 추가 마크를 받지 않아야 한다. 플래너가 머지 조인 내부 아래에 Material을 삽입하는 시점의 비용/정확성 트레이드오프는 postgres-scan-nodes.md / postgres-path-generation.md 소관이다.

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

각 항목은 후속 문서를 위한 시작점이다. 깊이는 의도적으로 얕다.

• 블록/배치 중첩 루프와 내부 리스캔 비용의 해소. PostgreSQL의 ExecNestLoop은 외부 튜플마다 내부를 다시 읽는다. 교과서의 블록 중첩 루프 개선(DSC §15.5.1)은 그 비용을 외부 블록 단위로 분할 상환한다. SQL Server의 “배치 모드”와 Oracle의 벡터 조인은 내부 패스당 여러 외부 행을 처리하는 방식으로 더 나아간다. PostgreSQL은 내부 탐색 자체가 저렴한 경우에만 중첩 루프를 선호하도록 매개변수화 인덱스 스캔 경로에 의존하며, Memoize(매개변수화 내부 위의 캐싱 노드)로 반복 동일 내부 리스캔을 건너뛴다. Memoize가 제공하는 가치 대 진정한 블록 조인 비교가 정량화될 수 있다.

• 단일 수준 대 재귀(GRACE) 분할. PostgreSQL의 하이브리드 해시 조인은 단일 분할 수준을 사용한다. nbatch를 배로 늘린 후에도 배치가 넘치면 추가 증가를 비활성화하고 배치가 예산을 초과하도록 허용한다(파일 헤더가 설명하는 “최선 노력”). GRACE 해시 조인(Kitsuregawa et al., 1983)과 컬럼 스토어의 재귀 분할 변형은 각 파티션이 맞을 때까지 재귀적으로 분할한다. 트레이드오프는 분할 패스 수 대 극심하게 편향된 키에서의 메모리 폭발 위험이다. PostgreSQL의 증가-비활성화 휴리스틱을 GRACE 재귀와 대조하면 각각이 유리한 시점이 명확해진다.

• 래딕스 / 캐시 인식 해시 조인. Manegold, Boncz & Kersten의 고전적 결과 (“Optimizing Main-Memory Join on Modern Hardware”, IEEE TKDE 2002)와 이후 Balkesen et al. SIGMOD 2013 연구는, 모든 데이터가 RAM에 맞는 경우에도 TLB·캐시 인식 래딕스 분할 패스가 단일 대형 체인 해시 테이블보다 현대 CPU에서 우수하다는 것을 보여 준다. PostgreSQL의 ExecScanHashBucket은 포인터 체이싱 체인 테이블로, 단순하고 배치 성장에 걸쳐 포인터가 안정적이지만 캐시 최적화는 아니다. PostgreSQL 해시 조인을 인메모리 분석 엔진과 비교할 때 관련성이 있다.

• 분석 주류에서 정렬-머지 대 해시. 오래된 “정렬-머지 대 해시 조인” 논쟁 (Kim et al., “Sort vs. Hash Revisited”, VLDB 2009; Albutiu et al., “Massively Parallel Sort-Merge Joins”, VLDB 2012)은 SIMD 가속 정렬과 NUMA 대역폭을 중심으로 전개된다. PostgreSQL은 두 알고리즘을 모두 유지하고 비용 모델이 선택하게 한다. SIMD 정렬도 NUMA 인식 머지도 없다. 세 알고리즘 중 플래너가 어떻게 선택하는지는 postgres-path-generation.md에서 다룬다.

• 최악-케이스-최적 및 다방향 조인. PostgreSQL의 세 조인 모두 이진이다. 다중 릴레이션 조인은 이진 조인의 좌-심(left-deep) 또는 부시(bushy) 트리로 표현되며, 순환 쿼리에서는 폭발할 수 있다. 최악-케이스-최적 조인 알고리즘(Ngo et al.의 “Leapfrog Triejoin”, Veldhuizen 2014; AGM 경계)은 모든 릴레이션을 한꺼번에 조인하며 그런 쿼리에서 증명 가능하게 우수하다. 주류 행 스토어는 핵심에 이를 채택하지 않는다. 그 이유(플래너·스토리지·API 가정에 미치는 영향)에 대한 설명이 유용한 프론티어 포인터가 된다.

• CUBRID 조인 실행기와의 대조. CUBRID는 XASL 트리 안에서 조인을 실행하며, 중첩 루프, 정렬-머지, 해시 리스트 스캔 변형을 가진다. CUBRID의 해시 조인은 전통적으로 내부를 스필 가능한 다중 배치 테이블 대신 “해시 리스트 스캔”으로 구체화했다. CUBRID의 해시-리스트-스캔 스필 동작과 PostgreSQL의 하이브리드 해시 배치 방식을 나란히 비교하면 같은 메모리 예산 문제에 대한 두 가지 다른 답을 볼 수 있다(CUBRID 코드 분석 트리 상호 참조).

출처

교과서 장 (knowledge/research/dbms-general/ 아래)

• Database System Concepts (Silberschatz, Korth & Sudarshan, 7판), 15장 “Query Processing”, §15.5 “Join Operation” — §15.5.1 중첩 루프와 블록 중첩 루프, §15.5.2 인덱스 중첩 루프, §15.5.4 머지 조인(정렬-머지, 마크/복원 중복 처리 논의 포함), §15.5.5 해시 조인(§15.5.5.1–15.5.5.2 GRACE / 하이브리드 재귀 분할 및 빌드/탐색 비용 모델 포함).

트리 내 설계 주석

• src/backend/executor/nodeHashjoin.c 헤더 — 하이브리드 해시 알고리즘의 권위 있는 설명. 지연 대 즉시 배치 크기 결정(직렬 대 병렬), 2의 거듭제곱 배치 배가 규칙, 최선 노력 증가-비활성화 휴리스틱, 전체 병렬 배리어 페이즈 기계(PHJ_BUILD_*, PHJ_BATCH_*, PHJ_GROW_*) 포함.
• src/backend/executor/nodeMergejoin.c 헤더 — 머지 조인 알고리즘 골격(Join { ... } 의사 코드)과 EXEC_MJ_* 상태로 주석된 외부/내부 중복 예시.

PostgreSQL 소스 (/data/hgryoo/references/postgres/, REL_18 273fe94)

• src/backend/executor/nodeNestloop.c — ExecNestLoop, ExecInitNestLoop (매개변수화 내부 REWIND 로직), ExecReScanNestLoop.
• src/backend/executor/nodeMergejoin.c — ExecMergeJoin 상태 기계, MJExamineQuals, MJEvalOuterValues/MJEvalInnerValues, MJCompare, MJFillOuter/MJFillInner, ExecInitMergeJoin.
• src/backend/executor/nodeHashjoin.c — ExecHashJoinImpl 상태 기계, ExecHashJoinOuterGetTuple, ExecHashJoinNewBatch, ExecHashJoinSaveTuple, ExecInitHashJoin.
• src/backend/executor/nodeHash.c — MultiExecHash/MultiExecPrivateHash, ExecHashTableCreate, ExecChooseHashTableSize, ExecHashTableInsert, ExecHashGetBucketAndBatch, ExecHashIncreaseNumBatches, ExecScanHashBucket.
• src/include/executor/hashjoin.h — HashJoinTableData, 버킷/배치/스필 필드, HJTUPLE_* 매크로.
• src/include/nodes/execnodes.h — JoinState, NestLoopState, MergeJoinState, HashJoinState.

상호 참조 (인접 메커니즘을 담당하는 형제 문서)

• postgres-executor.md — demand-pull 프레임워크, ExecProcNode 디스패치, ExecReScan, TupleTableSlot 추상화, 튜플별 메모리.
• postgres-scan-nodes.md — 조인이 끌어오는 리프 스캔. 인덱스 중첩 루프를 빠르게 만드는 매개변수화 인덱스 스캔(PARAM_EXEC의 런타임 스캔 키)과 머지 조인에 입력을 공급하는 Material / Sort 노드 포함.
• postgres-expression-eval.md — 컴파일된 joinqual / otherqual / 해시 절 ExprState, ExecQual, ExecProject, 측별 해시 및 머지 키 표현식.
• postgres-path-generation.md / postgres-planner-overview.md — 플래너가 세 조인 알고리즘 중 선택하고 내부/외부를 배정하는 방법.