콘텐츠로 이동
hgryoo · Docs

(KO) CUBRID Hash Join — 빌드/프로브 패턴, hash-scan 프리미티브, 그리고 spill 동작

목차

학술적 배경

섹션 제목: “학술적 배경”

해시 조인(hash join) 은 동등 조인의 한 쪽을 조인 컬럼을 키로 하는 연관 테이블(associative table)에 적재한 뒤, 다른 쪽을 훑으면서 매 튜플을 그 테이블에서 조회하는 전략이다. 이 전략은 더 오래된 두 조인 계열에 대한 직접적 대안이다. 하나는 중첩 루프(nested-loop) 로 인덱스가 없으면 입력 크기를 이차다. 다른 하나는 정렬-병합 (sort-merge) 으로 두 번 정렬한 후에 선형이다. 해시 조인은 메모리를 시간에 맞바꾼다. 작은 쪽이 메모리에 들어가면 두 입력 각각에 대한 한 번의 I/O 패스로 O(|R| + |S|)에 끝난다는 점이다. 이는 단일 패스 동등 조인이 달성할 수 있는 최선이다.

정본(canonical references)은 DeWitt, Katz, Olken, Shapiro, Stonebraker, Wood, Implementation Techniques for Main Memory Database Systems(SIGMOD 1984)와 Shapiro, Join Processing in Database Systems with Large Main Memories(TODS 1986)이다. 둘이 함께 고전 해시 조인(classic hash join) — 빌드 측을 읽어 해시 테이블에 적재한 뒤 두 번째 측으로 프로브 — 와 GRACE 해시 조인(Kitsuregawa, Tanaka, Moto-oka, 1983) — 양 측을 사전 분할하여 각 파티션 조인이 메모리에 들어가도록 — 을 형식화했다. Graefe의 Query Evaluation Techniques for Large Databases(CSUR 1993) §3는 모든 현대 엔진(CUBRID 포함)이 그 조합 어딘가에 위치하는 네 가지 설계 점을 열거한다.

  1. 고전 해시 조인(Classic hash join). 한 패스. R을 해시 테이블로 빌드한 뒤 S를 스캔하면서 프로브한다. R이 메모리에 들어갈 때만 올바르다. 그렇지 않으면 테이블이 thrash하고 알고리즘은 R의 메모리-거주 청크별로 S 위에서 다중 패스 순차 스캔으로 퇴화한다는 점이다. 단순함은 진짜다. 분할 로직이 없다. 그러나 메모리 계약은 취약하다.

  2. GRACE 해시 조인. 두 패스. 1단계는 R과 S를 한 번씩 읽으며 h_partition(join_key)를 키로 B개 버킷에 해시 분할한다. 2단계는 파티션 쌍 (R_i, S_i)를 독립적으로 고전 해시 조인으로 조인한다. 각 R_i가 메모리에 들어가는 한 알고리즘은 양 측을 두 패스로 끝난다. 순수 GRACE는 어떤 조인 작업이 일어나기 전에 모든 것을 디스크에 쓰므로 첫 매칭 튜플이 |R|+|S| I/O만큼 지연된다. 짧은 쿼리에는 나쁘다.

  3. 하이브리드 해시 조인(Hybrid hash join) (Shapiro 1986). 혼합: 1단계 동안 첫 파티션의 R 행을 인메모리 해시 테이블에 그대로 둠으로써 파티션 0에 대한 프로브 튜플은 즉시 조인된다. 나머지는 spill한다. 쉬운 경우에는 고전 해시의 지연을 회복하면서, 어려운 경우에는 GRACE의 정합성 보증을 유지한다.

  4. 재귀 분할(Recursive partitioning). 어떤 한 파티션의 R도 들어가지 않으면, 다른 해시 함수로 그 쌍을 재분할하고 재귀한다. 심한 데이터 skew거나 파티션 수가 과소 추정되었을 때만 필요하다.

네 가지를 가로지르는 세 가지 직교 고려 사항은 다음과 같다.

  • 해시 테이블 레이아웃. open addressing, 버킷별 리스트를 가지는 separate chaining, 또는 교과서의 인메모리 확장형 해시 같은 directory-of-buckets. CUBRID의 인메모리 경로는 chained hashing (mht_hls)을 쓰고, 디스크 경로는 directory 스타일 확장형 해시 (FHS, file hash structure — cubrid-extendible-hash.md 참조)를 쓴다.

  • 빌드 측 선택. 해시 테이블이 메모리 점유의 주범이므로 더 작은 관계가 빌드로 간다. 사전 계산된 카디널리티가 있으면 CBO 결정이고, 없으면 양 측을 결정 임계점까지 동시 읽다가 한 측이 끝나는 순간 전환하는 방식으로 동적으로 결정할 수 있다(때로 역할 반전(role reversal) 이라 부른다).

  • NULL 의미론. SQL의 동등 비교는 NULL를 UNKNOWN을 반환하므로, 해시 키가 된 NULL은 동등 조인에서 결코 매칭되지 않는다. 해시 시점에 걸러내거나, outer 조인에서는 null-padded outer 튜플을 내보내는 대체 경로로 라우팅해야 한다.

교과서 Garcia-Molina/Ullman/Widom, Database Systems: The Complete Book §15.4–§15.5는 같은 축으로 해시 조인과 정렬-병합을 대조한다. 유용한 정렬-순서 출력 요건이 없는 동등 조인에서는 하이브리드 해시가 정렬-병합을 약 log(|R|/M) 배 능가한다는 결론이다(정렬-병합은 그만큼의 머지 패스가 필요하고, 해시는 B개 파티션에서 |R|<M·B이면 한 패스로 끝나기 때문이다). 정렬-병합이 이기는 경우는 단 하나, 다운스트림 연산자 (주로 조인 키 위의 MERGE JOIN 또는 GROUP BY/ORDER BY)가 정렬된 출력을 공짜로 원할 때뿐이다.

CUBRID는 이 설계 공간을 두 층위에서 소비한다.

  • 옵티마이저(qo_hjoin_cost, qo_examine_hash_join)는 nested-loop, sort-merge와 함께 해시 조인을 세 가지 조인 방법 중 하나로 인정한다. 단 강한 게이팅 편향이 있다. 기본적으로 qo_examine_hash_join은 사용자가 inner relation에 /*+ USE_HASH */를 적지 않으면 즉시 반환한다. 비용 모델 자체는 빌드/프로브에 고정 CPU 오버헤드 상수를 쓰고 spill을 공짜로 취급한다(IO 항은 현재 비활성화). 결국 운영에서 실효적 결정 레버는 힌트다.
  • 실행기(qexec_hash_join)는 Graefe의 네 설계를 모두 한꺼번에 구현한다. 빌드 측이 들어가면 인메모리 레이아웃을, 인덱스만 들어가면 하이브리드 레이아웃(인메모리 인덱스, 디스크 튜플 저장)을, 인덱스조차 들어가지 않으면 확장형 해시 파일을 고른다. 그리고 선택된 프리미티브의 파티션당 메모리 예산을 여전히 초과하면 grace 스타일 분할 (hjoin_try_partition)로 폴백한다.

DBMS 공통 설계 패턴 (Common DBMS Design)

섹션 제목: “DBMS 공통 설계 패턴 (Common DBMS Design)”

해시 조인을 지원하는 모든 관계형 엔진은 같은 이음매(seam)를 노출한다. 실행기 쪽의 빌드/프로브 단계를 소유하는 물리 연산자(physical operator) 와, 옵티마이저 쪽에서 nested-loop 및 sort-merge보다 그 연산자를 고르는 비용 규칙(cost rule). 공통 어휘를 먼저 명명해 두면 다음 절의 CUBRID 식별자들이 한 벌의 다이얼 설정처럼 읽힌다는 점이다.

PostgreSQL — nodeHashjoin.c + nodeHash.c

섹션 제목: “PostgreSQL — nodeHashjoin.c + nodeHash.c”

PostgreSQL은 연산자를 둘로 쪼갠다. Hash(자식 출력을 HashJoinTable로 물질화하는 blocking 노드)와 HashJoin(프로빙 노드). 빌드는 Hash의 첫 ExecProcNode에서 일어나고, 프로브는 현재 outer 튜플에 대한 inner 해시 테이블이 소진될 때까지 HashJoin의 next()에서 일어난다. PostgreSQL은 v7.x부터 하이브리드 해시를 써 왔으며 work_mem을 넘으면 BatchFile-기반 grace 분할이 발동한다. v11에는 worker 배치 사이의 shared barrier를 두어 parallel-aware 해시 조인이 추가되었다. 해시 함수는 조인 컬럼의 자료형에 등록된 hashfunc이며, 다중 컬럼 키는 컬럼별 해시를 (h<<5)|(h>>27) ^ h2로 결합한다. 빌드 측 선택은 pg_class.reltuples/pg_class.relpages에 기반한 플래너 결정으로, 런타임에 뒤집히지는 않는다.

MySQL — InnoDB의 HashJoinIterator (8.0+)

섹션 제목: “MySQL — InnoDB의 HashJoinIterator (8.0+)”

MySQL은 8.0.18에서야 해시 조인을 도입했고 많은 경우의 block-nested-loop 를 대체했다. 이터레이터는 sql/iterators/hash_join_iterator.cc에 있다. 빌드 측은 mem_root에 인메모리 해시 테이블로 보관하며, 오버플로 시 양 입력을 배치별 청크 파일로 spill한 뒤 배치 쌍을 차례로 처리한다. 사실상 하이브리드 최적화 없는 GRACE다. MySQL은 의도적으로 이터레이터에서 병렬 해시 조인을 구현하지 않으며, 병렬성은 병렬 쿼리 기능을 위해 파티션 수준에서 처리된다는 점이다.

SQL Server — Hash Match 연산자

섹션 제목: “SQL Server — Hash Match 연산자”

SQL Server는 같은 물리 연산자(Hash Match) 안에서 In-Memory Hash, GRACE, Recursive Hash 중 하나를 고르며, 선택은 메모리 grant에 따라 런타임에 결정된다. 빌드 측이 grant를 초과하면 연산자는 버킷 페이지를 TempDB로 spill한다. 한 파티션이 여전히 들어가지 않으면 보조 함수로 재해시한다(recursive hash). 최후 수단으로 잔여 버킷 파일을 도는 bailout으로 떨어진다. 옵티마이저의 조인 규칙은 세 조인 방법 (PhyOp_HashJoin, PhyOp_LoopsJoin, PhyOp_MergeJoin)을 모두 평가하고 비용으로 가지친다. CUBRID 기본 설정의 힌트 필수 게이트 같은 것은 없다.

Oracle — HASH JOIN 연산자와 HJ 태그 변종

섹션 제목: “Oracle — HASH JOIN 연산자와 HJ 태그 변종”

Oracle은 HASH JOIN(인메모리 build-then-probe), HASH JOIN SEMI, HASH JOIN ANTI, HASH JOIN OUTER를 별개 실행 계획 연산자로 노출한다. spill은 PGA 임시 세그먼트로 간다. Oracle 옵티마이저는 실행 시점이 아니라 파싱 시점에 _hash_join_enabled와 비용 모델로 결정한다. OUTER 변종은 PostgreSQL의 HJ_NULL_INNER 기제와 비슷하게 빌드 엔트리별 matched 비트를 두고 같은 프로브 루프에서 직접 null-padded 튜플을 내보낸다는 점이다.

이론 ↔ CUBRID 명칭 매핑

