HASH 조인

해시 조인(Hash Join)

해시 조인(Hash Join)은 두 개의 테이블을 조인할 때, 더 작은 테이블을 메모리에 올리고 해시 테이블을 만들어 효율적으로 조인하는 방식
대용량 테이블을 조인할 때 주로 사용되며, 조인 조건에 인덱스가 없는 경우에도 빠르게 작동

해시 조인의 원리

해시 조인은 크게 두 단계로 나뉩니다.

빌드 단계 (Build Phase):
1. 옵티마이저는 두 테이블 중 더 작은 테이블(빌드 테이블)을 선택
2. 이 테이블의 조인 키(컬럼)를 사용하여 메모리 기반 해시 테이블을 생성. 각 조인 키 값은 해시 함수의 입력으로 사용되어 해시 테이블의 특정 위치에 저장.
프로브 단계 (Probe Phase):
1. 더 큰 테이블(프로브 테이블)을 순차적으로 읽어옮
2. 프로브 테이블의 각 행에서 조인 키를 추출하여, 빌드 단계에서 사용한 동일한 해시 함수로 해시 값을 계산
3. 계산된 해시 값을 이용해 빌드 테이블의 해시 테이블에서 일치하는 행을 찾음.
4. 일치하는 행을 찾으면, 두 테이블의 행을 결합하여 결과를 반환.

만약 빌드 테이블이 메모리에 다 들어가지 않을 정도로 크다면, 테이블을 여러 개의 파티션으로 나누어 디스크에 임시로 저장한 뒤, 각 파티션별로 빌드와 프로브 단계를 반복하는 '그레이스풀 해시 조인(Graceful Hash Join)'이 수행

파이썬 예제

두 개의 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 단계:
1. Oracle은 먼저 두 테이블 중 더 작은 테이블을 선택하여 빌드 테이블로 지정합니다.
2. 빌드 테이블의 각 행을 읽어 조인 키에 해시 함수를 적용하여 해시 값을 계산합니다.
3. 계산된 해시 값에 해당하는 버킷에 해당 행의 데이터를 저장합니다. 만약 같은 버킷에 이미 다른 데이터가 있다면, 이를 연결 리스트(Linked List) 형태로 연결하여 **해시 충돌(Hash Collision)**을 처리합니다.
Probe 단계:
1. 이제 더 큰 테이블인 프로브 테이블을 순차적으로 읽습니다.
2. 프로브 테이블의 각 행에서 조인 키를 추출하여, 빌드 단계에서 사용한 동일한 해시 함수로 해시 값을 계산합니다.
3. 계산된 해시 값을 이용해 빌드 테이블의 해시 버킷 위치를 즉시 찾아갑니다.
4. 해당 버킷 안의 연결 리스트를 탐색하여 조인 키가 일치하는 행을 찾습니다.
5. 일치하는 행이 발견되면 두 테이블의 데이터를 결합하여 최종 결과를 생성합니다.

이러한 해시 버킷의 활용 덕분에, 해시 조인은 테이블의 크기와 상관없이 조인 키가 같은 데이터들을 O(1)에 가까운 시간 복잡도로 찾아낼 수 있어 대용량 데이터 조인에 매우 효과적입니다.