[데이터베이스] 조인의 원리

https://1eehyunji.tistory.com/entry/%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%B2%A0%EC%9D%B4%EC%8A%A4-%EC%A1%B0%EC%9D%B8Join

[데이터베이스] 조인(Join)

위 게시글에서 설명한 조인은 조인의 원리를 기반으로 작업이 이루어진다. 

조인의 원리인 중첩 루프 조인, 정렬 병합 조인, 해시 조인에 대해 알아보자!

 

중첩 루프 조인(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 join conditions, send to client
    }
}

 

정렬 병합 조인(Sort Merge Join)

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

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

 

만약 두 테이블의 정렬 조건의 데이터 차이가 커서, 정렬의 시간 차이가 커지는 경우 한 테이블은 다른 테이블의 정렬이 끝날 때까지 대기해야 하므로, 비효율적일 수 있다. 

 

 

해시 조인(Hash Join)

해시 조인은 해시 테이블을 기반으로 조인하는 방법이다. 또, 동등(=) 조인에서만 사용이 가능하다. 

MySQL의 해시 조인 단계는 빌드 단계와 프로브 단계로 나뉜다.

 

빌드 단계

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

예를 들어, person과 country라는 테이블을 조인한다고 했을 때 둘 중 용량이 더 적은 테이블을 기반으로 해시 테이블을 빌드한다.

또, 조인에 사용되는 필드가 해시 테이블의 키로 사용된다.

예를 들어, person과 country 테이블 중 country 테이블의 용량이 더 적고, 두 테이블의 조인에 사용되는 필드가 ID인 경우, 위 그림과 같이 country.ID가 해시 테이블의 키로 사용된다. 

 

프로브 단계

프로브 단계 동안 레코드 읽기를 시작하며, 각 레코드에서 person.ID에 일치하는 레코드를 찾아 결괏값을 반환한다.

즉, 해시 조인은 해시 함수를 이용하여 용량이 더 적은 쪽의 테이블을 기반으로 해시테이블을 만들고(빌드 단계), 용량이 더 큰 쪽의 테이블을 탐색하면서 조인을 수행(프로브 단계)한다.

 

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