섹션 제목: “이론 ↔ CUBRID 명칭 매핑”
이론 (Theory)CUBRID 명칭
해시 조인 물리 연산자HASHJOIN_PROC (XASL xasl->type); HASHJOIN_PROC_NODE (xasl.h)
빌드/프로브 드라이버qexec_hash_join → hjoin_execute_internal (query_hash_join.c)
실행 단위 공유 상태HASHJOIN_MANAGER (query_hash_join.h)
파티션별 실행 컨텍스트HASHJOIN_CONTEXT (query_hash_join.h)
측별 fetch / 도메인 / list-id 묶음HASHJOIN_FETCH_INFO (query_hash_join.h)
해시 테이블 프리미티브(빌드/프로브 표면)HASH_LIST_SCAN (query_hash_scan.h); 멤버 temp_key, temp_new_key, memory.hash_table, file.hash_table
해시 테이블 레이아웃 선택자HASH_METHOD ∈ {NOT_USE, IN_MEM, HYBRID, HASH_FILE} (query_hash_scan.h)
인메모리 해시 테이블mht_create_hls로 만든 MHT_HLS_TABLE (memory_hash.c)
디스크-기반 해시 테이블fhs_create로 연 FHSID(file hash structure ID) (query_hash_scan.c)
튜플별 키 디스크립터HASH_SCAN_KEY (val_count, values[])
튜플별 값 디스크립터(in-mem은 튜플, hybrid은 VPID/offset 저장)HASH_SCAN_VALUE (tuple과 pos의 union)
해시 키 계산qdata_hash_scan_key (query_hash_scan.c)
빌드 단계hjoin_build + hjoin_build_key (query_hash_join.c)
프로브 단계(inner)hjoin_probe + hjoin_probe_key
프로브 단계(outer-join, null-pad 폴백 포함)hjoin_outer_probe
GRACE 스타일 partitioning 트리거hjoin_check_partition → HASHJOIN_STATUS_PARTITION (query_hash_join.c)
GRACE 스타일 splitterhjoin_split_qlist (query_hash_join.c)
한 파티션의 메모리 예산PRM_ID_MAX_HASH_LIST_SCAN_SIZE (max_hash_list_scan_size, 기본 16 MB)
파티션당 fill marginPARTITION_FILL_FACTOR = 0.8 (query_hash_join.c)
비용 모델 진입점qo_hjoin_cost (query_planner.c:3604)
옵티마이저 admission gateqo_examine_hash_join (query_planner.c:6618)
해시-조인 CPU 가중 상수HJ_BUILD_CPU_OVERHEAD_FACTOR = 30, HJ_PROBE_CPU_OVERHEAD_FACTOR = 20 (query_planner.c:82–83)
플랜→XASL 하강make_hashjoin_proc (plan_generation.c:553); pt_to_hashjoin_proc (xasl_generation.c:14889)
실행기 디스패치qexec_execute_mainblock_internal의 case HASHJOIN_PROC: (query_executor.c:14748)
출력 튜플 writerhjoin_merge_tuple_to_list_id (query_hash_join.c)
병렬 실행 백엔드parallel_query::hash_join::execute_partitions (px_hash_join.cpp)

CUBRID의 구현

섹션 제목: “CUBRID의 구현”

CUBRID의 해시 조인은 전용 XASL 타입(HASHJOIN_PROC)을 가진 Volcano-형 blocking-build / streaming-probe 연산자다. 인접한 MERGELIST_PROC(sort-merge)와 달리 일반 SCAN_ID 체인으로 입력을 소비하지 않는다. 자체 드라이버(qexec_hash_join)를 소유하며, XASL의 aptr_list에서 이미 물질화된 list file 두 개를 양 입력으로 끌어와 빌드와 프로브를 순차로 구동하고 결과를 부모 XASL의 list_id에 쓴다.

XASL 형상 — HASHJOIN_PROC과 manager/context 분리

섹션 제목: “XASL 형상 — HASHJOIN_PROC과 manager/context 분리”

XASL 노드는 두 개의 HASHJOIN_INPUT 하위 구조(측당 하나)와 조인 키 컬럼 및 출력 프로젝션을 기술하는 QFILE_LIST_MERGE_INFO를 가진다.

// hashjoin_proc_node — src/query/xasl.h
typedef struct hashjoin_proc_node
{
  HASHJOIN_INPUT outer;
  HASHJOIN_INPUT inner;
  QFILE_LIST_MERGE_INFO merge_info;
#if defined (SERVER_MODE) || defined (SA_MODE)
  HASHJOIN_DOMAIN_INFO domain_info;
  HASHJOIN_STATS_GROUP stats_group;
#endif
} HASHJOIN_PROC_NODE;

두 HASHJOIN_INPUT 구조는 자식 XASL_NODE *xasl(해당 측의 list file을 생산하는 서브블록)과 during-join 술어 평가용 REGU_VARIABLE_LIST regu_list_pred를 들고 있다. merge_info는 sort-merge가 쓰는 것과 동일한 QFILE_LIST_MERGE_INFO로, ls_column_cnt(조인 키 컬럼 수), ls_outer_column[] / ls_inner_column[](각 측 튜플 안에서의 컬럼 위치), ls_pos_cnt / ls_pos_list[] / ls_outer_inner_list[](출력 프로젝션: 출력 값 각각이 어느 측의 어느 컬럼인가), join_type을 담는다.

qexec_hash_join이 실행되면 한 번의 실행 동안만 존재하는 두 구조를 추가로 만든다. HASHJOIN_MANAGER와 HASHJOIN_CONTEXT다.

// hashjoin_manager — src/query/query_hash_join.h
typedef struct hashjoin_manager
{
  HASHJOIN_INPUT *outer;            /* points into proc.hashjoin */
  HASHJOIN_INPUT *inner;
  QFILE_LIST_MERGE_INFO *merge_info;
  JOIN_TYPE join_type;
  int key_cnt;
  PRED_EXPR *during_join_pred;
  int num_parallel_threads;
  QUERY_ID query_id;
  VAL_DESCR *val_descr;
  HASHJOIN_CONTEXT single_context;  /* fast-path single partition */
  HASHJOIN_CONTEXT *contexts;       /* one per grace partition */
  UINT32 context_cnt;
  QFILE_TUPLE_VALUE_TYPE_LIST type_list;
  HASHJOIN_MERGE_METHOD qlist_merge_method;
  parallel_query::worker_manager *px_worker_manager;
  ...
} HASHJOIN_MANAGER;

분리는 의도적이다. HASHJOIN_MANAGER 는 파티션을 가로질러 일정한 모든 것(입력 포인터, 조인 타입, 출력 스키마, 병렬 worker pool)을 들고 있다. HASHJOIN_CONTEXT 는 한 파티션에 특화된 모든 것(빌드 측, 프로브 측, hash scan, 출력 list-id)을 들고 있다. spill이 없는 경우에는 컨텍스트가 정확히 하나(single_context)이며, grace partitioning 이 발동하면 contexts[]가 파티션당 한 엔트리로 할당되어 매니저가 이를 순회한다는 점이다.

flowchart LR
  XASL["XASL_NODE<br/>type=HASHJOIN_PROC<br/>aptr_list=[outer, inner]<br/>list_id=output"]
  PROC["HASHJOIN_PROC_NODE<br/>(in xasl->proc.hashjoin)<br/>outer.xasl, inner.xasl,<br/>merge_info, domain_info,<br/>stats_group"]
  MGR["HASHJOIN_MANAGER<br/>(qexec_hash_join 스택-로컬)<br/>join_type, key_cnt,<br/>type_list, contexts[]"]
  CTX["HASHJOIN_CONTEXT<br/>outer/inner FETCH_INFO,<br/>build, probe,<br/>hash_scan, list_id, status"]
  HLS["HASH_LIST_SCAN<br/>temp_key, temp_new_key,<br/>memory.hash_table OR<br/>file.hash_table"]
  XASL --> PROC
  XASL -- aptr_list[0] --> OUT["outer XASL → list_id"]
  XASL -- aptr_list[1] --> INR["inner XASL → list_id"]
  PROC --> MGR
  MGR --> CTX
  CTX --> HLS

드라이버 — qexec_hash_join과 빈-측 빠른 경로

섹션 제목: “드라이버 — qexec_hash_join과 빈-측 빠른 경로”

드라이버는 XASL 인터프리터에 의해 디스패치된다. qexec_execute_mainblock_internal의 해당 분기는 작다.

// qexec_execute_mainblock_internal — src/query/query_executor.c
case HASHJOIN_PROC:
  if (qexec_hash_join (thread_p, xasl, xasl_state->query_id, &xasl_state->vd) != NO_ERROR)
    {
      GOTO_EXIT_ON_ERROR;
    }
  break;

실행기가 이 분기에 도달하는 시점에 두 입력은 이미 물질화되어 있다(그 XASL들이 aptr_list에 놓여 있고, 사전-패스 for (xptr2 = xptr->aptr_list; ...) qexec_execute_mainblock(xptr2, ...) 루프에서 실행되었기 때문이다). 따라서 qexec_hash_join은 최종 카디널리티를 outer.xasl->list_id->tuple_cnt에서 직접 읽어 빌드 측과 partitioning을 선결정할 수 있다는 점이다.

드라이버의 첫 임무는 빈 측을 싸게 처리하는 것이다.

// qexec_hash_join — src/query/query_hash_join.c (condensed)
int qexec_hash_join (THREAD_ENTRY *thread_p, XASL_NODE *xasl,
                     QUERY_ID query_id, VAL_DESCR *val_descr)
{
  HASHJOIN_MANAGER manager;
  HASHJOIN_CONTEXT *single_context;
  HASHJOIN_STATUS status, part_status;


  hjoin_init_manager (thread_p, &manager, xasl, query_id, val_descr);
  single_context = &manager.single_context;


  status = hjoin_check_empty_inputs (&manager, single_context);
  switch (status)
    {
    case HASHJOIN_STATUS_FILL_NULL_VALUES:
      hjoin_outer_fill_null_values (thread_p, &manager, single_context);
      break;
    case HASHJOIN_STATUS_TRY:
      part_status = hjoin_try_partition (thread_p, &manager, single_context);
      switch (part_status)
        {
        case HASHJOIN_STATUS_SINGLE:    hjoin_execute (..., single_context); break;
        case HASHJOIN_STATUS_PARTITION: hjoin_execute_partitions (...); break;
        case HASHJOIN_STATUS_PARALLEL:  parallel_query::hash_join::execute_partitions (...); break;
        }
      break;
    case HASHJOIN_STATUS_END:
      /* nothing to do; output is empty */
      break;
    }
  qfile_copy_list_id (xasl->list_id, single_context->list_id, ...);
  hjoin_clear_manager (thread_p, &manager);
  ...
}

hjoin_check_empty_inputs가 첫 결정을 내린다.

// hjoin_check_empty_inputs — src/query/query_hash_join.c (condensed)
switch (manager->join_type)
  {
  case JOIN_INNER:
    status = (outer_tuple_cnt == 0 || inner_tuple_cnt == 0)
           ? HASHJOIN_STATUS_END : HASHJOIN_STATUS_TRY;
    break;
  case JOIN_LEFT:
    status = (outer_tuple_cnt == 0)
           ? HASHJOIN_STATUS_END
           : (inner_tuple_cnt == 0)
              ? HASHJOIN_STATUS_FILL_NULL_VALUES
              : HASHJOIN_STATUS_TRY;
    break;
  case JOIN_RIGHT:
    status = (inner_tuple_cnt == 0)
           ? HASHJOIN_STATUS_END
           : (outer_tuple_cnt == 0)
              ? HASHJOIN_STATUS_FILL_NULL_VALUES
              : HASHJOIN_STATUS_TRY;
    break;
  }

