조인 방식 비교 (네스티드 루프 조인 VS 블록 네스티드 루프 조인 VS 해시 조인)

1. 네스티드 루프 조인 (Nested Loop Join)

조인 연결 컬럼에 모두 인덱스가 있을 때 사용하는 기본 조인 방식

드라이빙 테이블에서 레코드 1건 읽기
        ↓
즉시 드리븐 테이블에서 일치하는 레코드 찾기
        ↓
별도 버퍼 없이 바로 반환 (중첩 반복문과 유사)

• 드리븐 테이블 인덱스가 없으면 왜 느린가?

드라이빙 테이블 일치 레코드 = 1,000건
        ↓
드리븐 테이블 인덱스 없음
        ↓
드리븐 테이블 풀 스캔 1,000번 수행 → 매우 느림

👉 옵티마이저는 최대한 드리븐 테이블이 인덱스를 사용하도록 실행 계획을 수립한다.

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

드리븐 테이블에 인덱스를 사용할 수 없을 때 조인 버퍼를 활용하는 방식

• 블록 네스티드 루프 조인 처리 흐름

WHERE de.from_date > '1995-01-01' AND e.emp_no < 109004;
-------------------------------------------------------------------------
① dept_emp 테이블에서 from_date > '1995-01-01' 조건으로 레코드 검색 (인덱스 사용)
        ↓
② 조인에 필요한 dept_emp 컬럼 전부를 조인 버퍼에 저장
        ↓
③ employees 테이블에서 emp_no < 109004 조건으로 레코드 검색 (PK 사용)
        ↓
④ employees 결과 + 조인 버퍼의 dept_emp 레코드를 결합해서 반환

• 조인 버퍼 사용 시 주의사항

실행 계획상 dept_emp가 드라이빙이지만, 실제로는 드리븐 테이블(employees)을 먼저 읽고 조인 버퍼에서 일치하는 레코드를 찾는 방식으로 동작한다. 즉 조인 순서가 거꾸로 실행된다.

두 방식의 핵심 차이

구분	네스티드 루프 블록	네스티드 루프
조인 버퍼 사용	❌	✅
드리븐 테이블 인덱스	✅ 있음	❌ 없음
EXPLAIN Extra 컬럼	없음	Using Join buffer
결과 정렬 순서	드라이빙 테이블 순서 유지	순서 흐트러질 수 있음

3. 해시 조인

MySQL 8.0.20부터 블록 네스티드 루프 조인 대신 해시 조인을 사용한다. 적절한 인덱스가 없을 때 주로 선택된다.

2단계 처리 방식

단계	이름	설명
1단계	빌드 단계 (Build Phase)	레코드 수가 적은 테이블을 메모리에 해시 테이블로 생성
2단계	프로브 단계 (Probe Phase)	나머지 테이블을 읽으며 해시 테이블에서 일치 레코드 탐색

 

메모리가 부족한 경우 (청크 분할 처리)

• 조인 버퍼(join_buffer_size, 기본값 256KB)가 해시 테이블보다 작을 때 발생한다.

1차 처리

dept_emp를 읽으며 메모리 해시 테이블 생성
        ↓
메모리 초과 → 나머지 dept_emp 레코드를 디스크에 청크로 저장
        ↓
employees를 읽으며 메모리 해시 테이블과 1차 조인 수행
        ↓
동시에 employees 레코드도 디스크에 청크로 저장

 

2차 처리

디스크의 빌드 테이블 청크 1번을 읽어 메모리 해시 테이블 재구성
        ↓
디스크의 프로브 테이블 청크 1번을 읽어 조인 수행
        ↓
청크 개수만큼 반복
        ↓
최종 결과 반환

 

해시 조인 vs 블록 네스티드 루프 조인

핵심 차이

구분	블록 네스티드 루프	해시 조인
조인 버퍼 활용	드라이빙 테이블을 버퍼에 저장	작은 테이블을 해시 테이블로 변환
일치 레코드 탐색	버퍼와 드리븐 테이블을 반복 비교	해시 함수로 즉시 탐색
시간 복잡도	O(N × M)	O(N + M)

 

1. 블록 네스티드 루프 방식

1. 드라이빙 테이블을 조인 버퍼에 저장
2. 드리븐 테이블을 풀스캔하면서, 조인 버퍼의 모든 레코드와 하나씩 비교
3. 일치하는 레코드 반환

• 예를 들어 버퍼에 1,000건, 드리븐 테이블에 10,000건이면
  👉 1,000 × 10,000 = 1,000만 번 비교

2. 해시 조인 방식

1. 빌드 테이블로 해시 테이블 생성
2. 프로브 테이블을 읽으며, 해시 함수로 즉시 일치 레코드 탐색
3. 일치하는 레코드 반환

• 동일한 상황에서 → 해시 테이블 생성: 1,000번, 프로브 탐색: 10,000번
  👉 총 11,000번만 수행

결론: 블록 네스티드 루프는 모든 레코드를 반복 비교하지만,
해시 조인은 해시 함수로 즉시 탐색하기 때문에 대용량 데이터에서 훨씬 효율적이다.