공부는 해도 해도 끝이 없구먼

Nested Loop Join

1. 기본 메커니즘

아래는 중첩 루프문(Nested Loop)의 수행 구조이다.

for(i=0; i<100; i++){
    for(j=0; j<100; j++){
    }
}

뒤에서 설명할 Sort Merge Join과 Hash Join도 각각 소트 영역(Sort Area)과 해시 영역(Hash Area)에 가공해 둔 데이터를 이용한다는 점만 다를 뿐 기본적인 조인 프로세싱은 다르지 않다.

단, 기억할 것은, 각 단계를 완료하고 나서 다음 단계로 넘어가는 게 아니라 한 레코드씩 순차적으로 진행한다는 사실이다.

2. NL Join 수행 과정 분석

프로그래밍을 할 줄 아는 분들이면 매커니즘은 자연스럽게 넘어갈 것이라 사료되는데,

아래의 조인문에서 조건절 비교 순서를 분석해 보자.

/*Data ON-AIR 참조*/

select /*+ ordered use_nl(e) */ e.empno, e.ename, d.dname, e.job, e.sal 
from dept d, emp e 
where e.deptno = d.deptno …………… 
① and d.loc = 'SEOUL' …………… 
② and d.gb = '2' …………… 
③ and e.sal >= 1500 …………… 
④ order by sal desc;

인덱스 상황은 다음과 같다.

* pk_dept : dept.deptno 
* dept_loc_idx : dept.loc 
* pk_emp : emp.empno 
* emp_deptno_idx : emp.deptno 
* emp_sal_idx : emp.sal

조건절 비교 순서, 그리고 위 5개 인덱스 중 어떤 것이 사용될지도 함께 고민해 보면 재밌을 것이다.

Execution Plan --------------------------------------------------- 0 
SELECT STATEMENT 1 0 SORT ORDER BY 2 1 NESTED LOOPS 3 2 
TABLE ACCESS BY INDEX ROWID DEPT 4 3 INDEX RANGE SCAN DEPT_LOC_IDX 5 2 
TABLE ACCESS BY INDEX ROWID EMP 6 5 INDEX RANGE SCAN EMP_DEPTNO_IDX

사용되는 인덱스 : dept_loc_idx, emp_deptno_idx

조건절 비교순서 : ② → ③ → ① → ④ 

실행계획을 해석할 때, 형제(Sibling) 노드 간에는 위에서 아래로 읽는다.

부모-자식(Parent-Child) 노드 간에는 안쪽에서 바깥쪽으로, 즉 자식 노드부터 읽는다.

위 실행계획의 실행 순서를 나열하면 다음과 같다.

1. dept_loc_idx 인덱스 범위 스캔(ID = 4)

2. 인덱스 rowid로 dept 테이블 액세스(ID = 3)

3. emp_deptno_idx 인덱스 범위 스캔(ID = 6)

4. 인덱스 rowid로 emp 테이블 액세스(ID = 5)

5. sal 기준 내림차순(desc) 정렬(ID = 1)

아래는 도식화한 NL Join 실행계획이다.

형제 노드 간에는 좌에서 우로 읽고,

부모-자식 노드 간에는 아래에서 위쪽으로, 즉 자식 노드부터 읽는다.

3. NL Join의 특징

- Random 액세스 위주의 조인 방식

- 조인을 한 레코드씩 순차적으로 진행

즉 NL Join은 소량의 데이터나 부분 범위 처리가 가능한 온라인 트랜잭션 환경에 적합한 조인 방식이라고 할 수 있다.

Sort Merge Join

NL Join은 인덱스에 조인 컬럼을 선두로 가지고 있는지가 매우 중요하다.

선두에 조건이 없으면 옵티마이저는 Sort Merge Join이나, Hash Join을 고려하게 된다.

이 중 Sort Merge Join의 Sort는 양쪽 집합을 조인 컬럼 기준으로 정렬함이고, Merge는 정렬된 양쪽 집합을 Merge 함을 의미한다.

1. 기본 메커니즘

아래는 dept 테이블을 기준으로 emp 테이블을 조인할 경우 Sort Merge Join을 이행하라는 힌트의 예제이다.

/*Data ON-AIR 참조*/

