데이터베이스(조인 알고리즘)

데이터베이스에서 두 테이블을 조인할 때 내부적으로 사용하는 물리적 실행 방법입니다. 각 알고리즘은 서로 다른 시간복잡도와 성능 특성을 가지며, 데이터베이스 옵티마이저가 데이터 크기와 상황에 맞게 자동으로 선택합니다.

 

중첩 루프 조인 (Nested Loop Join)

 

한 테이블의 각 행에 대해 다른 테이블의 모든 행을 순차적으로 검사하며 조인하는 방법입니다.

for each row in Table A:
    for each row in Table B:
        if A.key = B.key:
            return matched rows

 

 

성능 특성

• 시간복잡도: O(M × N)
• 공간복잡도: O(1) - 추가 메모리 거의 불필요

적합한 상황

-- 소규모 데이터셋 조인
SELECT * 
FROM small_customers c    -- 100행
JOIN small_orders o       -- 200행
ON c.customer_id = o.customer_id;

-- 결과: 100 × 200 = 20,000번 비교 (처리 가능한 수준)

 

특징

• 소규모 데이터셋일 때는 잘 작동
• 테이블 크기가 커질수록 비효율적
• 구현이 단순하고 메모리 사용량이 적음

 

정렬 병합 조인 (Sort Merge Join)

 

두 테이블을 조인할 필드를 기준으로 각각 정렬한 후, 정렬된 순서에 따라 행을 병합하여 조인하는 방법입니다.

과정:
1. Table A를 조인 키로 정렬
2. Table B를 조인 키로 정렬  
3. 두 정렬된 테이블을 병합하며 매칭

정렬된 상태에서 병합:
A: [1, 3, 5, 7, 9]
B: [2, 3, 5, 6, 8]
→ 매칭: (3,3), (5,5)

 

 

성능 특성

• 시간복잡도: O(M log M + N log N)
• 공간복잡도: 정렬을 위한 임시 공간 필요

적합한 상황

• 데이터가 이미 정렬되어 있을 때 더 효율적
• 등가 조인이 아닌 비등가 조인 (대소비교 연산자)에서 효율적
• 인덱스가 조인 키에 있어서 정렬된 상태로 접근 가능한 경우

-- 비등가 조인에서 효율적
SELECT *
FROM employees e
JOIN salary_grades s 
ON e.salary BETWEEN s.min_salary AND s.max_salary;

-- 범위 조건에서 정렬 병합 조인이 유리

 

 

해시 조인 (Hash Join)

 

한 테이블로 해시 테이블을 만든 다음, 다른 테이블을 순회하며 해시 테이블을 사용하여 조인하는 방법입니다.

 

2단계 작동 과정

빌드 단계 (Build Phase)

• 바이트가 더 작은 테이블로부터 해시 테이블을 생성
• 각 행의 조인 키에 해시 함수를 적용하여 해시 테이블에 저장

프로브 단계 (Probe Phase)

• 다른 테이블의 각 행에 대한 조인 키를 해싱
• 앞서 만든 해시값과 비교해서 해시 테이블에서 매칭되는 행을 찾음
• 매칭되는 행들을 조인 결과 테이블에 추가

동작 과정 시각화

빌드 단계 (작은 테이블 A):
Row: (1, 'Alice')  → Hash(1) = 3 → Bucket[3]
Row: (2, 'Bob')    → Hash(2) = 7 → Bucket[7]  
Row: (3, 'Charlie') → Hash(3) = 1 → Bucket[1]

해시 테이블:
Bucket[1]: (3, 'Charlie')
Bucket[3]: (1, 'Alice')  
Bucket[7]: (2, 'Bob')

프로브 단계 (큰 테이블 B):
Row: (1, 'Order1') → Hash(1) = 3 → Bucket[3] 확인 → 매치!
Row: (4, 'Order2') → Hash(4) = 2 → Bucket[2] 확인 → 없음
Row: (2, 'Order3') → Hash(2) = 7 → Bucket[7] 확인 → 매치!

 

 

성능 특성

• 시간복잡도: O(M + N) - 이론적 최적
• 공간복잡도: 작은 테이블 크기만큼 해시 테이블 메모리 필요
• 등가 조인에서 최적: 정확한 일치 조건에서 가장 효율적

 

조인 알고리즘 비교

알고리즘	시간복잡도	공간복잡도	최적 상황
중첩 루프	O(M × N)	O(1)	소규모 데이터
정렬 병합	O(M log M + N log N)	O(M + N)	정렬된 데이터, 비등가 조인
해시	O(M + N)	O(min(M, N))	대용량 데이터, 등가 조인

 

데이터 크기별 선택 기준

• 소규모 (< 1,000행): 중첩 루프 > 해시 > 정렬 병합
• 중간 규모 (1,000 ~ 100,000행): 해시 > 정렬 병합 > 중첩 루프
• 대용량 (> 100,000행): 해시 > 정렬 병합 >> 중첩 루프

⋇조인 알고리즘은 데이터베이스 내부에서 자동으로 선택되지만, 각 알고리즘의 특성을 이해하면 더 효율적인 쿼리 작성과 성능 튜닝에 도움이 됩니다.