Hash Join의 원리와 Workarea: Build·Probe·PGA·TEMP Spill

핵심 요약

Hash Join은 한쪽 Row Source로 Hash Table을 만든 뒤(Build), 다른 Row Source를 읽으며 같은 Hash Bucket을 탐색하는(Probe) 조인 방식입니다.

Build Input
→ Join Key Hash 계산
→ PGA Workarea에 Hash Table 생성

Probe Input
→ 같은 Hash 함수 적용
→ 대응 Bucket 탐색
→ 실제 Join Key 재비교
→ Match Row 반환

Oracle Optimizer는 일반적으로 다음 조건에서 Hash Join을 후보로 고려합니다.

• 비교적 많은 Row를 조인함
• Equijoin 조건을 사용할 수 있음
• 결과를 상당 부분 또는 End-of-Fetch까지 처리함
• NL의 반복 Index·ROWID Access보다 Build·Probe가 저렴함
• 작은 Post-Filter Data Set이 Workarea에 들어가거나 Spill을 포함해도 총비용이 낮음

개념적 비용입니다.

Hash Join 총비용
≈ Build Row Source 생성 비용
 + Hash Table 생성 CPU·Memory
 + Probe Row Source 생성 비용
 + Probe Hash·Bucket 탐색·실제 Key 비교
 + Spill 발생 시 TEMP Write·Read
 + Join 결과 후속 처리

중요합니다.

작은 원본 Table
  ≠ 반드시 Build Input

Predicate 후 Row 수 × 저장 Row 폭
  = Build Memory 판단의 핵심

이 이론의 범위

이 이론은 SQLP의 SQL 고급활용 및 튜닝 → 조인 순서와 조인 방식 → 해시 조인 범위에서 Build·Probe, Hash Bucket·Collision, Workarea·TEMP Spill과 실행계획 검증을 다룹니다.

학습 목표

이 이론을 학습한 뒤에는 다음을 설명할 수 있어야 합니다.

• Join Type·Order·Method·Access Path를 구분한다.
• Hash Join이 고려되는 대표 조건을 설명한다.
• Build Input과 Probe Input의 역할을 구분한다.
• 원본 Table 크기보다 Filter 후 A-Rows·Row 폭이 중요한 이유를 설명한다.
• Hash Collision과 Duplicate Join Key를 구분한다.
• 중복 Key의 Join 결과 행 수를 계산한다.
• Equijoin Key와 추가 Non-Equi Predicate의 역할을 구분한다.
• OPTIMAL·ONE PASS·MULTI-PASS를 설명한다.
• Hash Table이 PGA에 들어가지 않을 때 양쪽 입력을 Partition하는 흐름을 설명한다.
• V$SQL_WORKAREA·V$SQL_WORKAREA_ACTIVE·ALLSTATS LAST를 이용해 Memory·TEMP를 진단한다.
• Data Skew와 Cardinality 오차가 Spill·결과 행 수에 미치는 영향을 설명한다.
• NL·Sort Merge·Hash를 동일 Bind·Fetch 조건에서 비교한다.
• USE_HASH·LEADING·NO_USE_HASH의 역할을 구분한다.

1. 네 가지 결정을 분리한다

Hash Join은 Join Method입니다.

HASH JOIN
HASH JOIN OUTER
HASH JOIN RIGHT OUTER
HASH JOIN FULL OUTER
HASH JOIN SEMI
HASH JOIN ANTI

HASH JOIN이라는 Operation만으로 결과 의미를 판단하지 않습니다. OUTER·SEMI·ANTI의 행 보존·NULL·중복 규칙은 Join Type에서 확인합니다.

2. Hash Join이 고려되는 조건

대표 Equijoin입니다.

ON o.customer_id = c.customer_id

복합 Equijoin도 가능합니다.

ON d.order_id = h.order_id
AND d.line_no = h.line_no

등치 조건과 추가 Range 조건이 함께 있으면 등치 Column은 Hash 후보를 찾는 Key가 되고, 나머지 조건은 Bucket 후보에 추가로 평가될 수 있습니다.

ON b.customer_id = a.customer_id
AND b.order_date >= a.start_date

순수 Non-Equijoin만 있으면 사용할 Equality Hash Key가 없으므로 NL·Sort Merge가 주요 후보가 됩니다.

Hash Join이 유리할 가능성이 높은 조건입니다.

