[CS] 조인의 원리

조인은 SQL로 쿼리할 땐 INNER JOIN, LEFT JOIN처럼 표현하지만,
실제로 데이터베이스 엔진 내부에서는 다음 중 하나의 알고리즘으로 실행됨

---

중첩 루프 조인

• 두 테이블을 중첩 반복문처럼 돌면서 조인 조건에 맞는지 일일이 비교

• 작은 테이블일 땐 빠르지만
• 대용량 테이블에는 비효율적
• 인덱스가 없으면 전체 탐색하므로 성능 저하

for each row in A:
    for each row in B:
        if 조건 만족:
            결과 반환

---

정렬 병합 조인

• 조인 대상 테이블을 조인 기준 컬럼으로 정렬한 후 병합

• <, > 범위 조건 조인에 적합
• 인덱스가 없어도 괜찮음
• 둘 다 정렬된 상태여야 효과적

• 대용량 범위 조인에 유리
• 정렬 비용이 추가됨

---

해시 조인

• 한 테이블을 메모리에 올려서 해시 테이블 생성 → 다른 테이블과 매칭

• 동등(=) 조인에서만 사용 가능
• 중첩 루프보다 빠름 (한 테이블만 메모리에 올라가면)
• MySQL 8.0.18부터 지원

📌 단계별 구조

• 빌드 단계: 작은 테이블을 기반으로 해시 테이블 생성
• 프로브 단계: 다른 테이블의 각 행을 해시 테이블에서 탐색
• join_buffer_size 설정으로 사용 메모리 조절 가능

---

참고: 북스터디 - 면접을 위한 CS 전공지식 노트 (Chapter 4-7)