앞서 설명한 조인은 조인의 원리를 기반으로 조인 작업이 이루어진다.
조인의 원리인 중첩 루프 조인, 정렬 병합 조인, 해시 조인에 대해 알아보자.
앞서 설명한 조인의 종류는 이 원리를 기반으로 조인을 하는 것이다.
4.7.1 중첩 루프 조인
- 중첩 루프 조인(NLJ, Nested Loop Join) : 중첩 for 문과 같은 원리로 조건에 맞는 조인을 하는 방법
- 반복문의 외부에 있는 테이블을 선행 테이블 또는 외부 테이블(Outer Table)이라 함
- 반복문 내부에 있는 테이블을 후행 테이블 또는 내부 테이블(Inner Table)이라고 함
- 선행 테이블의 조건을 만족하는 행을 추출하여 후행 테이블을 읽으면서 조인을 수행
- 결과 행의 수가 적은 테이블을 조인 순서 상 선행 테이블로 선택하는 것이 전체 일량을 줄일 수 있음
- 랜덤 접근에 대한 비용이 많이 증가하므로 대용량의 테이블에서는 사용하지 x
- t1, t2 테이블을 조인한다고 했을 때, 첫 번째 테이블에서 행을 한 번에 하나씩 읽고 그 다음 테이블에서도 행을 하나씩 읽어 조건에 맞는 레코드를 찾아 결괏값을 반환
// pseudocode
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)라는 방식도 있다.
4.7.2 정렬 병합 조인
- 조인 컬럼 기준으로 정렬하고 이후 조인 작업을 수행하는 조인
- 조인할 때 쓸 적절한 인덱스가 없고 대용량의 테이블들을 조인하고 조인 조건으로 <, > 등 범위 비교 연산자가 있을 때 쓴다.
4.7.3 해시 조인
- 해시 테이블을 기반으로 조인하는 방법
- 중첩 루프 조인과 정렬 병합 조인의 문제점인 정렬 작업의 부담을 해결
- 조인 칼럼의 인덱스를 사용하지 않기 때문에 조인 칼럼의 인덱스가 존재하지 않을 경우 사용 가능
- 두 개의 테이블을 조인한다고 했을 때 하나의 테이블이 메모리에 온전히 들어간다면 보통 중첩 루프 조인보다 더 효율적(메모리에 올릴 수 없을 정도로 크다면 디스크를 사용하는 비용이 발생)
- 동등(=) 조인에서만 사용할 수 있음
- MySQL의 해시 조인 단계는 빌드 단계, 프로브 단계로 나뉜다
빌드 단계
- 입력 테이블 중 하나를 기반으로 메모리 내 해시 테이블을 빌드하는 단계
- 예를 들어 persons와 countries라는 테이블을 조인한다고 했을 대 둘 중에 바이트가 작은 테이블을 기반으로 해서 테이블을 빌드한다.
- 또한, 조인에 사용되는 필드가 해시 테이블의 키로 사용된다. 'countries.country_id'가 키로 사용되는 것을 볼 수 있다.
프로브 단계
- 프로브 단계 동안 레코드 읽기를 시작하며, 각 레코드에서 'persons.country_id'에 일치하는 레코드를 찾아 결괏값으로 반환한다.
- 이를 통해 각 테이블은 한 번씩만 읽게 되어 중첩해서 두 개의 테이블을 읽는 중첩 루프 조인보다 보통은 성능이 더 좋다.
- 참고로 사용 가능한 메모리양은 시스템 변수 join_buffer_size에 의해 제어되어, 런타임 시 조정할 수 있다.
Reference
주홍철 작가님의 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다.
