1. 중첩 루프 조인 (Nested Loop Join)
작동 방식:
-
외부 테이블의 각 튜플마다 내부 테이블을 스캔하여 조건에 맞는 튜플을 찾는 방식.
-
두 테이블 간의 이중 루프 구조로 작동:
for each row R in outer_table: for each row S in inner_table: if R.key = S.key: output R, S
특징:
- 가장 단순하고 범용적인 조인 방식.
- 인덱스가 있을 경우 효율적 (특히 소규모 + 인덱스 기반 접근).
- 테이블 간의 조인 조건이 복잡하거나 인덱스를 사용할 수 있는 경우 유리.
성능 분석:
- 최악의 경우 O(N * M)의 시간 복잡도.
- 인덱스가 없다면 대량 데이터에서 비효율적.
- 옵티마이저는 작은 외부 테이블 + 인덱스가 있는 내부 테이블 구조에서 선호.
2. 병합 조인 (Merge Join)
작동 방식:
-
양 테이블 모두 조인 키 기준으로 정렬되어 있어야 함.
-
정렬된 데이터를 병합하듯이 순차적으로 조인:
while not end of outer and inner: if outer.key < inner.key: advance outer elif outer.key > inner.key: advance inner else: output all matching pairs
특징:
- 사전 정렬이 필수 (정렬 비용이 발생할 수 있음).
- 정렬된 데이터라면 매우 빠른 조인 가능.
- 대량의 데이터 처리에 효과적.
성능 분석:
- 시간 복잡도는 O(N + M).
- 정렬이 이미 되어 있거나 인덱스 스캔으로 정렬된 결과를 사용할 수 있다면 매우 효율적.
- 조인 키의 분포가 균등하고 대량 데이터일 때 선호.
3. 해시 조인 (Hash Join)
작동 방식:
-
한 테이블(일반적으로 작은 테이블)을 해시 테이블로 구성.
-
다른 테이블을 스캔하면서 해시 테이블에 매핑하여 일치하는 튜플을 찾음.
1. Build phase: 해시 테이블 생성 (작은 테이블 기준) 2. Probe phase: 큰 테이블을 스캔하며 해시 매칭
특징:
- 정렬이 필요하지 않음.
- 인덱스 없이도 효과적.
- 균등한 해시 분포를 전제로 설계.
성능 분석:
- 평균 시간 복잡도는 O(N + M), 분포 불균형 시 성능 저하 가능.
- 내부적으로 메모리 사용량이 높음 (spill to disk 발생 가능).
- 옵티마이저는 두 테이블 모두 인덱스가 없고 중간 규모 이상일 때 선호.
종합 비교
| 기준 | 중첩 루프 조인 | 병합 조인 | 해시 조인 |
|---|---|---|---|
| 전제 조건 | 없음 (범용) | 조인 키 정렬 | 해시 버킷 생성 |
| 인덱스 활용 | 유리함 | 일부 경우 가능 | 필요 없음 |
| 성능 (일반적) | 느림 | 빠름 (정렬 전제) | 빠름 (메모리 충분 시) |
| 적합한 상황 | 소규모 + 인덱스 존재 | 대용량 + 정렬 or 인덱스 | 중대규모 + 비인덱스 |
| 메모리 사용 | 적음 | 중간 | 많음 (spill 가능) |
| 구현 복잡도 | 간단 | 중간 | 복잡 |
결론
데이터베이스 옵티마이저는 다음을 고려하여 조인 방식을 결정합니다:
- 데이터 크기
- 인덱스 유무
- 통계 정보
- 메모리 용량
- 조인 조건 복잡성
성능 최적화를 위해서는 쿼리 작성 시 조인 대상의 크기, 정렬 여부, 인덱스 존재 여부를 고려하여 의도된 실행 계획을 유도해야 하며, 경우에 따라 **힌트(SQL Hint)**를 이용한 조인 방식 강제도 고려됩니다.
1. 해시 조인 (Hash Join)
비유:
- A 그룹(작은 팀)의 명단을 이름 기준으로 사전처럼 정리(해시 테이블).
- B 그룹(큰 팀)의 명단을 보면서 A 그룹 해시 사전에 있는 이름인지 빠르게 찾는 방식.
실제 예시:
SELECT *
FROM Employees E
JOIN Departments D ON E.dept_id = D.dept_id;- 두 테이블 중 하나(예:
Departments)를 메모리에 해시 테이블로 만듦. Employees를 한 줄씩 보면서, 해당dept_id가 해시 테이블에 있으면 조인.
요점:
- 정렬 안 해도 됨.
- 인덱스 없어도 빠름.
- 메모리 충분하면 효율 최고.
- 단점: 메모리가 부족하면 느려짐 (디스크 임시 저장).
2. 병합 조인 (Merge Join)
비유:
- 두 정렬된 명단(A와 B)을 손에 들고, 앞에서부터 같이 읽어가며 일치하는 줄을 찾는 방법.
- 마치 두 사람이 손에 명단을 들고 동시에 내려가며 비교하는 느낌.
실제 예시:
SELECT *
FROM Orders O
JOIN Customers C ON O.customer_id = C.customer_id;Orders와Customers가 customer_id로 정렬되어 있다고 가정.- 두 테이블을 순차적으로 읽으며 조인 조건이 맞는 항목을 출력.
요점:
- 정렬이 필요함.
- 정렬이 되어 있거나 인덱스를 통해 정렬된 상태로 읽을 수 있다면 매우 빠름.
- 정렬 자체가 무거운 연산이라 정렬 비용이 크면 느려짐.
핵심 차이 다시 정리
| 항목 | 해시 조인 | 병합 조인 |
|---|---|---|
| 정렬 필요 | 없음 | 정렬 필수 |
| 인덱스 필요 | 없음 | 있으면 좋음 (정렬) |
| 메모리 사용량 | 큼 (해시 테이블) | 중간 (정렬 버퍼) |
| 속도 | 데이터 고르게 분포 시 빠름 | 정렬된 상태면 매우 빠름 |
도움이 되는 팁
- 데이터가 정렬되어 있다면 Merge Join이 빠름.
- 인덱스 없고 메모리 충분하면 Hash Join이 빠름.
- 해시 조인은 큰 데이터도 잘 처리하지만 메모리에 민감함.
- 병합 조인은 연속된 데이터를 효율적으로 다룸.
DevSecOps Pentest🚩