• 두 입력 또는 결과가 비교적 큼
• NL Inner Access를 수십만 번 반복해야 함
• Index Random Access보다 Scan이 저렴함
• Partition Pruning 후 큰 범위를 한 번 읽는 편이 유리함
• Full Fetch·Batch·Report 처리
• Build Input이 Memory에 적합함

주의가 필요한 조건입니다.

• 매우 작은 Outer와 효율적인 Inner Unique Index
• 첫 몇 행만 빠르게 필요한 화면 조회
• 순수 비등치 Join
• Build Input 과소 추정
• 넓은 Row·불필요한 Projection
• 중복 Key·Skew로 결과나 특정 Partition이 커짐
• 동시 Workarea 증가로 세션별 Memory 감소

3. Build Input과 Probe Input

3.1 Build Input

Build Input은 Hash Table을 만드는 Row Source입니다.

Build Row
→ Join Key 추출
→ Hash 값 계산
→ Bucket에 Key와 필요한 Row 정보 저장

개념적 Memory입니다.

Build Memory
≈ Predicate 후 Build A-Rows
 × Hash Table에 보관할 Row 폭
 + Bucket·Pointer·관리 Overhead

원본 Table만 비교하면 안 됩니다.

CUSTOMERS 원본 10,000,000행
→ region_code='JEJU' 후 8,000행

ORDERS 원본 50,000,000행
→ 최근 5분 후 3,000행

이 경우 원본은 CUSTOMERS가 작지만 실제 Post-Filter 입력은 ORDERS가 더 작습니다.

Build Input은 다음일 수 있습니다.

• Base Table Access 결과
• Inline View·CTE
• 선집계 결과
• 이전 Join의 중간 Row Source
• Partition Pruning 결과

3.2 Probe Input

Probe Input은 Build Hash Table을 탐색합니다.

Probe Row
→ 동일 Hash 함수
→ Bucket 위치 탐색
→ Bucket 후보와 실제 Join Key 비교
→ Match 결합

Probe Input도 항상 Full Scan은 아닙니다. Predicate·Partition 조건에 따라 Index Scan·Partition Scan·Full Scan 중 Cost가 낮은 Access Path를 사용할 수 있습니다.

3.3 기본 Plan 해석

기본적인 Inner Hash Join Plan입니다.

HASH JOIN
  Build Row Source
  Probe Row Source

일반적인 Inner Hash Join에서 첫 번째 자식은 Build, 두 번째 자식은 Probe로 읽습니다.

단, 다음 환경에서는 내부 입력 방향·Swap·Join Type을 추가 확인합니다.

• Right Outer·Full Outer
• Semi·Anti Join
• Parallel Execution
• Adaptive Plan
• Optimizer의 Input Swap
• Complex Transformation

+ALIAS +OUTLINE +NOTE와 실제 Workarea Operation을 함께 확인합니다.

4. Hash Function·Bucket·Collision

Hash 함수는 같은 Join Key에 대해 같은 Hash 값을 생성합니다.

hash(10) → Bucket 4
hash(20) → Bucket 1
hash(30) → Bucket 4

서로 다른 Key가 같은 Bucket에 들어가는 현상이 Hash Collision입니다.

Bucket 4
  Key 10
  Key 30

Probe Row가 Bucket에 도착하면 실제 Join Key를 다시 비교합니다.

같은 Hash 값
  → 후보 위치 탐색

실제 Key 비교
  → 진짜 Match만 반환

4.1 Collision과 Duplicate Key

Collision은 Hash 구조의 후보 탐색 문제이고 Duplicate는 SQL 결과 Cardinality 문제입니다.

5. 중복 Join Key와 결과 행 수

Hash Join은 중복을 제거하지 않습니다.

Build Key 20: 2행
Probe Key 20: 3행

결과
= 2 × 3
= 6행

Key별 결과식입니다.

Key별 Join 결과
= Build의 동일 Key 행 수
 × Probe의 동일 Key 행 수

중복도가 높으면 다음 비용이 증가합니다.

• Hash Bucket 후보 비교
• Join 결과 A-Rows
• 후속 GROUP BY·SORT
• 상위 Join 입력
• Client·Network 전송

Join Method를 바꿔도 업무상 필요한 결과 행 생성 비용은 사라지지 않습니다.

