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)에 가까운 시간 복잡도로 조인 조건을 만족하는 데이터를 찾을 수 있음.