Oracle Hash Join의 해시테이블 내부 구조
전체 구조 개요
Hash Table (PGA Memory)
├── Bucket Array (해시 테이블의 배열)
│ ├── Bucket #0 → Hash Entry Chain
│ ├── Bucket #1 → Hash Entry Chain
│ ├── Bucket #2 → Hash Entry Chain
│ ├── ...
│ └── Bucket #N → Hash Entry Chain
│
└── Hash Entry Pool (실제 데이터 저장 영역)
├── Entry1 [hash, key, data, next*]
├── Entry2 [hash, key, data, next*]
└── ...
해시 버킷 (Hash Bucket)
- Bucket이란?
- - Hash Table을 구성하는 **논리적 슬롯(Slot)**
- - 포인터 배열로 구현됨
- - 각 bucket은 hash entry chain의 **시작점(head pointer)**를 가리킴
Bucket 개수 결정
Bucket 수 = 2의 거듭제곱 (예: 256, 512, 1024, 2048...)
- Oracle이 자동 계산:
- - Build input의 cardinality
- - 사용 가능한 메모리
- - 통계 정보 (NUM_ROWS, NUM_DISTINCT)
Bucket 선택 방식
# 의사 코드 hash_value = hash_function(join_key) bucket_number = hash_value % bucket_count # 또는 비트 마스킹 bucket[bucket_number] # 해당 bucket 접근
- 해시 버킷의 저장 구조
해시 버킷에 저장되는 내용
- 해시 버킷에는 주소 정보가 아닌 실제 데이터 행(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 ...
Hash Entry
- **Entry 구성 요소**
``` +---------------------------+ | Hash Entry Structure | +---------------------------+ | 1. Hash Value (4-8 bytes) | ← 해시함수 결과값 | 2. Next Pointer (8 bytes) | ← 다음 entry 주소 (chaining) | 3. Join Key Value(s) | ← 실제 join 컬럼 원본값 | 4. Row Data | ← SELECT에 필요한 컬럼들 +---------------------------+ ```
- **Entry 저장 정보 예시**
```sql -- 쿼리 예시 SELECT e.emp_id, e.name, d.dept_name FROM employees e, departments d WHERE e.dept_id = d.dept_id;
-- departments (작은 테이블) → Build Input -- employees (큰 테이블) → Probe Input ```
- Hash Entry 내용:**
``` Entry for dept_id = 10: - Hash Value: 2348756 (hash 함수 결과) - Next Pointer: 0x7F8A3C (다음 entry 주소 또는 NULL) - Join Key: dept_id = 10 (원본값) - Row Data: dept_name = 'Sales', location = 'Seoul' ```
- 4. Hash Join 전체 프로세스
- **Phase 1: Build Phase**
``` 1. 작은 테이블(Build Input) 읽기
↓
2. 각 row에 대해:
hash_value = hash(join_key) bucket_num = hash_value % bucket_count ↓
3. Hash Entry 생성:
- Hash value 저장 - Join key 원본값 저장 - 필요한 컬럼 데이터 저장 ↓
4. 해당 bucket의 chain에 추가 (linked list) ```
- 메모리 구조:**
``` Bucket Array Hash Entry Pool [0] → NULL [1] → Entry_A ─────→ [Hash:1234, Key:10, Data:..., Next→Entry_B] [2] → Entry_C ↓ [3] → NULL [Hash:5678, Key:20, Data:..., Next:NULL] ... ```
- **Phase 2: Probe Phase**
``` 1. 큰 테이블(Probe Input) 읽기
↓
2. 각 row에 대해:
hash_value = hash(join_key) bucket_num = hash_value % bucket_count ↓
3. 해당 bucket의 chain을 순회:
entry = bucket[bucket_num]
while entry != NULL:
if entry.hash_value == hash_value: # 1차 비교 (빠름)
if entry.join_key == probe_key: # 2차 비교 (정확)
→ JOIN 성공, 결과 반환
entry = entry.next
```
- 5. Hash Collision 처리
- **충돌 발생 시나리오**
``` hash(dept_id=10) = 1234 → 1234 % 256 = 50 → Bucket #50 hash(dept_id=30) = 5678 → 5678 % 256 = 50 → Bucket #50 ← 충돌! ```
- **Chaining으로 해결**
``` Bucket #50
↓
[Entry1: hash=1234, key=10, next→]
↓
[Entry2: hash=5678, key=30, next→]
↓
[Entry3: hash=9012, key=70, next=NULL]
Probe 시: Chain을 순차 탐색하며 실제 key 값 비교 ```
- 6. 메모리 관리
- **저장 위치: PGA**
```sql -- 메모리 할당 우선순위 PGA_AGGREGATE_TARGET (자동 관리)
└── Work Area
└── Hash Area
├── Bucket Array (포인터 배열)
└── Hash Entry Pool (실제 데이터)
```
- **메모리 부족 시: Temp Spill**
``` Optimal: 전체 hash table이 메모리에 fit
↓
OnePass: 일부 partition이 디스크로 (1회 읽기)
↓
MultiPass: 여러 partition이 디스크로 (여러 번 읽기) ← 성능 저하! ```
- 확인 방법:**
```sql SELECT sql_id, operation_type,
estimated_optimal_size/1024/1024 as optimal_mb,
estimated_onepass_size/1024/1024 as onepass_mb,
last_memory_used/1024/1024 as used_mb,
last_execution,
CASE
WHEN last_memory_used < estimated_onepass_size THEN 'MultiPass'
WHEN last_memory_used < estimated_optimal_size THEN 'OnePass'
ELSE 'Optimal'
END as execution_type
FROM v$sql_workarea WHERE operation_type = 'HASH-JOIN' ORDER BY last_execution DESC; ```
- 7. 성능 영향 요소
- **좋은 경우 (O(1) lookup)**
``` ✓ 충분한 메모리 (Optimal execution) ✓ 적절한 bucket 수 (충돌 최소화) ✓ 균등한 hash 분포 ✓ 작은 build input ```
- **나쁜 경우 (O(n) lookup)**
``` ✗ 메모리 부족 (MultiPass → 디스크 I/O) ✗ Bucket 수 부족 (긴 chain) ✗ 심한 데이터 skew (특정 bucket에 집중) ✗ 큰 build input ```
- 8. 실무 활용 예시
- **Hash Join 모니터링**
```sql -- 현재 실행 중인 hash join 확인 SELECT s.sid, s.serial#, s.username,
w.operation_type, w.policy,
w.work_area_size/1024/1024 as workarea_mb,
w.expected_size/1024/1024 as expected_mb
FROM v$sql_workarea_active w, v$session s WHERE w.sid = s.sid
AND w.operation_type = 'HASH-JOIN';
```
- **통계 수집 (중요!)**
```sql -- Hash join 성능은 통계 정확도에 크게 의존 BEGIN
DBMS_STATS.GATHER_TABLE_STATS( ownname => 'SCOTT', tabname => 'EMPLOYEES', estimate_percent => DBMS_STATS.AUTO_SAMPLE_SIZE, method_opt => 'FOR ALL COLUMNS SIZE AUTO' );
END; / ```
- **힌트 활용**
```sql -- Hash join 강제 + build input 지정 SELECT /*+ USE_HASH(e d) SWAP_JOIN_INPUTS(d) */
e.emp_id, d.dept_name
FROM employees e, departments d WHERE e.dept_id = d.dept_id;
-- SWAP_JOIN_INPUTS: departments를 build input으로 사용 ```
- 9. 핵심 정리
|구성요소 |역할 |저장 내용 | |--------------|------|--------------------------------| |**Hash Table**|전체 구조 |PGA 메모리에 생성 | |**Bucket** |논리적 슬롯|Entry chain의 head pointer | |**Hash Entry**|실제 데이터|Hash value + Join key + Row data| |**Chain** |충돌 해결 |Linked list로 같은 bucket의 entry 연결|
- 핵심 원리:**
- Hash value로 **빠르게 bucket 찾기** (O(1)) - 원본 key 값으로 **정확한 매칭** (충돌 해결) - Chaining으로 **여러 entry 관리** - PGA 메모리 활용으로 **빠른 접근**
DBA 업무 시 hash join 성능 문제가 있다면 통계 정보, PGA 메모리 설정, 그리고 build input 크기를 먼저 확인하시는 것이 좋습니다!
실제 메모리 구조 예시
Build 단계
- Build 단계: employees 테이블 (작은 테이블)
-- 예시 쿼리
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 # 체인의 다음 엔트리로
Probe 단계 에서도 해시버킷이 사용되나?
답변 : 아니요
왜 이렇게 설계 되었을까?
- 디스크 기반 접근 (주소만 저장한다면):
- 조인 매칭마다 디스크 I/O 발생
- 성능: 매우 느림
- 메모리 기반 접근 (실제 데이터 저장):
- 모든 매칭이 메모리에서 처리
- 성능: 매우 빠름 (Hash Join의 장점)
결론 : 해시 버킷 구조의 핵심 포인트
- 데이터 블럭의 주소만 저장 하나요?
- NO → 실제 행 데이터를 메모리에 복사하여 저장
- 왜 데이터를 저장하나요?
- Probe 단계에서 디스크 I/O 없이 빠르게 접근하기 위함
- DB의 어디 영역에 저장하나요?
- 저장 위치: PGA의 Work Area (메모리)
- 해시충돌시 처리방법은?
- 체이닝(Chaining) 방식 - 링크드 리스트
- 메모리 부족 시 에는?
- 디스크 임시 테이블스페이스 사용 (성능 저하)
- 따라서 Hash Join은 **작은 테이블 전체를 메모리에 로드**하는 것이 핵심입니다!