해시 버킷의 저장구조

Oracle Hash Join의 내부 구조

• 해시 버킷의 저장 구조

해시 버킷에 저장되는 내용

• 해시 버킷에는 주소 정보가 아닌 실제 데이터 행(row data) 이 저장됩니다.

# 해시 테이블 구조:
#[해시 버킷 배열]
Bucket 0  → [emp_id=101, name='김철수', dept_id=10] → [emp_id=501, name='이영희', dept_id=10] → NULL
Bucket 1  → [emp_id=202, name='박민수', dept_id=20] → NULL
Bucket 2  → NULL
Bucket 3  → [emp_id=303, name='정수진', dept_id=30] → [emp_id=403, name='최지원', dept_id=30] → NULL
...

각 버킷 엔트리에 포함되는 정보

┌─────────────────────────────┐
│  해시 버킷 엔트리 (Entry)       │
├─────────────────────────────┤
│ 1. 조인 키 값                  │  ← emp_id = 101
│ 2. 필요한 컬럼 데이터            │  ← name, dept_id 등
│ 3. Next 포인터 (체이닝)         │  ← 다음 엔트리 주소
└─────────────────────────────┘

실제 메모리 구조 예시

Build 단계

• Build 단계: employees 테이블 (작은 테이블)

SELECT * FROM employees WHERE dept_id = 10;
-- 예시 쿼리
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 단계에서 생성되는 해시 테이블:

메모리 영역 (PGA - Work Area)
해시 테이블 버킷:

Bucket[0] → NULL

Bucket[1] → [Entry 1] → NULL
            ┌──────────────────────────────┐
            │ emp_id: 101     (조인 키)    │
            │ name: '김철수'   (일반 컬럼)  │
            │ salary: 5000000 (일반 컬럼)  │
            │ next: NULL      (체인 포인터) │
            └──────────────────────────────┘

Bucket[2] → [Entry 2] → [Entry 3] → NULL
            ┌──────────────────┐   ┌──────────────────┐
            │ emp_id: 202      │   │ emp_id: 302      │
            │ name: '이영희'    │   │ name: '박민수'    │
            │ salary: 6000000  │   │ salary: 5500000  │
            │ next: 0x3000     │   │ next: NULL       │
            └──────────────────┘

• 실제 메모리 레이아웃

메모리 주소   | 내용
─────────────┼────────────────────────────
0x1000       | emp_id = 101
0x1004       | name = "김철수" (포인터 또는 인라인)
0x1008       | salary = 5000000
0x100C       | next = NULL
─────────────┼────────────────────────────
0x2000       | emp_id = 202
0x2004       | name = "이영희"
0x2008       | salary = 6000000
0x200C       | next = 0x3000  (다음 엔트리 주소)
─────────────┼────────────────────────────
0x3000       | emp_id = 302
0x3004       | name = "박민수"
0x3008       | salary = 5500000
0x300C       | next = NULL

• Build 과정 상세

# 의사 코드로 표현한 Build 단계

hash_table = Array[BUCKET_SIZE]  # 버킷 배열 초기화

for row in small_table:
    # 1. 해시 값 계산
    hash_value = hash_function(row.join_key)
    bucket_index = hash_value % BUCKET_SIZE
    
    # 2. 엔트리 생성 (실제 데이터 복사)
    entry = {
        'join_key': row.join_key,
        'column1': row.column1,
        'column2': row.column2,
        'next': NULL  # 체인 포인터
    }
    
    # 3. 버킷에 삽입 (체이닝 방식)
    if hash_table[bucket_index] is NULL:
        hash_table[bucket_index] = entry
    else:
        # 충돌 발생 - 체인의 맨 앞에 추가
        entry.next = hash_table[bucket_index]
        hash_table[bucket_index] = entry

Probe 단계

# Probe 단계

for probe_row in large_table:
    # 1. 해시 값 계산
    hash_value = hash_function(probe_row.join_key)
    bucket_index = hash_value % BUCKET_SIZE
    
    # 2. 해당 버킷의 체인을 순회
    entry = hash_table[bucket_index]
    while entry is not NULL:
        # 3. 실제 조인 키 비교 (중요!)
        if entry.join_key == probe_row.join_key:
            # 조인 성공 - 결과 생성
            output(entry.data + probe_row.data)
        
        entry = entry.next  # 체인의 다음 엔트리로

왜 이렇게 설계 되었을까?

1. 디스크 기반 접근 (주소만 저장한다면):
   1. 조인 매칭마다 디스크 I/O 발생
   2. 성능: 매우 느림
2. 메모리 기반 접근 (실제 데이터 저장):
   1. 모든 매칭이 메모리에서 처리
   2. 성능: 매우 빠름 (Hash Join의 장점)

결론 : 해시 버킷 구조의 핵심 포인트

1. 데이터 블럭의 주소만 저장 하나요?

   NO → 실제 행 데이터를 메모리에 복사하여 저장

2. 왜 데이터를 저장하나요?

   Probe 단계에서 디스크 I/O 없이 빠르게 접근하기 위함

3. DB의 어디 영역에 저장하나요?

   저장 위치: PGA의 Work Area (메모리)

4. 해시충돌시 처리방법은?

   체이닝(Chaining) 방식 - 링크드 리스트

5. 메모리 부족 시 에는?

   디스크 임시 테이블스페이스 사용 (성능 저하)

• 따라서 Hash Join은 **작은 테이블 전체를 메모리에 로드**하는 것이 핵심입니다!