[cs 스터디] 4-7. 조인의 원리

조인의 원리: 중첩 루프 조인, 정렬 병합 조인, 해시 조인

중첩 루프 조인

: 중첩 루프 조인(NLJ, Nested Loop Join)은 중첩 for문과 같은 원리로 조건에 맞는 조인을 하는 방법
랜덤 접근에 대한 비용이 많이 증가 -> 대용량 테이블에서는 사용X

for each row in t1 matching reference key {
	for each row in t2 matching reference key {
    	if row satisfies join conditions, send to client
    }
}

중첨 루프 조인에서 발전한 조인할 테이블을 작은 블록으로 나눠 블록 하나씩 조인하는 블록 중첩 루프 조인(BNL, Block Nested Loop)도 있음

정렬 병합 조인

: 정렬 병합 조인이란 각각의 테이블을 조인할 필드 기준으로 정렬하고 정렬이 끝난 후에 조인 작업을 수행하는 조인

• 조인할 때 쓸 적절한 인덱스가 없거나
• 대용량 테이블을 조인하거나
• 조인 조건으로 <, > 같은 범위 비교 연산자를 쓸 경우

해시 조인

: 해시 조인은 해시 테이블을 기반으로 조인하는 방법
두 개의 테이블을 조인한다고 할 때 하나의 테이블이 메모리에 온전히 들어간다면 중첩 루프 조인보다 더 효율적임
동등 조인에서만 사용 가능

MySQL의 경우 8.0.18 릴리스와 함께 이 기능을 사용할 수 있게 되었음
MySQL에서의 해시 조인 단계는 빌드 단계, 프로브 단계로나뉨

빌드 단계
: 입력 테이블 중 하나를 기반으로 메모리 내 해시 테이블을 빌드하는 단계

• person, countries라는 테이블을 조인하는경우
  - 둘 중 바이트가 더 작은 테이블을 기반으로 테이블을 빌드
  또한 조인에 사용되는 필드가 해시 테이블의 키로 사용된다.

---

프로브 단계
: 프로브 단계 동안 레코드 읽기를 시작하며 각 레코드에서 키에 일치하는 레코드를 찾아 결괏값을 반환한다.
이를 통해 각 테이블은 한 번씩만 읽게 되어 중첩해서 두 개의 테이블을 읽는 중첩 루프 조인보다 성능이 더 좋음
(* 사용 가능한 메모리양은 시스템 변수 join_buffer_size에 의해 제어됨. 런타임 시 조정 가능)