[Database] SQL 성능의 심장: 3가지 조인(Join) 원리 완벽 분석 (NL, Hash, Sort Merge)

단순히 A INNER JOIN B라고 쓴다고 해서 데이터베이스가 항상 똑같은 방식으로 데이터를 찾지는 않습니다. 오라클이나 PostgreSQL의 옵티마이저는 테이블의 크기, 인덱스 유무, 정렬 상태에 따라 가장 효율적인 '조인 알고리즘'을 선택합니다.

오늘은 성능 튜닝의 핵심인 NL Join, Hash Join, Sort Merge Join의 내부 메커니즘을 상세히 파헤쳐 보겠습니다.

---

1. Nested Loops Join (중첩 루프 조인) : "인덱스를 타고 흐르는 연쇄 작업"

프로그래밍의 중첩 for문과 동일한 방식입니다. 선행 테이블(Driving/Outer)에서 행을 하나씩 추출해, 후행 테이블(Driven/Inner)의 인덱스를 탐색하며 조인 조건을 만족하는 행을 찾습니다.

🔄 작동 프로세스

1. 선행 테이블에서 조건을 만족하는 행을 하나 찾습니다.
2. 해당 행의 조인 키를 가지고 후행 테이블의 인덱스를 탐색합니다.
3. 인덱스에서 찾은 주소(ROWID)로 후행 테이블의 실제 데이터를 읽습니다.
4. 이 과정을 선행 테이블의 모든 행에 대해 반복합니다.

✅ 실무 예시 (사원과 부서)

• 상황: 사원 번호가 '7934'인 사원의 부서명을 조회할 때.
• 작동:
  • EMP 테이블(선행)에서 사원번호 7934를 찾습니다 (1건).
  • 해당 사원의 DEPTNO(예: 10번)를 들고 DEPT 테이블(후행)의 부서번호 인덱스로 곧장 달려가 10번 부서명을 가져옵니다.
• 결론: 소량의 데이터를 조회하거나, 후행 테이블에 반드시 적절한 인덱스가 있을 때 최강의 성능을 발휘합니다.

---

2. Hash Join (해시 조인) : "대용량 데이터 조인의 해결사"

대량의 데이터를 조인해야 하는데 인덱스가 없거나, 인덱스를 타는 것보다 전체를 다 읽는 게 빠를 때 사용하는 현대적 알고리즘입니다.

🔄 작동 프로세스

1. Build 단계: 두 테이블 중 작은 쪽(Build Input)을 읽어 메모리 내에 해시 테이블을 생성합니다. (해시 함수를 이용해 키값을 주소로 변환)
2. Probe 단계: 큰 테이블(Probe Input)을 한 줄씩 읽으며 해시 함수를 적용해, 메모리에 만들어둔 해시 테이블에 매칭되는 데이터가 있는지 즉시 확인합니다.

✅ 실무 예시 (월간 매출 통계)

• 상황: 1,000만 건의 매출 테이블과 10만 건의 상품 테이블을 조인할 때.
• 작동:
  • 상대적으로 작은 상품 테이블을 읽어 메모리에 '해시 지도'를 만듭니다.
  • 1,000만 건의 매출 데이터를 읽으면서 이 지도에 대조해 봅니다.
• 결론: 인덱스가 없어도 매우 빠릅니다. 단, 해시 테이블이 메모리(Work Area)보다 크면 디스크를 쓰게 되어 성능이 떨어질 수 있습니다. 동등 조인(=)에서만 사용 가능합니다.

---

3. Sort Merge Join (소트 머지 조인) : "정렬과 지퍼 채우기"

양쪽 테이블을 조인 컬럼 기준으로 각각 정렬한 뒤, 순서대로 스캔하며 매칭하는 방식입니다.

🔄 작동 프로세스

1. Sort 단계: 두 테이블을 조인 키 기준으로 정렬합니다. (이미 인덱스로 정렬되어 있다면 이 단계는 생략 가능)
2. Merge 단계: 정렬된 두 리스트를 위에서부터 아래로 읽으며 조인 조건에 맞는지 확인합니다. 마치 지퍼를 양쪽에서 채워 올리는 것과 비슷합니다.

✅ 실무 예시 (범위 조인)

• 상황: = 조건이 아니라 BETWEEN이나 > 같은 범위 조건으로 조인할 때.
• 작동:
  • 해시 조인은 =일 때만 쓸 수 있으므로, 대량의 데이터 범위 조인 시에는 두 테이블을 정렬한 뒤 순서대로 맞춰보는 Sort Merge가 유리합니다.
• 결론: 조인 조건이 범위 비교이거나, 인덱스는 없는데 해시 조인을 쓰기엔 메모리가 부족할 때 선택되는 훌륭한 대안입니다.

---

4. 한눈에 비교하는 조인 알고리즘 선택 기준

비교 항목	Nested Loops Join	Hash Join	Sort Merge Join
주요 용도	소량 데이터, OLTP	대량 데이터, DW/통계	대량 데이터, 범위 조인
인덱스 필요성	후행 테이블에 필수	필요 없음	필요 없음 (있으면 Sort 생략)
조인 조건	모든 조건 가능	동등 조인(=)만 가능	모든 조건 가능
메모리 사용	매우 적음	해시 테이블용 메모리 필요	정렬용 메모리 필요