일반 Equijoin에서 NULL Join Key끼리는 NULL=NULL이 TRUE가 아니므로 Match하지 않습니다. Outer Join은 Join Type의 보존 규칙에 따라 NULL 확장 Row를 반환할 수 있습니다.

6. 간단한 업무 예제

SELECT /*+ GATHER_PLAN_STATISTICS */
       c.customer_id,
       c.customer_name,
       o.order_id,
       o.order_date,
       o.order_amount
FROM   customers c
JOIN   orders o
  ON   o.customer_id=c.customer_id
WHERE  c.region_code=:region_code
AND    o.order_date>=:from_date;

개념적 Plan입니다.

HASH JOIN
  TABLE ACCESS FULL CUSTOMERS
  TABLE ACCESS FULL ORDERS

흐름입니다.

1. region_code 조건을 통과한 CUSTOMERS Row Source 생성
2. CUSTOMER_ID Hash Table Build
3. 날짜 조건을 통과한 ORDERS Row Source 생성
4. 주문 CUSTOMER_ID Hash 계산
5. Bucket 후보 탐색
6. 실제 CUSTOMER_ID 비교
7. 결과 반환

Full Scan이 보인다는 이유만으로 비효율이라고 판단하지 않습니다. 많은 Row가 필요하면 Full Scan+Hash Join이 수많은 Index Random Access보다 저렴할 수 있습니다.

7. PGA Workarea와 Hash Table

Hash Join은 PGA SQL Workarea에서 Hash Table·Partition 관리 구조를 처리합니다.

PGA Workarea
└─ Hash Table
   ├─ Bucket
   ├─ Key·Row 정보
   └─ Partition 관리 구조

7.1 OPTIMAL

Build Hash Table이 Workarea 안에 들어감
→ TEMP Spill 없음
→ Build·Probe 입력 Access와 Hash CPU가 주요 비용

OPTIMAL은 Workarea Spill이 없다는 의미입니다. Table·Index·Storage I/O가 없다는 의미가 아닙니다.

7.2 ONE PASS

Build 전체가 Memory에 들어가지 않음
→ 일부 Build Partition TEMP Write
→ 대응 Probe Partition TEMP Write
→ Partition별 한 번 추가 처리

일부 Partition은 Memory에서 즉시 처리하고 Disk Partition은 이후 한 번의 추가 Pass로 처리합니다.

7.3 MULTI-PASS

Disk Partition 하나도 Workarea에 충분히 들어가지 않음
→ 재분할
→ TEMP Write·Read 반복

Multi-Pass는 큰 성능 저하의 신호입니다. 그러나 원인은 단순 PGA 부족만이 아닐 수 있습니다.

• Build A-Rows 과소 추정
• 넓은 Build Row
• Predicate 적용 지연
• Join Order 오류
• Data Skew
• Concurrent Workarea 증가

8. Memory 부족 시 Partition 처리

Hash Table이 PGA에 들어가지 않으면 양쪽 입력을 같은 Hash 규칙으로 Partition합니다.

Build Input
→ B0, B1, B2, B3

Probe Input
→ P0, P1, P2, P3

처리입니다.

1. Build Row를 Hash Partition으로 나눔
2. 일부는 Memory, 일부는 TEMP 기록
3. Probe Row를 같은 규칙으로 나눔
4. Memory Build Partition은 즉시 Probe
5. Disk Build Partition에 대응하는 Probe Row는 TEMP 기록
6. B0와 P0, B1과 P1을 각각 읽어 조인
7. Partition이 Memory보다 크면 다시 분할

추가 비용입니다.

• Build TEMP Write
• Probe TEMP Write
• Partition TEMP Read
• Multi-Pass 재분할
• Hash·Copy CPU
• TEMP Contention

9. Data Skew와 Partition 불균형

Build 전체 크기뿐 아니라 Join Key 분포도 중요합니다.

일반 Key
  각 10행

인기 Key
  5,000,000행

Hash Partition이 균등하지 않으면 특정 Partition이 매우 커질 수 있습니다.

영향입니다.

• 큰 Partition의 Memory 요구량 증가
• 특정 Bucket의 후보 비교 증가
• Multi-Pass 가능성
• Parallel Worker 부하 불균형
• 결과 Cardinality 폭증

확인합니다.

