Hash join Probe 단계 처리과정

hash join Probe단계 처리 과정

• 질문 : 해시조인에서 Probe 단계에서 해시바킷을 사용 하니요?

  ==> 아니요! Probe 테이블의 컬럼은 해시 버킷에 저장되지 않습니다.

• 예제

SELECT e.emp_id, e.name, e.salary, d.dept_name
FROM employees e      -- ← Build 테이블 (작은 테이블)
JOIN departments d    -- ← Probe 테이블 (큰 테이블)
ON e.dept_id = d.dept_id

해시 버킷에 저장되는 것

• 오직 Build 테이블의 데이터만 저장됩니다!

• 해시 테이블 구조:

Bucket[0] → NULL

Bucket[1] → [employees 행]
            ┌──────────────────────────┐
            │ dept_id: 10  (조인 키)   │
            │ emp_id: 101              │
            │ name: '김철수'           │
            │ salary: 5000000          │
            │ next: NULL               │
            └──────────────────────────┘
            ↑
            employees 테이블 데이터만!
            departments 데이터는 없음!

Hash Join 전체 프로세스

1. 1단계: Build (해시 테이블 생성)

   # Build 단계 - employees 테이블만 메모리에 로드
   
   hash_table = []
   
   for row in employees:  # Build 테이블
       hash_value = hash(row.dept_id)
       bucket_index = hash_value % BUCKET_SIZE
       
       # employees 테이블의 필요한 컬럼만 저장
       entry = {
           'dept_id': row.dept_id,    # 조인 키
           'emp_id': row.emp_id,      # SELECT 절에 있음
           'name': row.name,          # SELECT 절에 있음
           'salary': row.salary,      # SELECT 절에 있음
           'next': NULL
       }
       
       hash_table[bucket_index].insert(entry)

   *이 시점에 메모리 상태:**

   메모리 (PGA)
   └─ Hash Table
      └─ employees 데이터만 저장
      
   departments 테이블은 아직 읽지도 않음!

2. 2단계: Probe (조인 수행)

   # Probe 단계 - departments 테이블을 순차적으로 읽음
   
   for dept_row in departments:  # Probe 테이블 (순차 스캔)
       # 1. departments 행의 조인 키로 해시 계산
       hash_value = hash(dept_row.dept_id)
       bucket_index = hash_value % BUCKET_SIZE
       
       # 2. 해시 테이블에서 매칭되는 employees 행 찾기
       entry = hash_table[bucket_index]
       while entry is not NULL:
           if entry.dept_id == dept_row.dept_id:
               # 3. 조인 성공!
               # 이 순간 dept_row.dept_name을 사용
               result = {
                   'emp_id': entry.emp_id,          # 메모리(해시 테이블)에서
                   'name': entry.name,              # 메모리(해시 테이블)에서
                   'salary': entry.salary,          # 메모리(해시 테이블)에서
                   'dept_name': dept_row.dept_name  # 현재 읽은 행에서!
               }
               output(result)
           
           entry = entry.next
       
       # 4. 다음 departments 행으로 (이전 행은 버림)

핵심 차이점

┌─────────────────────────────────────────────────┐
│ Build 테이블 (employees)                         │
├─────────────────────────────────────────────────┤
│ ✅ 전체 데이터를 메모리(해시 테이블)에 저장       │
│ ✅ SELECT 절의 모든 컬럼 포함                     │
│ ✅ Probe 단계 내내 메모리에 유지                  │
└─────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────┐
│ Probe 테이블 (departments)                       │
├─────────────────────────────────────────────────┤
│ ❌ 해시 테이블에 저장 안 됨                       │
│ ✅ 순차적으로 한 행씩 읽음                        │
│ ✅ 조인 성공 시 그 순간만 사용                    │
│ ✅ 다음 행으로 넘어가면 이전 행 데이터는 버림     │
└─────────────────────────────────────────────────┘

실제 동작 타임라인

Time 1: Build 단계

─────────────────────────────────────────
메모리: [employees 전체 로드]
디스크: departments (아직 안 읽음)

Time 2: Probe 시작

─────────────────────────────────────────
메모리: [employees 전체]
읽는 중: departments 행1 {dept_id:10, dept_name:'영업부'}
→ 매칭 찾기 → 결과 출력 → 버림

Time 3: Probe 계속

─────────────────────────────────────────
메모리: [employees 전체]
읽는 중: departments 행2 {dept_id:20, dept_name:'개발부'}
→ 매칭 찾기 → 결과 출력 → 버림

(departments는 메모리에 저장 안 됨!)

왜 이렇게 설계되었나?

1. 메모리 효율: Probe 테이블이 매우 클 수 있어서 모두 메모리에 올릴 수 없음
2. 스트리밍 처리: Probe 테이블은 한 행씩 읽어서 즉시 처리 후 버림
3. 작은 테이블만 메모리에: Build 테이블(작은 것)만 메모리에 올려서 빠른 검색

• 메모리 사용량 비교
  • 시나리오: employees (100,000행) JOIN orders (10,000,000행)

• • 실제 방식 (Hash Join):

메모리 사용: 100,000행 (employees만) = 약 6-10 MB

• • 만약 둘 다 저장한다면:

메모리 사용: 100,000 + 10,000,000행 = 약 600 MB ~ 1 GB → 메모리 부족으로 디스크 사용 → 성능 저하!

핵심 정리

|항목          |Build 테이블 (employees)|Probe 테이블 (departments)|
|------------|---------------------|-----------------------|
|해시 버킷 저장    |✅ 예                  |❌ 아니오                  |
|메모리 상주      |✅ 전체 과정 동안           |❌ 한 행씩만                |
|처리 방식       |전체 로드                |순차 스캔                  |
|dept_name 저장|-                    |❌ 저장 안 됨, 사용 시점에만      |

• Probe 테이블에서 select 절에 사용된 컬럼은 해시 버킷에 저장되지 않고, Probe 단계에서 테이블을 읽을 때마다 그 순간에만 사용됩니다