편집 요약 없음 |
|||
| 121번째 줄: | 121번째 줄: | ||
{{해시 버킷의 저장구조}} | {{:해시 버킷의 저장구조}} | ||
==== 해시 버킷 개수의 결정 ==== | ==== 해시 버킷 개수의 결정 ==== | ||
2025년 10월 21일 (화) 10:54 판
해시 조인(Hash Join)
해시조인시 사용되는 해시(hash)함수는 입력된 데이터를 '잘게 다져서' 고유하고 일정한 크기의 식별자로 만들어 냄.
- 해시의 주요특징
- 단방향성 : 해시값을 원래의 값으로 되돌릴수 없다.
- 고유성 : 입력값이 바뀌면 해시값은 완전히 달라진다.
- 고정된길이 : 입력값의 크기와 상관없이 항상 동일한 길이의 출력값을 가진다.
* hash의 영문의 뜻 : 잘게 썰다, 다지다의 의미(요리에서 재료를 잘게 썰어서 섞을때 쓰이는말, 예로 맥도날도 '해시브라운(감자를 다져서 튀긴요리)'
- 해시 조인(Hash Join)은 두 개의 테이블을 조인할 때, 더 작은 테이블을 메모리에 올리고 해시 테이블을 만들어 효율적으로 조인하는 방식
- 대용량 테이블을 조인할 때 주로 사용되며, 조인 조건에 인덱스가 없는 경우에도 빠르게 작동
해시 조인의 원리
- 해시 조인은 크게 두 단계로 나뉩니다.
- 빌드 단계 (Build Phase):
- 옵티마이저는 두 테이블 중 더 작은 테이블(빌드 테이블)을 선택
- 이 테이블의 조인 키(컬럼)를 사용하여 PGA 메모리 영역에 해시 테이블을 생성. 각 조인 키 값은 해시 함수를 통하여 해시값으로 변환되어 해시 테이블의 특정 위치에 저장.
- 해시테이블 저장시 변환된 해시값들은 해시버킷의 갯수 만큼 쪼개서 할당되고 "버킷"에 행을 연결리스트(체인) 형태로 저장됨.
- 각 버킷은 "해당 해시 범위에 속하는 행들의 포인터(체인 헤드)" 역활을 하며 , 동일 해시값 이나 충돌이 발생하면 같은 버킷내에서 체인으로 연결됨.(많이 연결될수록 성능 저하,이구간이 성능저하 구간)
- 프로브 단계 (Probe Phase):
- 더 큰 테이블(프로브 테이블)을 순차적으로 읽어옮
- 프로브 테이블의 각 행에서 조인 키를 추출하여, 빌드 단계에서 사용한 동일한 해시 함수로 해시 값을 계산
- 계산된 해시 값을 이용해 빌드 테이블의 해시 테이블에서 일치하는 행을 찾음.(대상 버킷을 찾고 해당 버킷의 체인을 스캔하여 조인키를 비교)
- 일치하는 행을 찾으면, 두 테이블의 행을 결합하여 결과를 반환.
- 만약 빌드 테이블이 PGA 메모리에 다 들어가지 않을 정도로 크다면, 테이블을 여러 개의 파티션으로 나누어 디스크에 임시로 저장한 뒤(성능 저하 구간), 각 파티션별로 빌드와 프로브 단계를 반복하는 '그레이스풀 해시 조인(Graceful Hash Join)'이 수행(성능저하 구간)
- 런타임 파티셔닝을 수행해 부분(배치/파티션) 단위로 템프에 내린 후(DISK I/O발생,성능저하) 다시 합쳐서 1-pass/멀티패스 방식으로 진행함.
파이썬 예제
- 두 개의 CSV 파일 sales.csv와 products.csv가 있다고 가정하고, 이를 파이썬 딕셔너리로 해시 조인을 구현하는 예제.
1. 데이터 준비 (sales.csv, products.csv 파일)
1) 대량 테이블 - 판매(sales.csv 파일)
sale_id,product_id,amount 1,101,100 2,102,150 3,101,200 4,103,50 .... ....
2) 제품 (products.csv)
product_id,product_name 101,Laptop 102,Mouse 103,Keyboard
2. 해시 조인 구현 코드
소량인 products 테이블을 빌드 테이블로, sales 테이블을 프로브 테이블로 사용하여 조인을 수행.
import csv
# 1. 빌드 테이블: products.csv를 읽어 메모리 해시 테이블(딕셔너리) 생성
# 'product_id'를 키로, 'product_name'을 값으로 저장
products_hash_table = {}
with open('products.csv', 'r') as f:
reader = csv.DictReader(f)
for row in reader:
# 해시 테이블 생성 (딕셔너리)
products_hash_table[row['product_id']] = row['product_name']
print("--- 빌드 단계 (해시 테이블) ---")
print(products_hash_table)
# 출력: {'101': 'Laptop', '102': 'Mouse', '103': 'Keyboard'}
print("\n--- 프로브 단계 (조인 결과) ---")
# 2. 프로브 테이블: sales.csv를 읽어 해시 테이블에서 찾기
with open('sales.csv', 'r') as f:
reader = csv.DictReader(f)
for row in reader:
# sale_id 3의 'product_id'인 '101'을 해시 테이블에서 찾음
product_id = row['product_id']
if product_id in products_hash_table:
# 해시 테이블에서 'product_id'를 키로 검색하여 'product_name'을 가져옴
product_name = products_hash_table[product_id]
print(f"Sale ID: {row['sale_id']}, Product Name: {product_name}, Amount: {row['amount']}")
- 예상 출력:
# Sale ID: 1, Product Name: Laptop, Amount: 100 # Sale ID: 2, Product Name: Mouse, Amount: 150 # Sale ID: 3, Product Name: Laptop, Amount: 200 # Sale ID: 4, Product Name: Keyboard, Amount: 50
- products_hash_table이라는 딕셔너리가 바로 해시 테이블 역할을 합니다.
- sales 테이블의 각 행을 읽을 때마다 product_id를 딕셔너리(해시 테이블)에서 빠르게 찾아 product_name을 가져와 조인된 결과를 출력하는 방식
- 이를 통해 전체 products 테이블을 다시 스캔할 필요 없이 O(1)에 가까운 시간 복잡도로 조인 조건을 만족하는 데이터를 찾을 수 있음.
HASH 조인의 성능 향상 원리
Hash 버킷의 역할과 기능
- 해시 버킷은 두 테이블을 효율적으로 조인하기 위한 핵심적인 논리적 저장 공간.
- 이는 조인 키(Join Key)를 기반으로 데이터를 빠르게 찾고 저장하는 데 사용.
역할: 데이터의 논리적 분류 및 저장소
- 해시 버킷은 조인 키 값을 해시 함수에 넣어 얻은 해시 값이 같은 데이터들을 모아두는 공간.
- 이는 거대한 데이터를 조인 키를 기준으로 더 작은 그룹으로 나누어 관리하는 역할을 합니다.
- 이를 통해 빌드 테이블의 모든 데이터를 일일이 탐색하지 않고도, 특정 조인 키에 해당하는 데이터가 어느 버킷에 있는지 바로 알 수 있습니다.
기능: Build 단계와 Probe 단계에서의 활용
- Build 단계:
- Oracle은 먼저 두 테이블 중 더 작은 테이블을 선택하여 빌드 테이블로 지정합니다.
- 빌드 테이블의 각 행을 읽어 조인 키에 해시 함수를 적용하여 해시 값을 계산합니다.
- 계산된 해시 값에 해당하는 버킷에 해당 행의 데이터를 저장합니다. 만약 같은 버킷에 이미 다른 데이터가 있다면, 이를 연결 리스트(Linked List) 형태로 연결하여 **해시 충돌(Hash Collision)**을 처리합니다.
- Probe 단계:
- 이제 더 큰 테이블인 프로브 테이블을 순차적으로 읽습니다.
- 프로브 테이블의 각 행에서 조인 키를 추출하여, 빌드 단계에서 사용한 동일한 해시 함수로 해시 값을 계산합니다.
- 계산된 해시 값을 이용해 빌드 테이블의 해시 버킷 위치를 즉시 찾아갑니다.
- 해당 버킷 안의 연결 리스트를 탐색하여 조인 키가 일치하는 행을 찾습니다.
- 일치하는 행이 발견되면 두 테이블의 데이터를 결합하여 최종 결과를 생성합니다.
- 이러한 해시 버킷의 활용 덕분에, 해시 조인은 테이블의 크기와 상관없이 조인 키가 같은 데이터들을 O(1)에 가까운 시간 복잡도로 찾아낼 수 있어 대용량 데이터 조인에 매우 효과적입니다.
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 Table (PGA Memory) │ ├─────────────────────────────────────────────────────────┤ │ │ │ [Bucket Array - 포인터만 저장] │ │ ┌──────┬──────────┐ │ │ │ #0 │ NULL │ │ │ ├──────┼──────────┤ │ │ │ #1 │ 0x1000 ──┼──┐ │ │ ├──────┼──────────┤ │ │ │ │ #2 │ NULL │ │ │ │ ├──────┼──────────┤ │ │ │ │ #3 │ 0x2000 ──┼──┼──┐ │ │ └──────┴──────────┘ │ │ │ │ │ │ │ │ [Hash Entry Pool - 실제 데이터 저장] │ │ │ │ │ │ ┌──────────────────┐ │ │ │ │ │ 0x1000 주소 │←┘ │ │ │ ├──────────────────┤ │ │ │ │ Hash: 1234 │ │ │ │ │ Next: 0x1100 ────┼──┐ │ │ │ │ Key: 10 │ │ │ │ │ │ Data: 'Sales' │ │ │ │ │ └──────────────────┘ │ │ │ │ │ │ │ │ ┌──────────────────┐ │ │ │ │ │ 0x1100 주소 │←─┘ │ │ │ ├──────────────────┤ │ │ │ │ Hash: 5678 │ │ │ │ │ Next: NULL │ │ │ │ │ Key: 30 │ │ │ │ │ Data: 'IT' │ │ │ │ └──────────────────┘ │ │ │ │ │ │ ┌──────────────────┐ │ │ │ │ 0x2000 주소 │←───┘ │ │ ├──────────────────┤ │ │ │ Hash: 9012 │ │ │ │ Next: NULL │ │ │ │ Key: 20 │ │ │ │ Data: 'HR' │ │ │ └──────────────────┘ │ │ │ └─────────────────────────────────────────────────────────┘
해시 버킷 (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 접근
- 해시 버킷의 저장 구조
해시 버킷에 저장되는 내용
- Hash Bucket (Pointer Array)
- Hash Bucket은 Hash Entry의 주소(포인터)만 가지고 있습니다.
- 단순한 포인터 배열
Bucket[0] → 0x00000000 (NULL, 비어있음) Bucket[1] → 0x7F8A3C00 (Entry 시작 주소) Bucket[2] → 0x00000000 (NULL, 비어있음) Bucket[3] → 0x7F8A4D20 (Entry 시작 주소) ... 각 bucket = 8 bytes (포인터 크기)
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에 필요한 컬럼들 +---------------------------+
- Hash Entry (Actual Data)
- 실제 데이터를 담는 구조체
메모리 주소: 0x7F8A3C00 +---------------------------+ | Hash Value: 1234 | 4-8 bytes | Next Pointer: 0x7F8A3C40 | 8 bytes (다음 entry) | Join Key: dept_id = 10 | 가변 크기 | Row Data: 'Sales', ... | 가변 크기 +---------------------------+ 메모리 주소: 0x7F8A3C40 +---------------------------+ | Hash Value: 5678 | | Next Pointer: NULL | | Join Key: dept_id = 20 | | Row Data: 'Marketing',... | +---------------------------+
Entry 저장 정보 예시
-- 쿼리 예시
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'
- **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) 방식 - 링크드 리스트
- 메모리 부족 시 에는?
- 디스크 임시 테이블스페이스 사용 (성능 저하)
- 구조 비교
- C 언어 스타일 구조체로 설명
```c // Hash Bucket (포인터 배열) typedef struct {
HashEntry* head; // 8 bytes (포인터만!)
} HashBucket;
// Hash Entry (실제 데이터) typedef struct HashEntry {
uint32_t hash_value; // 4 bytes struct HashEntry* next; // 8 bytes (다음 entry 포인터) void* join_key; // 가변 크기 (실제 join key 값) void* row_data; // 가변 크기 (실제 row 데이터)
} HashEntry;
// Hash Table typedef struct {
uint32_t bucket_count; // bucket 개수 HashBucket* buckets; // bucket 배열 (포인터만!) HashEntry* entry_pool; // entry 저장 공간 (실제 데이터!)
} HashTable; ```
- 메모리 크기 비교
``` 예시: 1024개 bucket, 10000개 entry
Bucket Array: = 1024 buckets × 8 bytes (포인터) = 8 KB (매우 작음!)
Hash Entry Pool: = 10000 entries × 평균 100 bytes (데이터 크기) = 1 MB (실제 데이터 공간이 큼!) ```
- 동작 과정 상세
- **1. Build Phase - Entry 추가**
```python
- 의사 코드
def insert_entry(join_key, row_data):
# 1. Hash 계산 hash_value = hash_function(join_key) bucket_index = hash_value % bucket_count # 2. 새 Entry 생성 (실제 데이터 저장) new_entry = HashEntry() new_entry.hash_value = hash_value new_entry.join_key = join_key # 실제 값 new_entry.row_data = row_data # 실제 데이터 new_entry.next = NULL # 3. Bucket의 chain 맨 앞에 추가 new_entry.next = buckets[bucket_index].head # 기존 head buckets[bucket_index].head = new_entry # 새 entry를 head로
```
- **2. Probe Phase - Entry 검색**
```python def probe_entry(probe_key):
# 1. Hash 계산으로 bucket 찾기
hash_value = hash_function(probe_key)
bucket_index = hash_value % bucket_count
# 2. Bucket에서 시작 포인터 가져오기
current_entry = buckets[bucket_index].head # 포인터!
# 3. Chain 순회 (실제 데이터 비교)
while current_entry != NULL:
if current_entry.hash_value == hash_value: # 1차 필터
if current_entry.join_key == probe_key: # 2차 비교 (실제 값!)
return current_entry.row_data # 매칭 성공
current_entry = current_entry.next # 다음 entry로
return NULL # 매칭 실패
```
- 실제 예시
```sql -- 테이블 departments: dept_id(10, 20, 30)
-- Hash Table 생성 (bucket_count = 4) ```
- Build 후 상태:**
``` Bucket Array (포인터만): [0] → NULL [1] → 0xA000 (dept_id=10의 entry 주소) [2] → 0xB000 (dept_id=20의 entry 주소) [3] → 0xC000 (dept_id=30의 entry 주소)
Entry Pool (실제 데이터): 주소 0xA000: [hash=1, next=NULL, key=10, data='Sales'] 주소 0xB000: [hash=2, next=NULL, key=20, data='HR'] 주소 0xC000: [hash=3, next=NULL, key=30, data='IT'] ```
- Collision 발생 시:**
``` dept_id=10: hash % 4 = 1 → Bucket[1] dept_id=50: hash % 4 = 1 → Bucket[1] (충돌!)
Bucket Array: [1] → 0xA000 (첫 번째 entry 주소)
Entry Pool: 주소 0xA000: [hash=X, next=0xD000, key=10, data='Sales']
↓
주소 0xD000: [hash=Y, next=NULL, key=50, data='Finance'] ```
- 핵심 정리
|항목 |Hash Bucket |Hash Entry | |----------|-------------|------------------| |**역할** |색인 (Index) |실제 데이터 저장소 | |**저장 내용** |포인터 (8 bytes)|Hash값 + Key + Data| |**메모리 크기**|매우 작음 |대부분의 메모리 사용 | |**비유** |책의 목차 |책의 본문 |
- 쉽게 비유하면:**
- **Bucket** = 아파트 동 번호판 (몇 호인지 주소만 표시) - **Entry** = 실제 집 (사람들과 가구가 있는 공간)
Oracle DBA로서 성능 튜닝 시:
- Bucket 수는 메모리에 큰 영향 없음 (포인터만) - Entry Pool 크기가 실제 메모리 사용량 결정 - `v$sql_workarea`에서 보는 메모리는 대부분 Entry Pool 크기입니다!
해시 버킷 개수의 결정
- 해시 조인의 최대 해시 버킷 개수는 사전 설정된 고정값이 아니라, 조인하려는 테이블의 크기, 옵티마이저의 예측, 그리고 PGA_AGGREGATE_TARGET 파라미터에 의해 동적으로 결정
- 빌드 테이블(Build Table)의 크기: 옵티마이저가 예측한 더 작은 테이블(빌드 테이블)의 크기에 따라 필요한 해시 버킷의 수가 결정됨
- 할당된 PGA 메모리: PGA_AGGREGATE_TARGET에 의해 세션에 할당된 PGA 메모리 내에서 해시 테이블이 생성됨.
- 메모리 부족 시: 만약 할당된 PGA 메모리만으로 해시 테이블을 모두 생성할 수 없다면, Oracle은 일부 해시 버킷을 디스크의 임시 테이블스페이스(temp tablespace)로 분할하여 저장합니다.
- 이를 '해시 스필(Hash Spill)'이라고 부르며, 이 경우 I/O가 발생하여 성능이 저하됨.
HASH 조인이 느려지는 원인
- 해시 조인 성능이 느려지는 주요 원인 중 하나는 해시 버킷 때문입니다.
- 정확히 말하면, 해시 충돌이 심하게 발생하거나 해시 테이블이 메모리에 맞지 않아 디스크 I/O가 발생하는 경우입니다.
- 해시 버킷 자체는 효율성을 위한 도구지만, 비정상적인 상황에서는 오히려 성능 저하의 원인이 됩니다.
1. 해시 충돌 (Hash Collisions)
- 원리: 해시 함수는 조인 키가 다르더라도 동일한 해시 값을 반환할 수 있습니다. 이것이 해시 충돌입니다.
- 문제점: 해시 충돌이 발생하면, 하나의 버킷에 여러 행이 연결 리스트 형태로 쌓이게 됩니다. 이 버킷을 탐색할 때, 원하는 데이터를 찾기 위해 연결된 모든 데이터를 순차적으로 비교해야 하므로, 탐색 시간이 O(1)에서 O(N)으로 늘어납니다.
- 결과: 조인 키 데이터 분포가 불균형하거나(데이터 편중), 해시 함수가 비효율적이면 해시 충돌이 자주 발생하여 성능이 크게 저하됩니다.
- (결론) 해시조인은 조인키로 사용되는 컬럼이 중복이 많을수록 성능이 좋지 않음
- 파이썬으로 해시 충돌 구현 예제
- 고의로 해시 충돌을 유발하는 데이터를 사용하여 해시 조인의 성능 차이를 보여줍니다.
- products_collision 리스트의 모든 product_id는 해시 함수를 거치면 같은 값을 반환하도록 설계되었습니다.
import time
# 일반적인 데이터 (해시 충돌이 거의 없음)
products_normal = [
{'product_id': 101, 'product_name': 'Laptop'},
{'product_id': 102, 'product_name': 'Mouse'},
{'product_id': 103, 'product_name': 'Keyboard'},
]
# 의도적으로 해시 충돌을 유발하는 데이터
# 101, 201, 301 모두 100으로 나눈 나머지가 1이 되도록 설계
products_collision = [
{'product_id': 101, 'product_name': 'Laptop'},
{'product_id': 201, 'product_name': 'Mouse'},
{'product_id': 301, 'product_name': 'Keyboard'},
]
# 조인 대상 데이터 (각 product_id에 대한 sales 데이터)
sales = [{'sale_id': i, 'product_id': 101, 'amount': 100} for i in range(1000)] + \
[{'sale_id': i+1000, 'product_id': 201, 'amount': 150} for i in range(1000)] + \
[{'sale_id': i+2000, 'product_id': 301, 'amount': 200} for i in range(1000)]
# 사용자 정의 해시 함수 (단순화를 위해)
def custom_hash(key):
return key % 100
def hash_join(build_table, probe_table):
# 빌드 단계: 해시 버킷(딕셔너리) 생성
# 파이썬 딕셔너리의 키 충돌을 구현하기 위해, 딕셔너리의 값을 리스트로 저장
hash_buckets = {}
for item in build_table:
key = item['product_id']
bucket_index = custom_hash(key)
if bucket_index not in hash_buckets:
hash_buckets[bucket_index] = []
hash_buckets[bucket_index].append(item)
# 프로브 단계: 조인
start_time = time.time()
joined_results = []
for sale in probe_table:
key = sale['product_id']
bucket_index = custom_hash(key)
# 해시 버킷에서 일치하는 데이터를 찾기 (충돌 발생 시 순차 탐색)
if bucket_index in hash_buckets:
for product_info in hash_buckets[bucket_index]:
if product_info['product_id'] == key:
joined_results.append({**sale, **product_info}) # **은 언패킹연산자 {**A,**B} 는 A,B딕셔너리를 합쳐줌.
break
end_time = time.time()
return end_time - start_time
# 일반적인 데이터로 조인
normal_time = hash_join(products_normal, sales)
# 해시 충돌 데이터로 조인
collision_time = hash_join(products_collision, sales)
print(f"일반 데이터 조인 시간: {normal_time:.6f} 초")
print(f"해시 충돌 조인 시간: {collision_time:.6f} 초")
print(f"성능 저하 비율: {(collision_time / normal_time):.2f}배 느림")
일반 데이터 조인 시간: 0.000971 초 해시 충돌 조인 시간: 0.001568 초 성능 저하 비율: 1.61배 느림
2. 메모리 부족 및 디스크 I/O
- 원리: 해시 조인은 더 작은 테이블(빌드 테이블)을 메모리에 올려 해시 테이블을 만드는 것이 기본 전제입니다.
- 문제점: 빌드 테이블이 너무 커서 **메모리(PGA)**에 다 담을 수 없게 되면, Oracle은 해시 테이블을 여러 파티션으로 나누어 일부를 **임시 테이블스페이스(Temporary Tablespace)**에 저장합니다.
- 결과: 조인을 수행하기 위해 디스크에 기록된 파티션 데이터를 읽고 쓰는 디스크 I/O 작업이 반복적으로 발생합니다. 이는 메모리에서만 작업할 때보다 훨씬 느리므로 성능 저하의 결정적인 원인이 됩니다.
HASH 조인에 대한 의문점
- hash join에서 해시 함수는 조인 키가 다르더라도 동일한 해시 값을 반환할 수 있습니다. 이것이 해시 충돌입니다.
- 또한 조인키로 사용되는 컬럼이 중복이 많을수록 성능이 좋지 않습니다.
- 그러면 조인키로 사용되는 컬럼의 값 이 중복이 심하면 성능 않좋아 진다는것인가?
- 아니면 해시함수를 통하여 생성된 해시값이 동일한경우에 성능이 않좋아 진다는 것인가?
- 둘다 해당한다는것인가?
- 둘 다 성능에 영향을 미치지만, 서로 다른 이유이며 실무에서는 1번이 훨씬 더 큰 문제입니다.
조인 키 값의 중복 (더 흔한 문제)
- 조인 키 컬럼 자체의 중복이 많으면 성능이 나빠집니다.
-- 예시: 성별 컬럼으로 조인 (값이 'M', 'F' 두 개뿐) SELECT /*+ USE_HASH(a b) */ * FROM employees a JOIN customers b ON a.gender = b.gender
- 문제점:
- - `gender = 'M'` 인 행들이 모두 같은 해시 버킷에 저장됨
- - Probe 단계에서 해당 버킷의 수많은 행들을 일일이 비교해야 함
- - 해시 조인의 장점(O(1) 검색)이 사라짐
해시 충돌 (드문 문제)
- 서로 다른 조인 키 값이 우연히 같은 해시 값을 생성하는 경우입니다.
# 예시 (실제는 아니지만 개념 설명)
hash('emp_id_12345') = 789 # 해시값 789
hash('emp_id_99999') = 789 # 다른 키인데 같은 해시값!
- 문제점:
- - 서로 다른 키인데 같은 버킷에 저장됨
- - 역시 Probe 시 추가 비교 필요
실제 상황 비교
-- 시나리오 A: 카디널리티 낮음 (중복 많음) - 실제 큰 문제
employees: 1,000,000명
성별(gender)컬럼 값: 남자('M'), 여자('F') 두 개만
→ 각 버킷에 약 500,000개 행 저장
→ 성능 매우 나쁨
-- 시나리오 B: 카디널리티 높음 (중복 적음) - 좋음
employees: 1,000,000명
employee_id: 1,000,000개 유니크 값
→ 각 버킷에 평균 1~2개 행
→ 해시 충돌 있어도 영향 미미
→ 성능 좋음
- 결론
- - 조인 키 중복 문제 : 실무에서 흔하고 심각한 성능 저하 원인
- - 해시 충돌 문제 : Oracle의 해시 함수가 잘 설계되어 있어 드물게 발생
- - **실무 팁**: 조인 키는 **카디널리티가 높은 컬럼**(예: ID, 주문번호)을 사용해야 함
성별, 부서코드(10개 정도) 같은 낮은 카디널리티 컬럼으로 Hash Join하면 성능이 매우 나빠집니다!
결론
- 해시 조인이 효율적으로 작동하는 것은 해시 버킷이 잘 분산되어 있고, 해시 테이블이 메모리에서 모두 처리될 때입니다. 만약 데이터가 한쪽으로 치우쳐 해시 충돌이 심하거나, 메모리 부족으로 디스크 I/O가 발생하면 해시 조인의 장점이 사라져 성능이 느려지게 됩니다.
HASH 조인의 장/단점
장점
- 대용량 테이블간 "=" 조건의 조인에 적합(정렬 불필요,입력 순서 무관)
- 빠른 접근 가능(버킷을 이용한 빠른 처리)
- 병렬처리에 적합하면 효율성이 좋음
단점
- "=" 조건에만 적합, 범위 조건(between 이나 like) 조인은 사용할수 없음.
- 메모리에 의존적임(빌드테이블이 메모리내에 들어가지 못하면 템프 i/o가 발생)
- 조인키값이 한쪽에 치우치거나(skew),중복도가 높으면 특정 버킷에 연결된 버킷이 길어져 탐색하는 시간이 증가함(CPU사용량 급증, 충돌증가)
- 버킷수가 데이터 대비 부족하면 충돌 발생과 체인 길이가 늘어 탐색 비용이 증가함