1. Nested Loop Join
가. 기본 메커니즘 : 중첩 루프문(Nested Loop)과 같음
< C, JAVA >
for(i=0; i<100; i++){ -- outer loop
for(j=0; j<100; j++){ -- inner loop
// Do Anything ...
}
}
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;
-- 아래 쿼리와 100% 같은 순서로 데이터를 액세스 하고 출력 순서도 같음
[예제] 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)
나. 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
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) 노드 간에는 안쪽에서 바깥쪽으로(자식 노드 먼저) 읽는다
- 실행계획 실행순서 (텍스트)
- ID=4 DEPT_LOC_IDX 인덱스 범위 스캔
- ID=3 인덱스 ROWID 로 DEPT 테이블 액세스
- ID=6 EMP_DEPTNO_IDX 인덱스 범위 스캔
- ID=5 인덱스 ROWID 로 EMP 테이블 액세스
- ID=1 SAL 기준 내림차순 정렬
- 실행계획 실행순서 (그림)
- 형제 노드 간에는 좌에서 우로, 부모-자식 노드 간에는 아래에서 위로 읽는다
- 정렬을 제외하고 한 레코드씩 순차적으로 아래 단계를 진행
- DEPT.LOC = 'SEOUL' 검색을 위해서 DEPT_LOC_IDX 인덱스 범위 스캔
- DEPT_LOC_IDX 에서 ROWID 를 얻어 DEPT 테이블에 DEPT.GB = '2' 필터 조건을 만족하는 레코드 찾음
- DEPT 테이블에서 읽은 DEPTNO 값으로, 조인 조건을 만족하는 EMP 쪽 레코드 검색을 위해서 EMP_DEPTNO_IDX 인덱스 범위 스캔
- EMP_DEPTNO_IDX 에서 ROWID 를 얻어 EMP 테이블에 SAL >= 1500 필터 조건을 만족하는 레코드를 찾음
- 1~4 과정을 통과한 레코드를 SAL 칼럼 기준 내림차순 정렬 후 결과 리턴
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)
 |
 |