세 가지 status가 있다. END(한 측 또는 양 측이 비어 있어 출력이 비는 경우), FILL_NULL_VALUES(outer 조인의 보존 측은 비어 있지 않으나 null-공급 측이 빈 경우 — 해시 테이블을 만들지 않고 보존 측 튜플을 null-padded로 바로 내보냄), TRY(빌드/프로브 진행). FILL_NULL_VALUES 지름길은 빈 lookup 테이블에 대한 outer 조인에서 수익을 낸다. 그렇지 않으면 빌드 단계 전체가 낭비될 것이기 때문이다.

flowchart TB
  START([qexec_hash_join])
  CHK{hjoin_check_empty_inputs}
  END_NULL[HASHJOIN_STATUS_END<br/>출력 비어 있음]
  FILL[hjoin_outer_fill_null_values<br/>보존 측 행을 null-padded로 방출]
  TRY{hjoin_try_partition}
  SINGLE[HASHJOIN_STATUS_SINGLE<br/>single_context에 hjoin_execute]
  PART[HASHJOIN_STATUS_PARTITION<br/>contexts[] 위에서<br/>hjoin_execute_partitions]
  PXL[HASHJOIN_STATUS_PARALLEL<br/>parallel_query::hash_join::<br/>execute_partitions]
  COPY[qfile_copy_list_id<br/>→ xasl->list_id]
  START --> CHK
  CHK -- END --> END_NULL --> COPY
  CHK -- FILL_NULL_VALUES --> FILL --> COPY
  CHK -- TRY --> TRY
  TRY -- SINGLE --> SINGLE --> COPY
  TRY -- PARTITION --> PART --> COPY
  TRY -- PARALLEL --> PXL --> COPY
  COPY --> DONE([매니저 정리])

빌드 단계

섹션 제목: “빌드 단계”

hjoin_build가 빌드 루프다. 여기서 중요한 것은 셋이다. 어느 측이 빌드를 맡는가, 키에 무엇이 들어오는가, 값으로 무엇이 저장되는가.

빌드 측 선택 은 컨텍스트별로 hjoin_init_context에서 일어난다.

// hjoin_init_context — src/query/query_hash_join.c (condensed)
switch (manager->join_type)
  {
  case JOIN_INNER:
    if (outer->list_id->tuple_cnt < inner->list_id->tuple_cnt)
      { context->build = outer; context->probe = inner; }
    else if (outer->list_id->tuple_cnt == inner->list_id->tuple_cnt
             && outer->list_id->page_cnt < inner->list_id->page_cnt)
      { context->build = outer; context->probe = inner; }
    else
      { context->build = inner; context->probe = outer; }
    break;
  case JOIN_LEFT:
    /* preserve outer; null-pad inner */
    context->build = inner; context->probe = outer; break;
  case JOIN_RIGHT:
    context->build = outer; context->probe = inner; break;
  }

inner join에서는 작은 측이 이긴다. 동률일 땐 page count가 tie-breaker다 (page count는 tuple-width × tuple-count의 대리이므로 단순 tuple count 보다 총 바이트의 더 가까운 대리다). outer join에서는 의미론에 의해 선택이 강제된다. null-공급 측이 빌드여야 그 해시 테이블을 프로빙해 미스 시 보존 측에 대한 null-padding을 발동할 수 있다.

튜플별 빌드 는 무-파티션 경우에 다음과 같이 일어난다.

// hjoin_build — src/query/query_hash_join.c (condensed)
while ((scan_code = qfile_scan_list_next (thread_p, &build->list_scan_id,
                                          &build->tuple_record, PEEK)) == S_SUCCESS)
  {
    error = hjoin_fetch_key (thread_p, build, &build->tuple_record, key,
                             NULL /* compare_key */, &need_skip_next);
    if (need_skip_next)
      { need_skip_next = false; continue; }   /* NULL in any join column */
    hash_scan->curr_hash_key =
      qdata_hash_scan_key (key, UINT_MAX, hash_method);
    error = hjoin_build_key (thread_p, hash_scan,
                             &build->list_scan_id, &build->tuple_record);
  }

루프는 글자 그대로 Volcano 형상이다. 다음 튜플을 끌어오고, 조인 키 컬럼을 HASH_SCAN_KEY로 물질화하고, 해시하고, 삽입한다. 흥미로운 세부 사항은 need_skip_next다. 조인 컬럼 어디에든 NULL이 들어 있는 튜플은 빌드 측에서 조용히 떨어진다. SQL의 NULL에 대한 =는 결코 TRUE가 되지 않기 때문이다. (outer-join의 보존-NULL 튜플의 경우 떨어짐은 프로브 측에서 일어난다. 전용 fill null 파티션으로 라우팅된다, 아래 Spill 참조.)

partition된 경우에는 splitter 패스에서 튜플이 이미 해시되었고 해시 키가 튜플의 첫 번째 값 슬롯에 보관되어 있다. hjoin_build는 다시 계산하지 않고 그것을 읽는다.

// hjoin_build (partitioned arm) — src/query/query_hash_join.c (condensed)
tuple_value = build->tuple_record.tpl + QFILE_TUPLE_LENGTH_SIZE;
tuple_value += QFILE_TUPLE_VALUE_HEADER_LENGTH;
hash_scan->curr_hash_key = (UINT32) OR_GET_INT (tuple_value);
hjoin_build_key (thread_p, hash_scan, &build->list_scan_id, &build->tuple_record);

이는 PostgreSQL이 batched hash join에서 쓰는 동일한 트릭이다. 파티션 시점에 한 번 해시하고, 빌드/프로브 시점에 그 해시 워드를 재사용한다.

hjoin_build_key는 다형 삽입(polymorphic insert)이다. hash_scan->hash_list_scan_type으로 디스패치한다.

// hjoin_build_key — src/query/query_hash_join.c (condensed)
switch (hash_scan->hash_list_scan_type)
  {
  case HASH_METH_IN_MEM:
    hash_value = qdata_alloc_hscan_value (thread_p, tuple_record->tpl);
    mht_put_hls (hash_scan->memory.hash_table,
                 (void *) &hash_scan->curr_hash_key,
                 (void *) hash_value);
    break;
  case HASH_METH_HYBRID:
    hash_value = qdata_alloc_hscan_value_OID (thread_p, list_scan_id);
    mht_put_hls (hash_scan->memory.hash_table,
                 (void *) &hash_scan->curr_hash_key,
                 (void *) hash_value);
    break;
  case HASH_METH_HASH_FILE:
    SET_TFTID (tftid, list_scan_id->curr_vpid.volid,
               list_scan_id->curr_vpid.pageid, list_scan_id->curr_offset);
    fhs_insert (thread_p, hash_scan->file.hash_table,
                (void *) &hash_scan->curr_hash_key, &tftid);
    break;
  }

세 분기는 값으로 무엇을 저장하는가 만 다르다. 깊이 복사된 튜플 (인메모리), (volid, pageid, offset) 튜플 위치(하이브리드), 또는 확장형 해시 버킷에 기록되는 TFTID(해시-파일). 키 — 32비트 해시 워드 는 셋 모두에서 같다.

프로브 단계

섹션 제목: “프로브 단계”

hjoin_probe는 inner-join 프로브 루프다. 빌드 루프의 바깥 형상을 거울처럼 따른다(프로브 측 list file 위의 qfile_scan_list_next) 그리고 그 안에서 같은 키로 해시되는 빌드 엔트리들의 체인을 도는 내부 do { } while (true) 루프를 돈다.

// hjoin_probe — src/query/query_hash_join.c (condensed)
while ((scan_code = qfile_scan_list_next (thread_p, &probe->list_scan_id,
                                          &probe->tuple_record, PEEK)) == S_SUCCESS)
  {
    if (manager->context_cnt == 0)
      {  /* fresh fetch — no pre-computed hash on tuple */
        hjoin_fetch_key (thread_p, probe, &probe->tuple_record, key, NULL, &need_skip_next);
        if (need_skip_next) { continue; }   /* NULL → no inner match possible */
        hash_scan->curr_hash_key = qdata_hash_scan_key (key, UINT_MAX, hash_method);
      }
    else
      {  /* partitioned — read pre-computed hash word out of tuple slot 0 */
        ...
      }


    do
      {
        hjoin_probe_key (thread_p, hash_scan, &build->list_scan_id, &build->tuple_record);
        if (build->tuple_record.tpl == NULL) break;     /* not found */
        if (manager->context_cnt != 0)
          { hjoin_fetch_key (thread_p, probe, &probe->tuple_record, key, NULL, &need_skip_next); }
        hjoin_fetch_key (thread_p, build, &build->tuple_record, found_key,
                         key /* compare_key */, &need_skip_next);
        if (need_skip_next)
          { continue; }     /* hash collision: same hash, different key */
        hjoin_merge_tuple_to_list_id (thread_p, list_id,
                                      &outer->tuple_record, &inner->tuple_record,
                                      manager->merge_info, &overflow_record);
      }
    while (true);
  }

내부 루프가 바로 연산자가 해시 충돌을 정합성 있게 견디게 만드는 지점이다. hjoin_probe_key는 해시 워드가 현재 프로브 해시와 같은 어느 빌드 엔트리든 반환한다. 본문은 빌드 튜플의 키 컬럼을 found_key로 fetch하고 프로브 키와 다시 비교 한다. 컬럼이 다르면 (같은 해시, 다른 값 — 충돌), need_skip_next가 설정되고 루프는 체인의 다음 엔트리로 이동한다. 키가 정확히 일치할 때만 hjoin_merge_tuple_to_list_id가 조인 출력 튜플을 쓴다.

이는 PostgreSQL의 ExecHashJoin이 해싱 후 ExecQual(hjclauses, econtext)로 거는 동일한 정합성 가드다. 해시는 빠른 필터일 뿐 결정적 매치가 아니다.

hjoin_probe_key 자체는 테이블 레이아웃으로 디스패치한다.

// hjoin_probe_key — src/query/query_hash_join.c (condensed)
switch (hash_scan->hash_list_scan_type)
  {
  case HASH_METH_IN_MEM:
    hash_value = (tuple_record->tpl == NULL)
      ? mht_get_hls (hash_scan->memory.hash_table,
                     (void *) &hash_scan->curr_hash_key,
                     (void **) &hash_scan->memory.curr_hash_entry)
      : mht_get_next_hls (hash_scan->memory.hash_table, ...);
    if (hash_value != NULL) tuple_record->tpl = hash_value->tuple;
    break;


  case HASH_METH_HYBRID:
    hash_value = (tuple_record->tpl == NULL)
      ? mht_get_hls (...) : mht_get_next_hls (...);
    if (hash_value != NULL)
      {
        MAKE_TUPLE_POSTION (tuple_position, hash_value->pos, list_scan_id);
        qfile_jump_scan_tuple_position (thread_p, list_scan_id,
                                         &tuple_position, tuple_record, PEEK);
      }
    break;


  case HASH_METH_HASH_FILE:
    eh_search = (tuple_record->tpl == NULL)
      ? fhs_search (thread_p, hash_scan, &tftid)
      : fhs_search_next (thread_p, hash_scan, &tftid);
    if (eh_search == EH_KEY_FOUND)
      {
        MAKE_TFTID_TO_TUPLE_POSTION (tuple_position, tftid, list_scan_id);
        qfile_jump_scan_tuple_position (thread_p, list_scan_id,
                                         &tuple_position, tuple_record, PEEK);
      }
    break;
  }

