433. 해시 조인 (Hash Join) - Build와 Probe

⚠️ 이 문서는 인덱스도 없고 데이터도 엄청나게 많은 두 테이블을 조인할 때, 디스크를 미친 듯이 긁어대는 NL 조인(431번)과 정렬하느라 메모리를 다 써버리는 소트 머지 조인(432번)의 단점을 모두 씹어먹고 **대용량 데이터 조인의 끝판왕으로 군림하는 '해시 조인'**을 다룹니다.

핵심 인사이트 (3줄 요약)

본질: 두 테이블 중 작은 테이블을 메모리로 가져와서 초고속 해시 맵(Hash Map)을 만들고, 큰 테이블을 읽으면서 그 해시 맵에 하나씩 던져서 짝을 맞추는 방식이다.

가치: 정렬(Sort)할 필요가 없고, 디스크 랜덤 액세스(Random I/O)도 전혀 발생하지 않기 때문에 대용량 데이터 웨어하우스(OLAP) 환경에서 압도적인 속도를 낸다.

한계: 해시 함수의 특성상 값이 정확히 일치하는 동등 조인(Equi Join, =)에서만 사용 가능하며, 크기가 작은 쪽을 'Build Input'으로 잡아야 메모리 초과(OOM)를 막을 수 있다.

Ⅰ. 개요: 1억 건의 미팅 (Context & Necessity)

"10만 건의 부서 테이블과 1억 건의 직원 테이블을 조인해 줘!" 두 테이블 모두 부서코드에 인덱스가 없다.

NL 조인: 10만 번 $\times$ 1억 번 = 10조 번 디스크를 읽어야 한다. (서버 터짐)
소트 머지 조인: 1억 건의 직원을 부서코드로 '가나다순' 정렬해야 한다. (메모리 터짐)

이때 구원투수로 등장하는 것이 **해시 조인(Hash Join)**이다. 옵티마이저는 짱구를 굴린다. "작은 쪽인 부서 테이블을 싹 다 메모리에 올려서 **해시 자판기(Hash Map)**로 만들어버리자! 그리고 1억 명의 직원들을 한 명씩 불러서 이 자판기에 동전(부서코드)을 넣게 하면, 1초 만에 자기 부서를 찾아갈 수 있잖아?"

📢 섹션 요약 비유: 해시 조인은 **'우편물 분류 자동화 기계'**와 같습니다. 기계 안에 지역별(해시 함수) 칸막이를 미리 쫙 만들어두고(Build), 1억 통의 편지를 컨베이어 벨트에 태워서 휙휙 던지면(Probe) 0.01초 만에 자기 칸으로 쏙쏙 떨어지는 마법의 속도입니다.

Ⅱ. 해시 조인의 2단계 메커니즘 ★

면접에서 "해시 조인의 원리를 설명해 보세요"라고 할 때 반드시 나와야 하는 두 단어가 있다.

1. Build Phase (빌드 단계) - 작은 테이블로 자판기 만들기

조인할 두 테이블 중 **작은 테이블(Build Input)**을 고른다.
이 테이블의 데이터를 처음부터 끝까지 한 번 싹 읽으면서(Full Scan), 조인 컬럼의 값을 해시 함수에 넣어 메모리(Hash Area)에 해시 맵을 생성한다.

2. Probe Phase (프로브 단계) - 큰 테이블로 자판기 찔러보기

이제 **큰 테이블(Probe Input)**을 처음부터 끝까지 한 번 싹 읽는다(Full Scan).
여기서 나온 조인 컬럼의 값을 똑같은 해시 함수에 넣는다.
메모리에 만들어둔 자판기(해시 맵)를 쿡 찌르면(Probe), 짝꿍이 있는지 없는지 0.0001초 만에 튀어나온다.

Ⅲ. 치명적 단점과 튜닝 포인트

해시 조인도 약점은 있다.

1. 메모리 폭발 (Hash Area 부족)