select /*+ ordered use_merge(e) */ d.deptno, d.dname, e.empno, e.ename 
from dept d, emp e 
where d.deptno = e.deptno 
Execution Plan ------------------------------------------------------------- 0 
SELECT STATEMENT Optimizer=CHOOSE (Cost=11 Card=654 Bytes=35K) 1 0 
MERGE JOIN (Cost=11 Card=654 Bytes=35K) 2 1 
SORT (JOIN) (Cost=6 Card=654 Bytes=14K) 3 2 
TABLE ACCESS (FULL) OF 'DEPT' (Cost=2 Card=654 Bytes=14K) 4 1 
SORT (JOIN) (Cost=5 Card=327 Bytes=11K) 5 4 
TABLE ACCESS (FULL) OF 'EMP' (Cost=2 Card=327 Bytes=11K)

아래는 도식화된 Sort Merge 수행 과정이다.

실제 조인 수행 과정이 NL Join과 크게 다르지 않다. outer 집합과 inner 집합을 미리 정렬해 둔다는 점만 다르다. 다시 말하지만, 양쪽 집합을 먼저 정렬해 두었기 때문에 위와 같은 처리 로직이 가능하다.

2. Sort Merge Join의 특징

- 조인 하기 전에 양쪽 집합을 정렬한다.

- 부분적으로 부분 범위처리가 가능하다.

- 테이블별 검색 조건에 의해 전체 일량이 좌우된다.

- 스캔 위주의 조인 방식이다.

  - >Inner 테이블 반복 엑세스를 하지 않아서 Random 엑세스가 발생되지 않으나, 전혀없지는 않아서 랜덤 엑세스가 많으면 안 쓰는게 낫다.

Hash Join

1. 기본 메커니즘

Hash Join은 NL Join이나 Sort Merge Join이 효과적이지 못한 상황을 해결하고자 나온 조인 방식이다.

Hash Join 힌트를 사용해 보자.

/*Data ON-AIR 참조*/

select /*+ ordered use_hash(e) */ d.deptno, d.dname, e.empno, e.ename 
from dept d, emp e 
where d.deptno = e.deptno 
Execution Plan ------------------------------------------------------------- 0 
SELECT STATEMENT Optimizer=CHOOSE (Cost=5 Card=654 Bytes=35K) 1 0 
HASH JOIN (Cost=5 Card=654 Bytes=35K) 2 1 
TABLE ACCESS (FULL) OF 'DEPT' (Cost=2 Card=654 Bytes=14K) 3 1 
TABLE ACCESS (FULL) OF 'EMP' (Cost=2 Card=327 Bytes=11K)

Hash Join은 둘 중 작은 집합(Build Input)을 읽어 해시 영역(Hash Area)에 해시 테이블(= 해시 맵)을 생성하고,

반대쪽 큰 집합(Probe Input)을 읽어 해시 테이블을 탐색하면서 조인하는 방식이다.

각 단계별로 살펴보자.

• 1단계 : 두 집합 중 작다고 판단되는 집합을 읽어 해시 함수를 이용하여 해시 버킷으로 구성된 배열인 해시 테이블을 만든다. 해시 함수에서 리턴받은 해시 값이 같은 데이터를 같은 해시 버킷에 체인(연결 리스트)으로 연결한다.
• 2단계 : 해시 테이블 생성을 위해 선택되지 않은 나머지 데이터 집합(Probe Input)을 스캔한다.
• 3단계 : Probe Input에서 읽은 데이터로 해시 테이블을 탐색할 때도 해시 함수를 사용한다. 즉, 해시 함수에서 리턴받은 버킷 주소로 찾아가 해시 체인을 스캔하면서 데이터를 찾는다.

NL Join처럼 조인 과정에서 발생하는 Random 액세스 부하가 없고 Sort Merge Join처럼 조인 전에 미리 양쪽 집합을 정렬하는 부담도 없다. 다만, 해시 테이블을 생성하는 비용이 수반된다. 따라서 Build Input이 작을 때 효과적이다. Build Input이 대용량 테이블이면 디스크에 W/R 하는 과정을 거치기 때문에 성능이 저하된다. Build Input으로 선택된 테이블이 작은 것도 중요하지만  해시 키값으로 사용되는 컬럼에 중복값이 없을 때 효과적이다.

