02 소트머지 조인

(1) 기본 메커니즘

• NL조인을 효과적으로 수행하려면, 조인 컬럼에 인덱스가 필요.
• 만약 적절한 인덱스가 없다면, Inner 테이블을 탐색할 때마다 반복적으로 Full Scan을 수행하므로 매우 비효율적.
• 옵티마이저는 소트머지조인이나 해시조인을 고려.

소트머지조인??

• 이름이 의미하는 것처럼 두 테이블을 각각 정렬한 다음에 두 집합을 머지 하면서 조인을 수행.
  • 소트 단계: 양쪽 집합을 조인 컬럼 기준으로 정렬.
  • 머지 단계: 정렬된 양쪽 집합을 서로 머지(Merge).
• Outer 루프와 Inner 루프가 Sort Area에 미리 정렬해 둔 자료구조를 이용한다는 점만 다를 뿐,
  실제 조인 오퍼레이션을 수행하는 과정은 NL 조인과 같음.
• Sort Area는 PGA 영역에 할당되므로 SGA를 경유해 인덱스와 테이블을 액세스할 때보다 훨씬 빠름.
• PGA는 프로세스만을 위한 독립적인 메모리 공간이어서 데이터를 읽을 때 래치 획득 과정이 없기 때문.

• 소트머지조인의 처리 메커니즘을 PL/SQL로 나타낸 것.

CREATE TABLE sorted_dept ( deptno primary key, dname  )
ORGANIZATION INDEX
AS 
SELECT deptno, dname FROM dept order by deptno
;

CREATE TABLE sorted_emp( empno , ename , deptno
  , constraint sorted_emp_pk primary key(deptno, empno) 
)
ORGANIZATION INDEX
AS 
SELECT empno, ename, deptno FROM emp order by deptno
;

BEGIN
  FOR outer IN (SELECT deptno, empno, rpad(ename, 10) ename FROM sorted_emp)
  LOOOP    -- outer 루프
    FOR inner IN (SELECT dname FROM sorted_dept WHERE deptno = outer.deptno)
    LOOP  -- inner 루프
      dbms_output.put_line(outer.empno||' : '||outer.ename||' : '||inner.dname);
    END LOOP;
  END LOOP;
END;
/

• 소트머지 조인은 use_merge힌트를 가지고 유도 가능.

SELECT /*+ ordered use_merge(e) */ d.deptno, d.dname, e.empno, e.ename
FROM   dept d, emp e
WHERE  d.deptno = e.deptno;

처리과정

1. Outer(=First)테이블인 dept를 deptno기준으로 정렬.
2. Inner(=Second)테이블인 emp를 deptno기준으로 정렬.
3. Sort Area에 정렬된 dept테이블을 스캔하면서, 정렬된 emp테이블과 조인.

• emp테이블이 정렬되어 있으므로 조인에 실패하는 레코드를 만나는 순간 멈출 수 있다.
• 스캔하다가 멈춘 시작점을 기억했다가 거기서부터 시작하면 되므로, 정렬된 emp에서 스캔 시작점을 찾으려고 매번 탐색하지 않아도 된다.
  

• M:M관계인 경우에서도 스캔도중 멈추는 것은 가능하나, 시작점을 찾는 일은 단순하지 않다.
• 시작점을 찾으려고 매번 이진탐색 수행하는 방법과 변수를 하나 더 선언해서 스캔했던 시작점을 기억하는 방법을 생각해 볼수 있음.
• Outer테이블까지 정렬한다는 사실을 통해 후자의 방법이 더 설득력이 있다고 보여진다.
  

(2) 소트머지 조인의 특징

• 실제 인덱스 오브젝트를 생성 하는건 아니지만, 조인을 위해서 실시간으로 인덱스를 생성하는것과 다름이 없다.
• 양쪽 집합을 정렬한 다음에는 NL 조인과 같은 방식으로 진행하지만 PGA 영역에 저장된 데이터를 이용하기 때문에 빠름.
  (SGA와 다르게 래치획득을 하지 않기 때문)
• 소트부하만 감수한다면, 건건이 버퍼캐시를 거치면서 조인하는 NL 조인보다 유리.
• 조인 컬럼에 대한 인덱스 유무에 따라 크게 영향을 받는 NL 조인에 비해 소트 머지 조인은 영향을 받지 않는다.
• 양쪽집합을 개별적으로 읽고 나서 조인 한다.
  : 조인 컬럼에 인덱스가 없는 상황에서 두 테이블을 독립적으로 읽어 조인 대상 집합을 줄일 수 있을 때 유리
• 스캔 위주의 액세스 방식을 사용하지만 모든 처리가 스캔 방식으로 이루어 진것은 아님.
  : 양쪽 소스 집합에서 정렬 대상 레코드를 찾는 작업만큼은 인덱스를 이용해 Random 액세스 방식으로 처리 될수 있고,
  그때 발생하는 Random 액세스량이 많다면 소트 머지 조인의 이점이 사라질 수도 있음.(해시조인도 동일)

소트머지 조인이 유용할 때

1. First 테이블에 소트 연산을 대체할 인덱스가 있을 때
2. 조인할 First 집합이 이미 정렬돼 있을 때
3. 조인 조건식이 등치(=)조건이 아닐 때

(3) First테이블에 소트 연산을 대체할 인덱스가 있을 때

SQL> CREATE INDEX dept_idx ON dept(loc, deptno);

인덱스가 생성되었습니다.

SQL> CREATE INDEX emp_idx ON emp(job, deptno);