tuple_record->tpl == NULL 체크가 체인-워크 앵커다. 한 프로브 키에 대한 첫 호출에서는 처음 매칭 엔트리를 묻고, 이후 호출에서는 다음 을 묻는다. 하이브리드와 해시-파일 경로는 위치 lookup 후 qfile_jump_scan_tuple_position으로 빌드 측 list file에서 튜플을 다시 읽는다. 이것이 해시 테이블에 튜플을 깊이 복사하지 않는 비용으로 지불하는 추가 페이지 fetch다.

hjoin_outer_probe는 outer-join 변종이다. 구조적으로는 inner-join 프로브에 한 분기를 더한 것이다. 다음 프로브 튜플로 가기 전, 적어도 하나의 매치가 방출되었는지 확인한다. 그렇지 않으면 보존 측 튜플과 outer->fill_record / inner->fill_record(둘 중 하나는 NULL) 를 이용해 null-padded 레코드를 방출한다.

// hjoin_outer_probe — src/query/query_hash_join.c (condensed)
any_record_added = false;
do
  {
    /* same chain walk as hjoin_probe, with during_join_pred check */
    ...
    any_record_added = true;
  }
while (true);


if (!any_record_added)
  {
    /* fill null for unmatched preserved row */
    hjoin_merge_tuple_to_list_id (thread_p, list_id,
                                  outer->fill_record, inner->fill_record,
                                  manager->merge_info, &overflow_record);
  }

during_join_pred는 PostgreSQL이 ON 절의 부등식 술어를 hash-join 프로브 루프에 붙일 때 쓰는 것과 동일한 hook이다. 이는 R LEFT JOIN S ON R.k = S.k AND R.x > S.x에서 두 번째 술어를 체인-워크 동안 매치된 쌍별로 평가하게 만든다. post-filter가 아니라 — 그래서 부적격 부등식이 match로 간주되지 않고, null-padding이 제대로 발동한다는 점이다.

flowchart TB
  P0([프로브 스캔 열기])
  P1[probe list_id 위에서<br/>qfile_scan_list_next]
  P2{조인 키에<br/>NULL?}
  P3[HASH_SCAN_KEY로 fetch_key]
  P4[hash_key = qdata_hash_scan_key]
  P5[hjoin_probe_key:<br/>체인의 첫 매치]
  P6{찾았는가?}
  P7[빌드 키 fetch,<br/>프로브 키와 compare_key]
  P8{충돌<br/>같은 h 다른 k?}
  P9{during_join_pred?}
  P10[merge_tuple_to_list_id<br/>출력 행 추가]
  P11[hjoin_probe_key:<br/>체인의 다음 매치]
  P12[outer 전용:<br/>any_record_added?]
  P13[null-padded 행 채움]
  P0 --> P1 --> P2
  P2 -- yes inner --> P1
  P2 -- yes outer --> P13 --> P1
  P2 -- no --> P3 --> P4 --> P5 --> P6
  P6 -- no --> P12
  P6 -- yes --> P7 --> P8
  P8 -- collision --> P11 --> P5
  P8 -- match --> P9
  P9 -- false --> P11
  P9 -- true --> P10 --> P11
  P12 -- inner / matched --> P1
  P12 -- outer / no match --> P13 --> P1

hash-scan 프리미티브 — 세 가지 테이블 레이아웃

섹션 제목: “hash-scan 프리미티브 — 세 가지 테이블 레이아웃”

HASH_LIST_SCAN은 hash join과 hash list scan(CUBRID에서 해시 키 기반의 IN-list 및 비상관 서브쿼리 프로빙을 가리키는 용어 — cubrid-post-processing.md 참조) 사이에서 공유되는 프리미티브다. 구조체는 query_hash_scan.h에 있다.

// hash_list_scan — src/query/query_hash_scan.h
struct hash_list_scan
{
  regu_variable_list_node *build_regu_list;    /* used by hash list scan only */
  regu_variable_list_node *probe_regu_list;    /* used by hash list scan only */
  HASH_SCAN_KEY *temp_key;                     /* probe key buffer */
  HASH_SCAN_KEY *temp_new_key;                 /* coerced/build key buffer */
  union {
    struct {
      MHT_HLS_TABLE *hash_table;               /* in-memory hash, chained */
      HENTRY_HLS_PTR curr_hash_entry;          /* iterator state */
    } memory;
    struct {
      FHSID *hash_table;                       /* extendible hash file */
      OID curr_oid;                            /* iterator state */
      bool is_dk_bucket;                       /* duplicate-key bucket flag */
    } file;
  };
  HASH_METHOD hash_list_scan_type;             /* IN_MEM | HYBRID | HASH_FILE */
  unsigned int curr_hash_key;
  bool need_coerce_type;
};

레이아웃 선택은 HASHJOIN_CONTEXT별로 hjoin_scan_init에서 한 번 이뤄진다. 빌드 측의 페이지 수 및 튜플 수를 단일 메모리 예산 mem_limit과 비교한다.

// hjoin_scan_init — src/query/query_hash_join.c (condensed)
mem_limit = prm_get_bigint_value (PRM_ID_MAX_HASH_LIST_SCAN_SIZE);


if ((UINT64) list_id->page_cnt * DB_PAGESIZE <= mem_limit)
  {
    hash_scan->hash_list_scan_type = HASH_METH_IN_MEM;
    hash_scan->memory.hash_table =
      mht_create_hls ("Hash Join", list_id->tuple_cnt, NULL, NULL);
  }
else if ((UINT64) list_id->tuple_cnt
         * (sizeof (HENTRY_HLS) + sizeof (QFILE_TUPLE_SIMPLE_POS)) <= mem_limit)
  {
    hash_scan->hash_list_scan_type = HASH_METH_HYBRID;
    hash_scan->memory.hash_table =
      mht_create_hls ("Hash Join", list_id->tuple_cnt, NULL, NULL);
  }
else
  {
    hash_scan->hash_list_scan_type = HASH_METH_HASH_FILE;
    hash_scan->file.hash_table =
      (FHSID *) db_private_alloc (thread_p, sizeof (FHSID));
    fhs_create (thread_p, hash_scan->file.hash_table, list_id->tuple_cnt);
  }

세 임계값, 세 레이아웃.

레이아웃조건키 위치튜플 위치
HASH_METH_IN_MEMpage_cnt * DB_PAGESIZE ≤ mem_limitmht_hls해시 엔트리 안(깊이 복사)
HASH_METH_HYBRID튜플은 안 들어가지만 tuple_cnt * (HENTRY+POS) ≤ mem_limitmht_hls원래 list-file 페이지, (volid,pageid,offset)으로 주소 지정
HASH_METH_HASH_FILE인덱스조차 안 들어감FHSID 디렉토리 + 버킷 페이지원래 list-file 페이지, TFTID로 주소 지정

하이브리드 모드는 고전 인메모리 해시와 순수 GRACE 사이의 CUBRID 고유 중간점이다. 해시 인덱스 는 들어가지만 해시 페이로드 는 들어가지 않는다. 프로브 측 hit마다 매치당 한 번의 추가 페이지 fetch (qfile_jump_scan_tuple_position)를 지불해 원래 list file에서 튜플을 다시 읽는다. 이는 인덱스 프로브가 여전히 메모리에 있으므로 순수 해시-파일 경로보다 싸다.

HASH_METH_HASH_FILE 경로는 카탈로그가 쓰는 것과 같은 확장형 해시 기제(cubrid-extendible-hash.md)에 의존한다. 버킷 VPID들의 디렉토리 이며 버킷이 local depth를 넘으면 두 배가 되고 중복 키 체인은 dk 버킷으로 처리된다. 메모리 사용량은 디렉토리 크기 + 한 번에 한 버킷 페이지-fix로 제한되고 나머지는 디스크에 산다는 점이다.

flowchart TB
  subgraph IN_MEM["HASH_METH_IN_MEM"]
    direction LR
    K1[hash_key] --> B1[bucket head]
    B1 --> E1["HENTRY_HLS<br/>{key=hash_key,<br/>data=HASH_SCAN_VALUE.tuple}"]
    E1 --> E2["HENTRY_HLS"]
  end
  subgraph HYBRID["HASH_METH_HYBRID"]
    direction LR
    K2[hash_key] --> B2[bucket head]
    B2 --> E3["HENTRY_HLS<br/>{key=hash_key,<br/>data=HASH_SCAN_VALUE.pos<br/>={vpid,offset}}"]
    E3 -. jump --> LF[list-file page]
    LF --> T2["tuple"]
  end
  subgraph FILE["HASH_METH_HASH_FILE"]
    direction LR
    K3[hash_key] --> DIR["FHSID directory"]
    DIR --> BKT["bucket page"]
    BKT --> R3["{TFTID = (volid,pageid,offset)}"]
    R3 -. jump --> LF2[list-file page]
    LF2 --> T3["tuple"]
  end

해시 키 정규화, 타입 강제, NULL 처리

섹션 제목: “해시 키 정규화, 타입 강제, NULL 처리”

R.k = S.k로 조인되는 두 관계는 R.k와 S.k가 타입, 정밀도, 스케일, 그리고 collation에 동의해야만 의미 있는 해시 조인을 가진다는 점이다. 그렇지 않으면 동일한 논리 값이 두 다른 워드로 해시되고 조인이 조용히 행을 놓친다. CUBRID의 방어선은 컨텍스트당 한 번 호출되는 hjoin_init_domain_info다.

// hjoin_init_domain_info — src/query/query_hash_join.c (condensed)
for (domain_index = 0; domain_index < domain_cnt; domain_index++)
  {
    outer_type = TP_DOMAIN_TYPE (outer_domains[domain_index]);
    inner_type = TP_DOMAIN_TYPE (inner_domains[domain_index]);


    if (outer_type == inner_type)
      common_type = outer_type;
    else
      {
        need_coerce_domains = true;
        common_type = (tp_more_general_type (outer_type, inner_type) > 0)
                      ? outer_type : inner_type;
      }


    if (outer_precision == inner_precision && outer_scale == inner_scale)
      { common_precision = inner_precision; common_scale = inner_scale; }
    else
      {
        need_coerce_domains = true;
        if (common_type == DB_TYPE_NUMERIC)
          {
            common_scale = MAX (outer_scale, inner_scale);
            common_precision = MAX (outer_integral, inner_integral) + common_scale;
            common_precision = MIN (common_precision, DB_MAX_NUMERIC_PRECISION);
          }
        else
          {
            common_precision = MAX (outer_precision, inner_precision);
            common_scale = 0;
          }
      }


    if (need_coerce_domains)
      coerce_domains[domain_index] = tp_domain_cache (...);
  }

결과는 domain_info->coerce_domains[] — 조인 컬럼당 하나의 공통 도메인이며, hjoin_fetch_key가 해싱 전 값을 공통 표현으로 강제할 때 사용한다. 이것이 없으면 INT 1과 BIGINT 1을 해시하면 두 다른 해시 워드가 나온다는 점이다.

hjoin_fetch_key는 튜플별 키 물질화기다. 튜플의 값 슬롯들을 돌며 인덱스(value_indexes[key_index])로 조인 컬럼들을 골라내고, 각각을 다음을 수행한다.

// hjoin_fetch_key — src/query/query_hash_join.c (condensed)
if (QFILE_GET_TUPLE_VALUE_FLAG (tuple_value) == V_UNBOUND)
  goto skip_next;       /* NULL → tuple drops out of join */


or_init (&buf, tuple_value + QFILE_TUPLE_VALUE_HEADER_SIZE, value_size);


