4.7 조인의 원리

참고한 책: 면접을 위한 CS 전공지식 노트 (http://www.yes24.com/Product/Goods/108887922)

4. 데이터베이스

    4.7. 조인의 원리

        4.7.1. 중첩 루프 조인

        4.7.2. 정렬 병합 조인

        4.7.3. 해시 조인

 

p. 226

4.7.1 중첩 루프 조인(NLJ, Nested Loop Join)

중첩 for문과 같은 원리로 조건에 맞는 조인을 하는 방법

랜덤 접근에 대한 비용이 많이 증가하므로 애용량의 테이블에서는 사용하지 않음.

//t1, t2 테이블을 조인한다.
for each row in t1 matching reference key {
	for each row in t2 matching reference key {
    	if row satisfies joiin conditions, send to Client
    }
}

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

 

p. 227

4.7.2 정렬 병합 조인

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

• 조인할 때 쓸 적절한 인덱스가 없고
• 대용량의 테이블들을 조인하고
• 조인 조건으로 <, > 등 범위 비교 연산자가 있을 때 사용

 

4.7.3 해시 조인

해시 테이블을 기반으로 조인하는 방법.

두 개의 테이블을 조인할 때 하나의 테이블이 메모리에 온전히 들어간다면 보통 중첩 루프 조인보다 더 효율적임.

메모리에 올릴 수 없을 정도로 크다면 디스크 사용 비용이 발생함.

동등(=) 조인에서만 사용할 수 있음.

MySQL의 해시 조인 단계는 빌드 단계, 프로브 단계로 나뉨.

 

빌드 단계

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

예) ps와 cs라는 테이블을 조인할 때 바이트가 더 작은 테이블을 기반으로 테이블을 빌드.

조인에 사용되는 필드가 해시 테이블의 키로 사용됨.

예) cs.c_id가 키로 사용됨.

 

프로브 단계

이 단계 동안 레코드 읽기를 시작하며, 예) 각 레코드에서 ps.c_id에 일치하는 레코드를 찾아 결과값으로 반환.

이를 통해 각 테이블은 한번씩만 읽게 되어 두 개의 테이블을 읽는 중첩 루프 조인보다 보통은 성능이 더 좋음.