오라클 NL Join, Sort Merge Join, Hash Join 특징 총정리

NL Join(Nested Loops Join) 수행 원리

1) 다음은 NL Join의 수행 방식을 단계별로 나타낸 것입니다.

 

① 선행 테이블에서 조건을 만족하는 첫 번째 행을 찾음 → 이때 선행 테이블에 주어진 조건을 만족하지 않는 경우 해당 데이터는 필터링 된다.
② 선행 테이블의 조인 키를 가지고 후행 테이블에 조인 키가 존재하는지 찾으러 감 → 조인 시도
③ 후행 테이블의 인덱스에 선행 테이블의 조인 키가 존재하는지 확인 → 선행 테이블의 조인 값이 후행 테이블에 존재하지 않으면 선행 테이블 데이터는 필터링 됨 (더 이상 조인 작업을 진행할 필요 없음)
④ 인덱스에서 추출한 레코드 식별자를 이용하여 후행 테이블을 액세스 → 후행 테이블에 주어진 조건까지 모두 만족하면 해당 행을 추출버퍼에 넣음. 
⑤ ~ ⑪ 앞의 작업을 반복 수행.

2) NL 조인(Join)은 프로그래밍 언어에서 사용하는 중첩된 반복문과 유사한 방식으로 조인을 수행한다.

 

3) NL Join의 가장 큰 특징은 랜덤 액세스(Random Access) 방식으로 데이터 읽는다는 것이다. 그리고 랜덤 액세스의 예로는 인덱스 스캔(Index Scan)이 있다. 즉, 인덱스 스캔(Index Scan)은 NL Join 방식으로 조인을 수행한다. 추가적으로 대량의 데이터를 랜덤 액세스로 접근하게 되면 많은 I/O가 발생하여 성능상 좋지 않기 때문에 무조건 랜덤 액세스가 좋은 게 아님을 인지!!

 

4) NL Join 기법은 조인이 성공하면 바로 조인 결과를 사용자에게 보여 줌. 따라서 결과를 가능한 한 빨리 화면에 보여줘야 하는 온라인 프로그램에 적당한 조인 기법이다.

 

5) NL Join 이외의 Sort Merge Join과 Hash Join은 조인 칼럼의 인덱스(Index)가 없어도 사용 가능하며, 메모리에 적재할 수 있는 크기보다 더 커지면 임시 영역(디스크)을 사용한다는 특징이 있다.

 

 

 

Sort Merge Join 수행 원리

1) 다음은 Sort Merge Join의 수행 방식을 단계별로 나타낸 것입니다.

① 선행 테이블에서 주어진 조건을 만족하는 행을 찾는다.
② 해당 행들에 대해서, 선행 테이블의 조인 키(칼럼)를 기준으로 데이터를 정렬.
③ 후행 테이블에서 주어진 조건을 만족하는 행을 찾는다.
④ 해당 행들에 대해서, 후행 테이블의 조인 키(칼럼)를 기준으로 데이터를 정렬.
⑤ JOIN을 수행.
⑥ 조인에 성공하면 추출버퍼에 넣는다.

 

2) Sort Merge Join은 NL Join에서의 랜덤 액세스로는 부담이 되던 넓은 범위의 데이터를 처리할 때 이용되던 조인 기법으로, 주로 Full Table Scan 방식으로 데이터를 읽는 기법이다. 정리하자면, Sort Merge Join은 조인 칼럼의 인덱스가 존재하지 않을 경우에도 사용할 수 있는 특징이 있다.

 

3) 이처럼 Sort Merge Join은 조인 칼럼을 기준으로 데이터를 정렬한 후 조인을 수행한다는 특징이 있지만, 조인 작업을 위해 항상 정렬 작업이 발생하는 것은 아니다. 예를 들어, 조인할 테이블 중에서 이미 앞 단계의 작업을 수행하는 도중에 정렬 작업이 미리 수행되었다면 조인을 위한 정렬 작업은 발생하지 않을 수 있다.

 