- 11, 19, 31, 32 는 스캔할 데이터가 더 있는지 확인하는 one-plus 스캔을 표시
- (X) 는 테이블 필터 조건에 의해 걸러진 경우, (O) 는 그렇지 않은 경우
- DEPT_LOC_IDX 인덱스 스캔 양에 따라 전체 일량이 좌우 됨 (단일 칼럼 인덱스를 6(5+1) 건 읽고 테이블 Random 액세스 발생) <부하지점1>
- DEPT.GB = '2' 에 의해 필터 되는 비율이 높다면 DEPT_LOC_IDX 에 GB 컬럼 추가 고려
- DEPT 의 최종 레코드 수 만큼 EMP_DEPTNO_IDX 인덱스 Random 액세스 발생 <부하지점2>
- EMP_DEPTNO_IDX 인덱스 읽은 후 EMP 테이블 Random 액세스 <부하지점3>
- EMP.SAL >= 1500 에 의해 필터 되는 비율이 높다면 EMP_DEPTNO_IDX 에 SAL 컬럼 추가 고려
- OLTP 에서는 NL JOIN 먼저 고려 하고 이후 HASH JOIN, SORT MERGE JOIN 검토
- 과도한 Random 액세스가 발생하는 지점 개선 (조인 순서 변경, 인덱스 칼럼 구성 변경, 다른 인덱스 사용)
다. NL Join의 특징
- 대부분 DBMS 가 블록(페이지) 단위로 I/O 수행 (하나의 레코드를 위해서 블록을 액세스 발생)
- Random 액세스 위주의 조인 방식 (인덱스가 완벽해도 대량 데이터 조인시 비효율)
- 조인이 한 레코드씩 순차적으로 진행 (대용량 데이터 처리시 치명적, 하지만 부분범위 처리시 빠른 응답 속도 보장, 선행 테이블의 처리 범위가 전체 일량 결정)
- 인덱스 구성 전략이 중요
- NL Join 은 소량 데이터 처리, 부분범위처리가 가능한 온라인 트랜잭션 환경에 적합한 조인 방식
2. Sort Merge Join
- NL Join 은 조인 칼럼을 선두로 갖는 인덱스가 필요, 없으면 Sort Merge Join 혹은 Hash Join 수행
- Sort Merge Join 의 두 단계
- 소트 단계 : 양쪽 집합을 조인 칼럼 기준으로 정렬한다. (Outer 테이블은 조인 칼럼에 인덱스가 있을 경우 패스)
- 머지 단계 : 정렬된 양쪽 집합을 서로 머지(Merge) 한다.
- Oracle 은 조인 연산자와 제한이 없지만, SQL Server 는 '=' 일 때만 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]))
- Inner 집합인 emp 테이블이 정렬돼 있기 때문에 조인에 실패하는 레코드를 만나는 순간 멈출 수 있음
- 정렬된 emp 에서 스캔 시작점을 찾기 위해 매번 탐색하지 않아도 됨 (직전에 멈춘 지점을 기억 했다가 거기 부터 스캔)
- 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
나. Sort Merge Join의 특징
- 조인 하기 전에 양쪽 집합을 정렬한다
- 양쪽 집합이 조인 칼럼 기준으로 정렬된 후 조인 (Random 액세스 위주의 NL Join 의 비효율 대안)
- 정렬해야 할 집합이 초대용량 테이블이면 정렬 자체가 큰 비용을 수반 하게 됨 (비효율)
- 일반 인덱스나 클러스터형 인덱스처럼 미리 정렬된 오브젝트를 이용하면 정렬 없이 바로 조인 가능 (효율)
- 부분적으로, 부분범위처리가 가능하다
- Outer 집합이 조인 칼럼 순으로 미리 정렬된 상태에서 사용자가 일부 로우만 Fetch 하다 멈출 수 있음
- 테이블별 검색 조건에 의해 전체 일량이 좌우된다
- NL Join : Outer 집합에서 조인 대상이 되는 건수에 의해 전체 일량이 결정 (Outer 집합의 매 건마다 Inner 집합을 탐색)
- 테이블 별 검색 조건에 (각 집합의 크기) 의해 전체 일량이 결정
- 스캔(Scan) 위주의 조인 방식이다
- NL Join : Random 액세스 위주의 조인 방식
- Inner 테이블을 반복 Random 테이블 액세스 안함
- 각 테이블 검색 조건에 해당하는 대상 집합을 찾을 때 인덱스를 이용한 Random 테이블 액세스 발생 가능
3. Hash Join
가. 기본 메커니즘
- NL Join 과 Sort Merge Join 이 효과적이지 못할 상황 해결
- NL Join 처럼 조인 과정에서 발생하는 Random 액세스 부하가 없음
- Sort Merge 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)을 읽어 해시 테이블을 탐색하면서 조인하는 방식
해시 함수
- 해시 함수는, 출력 값을 미리 알 순 없지만, 같은 입력값에 대해 같은 출력값을 보장하는 함수.
- '해시 충돌' : 다른 입력값 ==> 같은 출력값 상황 (입력값이 다른 엔트리가 한 해시 버킷에 담길 수 있음)
- 조인단계
- 1단계 : 집합 중 작다고 판단되는 집합을 읽어 해시 테이블 생성 (Build Input)
- 해시 함수를 이용해 해시 테이블 생성
- 해시 테이블은 해시 버킷으로 구성된 배열 (해시 함수에서 리턴받은 해시 값이 같은 데이터를 같은 해시 버킷에 체인으로 연결)
- 2단계 : Probe Input을 스캔
- 3단계 : 해시 테이블 탐색
- Probe Input 에서 읽은 데이터로 해시 테이블을 탐색할 때도 해시 함수 사용
- 해시 함수에서 리턴 받은 버킷 주소로 찾아가 해시 체인을 스캔
- 해시 테이블 생성 비용 있음 (Build Input 이 작을 때 유리)
- 해시 키 값으로 사용되는 칼럼에 중복 값이 거의 없을때 유리
- 해시 테이블 만드는 단계는 전체범위처리 지만, 반대쪽 Probe Input을 스캔하는 단계는 부분범위 처리 가능
- 파티션 단계
- 조인되는 양쪽 집합 모두 조인 칼럼에 해시 함수를 적용 후, 반환된 해시 값에 따라 동적으로 파티셔닝
- 독립적으로 처리할수 있는 여러 개의 작은 서브 집합으로 분할 - 파티션 짝(Pair) 생성
- 디스크 상의 Temp 공간에 일단 저장 해야 하므로 In-Memory Hash Join 보다 성능이 크게 떨어짐
- 조인 단계
- 파티션 짝(Pair)에 대해 하나씩 조인 수행
- Build Input 과 Probe Input 은 원래 테이블 크기와 관계 없이 작은 쪽으로 해시 테이블 생성
- 해시 테이블이 생성된 후 Probe Input 을 하나씩 읽으며 해시 테이블 탐색 (반복)
- 분할-정복(Divide-Conquer) 방식
- Recursive Hash Join(=Nested-loops Hash Join)
- 파티션 짝(Pair)끼리 조인을 수행하려고 '작은 파티션'을 메모리에 로드하는 과정에서 메모리가 부족한 경우 추가적인 파티셔닝 수행
- 해시 알고리즘의 성능 : 해시 충돌 최소화
- DBMS는 가능하면 충분히 많은 개수의 버킷을 할당함으로써 버킷 하나당 하나의 키 값만 갖게 하려고 노력함
- 해시 테이블에 저장할 키 칼럼에 중복 값이 많다면 하나의 버킷에 많은 엔트리가 달리게 되고 이는 해시 버킷 스캔 시간을 지연 시킴
라. Hash Join 사용기준
- 성능 키 포인트
- 한 쪽 테이블이 가용 메모리에 담길 정도로 충분히 작아야 함
- Build Input 해시 키 칼럼에 중복 값이 거의 없어야 함
- 선택 기준
- NL Join 이 비효율적일 때 (Table Full Scan)
- NL Join 드라이빙 집합에서 Inner 쪽 집합으로의 조인 액세스량이 많아 Random 액세스 부하가 심할 때
- Sort Merge Join 하기에는 테이블이 너무 커 소트 부하가 심할 때
- 수행 빈도가 낮고 쿼리 수행 시간이 오래 걸리는 대용량 테이블을 조인할 때 (혼자 쓰는 해시 테이블 만드는 부하 고려)
Hash Join
1. 수행 빈도가 낮고
2. 쿼리 수행
3. 대용량 테이블을 조인할 때(배치, DW, OLAP)
4. 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
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
가. Scalar Subquery의 캐싱 효과
- Scalar Subquery 사용시 내부적으로 캐시를 생성하고, 입력/출력 값을 저장
- 같은 입력 값이 들어오면 Subquery 실행하지 않고 캐싱된 출력값 반환, 다른 입력 값이 들어오면 Subquery 실행후 출력값 반환 및 저장
-- 출력 값 : d.dname
-- 입력 값 : e.empno
select empno, ename, sal, hiredate
, (select d.dname from dept d where d.deptno = e.deptno) dname
from emp e where sal >= 2000
- 입력 값과 출력 값을 빠르게 저장하고 찾기 위해 해싱 알고리즘이 사용 되므로 입력 값의 종류가 소수 일때 캐싱 효과를 얻음 (해시 충돌)
- 입력 값의 종류가 많을 경우 캐시 확인 비용으로 성능 저하 됨
- SQL Server 는 2000 버전 까지 이 기능이 동작하고, 2005 버전 부터 기능이 없어짐
나. 두 개 이상의 값을 리턴하고 싶을 때
- 사원(emp) 테이블 Full Scan 비효율
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