if (need_coerce_domains && coerce_domains[key_index] != NULL
    && coerce_domains[key_index] != domains[key_index])
  {
    domains[key_index]->type->data_readval (&buf, &pre_coerce_value, ...);
    tp_value_coerce (&pre_coerce_value, key->values[key_index],
                     coerce_domains[key_index]);
  }
else
  {
    domains[key_index]->type->data_readval (&buf, key->values[key_index], ...);
  }


if (compare_key != NULL)
  {
    /* collision check on probe side */
    compare_result = tp_value_compare (key->values[key_index],
                                       compare_key->values[key_index], 0, 0);
    if (compare_result != DB_EQ) goto skip_next;
  }

한 함수에 두 역할이 있다. 첫 호출(compare_key=NULL)은 해싱을 위한 키를 물질화한다. 두 번째 호출(compare_key=key로, key는 이미 물질화된 프로브 키)은 빌드 튜플의 키 컬럼을 다시 fetch해 프로브 키와 검증한다. 프로브 루프가 의존하는 충돌 검사다.

qdata_hash_scan_key가 실제 해시 함수다.

// qdata_hash_scan_key — src/query/query_hash_scan.c
unsigned int qdata_hash_scan_key (const void *key, unsigned int ht_size,
                                  HASH_METHOD hash_method)
{
  HASH_SCAN_KEY *ckey = (HASH_SCAN_KEY *) key;
  unsigned int hash_val = 0, tmp_hash_val;
  for (i = 0; i < ckey->val_count; i++)
    {
      hash_val = ROTL32 (hash_val, 13);
      tmp_hash_val = mht_get_hash_number (ht_size, ckey->values[i]);
      hash_val ^= tmp_hash_val;
      if (hash_val == 0) hash_val = tmp_hash_val;
    }
  if (hash_method == HASH_METH_HASH_FILE)
    hash_val = fhs_hash (&hash_val);  /* extra mixing for FHSID */
  return hash_val;
}

다중 컬럼 키는 표준 XOR-with-rotate 방식(ROTL32(h,13) ^ h_i)으로 결합되며, 모두-0 상태가 체인을 무너뜨리지 않도록 가드를 둔다. 디스크 경로에는 추가 mixing(fhs_hash) 한 라운드가 적용된다. FHSID 디렉토리는 해시 워드의 상위 비트 를 버킷 인덱스로 사용 하므로 mix되지 않은 해시는 그 비트들에 타입별 패턴을 누설하기 때문이다.

NULL 처리는 균일하다. 어떤 조인 컬럼에든 V_UNBOUND가 있으면 튜플은 조인에서 떨어진다. inner join에는 옳다(NULL은 결코 동등 하지 않다). outer join의 경우 splitter가 추가로 NULL-키의 보존-측 튜플을 전용 fill null 파티션으로 라우팅한다. 다음 절 참조.

Spill — grace 스타일 equi-hash partitioning

섹션 제목: “Spill — grace 스타일 equi-hash partitioning”

빌드 측의 footprint가 단일 파티션 실행을 위한 레이아웃 임계를 넘으면, hjoin_check_partition이 작업을 GRACE 스타일로 여러 파티션으로 쪼갠다. 결정은 hjoin_check_partition에 있다.

// hjoin_check_partition — src/query/query_hash_join.c (condensed)
mem_limit = prm_get_bigint_value (PRM_ID_MAX_HASH_LIST_SCAN_SIZE);
min_tuple_cnt = MIN (outer_list_id->tuple_cnt, inner_list_id->tuple_cnt);


part_cnt = CEIL_PTVDIV (
    (sizeof (HENTRY_HLS) + sizeof (QFILE_TUPLE_SIMPLE_POS)) * min_tuple_cnt,
    mem_limit * PARTITION_FILL_FACTOR);


if (part_cnt > 1)
  {
    if (IS_OUTER_JOIN_TYPE (manager->join_type))
      part_cnt += 1;        /* one extra partition for NULL-keyed preserved rows */
    manager->context_cnt = part_cnt;
    return HASHJOIN_STATUS_PARTITION;
  }
return HASHJOIN_STATUS_SINGLE;

파티션 수는 한 파티션의 해시 인덱스(+ 튜플 위치 포인터, 최악 경우 는 HASH_METH_HYBRID 오버헤드)가 mem_limit의 80%에 들어가도록 크기를 잡는다. 80% margin — PARTITION_FILL_FACTOR — 은 버킷 불균형에 대한 fudge factor다. 완벽히 해시된 입력은 정확히 100%에 들어가지만, 실제 해시 분포에는 long tail이 있기 때문이다.

분할 자체는 hjoin_split_qlist이며, outer와 inner 각각을 두 번 실행된다. GRACE 1단계 splitter다.

// hjoin_split_qlist — src/query/query_hash_join.c (condensed)
while ((scan_code = qfile_scan_list_next (thread_p, &list_scan_id,
                                          &tuple_record, PEEK)) == S_SUCCESS)
  {
    hjoin_fetch_key (thread_p, split_info->fetch_info, &tuple_record,
                     temp_key, NULL, &need_skip_next);
    if (need_skip_next)
      {
        if (is_outer_join)
          part_id = part_cnt - 1;     /* last partition := "fill null" bucket */
        else
          continue;                   /* inner: drop NULL-keyed tuples */
      }
    else
      {
        hash_key = qdata_hash_scan_key (temp_key, UINT_MAX, HASH_METH_IN_MEM);
        part_id = is_outer_join ? hash_key % (part_cnt - 1)
                                : hash_key % (part_cnt);
        hjoin_update_tuple_hash_key (thread_p, &tuple_record, hash_key);
      }


    qfile_add_tuple_to_list (thread_p, part_list_id[part_id], tuple_record.tpl);
  }

세 가지 세부가 짚을 만하다.

  • 해시 워드는 튜플에 캐시된다. hjoin_update_tuple_hash_key가 32비트 해시를 튜플 머리에 예약된 슬롯에 쓰므로 빌드/프로브 단계는 매 튜플을 두 번째로 다시 해시하지 않고 그 값을 읽는다. 이 비용은 XASL 생성 시점에 튜플 위치 0에 MAX_ALIGNMENT 크기의 추가 값 슬롯(초기 sentinel -1)을 남기는 식으로 지불된다. hjoin_update_tuple_hash_key는 덮어 쓰기 전에 그 sentinel이 여전히 있는지 assert한다.

  • outer-join fill null 파티션. JOIN_LEFT / JOIN_RIGHT의 경우 보존 측 조인 컬럼이 NULL인 튜플들을 위한 추가 파티션 하나가 할당되어 예약된다. 이 튜플들은 빌드 측의 어떤 것과도 매치되지 않으므로 그들의 조인은 SQL outer-join 의미론만으로 결정된다. null-pad해 방출하는 것이다. hjoin_execute는 마지막 파티션을 특별 취급한다.

    // hjoin_execute — src/query/query_hash_join.c (excerpt)
    if (IS_OUTER_JOIN_TYPE (manager->join_type)
        && context == &manager->contexts[manager->context_cnt - 1])
      {
        status = (status == HASHJOIN_STATUS_TRY)
               ? HASHJOIN_STATUS_FILL_NULL_VALUES : status;
      }

    그러면 전용 hjoin_outer_fill_null_values가 그 파티션의 보존 측 list file을 돌며 행마다 한 null-padded 튜플을 방출한다. 빌드 측은 전혀 건드리지 않는다.

  • append-vs-temp 춤. 각 파티션의 출력 list-file은 temp_part_list_id[] 작업 집합으로 조립된다. 한 파티션의 인메모리 버퍼가 차면 splitter는 그것을 파티션의 실제 list-file (part_list_id[])로 flush하고 새 버퍼를 시작한다. 이는 PostgreSQL의 BufFile 기반 배치 테이프와 같은 것이다. 차이라면 CUBRID의 QFILE_LIST_ID가 실행기가 모든 물질화된 중간 결과에 이미 사용하는 바로 그 추상이라, 파티션 테이프가 기존 qfile_scan_list_next 기제와 투명하게 통합된다는 점이다.

분할 후 hjoin_execute_partitions는 contexts[]를 순차로 돈다.

// hjoin_execute_partitions — src/query/query_hash_join.c (condensed)
for (context_index = 0; context_index < context_cnt; context_index++)
  {
    current_context = &manager->contexts[context_index];
    hjoin_execute (thread_p, manager, current_context);
    hjoin_merge_qlist (thread_p, manager, current_context);
  }

hjoin_merge_qlist는 파티션별 출력 stitching을 처리한다. 기본은 qlist_merge_method == HASHJOIN_MERGE_CONNECT로, 튜플을 복사하는 대신 qfile_connect_list로 list file들을 끝과 끝으로 이어 붙인다. 싼 옵션이며 각 파티션의 출력이 독립적이라는 점에서 정합적이다. 폴백 인 HASHJOIN_MERGE_APPEND(copy-append)와 HASHJOIN_MERGE_COMBINE(union with deduplication)은 연산자가 현재 운용하지 않는 경로를 위해 존재한다.

stateDiagram-v2
  [*] --> Check
  Check --> SingleRun : part_cnt == 1
  Check --> Partition : part_cnt > 1
  Partition --> SplitOuter : hjoin_split_qlist(outer)
  SplitOuter --> SplitInner : hjoin_split_qlist(inner)
  SplitInner --> ParallelOk : SERVER_MODE && enough pages
  SplitInner --> Sequential : single-thread fallback
  ParallelOk --> ForkWorkers : px_worker_manager::reserve
  ForkWorkers --> Joined : barrier on parallel::execute_partitions
  Sequential --> NextCtx
  NextCtx --> RunCtx : hjoin_execute(ctx[i])
  RunCtx --> MergeCtx : hjoin_merge_qlist
  MergeCtx --> NextCtx : i++
  MergeCtx --> Done : i == part_cnt
  SingleRun --> RunSingle : hjoin_execute(single_context)
  RunSingle --> Done
  Joined --> Done
  Done --> [*]

비용 모델 통합 — qo_hjoin_cost와 qo_examine_hash_join

섹션 제목: “비용 모델 통합 — qo_hjoin_cost와 qo_examine_hash_join”

해시 조인의 옵티마이저 측은 두 곳에 산다. qo_hjoin_cost (query_planner.c 안)는 후보 hash-join 플랜 노드에 대한 4-슬롯 비용 벡터(fixed_cpu_cost, fixed_io_cost, variable_cpu_cost, variable_io_cost)를 계산한다. 모델은 의도적으로 단순하고 전적으로 CPU 항이다.

// qo_hjoin_cost — src/optimizer/query_planner.c (condensed)
inner_cardinality = inner_plan_p->info->cardinality;
outer_cardinality = outer_plan_p->info->cardinality;


plan_p->fixed_cpu_cost = outer_plan_p->fixed_cpu_cost + inner_plan_p->fixed_cpu_cost;
plan_p->fixed_io_cost  = outer_plan_p->fixed_io_cost  + inner_plan_p->fixed_io_cost;
plan_p->variable_cpu_cost = outer_plan_p->variable_cpu_cost + inner_plan_p->variable_cpu_cost;
plan_p->variable_io_cost  = outer_plan_p->variable_io_cost  + inner_plan_p->variable_io_cost;


/* if inner plays build */
inner_build_cpu_cost  = inner_cardinality * QO_CPU_WEIGHT * HJ_BUILD_CPU_OVERHEAD_FACTOR;
inner_build_cpu_cost += outer_cardinality * QO_CPU_WEIGHT * HJ_PROBE_CPU_OVERHEAD_FACTOR;