2. Build Input이 가용 메모리 공간을 초과할 때 처리 방식 

 In-Memory Hash Join이 불가능할 때 DBMS는 ‘Grace Hash Join’이라고 알려진 조인 알고리즘을 사용하는데,

두 단계로 나누어 진행된다.

1) 파티션 단계

조인되는 양쪽 집합 모두 조인 칼럼에 해시 함수를 적용하고, 반환된 해시 값에 따라 동적으로 파티셔닝을 실시한다. 독립적으로 처리할 수 있는 여러 개의 작은 서브 집합으로 분할함으로써 파티션 짝(pair)을 생성하는 단계다. 파티션 단계에서 양쪽 집합을 모두 읽어 디스크 상의 Temp 공간에 일단 저장해야 하므로 In-Memory Hash Join보다 성능이 크게 떨어지게 된다.

2) 조인 단계

파티션 단계가 완료되면 각 파티션 짝(pair)에 대해 하나씩 조인을 수행한다. 이때, 각각에 대한 Build Input과 Probe Input은 독립적으로 결정된다. 즉, 파티션하기 전 어느 쪽이 작은 테이블이었는지에 상관없이 각 파티션 짝(pair)별로 작은 쪽 파티션을 Build Input으로 선택해 해시 테이블을 생성한다. 해시 테이블이 생성되고 나면 반대 쪽 파티션 로우를 하나씩 읽으면서 해시 테이블을 탐색하며, 모든 파티션 짝에 대한 처리가 완료될 때까지 이런 과정을 반복한다. Grace Hash Join은 한마디로, 분할 정복(Divide & Conquer) 방식이라고 말할 수 있다. 실제로는 DBMS 벤더마다 조금씩 변형된 형태의 하이브리드(Hybrid) 방식을 사용하지만 두 개의 큰 테이블을 Hash Join하는 기본 알고리즘은 Grace Hash Join에 바탕을 두고 있다.

3. Build Input이 해시 키 값에 중복이 많을 때 발생하는 비효율

앞서 설명하였듯이 해시 알고리즘의 성능은 해시 충돌을 얼마나 최소화할 수 있느냐에 달렸으며, 이를 방지하려면 그만큼 많은 해시 버킷을 할당해야만 한다. DBMS는 가능하면 충분히 많은 개수의 버킷을 할당함으로써 버킷 하나당 하나의 키 값만 갖게 하려고 노력한다. 그런데 해시 버킷을 아무리 많이 할당하더라도 해시 테이블에 저장할 키 컬럼에 중복 값이 많다면 하나의 버킷에 많은 엔트리가 달릴 수 밖에 없다. 그러면 해시 버킷을 아무리 빨리 찾더라도 해시 버킷을 스캔하는 단계에서 많은 시간을 허비하기 때문에 탐색 속도가 현저히 저하된다. Build Input의 해시 키 컬럼에는 중복 값이 (거의) 없어야 Hash Join이 빠르게 수행될 수 있음을 이해할 것이다.

4. Hash Join 사용기준

아래는 Hash Join 성능을 좌우하는 두 가지 포인트이다.

• 한 쪽 테이블이 가용 메모리에 담길 정도로 충분히 작아야 함
• Build Input 해시 키 칼럼에 중복 값이 거의 없어야 함

아래는 Hash Join 이 효과적으로 사용될 경우이다.

• 조인 칼럼에 적당한 인덱스가 없어 NL Join이 비효율적일 때
• 조인 칼럼에 인덱스가 있더라도 NL Join 드라이빙 집합에서 Inner 쪽 집합으로의 조인 액세스량이 많아 Random 액세스 부하가 심할 때
• Sort Merge Join 하기에는 두 테이블이 너무 커 소트 부하가 심할 때
• 수행빈도가 낮고 조인할 때

Hash Join은 앞선 다른 조인과 다르게 영구적이지 못하고 소멸되는 치명적인 단점이 있어 수행빈도가 높은 쿼리에 Hash Join을 많이 사용한다면 CPU/Memory 작별을 고해야 할지 모른다.

즉 'Hash Join'은 수행 빈도가 낮고, 쿼리 수행 시간이 오래 걸리는 대용량 테이블을 조인할 경우에 주로 사용해야 한다.