• Key별 빈도
• Histogram·Column Group
• Hash Join 자식 E-Rows·A-Rows
• 결과 A-Rows
• Parallel Worker별 처리량
• Workarea Spill·TEMP

Data Skew와 Duplicate 결과는 별도지만 동시에 발생할 수 있습니다.

10. 실행계획과 Workarea 검증

실행합니다.

SELECT /*+ GATHER_PLAN_STATISTICS */
       c.customer_id,
       SUM(o.order_amount)
FROM   customers c
JOIN   orders o
  ON   o.customer_id=c.customer_id
WHERE  c.region_code=:region_code
AND    o.order_date>=:from_date
GROUP BY c.customer_id;

실제 Cursor를 확인합니다.

SELECT *
FROM TABLE(
  DBMS_XPLAN.DISPLAY_CURSOR(
    :sql_id,
    :child_no,
    'ALLSTATS LAST +MEMSTATS +PREDICATE +ALIAS +OUTLINE +NOTE'
  )
);

10.1 Plan Runtime

상위 Operation 통계가 하위 작업을 포함할 수 있으므로 모든 Buffers·A-Time을 단순 합산하지 않습니다.

10.2 V$SQL_WORKAREA

SELECT sql_id,
       child_number,
       operation_id,
       operation_type,
       policy,
       estimated_optimal_size,
       estimated_onepass_size,
       last_memory_used,
       last_execution,
       last_tempseg_size,
       max_tempseg_size
FROM   v$sql_workarea
WHERE  sql_id=:sql_id
AND    child_number=:child_number
ORDER BY operation_id;

대표 Column입니다.

10.3 V$SQL_WORKAREA_ACTIVE

현재 실행 중 Workarea의 순간 상태를 봅니다.

• Actual Memory
• Number of Passes
• Temp Segment
• Operation Type
• Expected Size

WORKAREA_ADDRESS로 V$SQL_WORKAREA와 연결할 수 있습니다.

11. Hash Join Hint

11.1 USE_HASH

SELECT /*+ LEADING(c o) USE_HASH(o) */
       ...
FROM customers c
JOIN orders o
  ON o.customer_id=c.customer_id;

USE_HASH(o)는 o를 다른 Row Source와 연결할 때 Hash Join을 유도합니다.

중요합니다.

USE_HASH(o)
  → Join Method Hint
  → Join Order를 직접 지정하지 않음

따라서 LEADING·ORDERED와 함께 대안 Plan을 검증합니다.

11.2 NO_USE_HASH

/*+ NO_USE_HASH(o) */

o를 대상으로 하는 Hash Join 후보를 제외하도록 유도합니다. NL·Merge 중 무엇이 선택될지는 다른 유효 후보와 Cost에 따라 달라집니다.

11.3 Alias·Query Block

Alias가 있으면 Hint에도 Alias를 사용합니다.

FROM orders o

/*+ USE_HASH(o) */

CTE·Inline View·Transformation이 있으면 QB_NAME, +ALIAS, +OUTLINE, Hint Report를 사용해 실제 대상을 확인합니다.

12. NL·Sort Merge·Hash 비교

공정한 비교 조건입니다.

• 동일 결과
• 동일 Bind·Data Type
• 동일 Statistics
• 동일 Parallel Degree
• 동일 Fetch 범위
• 동일 Projection
• 유사한 Cache 상태

13. Hash Join 튜닝 순서

1. Join Type과 Equijoin Key를 확인한다.
2. Build·Probe 자식의 E-Rows·A-Rows를 확인한다.
3. Build의 Row 폭과 전달 Column을 확인한다.
4. 실제 Build 방향과 Outline을 확인한다.
5. Duplicate Key·Skew와 결과 A-Rows를 확인한다.
6. OPTIMAL·ONE PASS·MULTI-PASS와 TEMP를 확인한다.
7. Filter Pushdown·선집계·Projection 축소를 검토한다.
8. Join Order와 USE_HASH 대안을 시험한다.
9. NL·Merge를 동일 Bind·Fetch로 비교한다.
10. 동시 실행 시 PGA·TEMP·Parallel 회귀를 검증한다.

PGA부터 늘리지 않습니다.

입력 Row 감소
→ Row 폭 감소
→ Cardinality 개선
→ Join Order·Method 개선
→ 동시 Workarea 확인
→ PGA 정책 검토

자주 혼동하는 판단