/* if outer plays build */
outer_build_cpu_cost  = inner_cardinality * QO_CPU_WEIGHT * HJ_PROBE_CPU_OVERHEAD_FACTOR;
outer_build_cpu_cost += outer_cardinality * QO_CPU_WEIGHT * HJ_BUILD_CPU_OVERHEAD_FACTOR;


switch (plan_p->plan_un.join.join_type)
  {
  case JOIN_LEFT:    /* outer preserved → inner is build */
    plan_p->variable_cpu_cost += inner_build_cpu_cost;
    break;
  case JOIN_RIGHT:   /* inner preserved → outer is build */
    plan_p->variable_cpu_cost += outer_build_cpu_cost;
    break;
  case JOIN_INNER:   /* whichever is cheaper */
    plan_p->variable_cpu_cost +=
      MIN (inner_build_cpu_cost + inner_build_io_cost,
           outer_build_cpu_cost + outer_build_io_cost);
    break;
  }

두 비용 상수는 query_planner.c 상단에 정의되어 있다.

// query_planner.c — cost constants
#define HJ_BUILD_CPU_OVERHEAD_FACTOR 30
#define HJ_PROBE_CPU_OVERHEAD_FACTOR 20

빌드는 튜플당 프로브보다 약 50% 비싼 것으로 본다. 빌드는 해시 엔트리 를 할당·삽입하지만 프로브는 체인을 도는 것뿐이라는 점에서 합리적 근사다. 결정적으로 IO 항은 현재 비활성화되어 있다(mem_limit IO surcharge가 #if 0에 감싸여 있고, “No need to increase weight since partitioned hash join is used even when mem_limit is exceeded”라는 주석이 붙어 있다). 이는 옵티마이저 자신이 spill 비용을 과소 모델링한다는 자백이다. 인메모리 단일-파티션 실행과 spill된 다중-파티션 실행 사이의 비용 차이가 플래너의 눈에는 현재 0이다.

qo_examine_hash_join 은 admission 게이트다. planner_visit_node 의 STEP 5-5에서 qo_examine_nl_join, qo_examine_idx_join, qo_examine_merge_join과 함께 호출된다.

// planner_visit_node — src/optimizer/query_planner.c (excerpt)
/* STEP 5-5: examine hash-join */
if (!bitset_is_empty (&sm_join_terms))
  {
    kept += qo_examine_hash_join (new_info, join_type, head_info, tail_info,
                                  &sm_join_terms, &duj_terms, &afj_terms,
                                  &sarged_terms, &pinned_subqueries);
  }

흥미로운 부분은 qo_examine_hash_join의 게이팅 로직이다. 명시적 요청 전까지 연산자가 옵티마이저 hot path를 비켜 있도록 만드는 방법이다.

// qo_examine_hash_join — src/optimizer/query_planner.c (condensed)
mem_limit = prm_get_bigint_value (PRM_ID_MAX_HASH_LIST_SCAN_SIZE);
if (mem_limit <= 0) goto exit;            /* hash list scan disabled at all */


if (bitset_intersects (sarged_terms, &info->env->fake_terms))
  goto exit;                              /* fake terms incompatible */


for (each term in hash_join_terms)
  if (QO_IS_PATH_TERM (term) && QO_TERM_JOIN_TYPE (term) != JOIN_INNER)
    goto exit;                            /* path terms forbid hash-join */


if (QO_NODE_HINT (inner_node) & PT_HINT_NO_USE_HASH)        goto exit;
else if (QO_NODE_HINT (inner_node) & PT_HINT_USE_HASH)
  /* fall through */;
else if (QO_NODE_HINT (inner_node) & (PT_HINT_USE_NL | PT_HINT_USE_IDX | PT_HINT_USE_MERGE))
  goto exit;
else
  {
#if TEST_HASH_JOIN_ENABLE
    /* fall through */
#else
    goto exit;        /* default: hash-join is not considered */
#endif
  }

해석하면 규칙은 다음과 같다.

힌트 상태결과
NO_USE_HASHskip
USE_HASHconsider
USE_NL / USE_IDX / USE_MERGEskip(다른 조인 방법 강제)
(힌트 없음)skip(컴파일 타임 TEST_HASH_JOIN_ENABLE이 이를 뒤집음)

운영 빌드에서는 TEST_HASH_JOIN_ENABLE이 정의되어 있지 않다. 따라서 inner relation에 명시적 /*+ USE_HASH */ 힌트가 없으면 hash join은 결코 고려되지 않는다는 점이다. 이것은 의도적으로 보수적인 자세다. 해시 조인은 기능으로는 켜져 있지만 비용-정책으로는 꺼져 있다. 비용 모델은 존재하지만 게이팅된다. 해시 조인이 이득인 워크로드(전형적으로 큰 fact와 dimension 테이블의 분석형 동등 조인) 는 개발자가 마크업해야 한다. path-term과 key-limit 검사는 row multiplicity 계약이 중요한 의미-정합성에 민감한 구성을 더 배제한다.

admission이 통과하면 qo_join_new가 QO_JOINMETHOD_HASH_JOIN 메서드의 QO_PLAN을 만들고, 이후 qo_check_plan_on_info가 같은 DP 슬롯의 다른 플랜과 비교해 순위를 매긴다.

플랜 트리 통합 — make_hashjoin_proc와 디스패치

섹션 제목: “플랜 트리 통합 — make_hashjoin_proc와 디스패치”

qo_to_xasl이 살아남은 플랜 트리를 돌 때, hash-join 노드는 make_hashjoin_proc(plan_generation.c 안)에 의해 하강된다.

// make_hashjoin_proc — src/optimizer/plan_generation.c
static XASL_NODE *
make_hashjoin_proc (QO_ENV *env, QO_PLAN *plan, XASL_NODE *outer_xasl,
                    XASL_NODE *inner_xasl, QO_PROJECTION_INFO *projection_info)
{
  ...
  HASHJOIN_PROC_NODE *proc;
  ...
  xasl = pt_to_hashjoin_proc (parser, outer_xasl, inner_xasl);
  ...
}

pt_to_hashjoin_proc(파서 측 xasl_generation.c 안)는 xasl->type = HASHJOIN_PROC을 설정하고, proc->outer.xasl / proc->inner.xasl을 채우고, 플랜의 조인 키 컬럼 메타데이터 (ls_outer_column[], ls_inner_column[], ls_pos_list[] 등)에서 merge_info를 채운다. 두 자식 XASL은 부모의 aptr_list에도 연결되어, 실행기 사전 패스가 디스패처의 case HASHJOIN_PROC: 분기보다 먼저 그들을 평가하도록 한다.

make_hashjoin_proc 시점에 추가 검사 check_hashjoin_xasl이 한 번 더 동작한다.

// check_hashjoin_xasl — src/optimizer/plan_generation.c (condensed)
for (hashjoin_xasl = xasl->aptr_list; hashjoin_xasl != NULL;
     hashjoin_xasl = hashjoin_xasl->next)
  if (hashjoin_xasl->type == HASHJOIN_PROC) break;


if (hashjoin_xasl == NULL || hashjoin_xasl->aptr_list == NULL  /* outer */
    || hashjoin_xasl->aptr_list->next == NULL                  /* inner */)
  goto error_exit;


/* both sides present and merge_info column counts > 0 */

검사는 하강된 XASL이 양 자식이 붙어 있고 적어도 하나의 조인-키 컬럼이 있는 잘-형성된 HASHJOIN_PROC 노드임을 보장한다. 0개 키 컬럼의 hash join은 카르테시안 곱이 될 텐데, 연산자는 그것을 구현하지 않는다.

xasl_to_stream.c의 패킹 경로(xts_process_hashjoin_proc)와 그 크기 계산 함수(xts_sizeof_hashjoin_proc)는 broker가 XASL 트리를 서버로 보낼 때 쓰는 wire 포맷에서 노드가 round-trip하도록 보장한다.

변종 — inner, left-outer, right-outer, parallel

섹션 제목: “변종 — inner, left-outer, right-outer, parallel”

CUBRID의 hash join은 세 가지 SQL 조인 형상 + 병렬 변종을 지원한다.

  • JOIN_INNER — 정본(canonical) 경우. 빌드 측은 작은 쪽 어느 쪽이든. 충돌은 post-hash 키 비교로 거른다. 출력은 그룹화 안 됨.

  • JOIN_LEFT(left outer) — outer(LHS)는 보존, inner(RHS)는 null-공급. inner가 빌드로 강제된다(매치 실패 시 프로브 측 폴백에서 null-padding을 발동할 수 있도록). 폴백은 hjoin_outer_probe의 if (!any_record_added) 분기에 있다.

  • JOIN_RIGHT(right outer) — 대칭. outer가 빌드로 강제된다.

  • Parallel — 파티션 수가 > 1 이고 빌드 측이 충분히 크고 (min_page_cnt가 compute_parallel_degree 임계를 통과하고), worker pool이 ≥2 worker를 grant하면, hjoin_try_parallel이 실행을 HASHJOIN_STATUS_PARALLEL로 승격해 parallel_query::hash_join::execute_partitions로 디스패치한다. 각 worker는 독립적인 파티션 쌍을 맡아 그 위에서 hjoin_execute를 돌린다. 결과는 매니저별 mutex 아래 연결된다. 병렬 경로는 순차 경로와 같은 HASHJOIN_CONTEXT[] 배열에 편승하며, HASHJOIN_SHARED_SPLIT_INFO와 HASHJOIN_SHARED_JOIN_INFO에 추가 동기화를 둔다.

세 가지 주목할 만한 부재가 있다. full-outer join 경로 없음 (JOIN_OUTER / JOIN_FULL은 hjoin_init_context의 assert_release_error (false) 기본 분기에서 거부된다), semi-/anti- join 특수화 없음(CUBRID는 EXISTS / IN 서브쿼리를 다른 곳에서 재작성하며, 재작성된 형태는 HASHJOIN_PROC에 도달하지 않는다), 재귀 (재)분할 없음(grace partitioning 한 라운드 후, 과대한 파티션의 hjoin_scan_init은 단순히 HASH_METH_HASH_FILE로 떨어져 디스크 오버헤드를 받아들인다).

fill null values 분기 — hjoin_outer_fill_null_values — 는 빌드/ 프로브 기제를 완전히 우회한다는 점이 눈에 띈다. null-공급 측이 비어 있으면 해시 테이블이 전혀 만들어지지 않고, 연산자는 그저 보존 측을 돌며 행마다 한 null-padded 레코드를 방출한다.

flowchart LR
  TYPE{join_type}
  INN[JOIN_INNER<br/>build = 작은 측]
  LEF[JOIN_LEFT<br/>build = inner RHS]
  RIG[JOIN_RIGHT<br/>build = outer LHS]
  TYPE --> INN
  TYPE --> LEF
  TYPE --> RIG

  INN --> PIN[hjoin_probe<br/>null pad 없음]
  LEF --> POL[hjoin_outer_probe<br/>프로브 미스 시<br/>outer null-pad]
  RIG --> POR[hjoin_outer_probe<br/>프로브 미스 시<br/>inner null-pad]

  PIN --> OUT[xasl->list_id]
  POL --> OUT
  POR --> OUT

  EMP{빈 측?}
  TYPE -. inner empty .-> EMP
  EMP -- 보존 측 빔 --> NOP[빈 출력]
  EMP -- 공급 측 빔 --> FILL[hjoin_outer_fill_null_values<br/>보존 측만 돌며<br/>각 행을 null-pad]
  FILL --> OUT

소스 코드 가이드

섹션 제목: “소스 코드 가이드”

심볼은 책임별로 묶었다. 본 문서가 마지막으로 updated: 된 시점에 관찰된 (파일, 라인) 쌍은 절 끝의 위치 힌트 표를 참조한다.

드라이버와 라이프사이클

  • qexec_hash_join — public 진입점, qexec_execute_mainblock_internal의 case HASHJOIN_PROC에서 호출.
  • hjoin_init_manager, hjoin_clear_manager — HASHJOIN_MANAGER 라이프사이클.
  • hjoin_init_context, hjoin_clear_context, hjoin_destroy_qlist HASHJOIN_CONTEXT 라이프사이클(빌드 측 선택이 여기 산다).
  • hjoin_check_empty_inputs — HASHJOIN_STATUS_END / FILL_NULL_VALUES / TRY 결정.
  • hjoin_execute — 컨텍스트별 빌드+프로브 드라이버.
  • hjoin_execute_internal — list scan 열기, hjoin_build 실행, 프로브 스캔 열기, hjoin_probe 또는 hjoin_outer_probe 실행.
  • hjoin_outer_fill_null_values — 빈 null-공급 측을 가진 outer 조인 의 빠른 경로.
  • hjoin_execute_partitions — partition된 실행을 위한 contexts[]의 순차 walk.

빌드 / 프로브 프리미티브

  • hjoin_fetch_key — 한 튜플에서 조인-컬럼 값을 읽고, 선택적으로 기존 키와 비교.
  • hjoin_update_tuple_hash_key — partitioning 동안 32비트 해시 워드를 튜플의 예약 값 슬롯에 쓴다.
  • hjoin_build, hjoin_build_key — 빌드 루프와 튜플별 삽입 (mht_put_hls 또는 fhs_insert로 디스패치).
  • hjoin_probe, hjoin_outer_probe, hjoin_probe_key — 프로브 루프 와 체인-walk 프리미티브(mht_get_hls / mht_get_next_hls / fhs_search / fhs_search_next로 디스패치).
  • hjoin_merge_tuple_to_list_id, hjoin_merge_tuple — 출력 list-file 에 조인 행 쓰기. 한 페이지를 넘는 행에 대한 overflow 폴백 포함.

hash-scan 프리미티브 (hash list scan과 공유)

  • qdata_alloc_hscan_key, qdata_free_hscan_key — HASH_SCAN_KEY allocator/deallocator.
  • qdata_alloc_hscan_value, qdata_alloc_hscan_value_OID, qdata_free_hscan_value — HASH_SCAN_VALUE allocator(in-mem-tuple vs hybrid-position).
  • qdata_build_hscan_key, qdata_copy_hscan_key, qdata_copy_hscan_key_without_alloc — reguvar list로부터 키 물질화.
  • qdata_hash_scan_key — 해시 함수(다중 컬럼 rotate-XOR; HASH_FILE에는 fhs_hash 라운드).
  • qdata_hscan_key_compare, qdata_hscan_key_eq — 충돌 해소기.
  • qdata_print_hash_scan_entry — debug dumper.
  • hjoin_scan_init, hjoin_scan_clear — HASH_LIST_SCAN 라이프사이클 + method 선택(HASH_METH_IN_MEM / HYBRID / HASH_FILE).

도메인 처리

  • hjoin_init_domain_info — 조인 컬럼당 공통 도메인 계산, coerce_domains[] 설정, need_coerce_domains 플래그 설정.

Partitioning(spill / grace)

  • hjoin_check_partition — mem_limit과 min_tuple_cnt 기반의 partition 여부 결정.
  • hjoin_try_partition — 최상위 partitioning 드라이버. 오류 시 SINGLE로 폴백, parallel로의 디스패치 포함.
  • hjoin_prepare_partition — contexts[] 및 파티션별 list-file 할당.
  • hjoin_split_qlist — phase-1 splitter: 해시, 파티션 라우팅, 튜플에 해시 워드 캐시.
  • hjoin_init_split_info, hjoin_clear_split_info — HASHJOIN_SPLIT_INFO 라이프사이클.
  • hjoin_init_shared_split_info, hjoin_clear_shared_split_info — 병렬 동기화 프리미티브.
  • hjoin_merge_qlist — qfile_connect_list를 통한 파티션별 출력 list-file 연결(또는 대체 merge method를 위한 copy-append / union-with-distinct 폴백).

병렬

  • hjoin_try_parallel — admission gate(compute_parallel_degree + worker_manager::try_reserve_workers).
  • parallel_query::hash_join::build_partitions, parallel_query::hash_join::execute_partitions — worker 관리 splitter 와 파티션별 runner(src/query/parallel/px_hash_join/px_hash_join.cpp 안).

옵티마이저 측

  • qo_hjoin_cost — hash-join 플랜 노드의 4-슬롯 비용 벡터.
  • qo_examine_hash_join — admission gate(힌트 검사, path-term 배제, key-limit 배제).
  • make_hashjoin_proc, pt_to_hashjoin_proc — 플랜→XASL 하강.
  • check_hashjoin_xasl — 하강된 XASL의 well-formedness 검사.
  • xts_process_hashjoin_proc, xts_sizeof_hashjoin_proc — XASL 스트림 패킹.
  • qdump_print_hashjoin_proc_node — 쿼리 플랜 dumper.

Tracing / profiling

  • hjoin_trace_start, hjoin_trace_end, hjoin_trace_merge_stats 단계별 elapsed-time / fetch / ioread 누적.
  • hjoin_profile_start, hjoin_profile_end(컴파일 타임 HASHJOIN_PROFILE_TIME로 게이팅) — 더 세밀한 단계별 profiling.
  • hjoin_trace_get_worker_stats, hjoin_trace_drain_worker_stats 병렬 stats 병합.

updated: 2026-05-01 시점의 위치 힌트

섹션 제목: “updated: 2026-05-01 시점의 위치 힌트”
심볼파일라인
qexec_hash_joinsrc/query/query_hash_join.c182
hjoin_execute_partitionssrc/query/query_hash_join.c327
hjoin_executesrc/query/query_hash_join.c408
hjoin_outer_fill_null_valuessrc/query/query_hash_join.c463
hjoin_execute_internalsrc/query/query_hash_join.c609
hjoin_init_managersrc/query/query_hash_join.c723
hjoin_clear_managersrc/query/query_hash_join.c882
hjoin_init_domain_infosrc/query/query_hash_join.c970
hjoin_try_partitionsrc/query/query_hash_join.c1166
hjoin_check_partitionsrc/query/query_hash_join.c1320
hjoin_prepare_partitionsrc/query/query_hash_join.c1377
hjoin_build_partitionssrc/query/query_hash_join.c1534
hjoin_split_qlistsrc/query/query_hash_join.c1629
hjoin_merge_qlistsrc/query/query_hash_join.c1828
hjoin_try_parallelsrc/query/query_hash_join.c1952
hjoin_init_split_infosrc/query/query_hash_join.c2070
hjoin_clear_split_infosrc/query/query_hash_join.c2127
hjoin_init_shared_split_infosrc/query/query_hash_join.c2198
hjoin_init_contextsrc/query/query_hash_join.c2298
hjoin_clear_contextsrc/query/query_hash_join.c2394
hjoin_scan_initsrc/query/query_hash_join.c2465
hjoin_scan_clearsrc/query/query_hash_join.c2581
hjoin_check_empty_inputssrc/query/query_hash_join.c2637
hjoin_fetch_keysrc/query/query_hash_join.c2701
hjoin_update_tuple_hash_keysrc/query/query_hash_join.c2849
hjoin_buildsrc/query/query_hash_join.c2874
hjoin_build_keysrc/query/query_hash_join.c3046
hjoin_probesrc/query/query_hash_join.c3129
hjoin_outer_probesrc/query/query_hash_join.c3364
hjoin_probe_keysrc/query/query_hash_join.c3700
hjoin_merge_tuple_to_list_idsrc/query/query_hash_join.c3838
hjoin_merge_tuplesrc/query/query_hash_join.c3904
hjoin_trace_merge_statssrc/query/query_hash_join.c4163
qdata_alloc_hscan_keysrc/query/query_hash_scan.c206
qdata_hash_scan_keysrc/query/query_hash_scan.c287
qdata_hscan_key_eqsrc/query/query_hash_scan.c363
qdata_build_hscan_keysrc/query/query_hash_scan.c379
qdata_alloc_hscan_valuesrc/query/query_hash_scan.c634
qdata_alloc_hscan_value_OIDsrc/query/query_hash_scan.c669
scan_build_hash_list_scansrc/query/scan_manager.c8574
scan_hash_probe_nextsrc/query/scan_manager.c8789
qo_hjoin_costsrc/optimizer/query_planner.c3604
HJ_BUILD_CPU_OVERHEAD_FACTORsrc/optimizer/query_planner.c82
HJ_PROBE_CPU_OVERHEAD_FACTORsrc/optimizer/query_planner.c83
qo_examine_hash_joinsrc/optimizer/query_planner.c6617
planner_visit_node의 hash-join admissionsrc/optimizer/query_planner.c8021
make_hashjoin_procsrc/optimizer/plan_generation.c553
check_hashjoin_xaslsrc/optimizer/plan_generation.c1856
pt_to_hashjoin_procsrc/parser/xasl_generation.c14889
실행기의 case HASHJOIN_PROCsrc/query/query_executor.c14748
xts_process_hashjoin_procsrc/query/xasl_to_stream.c3609
hashjoin_proc_node structsrc/query/xasl.h376
HASH_LIST_SCAN structsrc/query/query_hash_scan.h110
HASHJOIN_MANAGER structsrc/query/query_hash_join.h319
HASHJOIN_CONTEXT structsrc/query/query_hash_join.h297
PRM_ID_MAX_HASH_LIST_SCAN_SIZEsrc/base/system_parameter.c3517

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

섹션 제목: “소스 검증 (2026-05-01 기준)”

  • 메모리 예산에 대한 옵티마이저 ↔ 실행기 대칭. qo_examine_hash_join(admission)과 hjoin_check_partition(spill 트리거) 모두 같은 PRM_ID_MAX_HASH_LIST_SCAN_SIZE를 읽는다. 따라서 파라미터는 hash join이 애초에 고려되는지(0으로 설정하면 옵티마이저 가 비활성화)와 활성화 시 partition 수를 함께 통제한다. 이 중복은 올바르지만 부서지기 쉽다. 한 쪽을 바꾸는 향후 리팩토링은 다른 쪽도 쫓아야 한다. 옵티마이저 문서(cubrid-query-optimizer.md)는 4-슬롯 비용 모델을 언급하지만 qo_examine_hash_join 수준의 zero-check 은 짚지 않는다.

  • 비용 모델은 spill을 과소 모델링한다. qo_hjoin_cost에서 짚힌 대로, spill된 파티션의 IO surcharge는 “partitioned hash join is used even when mem_limit is exceeded” 주석과 함께 #if 0로 막혀 있다. 이는 옵티마이저가 인메모리 hash join과 spill된 hash join을 IO 비용이 동일한 것으로 다룬다는 뜻이다. 실제로 spill 경로는 파티션별 list-file과 FHSID 버킷 페이지에 진짜 디스크 I/O를 지불 하므로, 플래너는 spill된 hash-join 비용을 과소 추정한다. 그것이 중요한 워크로드에서는 사용자가 USE_HASH 힌트를 tie-breaker가 아닌 강제 함수로 쓰도록 기대된다. 이는 보수적 admission 자세에 부합한다.

  • USE_HASH 힌트가 실효적 스위치다. 운영 빌드에서 TEST_HASH_JOIN_ENABLE은 설정되지 않으므로, 쿼리에 /*+ USE_HASH(inner_alias) */가 없으면 비용 모델이 선호하더라도 hash join은 결코 생성되지 않는다는 점이다. 실행기 문서가 hash join 을 디스패치 표에서 이름만 언급하는 것 (cubrid-query-executor.md의 qexec_hash_join)과, 후처리 문서가 공유 mht_hls 기제를 cubrid-post-processing.md를 강조하는 것과 일관된다.

  • hash-scan 프리미티브는 hash list scan 및 hash group-by와 공유된다. MHT_HLS_TABLE, HASH_SCAN_KEY, HASH_SCAN_VALUE, qdata_hash_scan_key, qdata_build_hscan_key, qdata_alloc_hscan_value, fhs_*는 모두 query_hash_join.c(이 문서), scan_manager.c의 scan_build_hash_list_scan / scan_next_hash_list_scan / scan_hash_probe_next(hash list scan, 비상관 서브쿼리와 IN-list 프로빙에서 사용 — cubrid-query-executor.md 의 scan-manager 절 참조), 그리고 query_executor.c의 qexec_hash_gby_* 패밀리(hash group-by — cubrid-post-processing.md 의 sort-vs-hash GROUP BY 절 참조)에 걸쳐 공유된다. 해시 키 인코딩의 어떤 진화든 세 곳 모두에 반영되어야 한다.

  • splitter는 예약된 튜플 슬롯을 가정한다. hjoin_split_qlist와 hjoin_update_tuple_hash_key는 32비트 해시 워드를 첫 번째 튜플 값 슬롯에 쓰며, 그 슬롯이 정확히 MAX_ALIGNMENT 바이트 너비이고 -1 sentinel로 초기화되어 있음을 assert한다. 이는 XASL 생성기 (pt_to_hashjoin_proc/make_hashjoin_proc)와의 계약이다. 슬롯 0의 순서를 바꾸거나 줄이는 향후의 튜플 형태 변경은 hash-join partitioning 을 조용히 깬다는 뜻이다. 계약은 XASL 빌드 시점에는 assert되지 않고, split 시점에만 assert된다.

  • 빌드 측 선택은 쿼리 단위가 아니라 파티션 단위. inner join에서 hjoin_init_context는 각 파티션마다 독립적으로 build = 작은 측을 재계산한다. split 후, 한 파티션이 다른 파티션과 다른 측을 빌드로 가질 수 있다. split이 행을 어떻게 분배했는지에 달려 있다. 파티션별로는 정합적이지만(각 파티션은 자기-완결적 고전 hash join), 이는 단일 쿼리의 trace 출력이 partition된 hash join를 혼합된 빌드 측을 보여줄 수 있음을 의미한다는 점이다. QP 모듈 덱은 이를 짚지 않는다.

  • partition된 프로브에서 hjoin_outer_probe의 충돌-skip은 assert-impossible 케이스다. 프로브 측이 partition된 경우, 프로브 키는 chain-walk 루프 안에서 lazy하게 fetch된다. 그곳에서 need_skip_next가 발동한다는 것은 사전-partition된 프로브 튜플에 NULL이 나타났다는 뜻이며, splitter가 이미 fill-null 파티션으로 라우팅했어야 한다. 코드는 방어적으로 null-padded 행을 방출하고 계속하지만 assert_release_error (false)는 이 분기가 well-formed XASL에서 발동될 것을 연산자가 예상하지 않음을 보여 준다. splitter 동작을 누가 바꿀 때 유용한 진단이다.

  • 해시 함수에 collation은 없다. qdata_hash_scan_key는 mht_get_hash_number를 호출해 타입별 해셔를 거친다. 문자열 타입의 경우 해시는 하부 프리미티브가 인코딩하는 한에서만 collation을 포함 한다. post-hash 키 비교(hjoin_fetch_key의 tp_value_compare)는 pr_clone_value / tp_value_coerce로 collation을 존중한다. 따라서 시스템은 collation으로 인한 의사-충돌을 잡기 위해 post-hash 비교에 의존한다. collation-동등한 두 문자열이 반드시 같은 워드로 해시된다고 단정할 수는 없다는 점이다.

  • HASHJOIN_MERGE_CONNECT가 운용되는 유일한 merge 경로다. hjoin_init_manager는 qlist_merge_method = HASHJOIN_MERGE_CONNECT 를 하드코딩한다. hjoin_merge_qlist의 MERGE_COMBINE과 MERGE_APPEND 분기는 이 한 줄을 편집해야만 도달 가능하므로 본 개정 시점에는 사실상 죽은 코드다. 향후 작업(예: distinct-result hash join, 파티션 출력의 union-with-deduplication 의미론이 필요한 경우)을 위해 보존된 것으로 추정된다.

미해결 질문

섹션 제목: “미해결 질문”

  • 블룸 필터 사전-프로브. 현대 hash join들(PostgreSQL parallel hash, MonetDB, DuckDB)은 빌드 측에서 프로브 측 스캔으로 블룸 필터 를 push down하여, 매칭되지 않을 프로브 행이 연산자 경계를 넘기 전에 버려지도록 한다. CUBRID의 hash join은 이를 구현하지 않는다. 보수적 admission 정책(USE_HASH-힌트를 받은 조인만 연산자에 도달)을 감안할 때 이것이 비용을 회수할지는 미해결 질문이다.

  • 적응형 역할 반전(adaptive role reversal). 빌드 측이 비용 모델 추정보다 크다고 판명될 때(카디널리티 추정이 빗나갔기 때문), 일부 엔진들(SQL Server의 Hash Match, 특정 형상의 최근 PostgreSQL) 은 빌드를 중단하고 다른 측을 빌드로 재시작한다. CUBRID의 hjoin_init_context는 물질화된 list-file 헤더에 이미 잡힌 tuple_cnt/page_cnt로 파티션당 한 번 빌드 측을 결정한다. 추정이 아니라 정확한 값이므로 그것이 보통 교정해 주는 정합성을 위해서는 역할 반전이 필요 없다. 그러나 qo_examine_hash_join admission에 들어간 추정이 틀렸다면, 실제 크기로는 nested-loop가 유리할 쿼리에 hash join이 선택될 수 있다. CUBRID에는 실행 시점에 연산자를 전환하는 폴백이 없다.

  • skew 하의 재귀 partitioning. grace partitioning 한 라운드 후에도 한 파티션의 빌드 측이 여전히 너무 큰 경우(조인 키의 심한 skew), CUBRID는 HASH_METH_HASH_FILE로 떨어져 디스크 확장형 해시 오버헤드를 받아들인다. SQL Server의 recursive hash는 대신 다른 해시 함수로 재분할한다. 조인 키에 심한 skew가 있는 워크로드(hot-key dimension)의 경우 CUBRID의 경로는 정합적이지만 대안보다 느리다.

  • 병렬 빌드 조정. 병렬 경로는 먼저 partition한 뒤 worker당 한 파티션 쌍을 할당한다. 한 파티션 안의 빌드는 단일 스레드다. PostgreSQL은 v11부터 worker들이 한 공유 해시 테이블에 협력적으로 삽입하는 공유-메모리 병렬 빌드를 가진다. CUBRID의 병렬 hash join은 파티션 수준 한정이며, shared-build 병렬성이 로드맵에 있는지는 소스에 문서화되어 있지 않다는 점이다.

  • Semi-/anti-join 특수화. EXISTS / NOT EXISTS / 비상관 IN 은 현재 표준 조인으로 재작성되거나 hash list scan으로 라우팅된다. 첫 빌드 매치 후 early-out할 수 있는 HASHJOIN_PROC semi-join 변종은 없다. 선택적 semi-join에 대한 비용 절감은 상당할 수 있다.

  • 비용 모델 IO 항. qo_hjoin_cost의 #if 0로 막힌 IO surcharge는 spill된 hash-join 비용의 알려진 과소 추정이다. 그 정당화 (“partitioned hash join is used even when mem_limit is exceeded”)는 모델이 왜 포기하는지를 설명하지만 무엇으로 대체해야 하는지는 말하지 않는다. min_page_cnt에 max(1, (build_size / mem_limit))을 곱하는 페이지 기반 추정기는 작은 변경이지만, spill된 hash join이 지배적인 워크로드에서 조인 메서드 선택에 큰 영향을 준다.

  • Full-outer hash join 없음. hjoin_init_context의 기본 분기는 assert_release_error (false)로 JOIN_OUTER를 거부한다. PostgreSQL 은 빌드 엔트리당 matched 비트와, 매치되지 않은 빌드 행을 방출 하는 최종 패스로 full-outer hash join을 구현한다. CUBRID는 그렇지 않다. full-outer 조인은 sort-merge로 라우팅되는 것으로 추정된다.

출처

섹션 제목: “출처”
  • src/query/query_hash_join.c, src/query/query_hash_join.h — 드라이버, manager/context, 빌드/프로브 단계, partitioning, 병렬 glue.
  • src/query/query_hash_scan.c, src/query/query_hash_scan.h — 공유 hash-scan 프리미티브(키/값 할당, 해시 함수, FHSID 확장형 해시 파일).
  • src/query/scan_manager.c — scan_build_hash_list_scan, scan_next_hash_list_scan, scan_hash_probe_next(hash list scan, HASH_LIST_SCAN의 형제 소비자).
  • src/query/query_executor.c — qexec_execute_mainblock_internal의 case HASHJOIN_PROC 디스패치(라인 ~14748).
  • src/query/xasl.h — HASHJOIN_PROC_NODE, HASHJOIN_INPUT, QFILE_LIST_MERGE_INFO 정의.
  • src/query/xasl_to_stream.c — xts_process_hashjoin_proc, xts_sizeof_hashjoin_proc 패킹.
  • src/query/query_dump.c — qdump_print_hashjoin_proc_node 플랜 트리 프린터.
  • src/optimizer/query_planner.c — qo_hjoin_cost, qo_examine_hash_join, hash-join CPU 상수 (HJ_BUILD_CPU_OVERHEAD_FACTOR, HJ_PROBE_CPU_OVERHEAD_FACTOR), planner_visit_node의 STEP 5-5 호출지.
  • src/optimizer/plan_generation.c — make_hashjoin_proc, check_hashjoin_xasl.
  • src/parser/xasl_generation.c — pt_to_hashjoin_proc.
  • src/query/parallel/px_hash_join/ — 병렬 실행 백엔드.
  • src/base/system_parameter.c — PRM_ID_MAX_HASH_LIST_SCAN_SIZE 파라미터 선언.
  • DeWitt, Katz, Olken, Shapiro, Stonebraker, Wood, Implementation Techniques for Main Memory Database Systems, SIGMOD 1984.
  • Shapiro, Join Processing in Database Systems with Large Main Memories, ACM TODS 1986.
  • Kitsuregawa, Tanaka, Moto-oka, Application of Hash to Data Base Machine and Its Architecture, New Generation Computing 1983 (GRACE).
  • Graefe, Query Evaluation Techniques for Large Databases, ACM Computing Surveys 1993, §3 (hash join survey).
  • Graefe, Volcano — An Extensible and Parallel Query Evaluation System, IEEE TKDE 1994 (operator integration).
  • Petrov, Database Internals, ch. 14 Query Execution(sort vs hash join).
  • Garcia-Molina, Ullman, Widom, Database Systems: The Complete Book, ch. 15.4–15.5 (hash join 비용 분석).
  • Silberschatz, Korth, Sudarshan, Database System Concepts, ch. on join operators (hash join + sort-merge 비교).