[DATABASE] 조인 수행 원리란? NL, Sort Merge, Hash 조인이란?

NL Join

---

프로그래밍에서 사용하는 중첩된 반복문과 유사한 방식으로 조인을 수행합니다.

선행 테이블의 조건을 만족하는 행을 추출하여 후행 테이블을 읽으면서 조인을 수행합니다.

이 작업은 선행 테이블의 조건을 만족하는 모든 행의 수만큼 반복 수행합니다.

따라서 결과행의 수가 적은 테이블을 선행 테이블로 선택하는 것이 좋습니다.

작업 방법

1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾음

2. 선행 테이블의 조인 키 값을 가지고 후행 테이블에서 조인 수행

3. 선행 테이블의 조건을 만족하는 모든 행에 대해 1번 작업 반복 수행

그림으로 좀더 세분화합니다.

1. 선행 테이블에서 조건을 만족하는 첫 번째 행을 찾음

2. 선행 테이블의 조인 키를 가지고 후행 테이블에 조인 키가 존재하는지 찾음

3. 후행 테이블의 인덱스에 선행 테이블의 조인 키가 존재하는지 확인

4. 인덱스에서 추출한 레코드 식별자를 이용하여 후행 테이블을 액세스. 만족시 해당 행을 추출버퍼에 넣음

5 ~ 11 번은 앞의 작업을 반복합니다.

Sort Merge Join

---

조인 컬럼을 기준으로 데이터를 정렬하여 조인을 수행합니다.

NL Join 은 랜덤 액세스 방식으로 데이터를 읽는 반면, Sort Merge 는 주로 스캔 방식으로 데이터를 읽습니다.

정렬 작업을 수행해야 하기때문에 임시 영역이 필요하며 모든 정렬 작업을 메모리에서 수행하기 어려운 경우 디스크를 사용하기 때문에 성능이 떨어질 수 있습니다.

일반적으로 대량의 조인 작업에서 정렬 작업을 필요로 하는 Sort Merge 보다는 CPU 작업 위주로 처리하는 Hash 기법이 유리합니다.

그러나 Sort Merge 는 동등 조인 뿐만 아니라 비동등 조인에 대해서도 작업이 가능하다는 장점이 있습니다.

작업 방법입니다.

1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾음

2. 선행 테이블의 조인 키를 기준으로 정렬 작업을 수행

1 ~ 2번 작업을 선행 테이블의 조건을 만족하는 모든 행에 대해 반복 수행

3. 후행 테이블에서 주어진 조건을 만족하는 행을 찾음

4. 후행 테이블의 조인 키를 기준으로 정렬 작업을 수행

3 ~ 4번 작업을 후행 테이블의 조건을 만족하는 모든 행에 대해 반복 수행

5. 정렬된 결과를 이용하여 조인을 수행하며 조인에 성공하면 추출버퍼에 넣음

Hash Join

---

조인을 수행할 테이블의 조인 컬럼을 기준으로 해쉬함수를 수행하여 서로 동일한 해쉬 값을 갖는 것들 사이에서 실제 값이 같은지를 비교하면서 조인을 수행합니다.

작업 방법입니다.

1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾음

2. 선행 테이블의 조인 키를 기준으로 해쉬 함수를 적용하여 해쉬 테이블을 생성. 조인 컬럼과 SELECT 절에서 필요로 하는 컬럼도 함께 저장됨

1 ~ 2 번 작업을 선행테이블의 조건을 만족하는 모든 행에 대해 반복 수행

3. 후행 테이블에서 주어진 조건을 만족하는 행을 찾음

4. 후행 테이블의 조인 키를 기준으로 해쉬 함수를 적용하여 해당 버킷을 찾음

5. 조인에 성공하면 추출버퍼에 넣음

3 ~5 번 작업을 후행 테이블의 조건을 만족하는 모든 행에 대해서 반복 수행

해쉬 함수를 적용한 값은 어떤 값으로 해슁될지 알 수 없지만, 동일한 값은 항상 같은 값으로 해슁됨이 보장됩니다.

해쉬 테이블의 크기가 메모리 적재할 수 있는 크기보다 더 커지면 임시 영역에 해쉬 테이블을 저장합니다.

그렇기 때문에 해쉬 조인할 때는 결과 행의 수가 테이블을 선행 테이블로 사용하는 것이 좋습니다.

이 내용은 'SQL 전문가 가이드, 한국데이터베이스 진흥원' 에서 공부한 내용입니다.