4-7. 조인의 원리 - 중첩 루프 조인, 정렬 병합 조인, 해시 조인

1. 중첩 루프 조인 (NLJ)

중첩 루프 조인은 두 테이블을 이중 반복문을 사용하여 연결하는 가장 기본적인 조인 방식이다. 외부 테이블의 모든 행을 하나씩 순차적으로 읽으며, 읽은 행마다 내부 테이블의 모든 행을 처음부터 끝까지 순차적으로 비교하여 조인 조건이 일치하는지 확인한다. 테이블의 크기가 커질수록 속도가 느려 성능 저하가 큰 단점이 있다.

for (A의 행) { for (B의 행) { if (A.key == B.key) { 결과 반환 } } }

 

 

 

2. 정렬 병합 조인 (SMJ)

정렬 병합 조인은 두 테이블을 미리 정렬한 후, 정렬된 순서에 따라 병합하여 조인하는 수행하는 방식이다. 두 테이블을 조인 키를 기준으로 각각 정렬한 후, 정렬된 두 테이블을 동시에 처음부터 스캔하며 조인 키 값이 일치하는 행이 나올 때까지 포인터를 이동시키고, 일치하면 결과를 반환한다. 대규모 데이터를 조인할 때 효율적이지만 정렬 과정에서 큰 비용이 발생할 수 있는 단점이 있다.

 

 

 

3. 해시 조인

해시 조인은 두 테이블 중 작은 테이블을 메모리에 로드하여 해시 테이블을 구축한 뒤, 큰 테이블을 스캔하며 조인하는 방식이다. 대부분의 작업이 해시 테이블 구축과 검색으로 이루어지므로 속도가 가장 빠르다. 해시 조인은 빌드 2단계로 이루어진다.

 

1) 빌드 단계

두 테이블 중 작은 테이블을 선택하여 빌드 테이블로 지정한다. 빌드 테이블의 조인 키를 해시 함수에 넣어 계산하고, 그 결과값에 따라 메모리에 해시 테이블을 구축한다. 이때 해시 테이블은 조인 키와 해당 행의 나머지 칼럼 정보를 저장한다.

 

2) 프로브 단계

나머지 큰 테이블을 프로브 테이블로 지정한다. 프로브 테이블을 하나씩 스캔하면서, 해당 행의 조인 키를 빌드 단계와 동일한 해시 함수에 넣어 계산한다. 계산된 해시 값을 사용하여 빌드 테이블의 해시 테이블에서 일치하는 버킷을 찾아 조인 조건이 일치하는 행을 검색한다. 일치하는 행이 발견되면 결과를 반환한다.