인덱스가 생성되었습니다.

SQL> SELECT /*+ ordered use_merge(e) */ *
2    FROM   dept d, emp e
3    WHERE  d.deptno = e.deptno
4    AND    d.loc = 'CHICAGO'
5    AND    e.job = 'SALESMAN'
6    ORDER BY e.deptno;


------------------------------------------------------------------------------------------
| Id  | Operation                     | Name     | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT              |          |     1 |    59 |     5  (20)| 00:00:01 |
|   1 |  MERGE JOIN                   |          |     1 |    59 |     5  (20)| 00:00:01 |
|   2 |   TABLE ACCESS BY INDEX ROWID | DEPT     |     1 |    22 |     2   (0)| 00:00:01 |
|*  3 |    INDEX RANGE SCAN           | DEPT_IDX |     1 |       |     1   (0)| 00:00:01 |
|*  4 |   SORT JOIN                   |          |     3 |   111 |     3  (34)| 00:00:01 |
|   5 |    TABLE ACCESS BY INDEX ROWID| EMP      |     3 |   111 |     2   (0)| 00:00:01 |
|*  6 |     INDEX RANGE SCAN          | EMP_IDX  |     3 |       |     1   (0)| 00:00:01 |
------------------------------------------------------------------------------------------

• dept테이블에 별도의 Sort Join오퍼레이션을 수행하지 않음.
• 단, 소트 머지 조인에서 인덱스를 이용해 소트연산을 대체할 수 있는 대상은 First 테이블에 국한됨.

소트 머지 조인에서의 부분범위 처리 활용

SELECT /*+ ordered use_merge(e) index(d dept_pk) */
       d.dname, e.empno, e.ename
FROM   dept d, emp e
WHERE  e.deptno = d.deptno;

• 소트머지 조인도 부분적으로 부분범위처리가 가능

ex1) 부분범위처리 테스트를 위해 아래와 같이 실행 한다.

Step1) emp테이블을 100,000번 복제한 t_emp 테이블 생성

Step2) dept테이블과 조인 하기 위해 deptno 컬럼에 인덱스 생성

CREATE TABLE dept
AS
SELECT * FROM scott.dept;

CREATE TABLE t_emp
AS
SELECT * FROM scott.emp, (SELECT rownum no FROM dual CONNECT BY level <= 100000);

Case1) 작은 dept테이블이 First테이블이 되도록 소트머지조인

SELECT /*+ leading(d) use_merge(e) full(d) full(e) */ *
FROM   t_emp e, dept d
WHERE  d.deptno = e.deptno;

결과는 P243 참조

Case2) 큰 t_emp 테이블(인덱스가 있는)이 First테이블이 되도록 소트머지조인

SELECT /*+ ordered use_merge(d) full(d) index(e t_emp_idx) */ *
FROM   t_emp e, dept d
WHERE  d.deptno = e.deptno;

결과는 p244 참조

(4) 조인할 First집합이 이미 정렬되어 있을 때

• 소트머지 조인할때, First쪽 집합이 조인컬럼을 기준으로 이미 group by, order by, distinct연산등을 수행하여 정렬된 상태인경우 생략
• Second테이블은 정렬되어 있을지라도 Sort Join오퍼레이션 수행

• Outer테이블을 group by하고도 Sort Join 오퍼레이션이 나타난 이유?? hash group by로 처리했기 때문

SELECT /*+ ordered use_merge(d) */ d.deptno, d.dname, e.avg_sal
FROMO (SELECT deptno, avg(sal) avg_sal FROM emp GROUP BY deptno) e
      ,dept d
WHERE e.deptno = d.deptno;

결과는 P244 참조

• 인라인 뷰에 order by절을 명시해 sort group by로 유도하여 Sort Join 오퍼레이션 생략
  (9i는 Order By 절을 명시하지 않아도 아래와 같이 나옴)

SELECT /*+ ordered use_merge(d) */ d.deptno, d.dname, e.avg_sal
FROM  (SELECT deptno, avg(sal) avg_sal FROM emp GROUP BY deptno ORDER BY deptno) e
      ,dept d
WHERE e.deptno = d.deptno;

결과는 P245 참조

• Second 집합이 Group By를 통해 이미 정렬돼 있는 경우
  (Sort Group By 하고서 조인을 위한 소트연산을 한번 더 수행 하는것을 확인)

SELECT /*+ ordered use_merge(e) */ d.deptno, d.dname, e.avg_sal
FROM   dept d
      ,(SELECT deptno, avg(sal) avg_sal FROM emp GROUP BY deptno ORDER BY deptno) e
WHERE  e.deptno = d.deptno;

결과는 P246 참조

(5) 조인 조건식이 등치(=) 조건이 아닐때

• 해시조인은 조인조건식이 등치조건일 때만 사용할수 있으나, 소트머지는 아니어도 사용할 수있다.

• dept테이블 deptno 기준으로 오름차순 정렬하도록 Order By 절을 추가하여도 Sort Order By 오퍼레이션이 나타나지 않음
• 단, 내림차순 정렬 또는 emp테이블 depno를 기준으로 정렬하도록 Order By 절 추가하면 Sort Order By 오퍼레이션단계가 추가

• dept테이블 deptno 기준으로 내림차순 정렬하도록 Order by 절을 추가하여도 Sort Order By 오퍼레이션이 나타나지 않음
• 단, 오름차순 정렬 또는 emp테이블 depno를 기준으로 정렬하도록 Order By 절 주가하면 Sort Order By 오퍼레이션단계가 추가