해시 버킷의 저장구조: 두 판 사이의 차이

2025년 10월 23일 (목) 13:55 기준 최신판

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'

1. 1. **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] ... ```

1. 1. **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

```

1. 5. Hash Collision 처리

1. 1. **충돌 발생 시나리오**

``` hash(dept_id=10) = 1234 → 1234 % 256 = 50 → Bucket #50 hash(dept_id=30) = 5678 → 5678 % 256 = 50 → Bucket #50 ← 충돌! ```

1. 1. **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 값 비교 ```

1. 6. 메모리 관리

1. 1. **저장 위치: PGA**

```sql -- 메모리 할당 우선순위 PGA_AGGREGATE_TARGET (자동 관리)

 └── Work Area
     └── Hash Area
         ├── Bucket Array (포인터 배열)
         └── Hash Entry Pool (실제 데이터)

```

1. 1. **메모리 부족 시: 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; ```

1. 7. 성능 영향 요소

1. 1. **좋은 경우 (O(1) lookup)**

``` ✓ 충분한 메모리 (Optimal execution) ✓ 적절한 bucket 수 (충돌 최소화) ✓ 균등한 hash 분포 ✓ 작은 build input ```

1. 1. **나쁜 경우 (O(n) lookup)**

``` ✗ 메모리 부족 (MultiPass → 디스크 I/O) ✗ Bucket 수 부족 (긴 chain) ✗ 심한 데이터 skew (특정 bucket에 집중) ✗ 큰 build input ```

1. 8. 실무 활용 예시

1. 1. **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';

```

1. 1. **통계 수집 (중요!)**

```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; / ```

1. 1. **힌트 활용**

```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으로 사용 ```

1. 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 단계 에서도 해시버킷이 사용되나?

답변 : 아니요

왜 이렇게 설계 되었을까?

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

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

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

1. 구조 비교

1. 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; ```

1. 메모리 크기 비교

``` 예시: 1024개 bucket, 10000개 entry

Bucket Array: = 1024 buckets × 8 bytes (포인터) = 8 KB (매우 작음!)

Hash Entry Pool: = 10000 entries × 평균 100 bytes (데이터 크기) = 1 MB (실제 데이터 공간이 큼!) ```

1. 동작 과정 상세

1. 1. **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로

```

1. 1. **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  # 매칭 실패

```

1. 실제 예시

```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'] ```

1. 핵심 정리

|항목 |Hash Bucket |Hash Entry | |----------|-------------|------------------| |**역할** |색인 (Index) |실제 데이터 저장소 | |**저장 내용** |포인터 (8 bytes)|Hash값 + Key + Data| |**메모리 크기**|매우 작음 |대부분의 메모리 사용 | |**비유** |책의 목차 |책의 본문 |

- 쉽게 비유하면:**

- **Bucket** = 아파트 동 번호판 (몇 호인지 주소만 표시) - **Entry** = 실제 집 (사람들과 가구가 있는 공간)

Oracle DBA로서 성능 튜닝 시:

- Bucket 수는 메모리에 큰 영향 없음 (포인터만) - Entry Pool 크기가 실제 메모리 사용량 결정 - `v$sql_workarea`에서 보는 메모리는 대부분 Entry Pool 크기입니다!