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) 노드 간에는 안쪽에서 바깥쪽으로(자식 노드 먼저) 읽는다
• 실행계획 실행순서 (텍스트)
  1. ID=4 DEPT_LOC_IDX 인덱스 범위 스캔
  2. ID=3 인덱스 ROWID 로 DEPT 테이블 액세스
  3. ID=6 EMP_DEPTNO_IDX 인덱스 범위 스캔
  4. ID=5 인덱스 ROWID 로 EMP 테이블 액세스
  5. ID=1 SAL 기준 내림차순 정렬
• 실행계획 실행순서 (그림)

• • 형제 노드 간에는 좌에서 우로, 부모-자식 노드 간에는 아래에서 위로 읽는다
  • 정렬을 제외하고 한 레코드씩 순차적으로 아래 단계를 진행
    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 칼럼 기준 내림차순 정렬 후 결과 리턴

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 수행 (하나의 레코드를 위해서 블록을 액세스 발생)

1. Random 액세스 위주의 조인 방식 (인덱스가 완벽해도 대량 데이터 조인시 비효율)
2. 조인이 한 레코드씩 순차적으로 진행 (대용량 데이터 처리시 치명적, 하지만 부분범위 처리시 빠른 응답 속도 보장, 선행 테이블의 처리 범위가 전체 일량 결정)
3. 인덱스 구성 전략이 중요

• NL Join 은 소량 데이터 처리, 부분범위처리가 가능한 온라인 트랜잭션 환경에 적합한 조인 방식

2. Sort Merge Join

• NL Join 은 조인 칼럼을 선두로 갖는 인덱스가 필요, 없으면 Sort Merge Join 혹은 Hash Join 수행
• Sort Merge Join 의 두 단계
  1. 소트 단계 : 양쪽 집합을 조인 칼럼 기준으로 정렬한다. (Outer 테이블은 조인 칼럼에 인덱스가 있을 경우 패스)
  2. 머지 단계 : 정렬된 양쪽 집합을 서로 머지(Merge) 한다.
• Oracle 은 조인 연산자와 제한이 없지만, SQL Server 는 '=' 일 때만 Sort Merge Join 수행

가. 기본 메커니즘

• 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 도식화

• • 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. 1단계 : 집합 중 작다고 판단되는 집합을 읽어 해시 테이블 생성 (Build Input)
     • 해시 함수를 이용해 해시 테이블 생성
     • 해시 테이블은 해시 버킷으로 구성된 배열 (해시 함수에서 리턴받은 해시 값이 같은 데이터를 같은 해시 버킷에 체인으로 연결)
  2. 2단계 : Probe Input을 스캔
  3. 3단계 : 해시 테이블 탐색
     • Probe Input 에서 읽은 데이터로 해시 테이블을 탐색할 때도 해시 함수 사용
     • 해시 함수에서 리턴 받은 버킷 주소로 찾아가 해시 체인을 스캔
• 해시 테이블 생성 비용 있음 (Build Input 이 작을 때 유리)
• 해시 키 값으로 사용되는 칼럼에 중복 값이 거의 없을때 유리
• 해시 테이블 만드는 단계는 전체범위처리 지만, 반대쪽 Probe Input을 스캔하는 단계는 부분범위 처리 가능

나. Build Input 이 가용 메모리 공간을 초과할 때 처리 방식 (In-Memory Hash Join, Grace Hash Join)

1. 파티션 단계
   • 조인되는 양쪽 집합 모두 조인 칼럼에 해시 함수를 적용 후, 반환된 해시 값에 따라 동적으로 파티셔닝
   • 독립적으로 처리할수 있는 여러 개의 작은 서브 집합으로 분할 - 파티션 짝(Pair) 생성
   • 디스크 상의 Temp 공간에 일단 저장 해야 하므로 In-Memory Hash Join 보다 성능이 크게 떨어짐
2. 조인 단계
   • 파티션 짝(Pair)에 대해 하나씩 조인 수행
   • Build Input 과 Probe Input 은 원래 테이블 크기와 관계 없이 작은 쪽으로 해시 테이블 생성
   • 해시 테이블이 생성된 후 Probe Input 을 하나씩 읽으며 해시 테이블 탐색 (반복)
   • 분할-정복(Divide-Conquer) 방식

• Recursive Hash Join(=Nested-loops Hash Join)
  • 파티션 짝(Pair)끼리 조인을 수행하려고 '작은 파티션'을 메모리에 로드하는 과정에서 메모리가 부족한 경우 추가적인 파티셔닝 수행

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

• 해시 알고리즘의 성능 : 해시 충돌 최소화
• DBMS는 가능하면 충분히 많은 개수의 버킷을 할당함으로써 버킷 하나당 하나의 키 값만 갖게 하려고 노력함
• 해시 테이블에 저장할 키 칼럼에 중복 값이 많다면 하나의 버킷에 많은 엔트리가 달리게 되고 이는 해시 버킷 스캔 시간을 지연 시킴

라. Hash Join 사용기준

• 성능 키 포인트
  • 한 쪽 테이블이 가용 메모리에 담길 정도로 충분히 작아야 함
  • Build Input 해시 키 칼럼에 중복 값이 거의 없어야 함
• 선택 기준
  • NL Join 이 비효율적일 때 (Table Full Scan)
  • NL Join 드라이빙 집합에서 Inner 쪽 집합으로의 조인 액세스량이 많아 Random 액세스 부하가 심할 때
  • Sort Merge Join 하기에는 테이블이 너무 커 소트 부하가 심할 때
  • 수행 빈도가 낮고 쿼리 수행 시간이 오래 걸리는 대용량 테이블을 조인할 때 (혼자 쓰는 해시 테이블 만드는 부하 고려)

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