SQL 조인 알고리즘 비교: Nested Loop Join (중첩 루프 조인)

조인 알고리즘(Join Algorithm)은 SQL의 JOIN 연산이 실제 데이터베이스 엔진 내부에서 어떻게 실행되는지를 결정하는 물리적 연산 방식입니다. 이는 단순한 SQL 문법을 넘어, 실행 성능과 최적화에 직결되는 개념이며, 데이터베이스 엔진, 성능 튜닝, 운영면접 등에서 자주 출제되는 심화 주제입니다.

이 문서에서는 조인 알고리즘의 개념, 중첩 루프 조인(Nested Loop Join)의 구조 및 성능, 그리고 다른 조인 알고리즘들과의 비교를 통해 면접 대비에 필요한 논리적, 기술적 근거를 정리합니다.

---

조인 알고리즘의 개념: 조인 실행 계획의 핵심

조인 알고리즘이란 무엇인가?

SQL에서 JOIN을 선언하면, 실제로는 DBMS가 이를 물리적인 조인 방식으로 변환하여 실행합니다. 이때 선택되는 알고리즘이 바로 조인 알고리즘입니다.

조인 알고리즘은 다음과 같은 역할을 수행합니다:

• 두 테이블 간 조인 조건을 효율적으로 평가
• 메모리, 인덱스, 디스크 I/O 등 자원을 고려해 최적화
• 전체 실행 비용을 고려하여 쿼리 성능을 결정

---

중첩 루프 조인(Nested Loop Join)의 구조와 실행 방식

중첩 루프 조인이란?

중첩 루프 조인(Nested Loop Join)은 가장 단순한 조인 알고리즘으로, 하나의 테이블(외부 루프)의 각 튜플에 대해, 다른 테이블(내부 루프)의 모든 튜플을 비교하는 방식입니다.

알고리즘 개요

for each row R1 in Table A:          → 외부 루프
    for each row R2 in Table B:      → 내부 루프
        if R1.key = R2.key:
            join R1 and R2 into result

• 외부 테이블: 작은 쪽이 유리
• 내부 테이블: 보통 인덱스를 활용하거나 메모리 최적화 대상

시간 복잡도

• O(N × M) (N: 외부 테이블 튜플 수, M: 내부 테이블 튜플 수)
• 매우 단순하지만, 성능이 가장 낮음
• 인덱스 사용 시 성능이 대폭 개선됨

---

중첩 루프 조인의 최적화 방식과 사용 조건

블록 중첩 루프(Block Nested Loop)

• 내부 루프를 한 블록 단위로 메모리에 적재하여 반복 비교 횟수를 줄임
• 디스크 I/O 감소 효과

인덱스 중첩 루프(Index Nested Loop)

• 내부 루프 테이블에 조인 키에 대한 인덱스가 존재할 경우
• 내부 루프 전체를 순회하지 않고 해당 키에 해당하는 값만 직접 검색

-- Index Nested Loop Join에 적합한 쿼리
SELECT *
FROM Orders O
JOIN Customers C ON O.CustomerID = C.CustomerID;

Customers.CustomerID에 인덱스가 있을 경우, 중첩 루프가 아닌 인덱스 탐색만 수행됨

언제 사용하는가?

• 작은 테이블 + 큰 테이블 조인
• 조인 조건 컬럼에 인덱스 존재
• 조인 필터링 결과가 매우 적을 때 (Selective Join)
• 비교 대상 테이블이 정렬되지 않거나 해시화가 어려울 때

---

다른 조인 알고리즘들과의 비교

알고리즘 종류	개념 요약	시간 복잡도	특징 / 장점	단점
Nested Loop Join	한 행마다 다른 테이블 전체 스캔	O(N×M)	단순, 인덱스 활용 시 빠름	대량 조인 시 성능 최악
Sort-Merge Join	양쪽 테이블을 정렬 후 병합	O(NlogN + MlogM)	정렬된 입력 데이터에 효과적	정렬 비용 큼, 중복 처리 필요
Hash Join	해시 테이블을 만들고 키로 연결	평균 O(N+M)	해시 가능한 데이터에 대해 매우 빠름	해시 충돌, 메모리 과다 사용 가능

 

---

면접에서 중첩 루프 조인을 설명할 때 핵심 포인트

Q1. 중첩 루프 조인을 언제 사용하나요?

• A: 조인 조건에 인덱스가 있을 경우, 비교 범위가 좁을 경우, 한쪽 테이블이 작을 경우 Nested Loop Join이 유리합니다.

Q2. 중첩 루프 조인의 단점은 무엇인가요?

• A: 기본 형태는 **O(N×M)**의 성능을 가지므로, 테이블의 크기가 클 경우 디스크 I/O 및 CPU 부하가 매우 큼
  → 대용량 테이블에는 적합하지 않음

Q3. 데이터베이스는 조인 알고리즘을 어떻게 선택하나요?

• A: DBMS의 쿼리 옵티마이저가 테이블 크기, 인덱스 여부, 통계 정보를 기반으로 적절한 조인 방식을 선택합니다.

---

정리

• 조인 알고리즘은 SQL JOIN 구문의 실행 시 내부적으로 어떤 물리 연산이 사용될지를 결정하는 방식입니다.
• 중첩 루프 조인(Nested Loop Join)은 가장 기본적인 조인 알고리즘으로, 한쪽 테이블의 각 행을 다른 테이블과 반복 비교하여 조건을 평가합니다.
• 성능은 O(N×M)이지만, 인덱스 사용 또는 소규모 조인에서는 여전히 유효합니다.