1. Nested Loop Join
가. 기본 메커니즘
프로그래밍을 해 본 독자라면 누구나 아래 중첩 루프문(Nested Loop)의 수행 구조를 이해할 것이고, 그렇다면 Nested Loop Join(이하 NL Join)도 어렵지 않게 이해할 수 있다.
< C, JAVA > for(i=0; i<100; i++){ -- outer loop for(j=0; j<100; j++){ -- inner loop // Do Anything ... } }
위 중첩 루프문과 같은 수행 구조를 사용하는 NL Join이 실제 어떤 순서로 데이터를 액세스하는지 아래 PL/SQL문이 잘 설명해 준다.
begin for outer in (select deptno, empno, rpad(ename, 10) ename from emp) loop -- outer 루프 for inner in (select dname from dept where deptno = outer.deptno) loop -- inner 루프 dbms_output.put_line(outer.empno||' : '||outer.ename||' : '||inner.dname); end loop; end loop; end;
위 PL/SQL문은 아래 쿼리와 100% 같은 순서로 데이터를 액세스하고, 데이터 출력순서도 같다. 내부적으로(=Recursive하게) 쿼리를 반복 수행하지 않는다는 점만 다르다.
[예제] Oracle select /*+ ordered use_nl(d) */ e.empno, e.ename, d.dname from emp e, dept d where d.deptno = e.deptno select /*+ leading(e) use_nl(d) */ e.empno, e.ename, d.dname from dept d, emp e where d.deptno = e.deptno [예제] SQL Server select e.empno, e.ename, d.dname from emp e inner loop join dept d on d.deptno = e.deptno option (force order) select e.empno, e.ename, d.dname from emp e, dept d where d.deptno = e.deptno option (force order, loop join)
사실 뒤에서 설명할 Sort Merge Join과 Hash Join도 각각 소트 영역(Sort Area)과 해시 영역(Hash Area)에 가공해 둔 데이터를 이용한다는 점만 다를 뿐 기본적인 조인 프로세싱은 다르지 않다.
나. NL Join 수행 과정 분석
이제 NL Join의 기본 메커니즘을 이해했으므로 아래 조인문에서 조건절 비교 순서가 어떻게 되는지 분석해 보자.
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 인 것을 위 실행계획을 보고 알 수 있다. 그럼 조건비교 순서는? SQL 조건절에 표시한 번호로 ② → ③ → ① → ④ 순이다. 실행계획을 해석할 때, 형제(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)
위 실행계획을 그림으로써 표현해 보면 [그림 Ⅲ-4-26]과 같다.
[그림 Ⅲ-4-26]을 해석할 때는, 형제 노드 간에는 좌에서 우로 읽고, 부모-자식 노드 간에는 아래에서 위쪽으로, 즉 자식 노드부터 읽는다.
1. dept.loc = ‘SEOUL’ 조건을 만족하는 레코드를 찾으려고 dept_loc_idx 인덱스를 범위 스캔한다. 2. dept_loc_idx 인덱스에서 읽은 rowid를 가지고 dept 테이블을 액세스해 dept.gb = ‘2’ 필터 조건을 만족하는 레코드를 찾는다. 3. dept 테이블에서 읽은 deptno 값을 가지고 조인 조건을 만족하는 emp 쪽 레코드를 찾으려고 emp_deptno_idx 인덱스를 범위 스캔한다. 4. emp_deptno_idx 인덱스에서 읽은 rowid를 가지고 emp 테이블을 액세스해 sal >= 1500 필터 조건을 만족하는 레코드를 찾는다. 5. 1~4 과정을 통과한 레코드들을 sal 칼럼 기준 내림차순(desc)으로 정렬한 후 결과를 리턴한다.
여기서 기억할 것은, 각 단계를 완료하고 나서 다음 단계로 넘어가는 게 아니라 한 레코드씩 순차적으로 진행한다는 사실이다. 단, order by는 전체 집합을 대상으로 정렬해야 하므로 작업을 모두 완료하고서 다음 오퍼레이션을 진행한다. 아래는 SQL Server에서의 실행계획이다.
StmtText ------------------------------------------------------------- |--Sort(ORDER BY:([e].[sal] DESC)) |--Filter(WHERE:([emp].[sal] as [e].[sal]>=(1500))) |--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1003])) |--Nested Loops(Inner Join, OUTER REFERENCES:([d].[deptno])) | |--Filter(WHERE:([dept].[gb] as [d].[gb]='2')) | | |--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1000])) | | |--Index Seek(OBJECT:([dept].[dept_loc_idx] AS [d]), SEEK:([loc]='CHICAGO') ) | | |--RID Lookup(OBJECT:([dept] AS [d]), SEEK:([Bmk1000]=[Bmk1000]) ) | |--Index Seek(OBJECT:([emp].[emp_deptno_idx]), SEEK:([e].[deptno]=[dept].[deptno])) |--RID Lookup(OBJECT:([emp] AS [e]), SEEK:([Bmk1003]=[Bmk1003]) LOOKUP ORDERED FORWARD)
SQL Server에서 제공하는 그래픽 모드 실행계획은 [그림 Ⅲ-4-27]과 같다.
[그림 Ⅲ-4-28]을 보면 지금까지 설명한 NL Join의 수행 절차를 좀 더 명확히 이해할 수 있다.
11, 19, 31, 32는 스캔할 데이터가 더 있는지 확인하는 one-plus 스캔을 표시한 것이다. (O)는 테이블 필터 조건에 의해 레코드가 걸러지지 않은 것을 의미하고, 반대로 (X)는 테이블 필터 조건에 의해 걸러진 것을 의미한다. [그림 Ⅲ-4-28]을 보면서, dept_loc_idx 인덱스를 스캔하는 양에 따라 전체 일량이 좌우됨을 이해하기 바란다. 여기서는 단일 칼럼 인덱스를 ‘=’ 조건으로 스캔했으므로 비효율 없이 6(=5+1)건을 읽었고, 그만큼 테이블 Random 액세스가 발생했다. 우선 이 부분이 NL Join의 첫 번째 부하지점이다. 만약 dept 테이블로 많은 양의 Random 액세스가 있었는데 gb = ‘2’ 조건에 의해 필터링되는 비율이 높다면 어떻게 해야 할까? 이미 1장에서 배웠듯이 dept_loc_idx에 gb 칼럼을 추가하는 방안을 고려해야 한다. 두 번째 부하지점은 emp_deptno_idx 인덱스를 탐색하는 부분이며, Outer 테이블인 dept를 읽고 나서 조인 액세스가 얼만큼 발생하느냐에 의해 결정된다. 이것 역시 Random 액세스에 해당하며, [그림 Ⅲ-4-28]에서는 gb = ‘2’ 조건을 만족하는 건수만큼 3번의 조인시도가 있었다. 만약 emp_deptno_idx의 높이(height)가 3이면 매 건마다 그만큼의 블록 I/O가 발생하고, 리프 블록을 스캔하면서 추가적인 블록 I/O가 더해진다. 세 번째 부하지점은 emp_deptno_idx를 읽고 나서 emp 테이블을 액세스하는 부분이다. 여기서도 sal >= 1500 조건에 의해 필터링되는 비율이 높다면 emp_deptno_idx 인덱스에 sal 칼럼을 추가하는 방안을 고려해야 한다. OLTP 시스템에서 조인을 튜닝할 때는 일차적으로 NL Join부터 고려하는 것이 올바른 순서다. 우선, NL Join 메커니즘을 따라 각 단계의 수행 일량을 분석해 과도한 Random 액세스가 발생하는 지점을 파악한다. 조인 순서를 변경해 Random 액세스 발생량을 줄일 수 있는 경우가 있지만, 그렇지 못할 때는 인덱스 칼럼 구성을 변경하거나 다른 인덱스의 사용을 고려해야 한다. 여러 가지 방안을 검토한 결과 NL Join이 효과적이지 못하다고 판단될 때 Hash Join이나 Sort Merge Join을 검토한다.
다. NL Join의 특징
대부분 DBMS가 블록(또는 페이지) 단위로 I/O를 수행하는데, 하나의 레코드를 읽으려고 블록을 통째로 읽는 Random 액세스 방식은 설령 메모리 버퍼에서 빠르게 읽더라도 비효율이 존재한다. 그런데 NL Join의 첫 번째 특징이 Random 액세스 위주의 조인 방식이라는 점이다. 따라서 인덱스 구성이 아무리 완벽하더라도 대량의 데이터를 조인할 때 매우 비효율적이다. 두 번째 특징은, 조인을 한 레코드씩 순차적으로 진행한다는 점이다. 첫 번째 특징 때문에 대용량 데이터 처리 시 매우 치명적인 한계를 드러내지만, 반대로 이 두 번째 특징 때문에 아무리 대용량 집합이더라도 매우 극적인 응답 속도를 낼 수 있다. 부분범위처리가 가능한 상황에서 그렇다. 그리고 순차적으로 진행하는 특징 때문에 먼저 액세스되는 테이블의 처리 범위에 의해 전체 일량이 결정된다. 다른 조인 방식과 비교했을 때 인덱스 구성 전략이 특히 중요하다는 것도 NL Join의 중요한 특징이다. 조인 칼럼에 대한 인덱스가 있느냐 없느냐, 있다면 칼럼이 어떻게 구성됐느냐에 따라 조인 효율이 크게 달라진다. 이런 여러 가지 특징을 종합할 때, NL Join은 소량의 데이터를 주로 처리하거나 부분범위처리가 가능한 온라인 트랜잭션 환경에 적합한 조인 방식이라고 할 수 있다.
2. Sort Merge Join
NL Join은 조인 칼럼을 선두로 갖는 인덱스가 있는지가 매우 중요하다. 만약 조인 칼럼을 선두로 갖는 인덱스가 없으면 Outer 테이블에서 읽히는 건마다 Inner 테이블 전체를 스캔하기 때문이다. 그럴 때 옵티마이저는 Sort Merge Join이나 다음 절에서 설명할 Hash Join을 고려한다. Sort Merge Join은 이름이 의미하는 것처럼 두 테이블을 각각 정렬한 다음에 두 집합을 머지(Merge)하면서 조인을 수행한다. Sort Merge Join은 아래 두 단계로 진행된다.
① 소트 단계 : 양쪽 집합을 조인 칼럼 기준으로 정렬한다. ② 머지 단계 : 정렬된 양쪽 집합을 서로 머지(merge)한다.
만약 조인 칼럼에 인덱스가 있으면(Oracle의 경우 Outer 테이블에만 해당) ①번 소트 단계를 거치지 않고 곧바로 조인할 수도 있다. Oracle은 조인 연산자가 부등호이거나 아예 조인 조건이 없어도 Sort Merge Join으로 처리할 수 있지만, SQL Server는 조인 연산자가 ‘=’ 일 때만 Sort Merge Join을 수행한다는 사실에도 유념하기 바란다.
가. 기본 메커니즘
아래 SQL은 dept 테이블을 기준으로 emp 테이블과 조인할 때 Sort Merge Join 방식을 사용하라고 힌트로 지시하고 있다.
[예제] Oracle 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) [예제] SQL Server select d.deptno, d.dname, e.empno, e.ename from dept d, emp e where d.deptno = e.deptno option (force order, merge join) StmtText ------------------------------------------------------------- |--Merge Join(Inner Join, MANY-TO-MANY MERGE:([d].[deptno])=([e].[deptno])) |--Sort(ORDER BY:([d].[deptno] ASC)) | |--Table Scan(OBJECT:([SQLPRO].[dbo].[dept] AS [d])) |--Sort(ORDER BY:([e].[deptno] ASC)) |--Table Scan(OBJECT:([SQLPRO].[dbo].[emp] AS [e]))
Sort Merge Join의 수행 과정을 그림으로 도식화하면 [그림 Ⅲ-4-29]와 같다.
[그림 Ⅲ-4-29]에서 주목할 점은, Inner 집합인 emp 테이블이 정렬돼 있기 때문에 조인에 실패하는 레코드를 만나는 순간 멈출 수 있다는 사실이다. 예를 들어, deptno=10인 레코드를 찾기 위해 ①번 스캔을 진행하다가 20을 만나는 순간 멈춘다. 또 한 가지는, 정렬된 emp에서 스캔 시작점을 찾으려고 매번 탐색하지 않아도 된다는 점이다. 예를 들어, deptno=20인 레코드를 찾는 ②번 스캔은 ①번에서 스캔하다가 멈춘 지점을 기억했다가 거기서부터 시작하면 된다. Outer 집합인 dept 테이블도 같은 순서로 정렬돼 있기 때문에 가능한 일이다. 아래는 Sort Merge Join이 머지하는 방식을 pseudo 코드로 작성한 것이다.
Outer 집합(정렬된 dept)에서 첫 번째 로우 o를 가져온다. Inner 집합(정렬된 emp)에서 첫 번째 로우 i를 가져온다. loop 양쪽 집합 중 어느 것이든 끝에 도달하면 loop를 빠져나간다. if o = i 이면 조인에 성공한 로우를 리턴한다. inner 집합에서 다음 로우 i를 가져온다. else if o < i 이면 outer 집합에서 다음 로우 o를 가져온다. else (즉, o > i 이면) inner 집합에서 다음 로우 i를 가져온다. end if end loop
[그림 Ⅲ-4-29]와 위 pseudo 코드를 잘 살펴보면, 실제 조인 수행 과정이 NL Join과 크게 다르지 않다. outer 집합과 inner 집합을 미리 정렬해 둔다는 점만 다르다. 다시 말하지만, 양쪽 집합을 먼저 정렬해 두었기 때문에 위와 같은 처리 로직이 가능하다.
나. Sort Merge Join의 특징
Sort Merge Join은 다음과 같은 특징을 가진다.
NL Join은 정렬 없이 Outer 집합을 한 건씩 차례대로 조인을 진행하지만, Sort Merge Join은 양쪽 집합을 조인 칼럼 기준으로 정렬한 후에 조인을 시작한다. 대량 집합 조인은 Random 액세스 위주의 NL Join의 경우 비효율이 있고, 이 비효율을 줄이고자 나온 조인 방식이 Sort Merge Join이다. 만약 정렬해야 할 집합이 초대용량 테이블이면 정렬 자체가 큰 비용을 수반하기 때문에 성능 개선 효과를 얻지 못할 수도 있다. 하지만, 일반 인덱스나 클러스터형 인덱스처럼 미리 정렬된 오브젝트를 이용하면 정렬작업을 하지 않고 바로 조인을 수행할 수 있어 Sort Merge Join이 좋은 대안이 될 수 있다.
Sort Merge Join은 양쪽 집합을 정렬해야 함으로 부분범위처리가 불가능할 거 같지만, 부분적으로는 가능하다. Outer 집합이 조인 칼럼 순으로 미리 정렬된 상태에서 사용자가 일부 로우만 Fetch 하다가 멈춘다면 Outer 집합은 끝까지 읽지 않아도 되기 때문이다.
- 테이블별 검색 조건에 의해 전체 일량이 좌우된다.
NL Join은 Outer 집합의 매 건마다 Inner 집합을 탐색한다. Outer 집합에서 조인 대상이 되는 건수에 의해 전체 일량이 좌우되는 이유다. 그러나 Sort Merge Join은 두 집합을 각각 정렬한 후에 조인함으로 각 집합의 크기, 즉 테이블별 검색 조건에 의해 전체 일량이 좌우된다.
NL Join이 Random 액세스 위주의 조인 방식이라면 Sort Merge Join은 스캔 위주의 조인 방식이다. Inner 테이블을 반복 액세스하지 않으므로 머지 과정에서 Random 액세스가 발생하지 않는 것이다. 하지만, Random 액세스가 전혀 없는 것은 아니다. 각 테이블 검색 조건에 해당하는 대상 집합을 찾을 때 인덱스를 이용한 Random 액세스 방식으로 처리될 수 있고, 이때 발생하는 Random 액세스량이 많다면 Sort Merge Join의 이점이 사라질 수 있다.
3. Hash Join
가. 기본 메커니즘
Hash Join은 NL Join이나 Sort Merge Join이 효과적이지 못한 상황을 해결하고자 나온 조인 방식이다. 아래는 Oracle과 SQL Server 각각에서 Hash Join으로 유도했을 때의 실행계획이다.
[예제] Oracle 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) [예제] SQL Server select d.deptno, d.dname, e.empno, e.ename from dept d, emp e where d.deptno = e.deptno option (force order, hash join) StmtText ------------------------------------------------------------- |--Hash Match(Inner Join, HASH:([d].[deptno])=([e].[deptno])) |--Table Scan(OBJECT:([SQLPRO].[dbo].[dept] AS [d])) |--Table Scan(OBJECT:([SQLPRO].[dbo].[emp] AS [e]))
Hash Join은 둘 중 작은 집합(Build Input)을 읽어 해시 영역(Hash Area)에 해시 테이블(= 해시 맵)을 생성하고, 반대쪽 큰 집합(Probe Input)을 읽어 해시 테이블을 탐색하면서 조인하는 방식이다.([그림 Ⅲ-4-30] 참조)
해시 함수는, 출력값을 미리 알 순 없지만, 같은 입력값에 대해 같은 출력값을 보장하는 함수다. 다른 입력값에 대한 출력값이 같을 수는 있는데, 이를 ‘해시 충돌’이라고 한다. 해시 테이블을 만들 때 해시 충돌이 발생하면, 입력값이 다른 엔트리가 한 해시 버킷에 담길 수 있다. 이런 원리를 바탕으로 Hash Join 과정을 좀 더 자세히 살펴보자.
- 1단계 : 해시 테이블 생성두 집합 중 작다고 판단되는 집합을 읽어 해시 테이블을 만든다. 해시 테이블을 만들 때 해시 함수를 사용한다. 해시 테이블은 해시 버킷으로 구성된 배열이라고 생각하면 된다. 해시 함수에서 리턴받은 해시 값이 같은 데이터를 같은 해시 버킷에 체인(연결 리스트)으로 연결한다.
- 2단계 : Probe Input을 스캔해시 테이블 생성을 위해 선택되지 않은 나머지 데이터 집합(Probe Input)을 스캔한다.
- 3단계 : 해시 테이블 탐색Probe Input에서 읽은 데이터로 해시 테이블을 탐색할 때도 해시 함수를 사용한다. 즉, 해시 함수에서 리턴받은 버킷 주소로 찾아가 해시 체인을 스캔하면서 데이터를 찾는다.
Hash Join은, NL Join처럼 조인 과정에서 발생하는 Random 액세스 부하가 없고 Sort Merge Join처럼 조인 전에 미리 양쪽 집합을 정렬하는 부담도 없다. 다만, 해시 테이블을 생성하는 비용이 수반된다. 따라서 Build Input이 작을 때라야 효과적이다. 만약 Hash Build를 위해 가용한 메모리 공간을 초과할 정도로 Build Input이 대용량 테이블이면 디스크에 썼다가 다시 읽어 들이는 과정을 거치기 때문에 성능이 많이 저하된다. Build Input으로 선택된 테이블이 작은 것도 중요하지만 해시 키 값으로 사용되는 칼럼에 중복 값이 거의 없을 때라야 효과적이다. 이유는 잠시 후 자세히 설명한다. 해시 테이블을 만드는 단계는 전체범위처리가 불가피하지만, 반대쪽 Probe Input을 스캔하는 단계는 NL Join처럼 부분범위처리가 가능하다는 사실도 기억하자.
나. Build Input이 가용 메모리 공간을 초과할 때 처리 방식
Hash Join은 Hash Build를 위한 가용한 메모리 공간에 담길 정도로 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에 바탕을 두고 있다.
- Recursive Hash Join(=Nested-loops Hash Join)
디스크에 기록된 파티션 짝(pair)끼리 조인을 수행하려고 ‘작은 파티션’을 메모리에 로드하는 과정에서 또다시 가용 메모리를 초과하는 경우가 발생할 수 있다. 그럴 때는 추가적인 파티셔닝 단계를 거치게 되는데, 이를 ‘Recursive Hash Join’이라고 한다.
다. Build Input 해시 키 값에 중복이 많을 때 발생하는 비효율
잘 알다시피 해시 알고리즘의 성능은 해시 충돌(collision)을 얼마나 최소화할 수 있느냐에 달렸으며, 이를 방지하려면 그만큼 많은 해시 버킷을 할당해야만 한다. [그림 Ⅲ-4-30]에는 개념적으로 설명하기 위해 하나의 버킷에 여러 키 값이 달리는 구조로 표현하였지만, DBMS는 가능하면 충분히 많은 개수의 버킷을 할당함으로써 버킷 하나당 하나의 키 값만 갖게 하려고 노력한다. 그런데 해시 버킷을 아무리 많이 할당하더라도 해시 테이블에 저장할 키 칼럼에 중복 값이 많다면 하나의 버킷에 많은 엔트리가 달릴 수 밖에 없다. 그러면 해시 버킷을 아무리 빨리 찾더라도 해시 버킷을 스캔하는 단계에서 많은 시간을 허비하기 때문에 탐색 속도가 현저히 저하된다. Build Input의 해시 키 칼럼에는 중복 값이 (거의) 없어야 Hash Join이 빠르게 수행될 수 있음을 이해할 것이다.
라. Hash Join 사용기준
Hash Join 성능을 좌우하는 두 가지 키 포인트는 다음과 같다.
- 한 쪽 테이블이 가용 메모리에 담길 정도로 충분히 작아야 함
- Build Input 해시 키 칼럼에 중복 값이 거의 없어야 함
위 두 가지 조건을 만족할 때라야 Hash Join이 가장 극적인 성능 효과를 낼 수 있음을 앞에서 살펴보았다. 그러면 Hash Join을 언제 사용하는 것이 효과적인지 그 선택 기준을 살펴보자.
- 조인 칼럼에 적당한 인덱스가 없어 NL Join이 비효율적일 때
- 조인 칼럼에 인덱스가 있더라도 NL Join 드라이빙 집합에서 Inner 쪽 집합으로의 조인 액세스량이 많아 Random 액세스 부하가 심할 때
- Sort Merge Join 하기에는 두 테이블이 너무 커 소트 부하가 심할 때
- 수행빈도가 낮고 조인할 때
앞쪽 세 가지 사항은 앞에서 이미 설명한 내용이므로 생략하기로 하고, 마지막 항목을 강조하면서 Hash Join에 대한 설명을 마치려고 한다. Hash Join이 등장하면서 Sort Merge Join의 인기가 많이 떨어졌다고 했는데, 그만큼 Hash Join이 빠르기 때문이다. Hash Join이 워낙 빠르다 보니 모든 조인을 Hash Join으로 처리하려는 유혹에 빠지기 쉬운데, 이는 매우 위험한 생각이 아닐 수 없다. 수행시간이 짧으면서 수행빈도가 매우 높은 쿼리(→ OLTP성 쿼리의 특징이기도 함)를 Hash Join으로 처리한다면 어떤 일이 발생할까? NL Join에 사용되는 인덱스는 (Drop하지 않는 한) 영구적으로 유지되면서 다양한 쿼리를 위해 공유 및 재사용되는 자료구조다. 반면, 해시 테이블은 단 하나의 쿼리를 위해 생성하고 조인이 끝나면 곧바로 소멸하는 자료구조다. 따라서 수행빈도가 높은 쿼리에 Hash Join을 사용하면 CPU와 메모리 사용률을 크게 증가시킴은 물론, 메모리 자원을 확보하기 위한 각종 래치 경합이 발생해 시스템 동시성을 떨어뜨릴 수 있다. 따라서 Hash Join은 ①수행 빈도가 낮고 ②쿼리 수행 시간이 오래 걸리는 ③대용량 테이블을 조인할 때(→ 배치 프로그램, DW, OLAP성 쿼리의 특징이기도 함) 주로 사용해야 한다. OLTP 환경이라고 Hash Join을 쓰지 못할 이유는 없지만 이 세 가지 기준(①~③)을 만족하는지 체크해 봐야 한다
4. Scalar Subquery
쿼리에 내장된 또다른 쿼리 블록을 서브쿼리라고 하는데, 그 중에서 함수처럼 한 레코드당 정확히 하나의 값만을 리턴하는 서브쿼리를 ‘Scalar Subquery’라고 한다. Scalar Subquery는 주로 select-list에서 사용되지만 몇 가지 예외사항을 뺀다면 칼럼이 올 수 있는 대부분 위치에서 사용 가능하다.
select empno, ename, sal, hiredate ,(select d.dname from dept d where d.deptno = e.deptno) dname from emp e where sal >= 2000
Scalar Subquery를 사용한 위 쿼리 문장은 아래 Outer 조인문과 100% 같은 결과를 낸다. 즉, dept와 조인에 실패하는 emp 레코드가 있다면 dname으로 null 값이 출력된다.
select /*+ ordered use_nl(d) */ e.empno, e.ename, e.sal, e.hiredate, d.dname from emp e right outer join dept d on d.deptno = e.deptno where e.sal >= 2000
위에서 예시한 쿼리는 결과만 같은 것이 아니라 조인을 수행하는 처리 경로도 동일한데, NL 방식으로 수행되도록 힌트를 사용했기 때문이다. 다만 Scalar Subquery에는 내부적으로 캐싱 기법이 작용된다는 점이 다르고, 이를 이용한 튜닝이 자주 행해진다.
가. Scalar Subquery의 캐싱 효과
아래 쿼리는 위치가 ‘CHICAGO’인 부서(dept)만 대상으로 급여 수준을 집계하려는 것인데, 사원(emp) 테이블 전체를 다 읽어야 하는 비효율이 있다.
select d.deptno, d.dname, avg_sal, min_sal, max_sal from dept d right outer join (select deptno, avg(sal) avg_sal, min(sal) min_sal, max(sal) max_sal from emp group by deptno) e on e.deptno = d.deptno where d.loc = 'CHICAGO'
아래와 같이 바꿀 수 있으면 좋겠지만 스칼라 서브쿼리는 한 레코드당 하나의 값만 리턴한다는 특징 때문에 그럴 수가 없다.
select d.deptno, d.dname ,(select avg(sal), min(sal), max(sal) from emp where deptno = d.deptno) from dept d where d.loc = 'CHICAGO'
그렇다고 아래와 같이 쿼리한다면 emp에서 같은 범위를 반복적으로 액세스하는 비효율이 생긴다.
select d.deptno, d.dname ,(select avg(sal) from emp where deptno = d.deptno) avg_sal ,(select min(sal) from emp where deptno = d.deptno) min_sal ,(select max(sal) from emp where deptno = d.deptno) max_sal from dept d where d.loc = 'CHICAGO'
이럴 때, 아래 처럼 구하고자 하는 값들을 모두 결합하고서 바깥쪽 액세스 쿼리에서 substr 함수로 분리하는 방법이 유용하게 쓰인다.
[예제] Oracle select deptno, dname , to_number(substr(sal, 1, 7)) avg_sal , to_number(substr(sal, 8, 7)) min_sal , to_number(substr(sal, 15)) max_sal from ( select d.deptno, d.dname ,(select lpad(avg(sal), 7) || lpad(min(sal), 7) || max(sal) from emp where deptno = d.deptno) sal from dept d where d.loc = 'CHICAGO' ) [예제] SQL Server select deptno, dname , cast(substring(sal, 1, 7) as float) avg_sal , cast(substring(sal, 8, 7) as int) min_sal , cast(substring(sal, 15, 7) as int) max_sal from ( select d.deptno, d.dname ,(select str(avg(sal), 7, 2) + str(min(sal), 7) + str(max(sal), 7) from emp where deptno = d.deptno) sal from dept d where d.loc = 'CHICAGO' ) x