조인 알고리즘 (Join Algorithms)

SELECT ... FROM 사원 JOIN 부서 ON 사원.부서ID = 부서.ID — SQL은 "두 표를 붙여라"라고만 말한다. 실제로 어떻게 붙일지는 데이터베이스 엔진이 고른다. 같은 결과를 내는 세 가지 대표 방법을 한 칸씩 따라가 보자.

1. 예제 데이터

작은 두 표를 조인한다. 조인 키는 사원.부서ID = 부서.ID. 사원 사랑은 존재하지 않는 부서(4)에 속해 있어 어떤 방법으로도 매칭되지 않는다 — INNER JOIN 결과에서 빠진다.

2. 세 알고리즘 따라가 보기

방식을 고르고 「한 단계 →」를 눌러 진행한다. 주황은 지금 보는 바깥 행, 파랑은 비교 중인 안쪽 행, 초록은 매칭이다.

3. 중첩 루프 조인 (Nested Loop Join)

가장 단순하다. 바깥 표의 모든 행에 대해 안쪽 표를 처음부터 끝까지 훑는다.

for e in 사원:              # 바깥 루프 (R행)
    for d in 부서:          # 안쪽 루프 (S행)
        if e.부서ID == d.ID:   # 매 쌍마다 키 비교
            emit(e, d)

키 비교가 |R| × |S|번 — 여기서는 7×3 = 21번. 표가 각각 10만 행이면 100억 번이다. 단, 안쪽 표의 조인 키에 인덱스가 있으면 "처음부터 끝까지" 대신 인덱스로 바로 찾으므로 |R| × log|S|로 확 줄어든다(Index Nested Loop). 바깥 표가 아주 작을 때 최고의 선택.

4. 해시 조인 (Hash Join)

두 단계로 나뉜다.

1. Build: 더 작은 표(부서)를 한 번 훑어 조인 키 → 행 해시 테이블을 메모리에 만든다.
2. Probe: 큰 표(사원)를 한 번 훑으며 각 행의 키로 해시 테이블을 O(1)로 조회한다.

# 1) build
ht = {}
for d in 부서:
    ht.setdefault(d.ID, []).append(d)
# 2) probe
for e in 사원:
    for d in ht.get(e.부서ID, []):
        emit(e, d)

전체가 O(|R| + |S|). 등가 조인(=)이고 두 표가 클 때 기본 선택지다. 약점: 해시 테이블이 메모리에 안 들어가면 디스크로 나눠 처리(Grace Hash Join)해야 하고, <, BETWEEN 같은 범위 조인에는 못 쓴다.

5. 정렬 병합 조인 (Sort-Merge Join)

두 표를 조인 키로 정렬한 뒤, 두 손가락(포인터)을 나란히 놓고 지퍼처럼 훑는다.

i = j = 0
while i < len(R) and j < len(S):
    if   R[i].key < S[j].key: i += 1
    elif R[i].key > S[j].key: j += 1
    else:                     emit(R[i], S[j]); i += 1

정렬만 되어 있으면 병합은 O(|R| + |S|) 한 번의 스캔. 문제는 정렬 비용 O(n log n)이다. 하지만 조인 키에 B-Tree 인덱스가 있으면 이미 정렬된 순서로 읽을 수 있어 정렬을 건너뛴다 — 이때는 해시 조인보다 빠를 수 있다. ORDER BY 가 뒤따르는 쿼리에도 유리하다.

6. 엔진은 무엇을 기준으로 고를까