7. 조인의 원리
본 게시글은 책 : 면접을 위한 CS 전공지식 노트 (출판사 : 길벗, 주홍철 지음) 을 참조하여 작성하였습니다. + 구글링
◆ 중첩 루프 조인 (NLJ, Nested Loop Join)
- 중첩 for문과 같은 원리로 조건에 맞는 조인을 하는 방법
- 랜덤 접근에 대한 비용이 많이 증가하므로 대용량의 테이블에서는 미사용
ex) "t1, t2 테이블을 조인한다." 라고 했을 때, 첫 번째 테이블에서 행을 한 번에 하나씩 읽고 그 다음 테이블에서도 행을 하나씩 읽어 조건에 맞는 레코드를 찾아 결괏값 반환
for each row in t1 matching reference key {
for each row in t2 matching reference key {
if row satisfies join conditions, send to client
}
}- 참고 : 이를 발전시켜 조인할 테이블을 작은 블록으로 나눠서 블록 하나씩 조인하는 블록 중첩 루프 조인 방식도 존재
◆ 정렬 병합 조인
- 각각의 테이블을 조인할 필드 기준으로 정렬하고 정렬이 끝난 이후에 조인 작업을 수행
- 조인할 때 사용할 적절한 인덱스가 없을 때나, 대용량의 테이블들을 조인, 조인 조건으로 '<', '>' 등의 비교 연산자가 있을 때 사용
◆ 해시 조인
- 해시 테이블을 기반으로 조인
- 두 개의 테이블을 조인한다고 했을 때 하나의 테이블이 메모리에 온전히 들어간다면, 일반 중첩 루프 조인보다 효율적
( 메모리에 올릴 수 없을 정도로 크다면 디스크를 사용하는 비용이 발생 )
- 동등(=) 조인에서만 사용
- MySQL의 경우 MySQL 8.0.18 릴리즈와 함꼐 이 기능을 사용 가능
- MySQL의 해시 조인 단계는 빌드 단계, 프로브 단계로 구성
- 빌드 단계 : 입력 테이블 중 하나를 기반으로 메모리 내 해시 테이블을 빌드하는 단계
ex) person과 countries라는 테이블을 조인한다고 했을 때, 둘 중에 바이트가 더 작은 테이블을 기반으로 해서 테이블을 빌드
:조인에 사용되는 필드가 해시 테이블의 키로 사용 됨
(위 예시에서 'countries.country_id'가 키로 사용)
- 프로브 단계
: 레코드 읽기를 시작하며, 각 레코드에서 "person.country_id"에 일치하는 레코드를 찾아서 결과값으로 반환
: 이를 통해 각 테이블은 한 번씩만 읽게 되어 중첩해서 두 개의 테이블을 읽는 중첩 루프 조인보다 성능이 향상
: 사용 가능한 메모리양은 시스템 변수 join_buffer_size에 의해 제어되며, 런타임 시에 조정
이 책은 어떠한 독자를 생각하면서 작성한 것일까요?!
위의 글과 관련하여 추가적인 내용이나 피드백은 언제나 환영입니다 :)