해시 버킷의 저장구조

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;

Build 단계에서 생성되는 해시 테이블:

메모리 영역 (PGA - Work Area)
├─ 해시 버킷 배열 (포인터 배열)
│  [0] → 0x1000  (첫 번째 엔트리 주소)
│  [1] → NULL
│  [2] → 0x2000
│  [3] → 0x3000 → 0x3100  (충돌 발생, 체인)
│  ...
│
└─ 실제 데이터 영역
   0x1000: {emp_id: 101, name: '김철수', dept_id: 10, next: NULL}
   0x2000: {emp_id: 202, name: '박민수', dept_id: 20, next: NULL}
   0x3000: {emp_id: 303, name: '정수진', dept_id: 30, next: 0x3100}
   0x3100: {emp_id: 403, name: '최지원', dept_id: 30, 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. 조인 매칭마다 디스크 I/O 발생
2. 성능: 매우 느림
메모리 기반 접근 (실제 데이터 저장):
1. 모든 매칭이 메모리에서 처리
2. 성능: 매우 빠름 (Hash Join의 장점)

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

데이터 블럭의 주소만 저장 하나요?
NO → 실제 행 데이터를 메모리에 복사하여 저장
왜 데이터를 저장하나요?
Probe 단계에서 디스크 I/O 없이 빠르게 접근하기 위함
DB의 어디 영역에 저장하나요?
저장 위치: PGA의 Work Area (메모리)
해시충돌시 처리방법은?
체이닝(Chaining) 방식 - 링크드 리스트
메모리 부족 시 에는?
디스크 임시 테이블스페이스 사용 (성능 저하)

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