카테시안 조인, 블록 네스티드 루프 조인, 해시 조인이 뭐야?

세 가지는 모두 조인을 수행하는 방식이지만, 각각 다른 알고리즘과 사용 시나리오를 가집니다:

• 카테시안 조인(Cartesian Product): 두 테이블의 모든 행을 곱한 결과 (조건 없음)
• 블록 네스티드 루프 조인(Block Nested Loop): 조인 버퍼를 사용한 중첩 루프 조인
• 해시 조인(Hash Join): 해시 테이블을 이용한 빠른 조인 (MySQL 8.0.18+)

조인(Join)의 기본 원리

조인은 두 테이블의 레코드를 특정 조건에 따라 결합하는 연산입니다. 조인 알고리즘은 이 결합을 얼마나 효율적으로 수행하는지에 따라 성능이 크게 달라집니다.

Nested Loop Join (기본 조인)

-- 외부 테이블의 각 행마다
FOR each row in table_A:
    -- 내부 테이블에서 매칭되는 행 찾기
    FOR each row in table_B:
        IF A.key = B.key:
            RETURN combined_row

드라이빙 테이블(외부)의 각 행마다 드리븐 테이블(내부)을 스캔하는 이중 루프 방식입니다.

드라이빙 vs 드리븐 테이블

• 드라이빙 테이블: 먼저 읽는 테이블 (외부 루프)
• 드리븐 테이블: 매번 스캔되는 테이블 (내부 루프)

1. 카테시안 조인 (Cartesian Product)

두 테이블의 모든 가능한 조합을 생성합니다. 조인 조건이 없거나 CROSS JOIN을 사용할 때 발생합니다.

-- 카테시안 조인 예시
SELECT * FROM employees, departments;
-- 또는
SELECT * FROM employees CROSS JOIN departments;

-- employees 10행 × departments 5행 = 50행 결과

특징:

• 결과 행 수 = 테이블A 행 수 × 테이블B 행 수
• 대부분의 경우 의도하지 않은 실수로 발생
• 매우 큰 결과 집합 생성 (성능 문제)
• 특정 분석 작업에서는 의도적으로 사용하기도 함

경고 신호:

• EXPLAIN에서 type: ALL이 여러 테이블에 표시
• rows 값이 비정상적으로 큼
• 쿼리가 예상보다 훨씬 많은 결과 반환

2. 블록 네스티드 루프 조인 (Block Nested Loop Join)

기본 Nested Loop Join의 개선 버전으로, 조인 버퍼를 사용하여 드리븐 테이블의 스캔 횟수를 줄입니다.

SELECT * FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE c.name LIKE '%Kim%';

-- customers에 인덱스 없으면 Block Nested Loop 사용
-- EXPLAIN Extra: Using join buffer (Block Nested Loop)

동작 원리:

1. 드라이빙 테이블(orders)의 여러 행을 조인 버퍼에 저장
2. 드리븐 테이블(customers)을 한 번 스캔하면서
3. 버퍼의 모든 행과 한 번에 비교
4. 버퍼가 가득 차면 반복 (멀티 패스)

특징:

• 드리븐 테이블 스캔 횟수 = ⌈드라이빙 행 수 / 버퍼 크기⌉
• 인덱스 없을 때 사용
• join_buffer_size로 버퍼 크기 조절
• MySQL 8.0.20에서 기본적으로 해시 조인으로 대체됨

3. 해시 조인 (Hash Join)

MySQL 8.0.18부터 도입된 조인 방식으로, 해시 테이블을 사용하여 매우 빠르게 조인합니다.

SELECT * FROM orders o
JOIN customers c ON o.customer_id = c.id;

-- 인덱스 없을 때 자동으로 해시 조인 사용
-- EXPLAIN Extra: Using join buffer (hash join)

동작 원리:

1. Build Phase: 작은 테이블로 해시 테이블 생성
2. 각 행의 조인 키를 해시 함수에 넣어 해시 테이블에 저장
3. Probe Phase: 큰 테이블을 스캔하면서
4. 각 행의 조인 키를 해시하여 해시 테이블에서 O(1)로 매칭

특징:

• 등가 조인(=)에서만 사용 가능
• Block Nested Loop보다 훨씬 빠름
• 메모리 사용량이 큼 (해시 테이블)
• 메모리 부족 시 디스크 사용 (온디스크 해시 조인)
• join_buffer_size와 hash_join_buffer_size로 제어

세 가지 조인 방식 비교

특징	카테시안 조인	블록 네스티드 루프	해시 조인
조건	조건 없음	조건 있음, 인덱스 없음	등가 조건, 인덱스 없음
성능	매우 느림	느림	빠름
복잡도	O(M × N)	O(M × N / buffer_size)	O(M + N)
메모리 사용	적음	조인 버퍼	해시 테이블 (많음)
EXPLAIN Extra	-	Using join buffer (Block Nested Loop)	Using join buffer (hash join)
사용 케이스	실수 또는 특수 분석	인덱스 없는 범위 조건	인덱스 없는 등가 조건

최적화 전략

1. 최선: 드리븐 테이블의 조인 컬럼에 인덱스 추가 → Nested Loop Join (가장 빠름)
2. 차선: 인덱스 없으면 해시 조인 자동 사용 (8.0.18+)
3. 카테시안 조인 방지: 항상 조인 조건 명시

해시 조인은 O(M+N) 복잡도로 가장 빠르지만, 인덱스가 있다면 Nested Loop Join이 더 빠릅니다.