자판기(Build)를 만들 때, 작은 테이블이라고 골랐는데도 메모리 공간(Hash Area)보다 크면 어떻게 될까?
메모리에 다 못 들어가서 디스크(Temp 공간)에 임시로 썼다 지웠다 하는 'Grace Hash Join' 모드로 강제 전환되며 속도가 박살 난다.
튜닝 힌트: Build Input을 최대한 쥐어짜서 작게 만들어야 한다.

2. 오직 "=" 조건만 가능 (비동등 조인 불가)

해시 함수는 3과 3이 똑같다는 건 1초 만에 알지만, 3이 5보다 작다는 사실은 모른다. (425번 문서 참조)
그래서 조인 조건이 A.date >= B.date 처럼 부등호가 들어가면 해시 조인은 아예 작동을 거부하고 소트 머지 조인(432번 문서)으로 도망가 버린다.

┌──────────────────────────────────────────────────────────────┐
│           해시 조인 (Hash Join: Build & Probe) 시각화                 │
├──────────────────────────────────────────────────────────────┤
│                                                              │
│ [ 1️⃣ Build 단계: 작은 테이블로 메모리에 해시 맵 만들기 ]                  │
│                                                              │
│  [🏢 부서(10건)] ──(Hash 함수)──▶  🗄️ 메모리 해시 맵 (Hash Area)     │
│                                   Hash(D1) -> 영업팀           │
│                                   Hash(D2) -> 개발팀           │
│                                                              │
│ [ 2️⃣ Probe 단계: 큰 테이블을 읽으면서 맵 찔러보기 ]                     │
│                                                              │
│  [👨‍💼 직원(1억건)] ──(Hash 함수)──▶  🗄️ 메모리 해시 맵 찔러보기!        │
│   직원A(D1)     ──(Hash 함수)──▶ "영업팀이네!" (0.01초 만에 매칭 완료) │
│   직원B(D2)     ──(Hash 함수)──▶ "개발팀이네!" (0.01초 만에 매칭 완료) │
└──────────────────────────────────────────────────────────────┘

Ⅳ. 결론

"디스크 시대의 한계를 메모리의 힘으로 박살 내다." 해시 조인은 CPU가 메모리에서 해시 테이블을 뒤지는 속도가, 디스크 바늘이 인덱스를 찾아 널뛰는 속도(랜덤 I/O)보다 수천 배 빠르다는 물리적 진리에 기반한 알고리즘이다. 그래서 하루 1번, 수억 건의 데이터를 통째로 조인해서 집계해야 하는 데이터 웨어하우스(DW) 환경에서는 해시 조인이 절대적인 권력을 쥔다. 백엔드 개발자는 쿼리를 짤 때 A = B라는 동등 조건이 있는지, 그리고 두 테이블 중 한쪽이 메모리에 쏙 들어갈 만큼 작은지를 파악하여 옵티마이저가 해시 조인을 선택하도록 판을 깔아주어야 한다.

📌 관련 개념 맵

관련 연산: 관계 대수 JOIN ($\bowtie$, 409번 문서)
대안 방식: Nested Loop Join (431번), Sort Merge Join (432번)
핵심 키워드: Build Input (작은 쪽), Probe Input (큰 쪽), Equi Join (동등 조인)
튜닝 힌트 (Oracle): /*+ USE_HASH(A B) SWAP_JOIN_INPUTS(B) */

👶 어린이를 위한 3줄 비유 설명

해시 조인은 놀이공원 '분실물 센터'와 같아요.
Build 단계는 분실물 센터 직원이 주워온 우산, 지갑(작은 테이블)을 'ㄱ,ㄴ,ㄷ' 서랍(해시 맵)에 예쁘게 싹 정리해 두는 거예요.
Probe 단계는 수만 명의 손님(큰 테이블)이 와서 "저 우산 잃어버렸어요!"라고 할 때, 직원이 'ㅇ' 서랍만 쏙 열어서 1초 만에 찾아주는(찔러보기) 방식이랍니다!