4) 정렬할 데이터가 많아 메모리에서 모든 정렬 작업을 수행하기 어려운 경우에는 임시 영역(디스크)을 사용하기 때문에 성능이 떨어질 수 있다. 그래서 일반적으로 대량의 조인 작업에서 정렬 작업을 필요로 하는 Sort Merge Join 보다는 CPU 작업 위주로 처리하는 Hash Join이 성능상 유리하다.

 

5) Sort Merge Join은 Hash Join과는 달리 동등 조인(Equi Join) 뿐만 아니라 Non-Equi Join에 대해서도 조인 작업이 가능하다. (동등&비동등 조인은 여기를 클릭하여 확인)

 

 

 

Hash Join 수행 원리

1) 다음은 Hash Join의 수행 방식을 단계별로 나타낸 것입니다.

① 선행 테이블에서 주어진 조건을 만족하는 행을 찾는다.
② 해당 행들에 대해서, 선행 테이블의 조인 키(칼럼)를 기준으로 Hash 함수를 적용하여 해쉬 테이블을 생성.
③ 후행 테이블에서 주어진 조건을 만족하는 행을 찾는다.
④ 해당 행들에 대해서, 후행 테이블에 Hash 함수를 적용하여 선행 테이블의 해쉬 테이블에서 맞는 버킷을 찾음. 
⑤ JOIN을 수행 & 조인에 성공하면 추출버퍼에 넣는다.
⑥ 후행 테이블의 조건을 만족하는 모든 행에 대해서 3~5번 반복.

 

2) 해쉬 조인(Hash Join)을 수행할 테이블의 조인 칼럼을 기준으로 Hash 함수를 적용하여 서로 동일한 Hash 값을 갖는 것들 사이에서 실제 값이 같은지를 비교하면서 조인을 수행하는 방식이다.

 

해쉬 함수를 적용한 실제 값은 어떤 값으로 해슁(Hashing)될 지 예측할 수 없다. 하지만 해쉬 함수가 적용될 때 동일한 값은 항상 같은 값으로 해슁됨이 보장된다. 하지만 해쉬 함수를 적용할 때 보다 큰 값이 항상 큰 값으로 해슁되고 작은 값이 항상 작은 값으로 해슁된다는 보장은 없다. 그렇기 때문에 Hash Join은 동등 조인(Equi join)에서만 사용할 수 있다는 특징이 있다.

 

3) CPU 작업 위주로 데이터 처리하는 Hash Join은 NL Join의 랜덤 액세스 문제점과 Sort Merge Join의 문제점인 정렬 작업의 부담을 해결 위한 대안으로 등장하였다.

 

4) Hash Join은 조인 작업을 수행하기 위해 ‘해쉬 테이블’을 메모리에 생성한다. → Hash Table의 크기가 메모리에 적재할 수 있는 크기보다 더 커지면 임시 영역(디스크)에 해쉬 테이블을 저장함. 그렇기 때문에 Hash Join을 할 때는 결과 행의 수가 적은 테이블을 선행 테이블로 사용하는 것이 좋다. 선행 테이블의 결과를 완전히 메모리에 저장할 수 있다면 임시 영역에 저장하는 작업이 발생하지 않기도 하고 CPU연산을 조금 덜 수행할 수 있기 때문

 

5) Hash Join에서는 선행 테이블을 이용하여 먼저 해쉬 테이블을 생성한다고 해서 선행 테이블을 Build Input이라고도 하며, 후행 테이블은 만들어진 해쉬 테이블에 대해 해쉬 값의 존재여부를 검사한다고 해서 Prove Input이라고도 한다.

 

 

 

NL Join, Sort Merge Join, Hash Join의 공통점

위 3개의 조인은 모두 조인에 성공하면 결과를 추출버퍼에 넣는다는 공통점이 있다. 추출버퍼는 SQL문의 실행결과를 보관하는 버퍼로서 일정 크기를 설정하여 추출버퍼에 결과가 모두 차거나 더 이상 결과가 없어서 추출버퍼를 채울 것이 없으면 결과를 사용자에게 반환한다. ※추출버퍼: 운반단위, Array Size, Prefetch Size라고도 함. 

 

 

출처 : https://hoon93.tistory.com/46