2. 소트 머지 조인

조회 수 2616 추천 수 0 2011.03.29 18:13:45
실천하자 *.136.168.206

02. 소트 머지 조인 (Sort Merge Join)


(1) 기본 메커니즘

  • 1단계 : Sort  - 양쪽 집합을 조인 컬럼 기준 정렬
  • 2단계 : Merge - 양쪽 집합을 서로 머지


  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)

    loop    -- 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;


  • NL 조인 & 소트 머지 조인

=================================================================

  다른점 |  같은점

=================================================================

  a. 자료구조 방법 |  a. 조인 오퍼레이션 수행 과정

  b. PGA 영역 활용 (Sort Area) |  b. Outer 조인 시 순서 고정

=================================================================

  ☞  a. Outer, Inner 루프가 Sort Area에 미리 정렬하는 자료구조 이용

  ☞  b. Sort Area는 PGA 영역에 할당되어 SGA를 경유하여 인덱스와 테이블 액세스할 때보다 훨씬 빠름

          ∵ PGA는 독립적 메모리 공간이기 때문에 데이터 리딩 시, 래치 획득 과정 생략

  • 참고

  Outer  ≒  1st 테이블

  Inner  ≒  2nd 테이블


  • 힌트를 이용한 소트머지 유도

  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(=1st) 테이블 dept를 deptno 기준 정렬

2. Inner(=2nd) 테이블 emp 를 deptno 기준 정렬

3. Sort Area에 정렬된 dept 테이블을 스캔하면서, 정렬된 emp 테이블과 조인

    • 1:M 조인 시

정렬된 Inner(=2nd) 테이블에서 스캔 시작점을 찾으려고 매번 탐색하지 않아도 됨

∵ 전단계 스캔 후 멈춘 지점을 기억했다 재탐색

2_3.JPG

    • M:M 조인 시

A. 시작점을 찾기 위해 매번 이진 탐색 수행

B. 시작점을 기억하는 변수 선언

   ☞ 소트 머지 조인 시 Outer 테이블까지 정렬한다는 사실을 통해 B 방법일 것이라 저자 추측

      A 방법일 경우, Outer 테이블까지 정렬할 이유가 없다고 판단

2_4.jpg


(2) 특징

  • 조인 컬럼의 인덱스 유무에 따른 영향력 적음
  • 양쪽 집합을 각각 읽은 후 조인
  • 스캔 위주의 액세스 방식 사용 (단, 상황에 따라 Random 액세스 발생)

  select /* ordered use_merge(e) */ d.deptno, d.dname, e.empno, e.ename

  from   dept d, emp e

  where  d.deptno = e.deptno

  and    d.loc = 'CHICAGO'
  and    e.job = 'SALESMAN'

  

  • Sort Merge Join 유리한 상황
ㄱ. 1st 테이블에 소트 연산을 대체할 인덱스 있을 시
ㄴ. 조인할 1st 집합이 이미 정렬되어 있을 시
ㄷ. 조인 조건식이 등치(=)조건이 아닐 시 



(3) 1st 테이블에 소트 연산을 대체할 인덱스 있을 시
  • 한쪽 집합(2nd 테이블)은 전체범위 처리하고 다른 한쪽(1st 테이블)은 일부만 읽고 멈출 수 있음 
☞ 1st 테이블 조인 컬럼에 인덱스가 있을 경우 가능
          → OLTP성 업무에서 소량의 테이블과대량의 테이블 조인 시 소트 머지 조인을 유용하게 사용 가능
  • 1st 테이블의 인덱스로 소트 연산을 대체하는 예
  create index dept_idx on dept(loc, deptno);
  create index emp_idx on emp(job, deptno);

  select /*+ ordered use_merge(e) */ * from dept d, emp e
  where  d.deptno = e.deptno
  and    d.loc = 'CHICAGO'
  and    e.job = 'SALESMAN'
  order by e.deptno;
    • 1st 테이블(dept) 경우
a. d.loc = 'CHICAGO' 
b. dept_idx(loc, deptno) 인덱스 사용 
   ☞ 결과 집합은 deptno 순으로 정렬 ∴ 소트 머지 조인에서 Sort 연산 생략
    • 2nd 테이블(emp) 경우
a. e.job = 'SALESMAN'
b. emp_idx (jobdeptno) 인덱스 사용 
   ☞ 결과 집합은 deptno 순으로 정렬 ∴ 소트 머지 조인에서 Sort 연산 발생 (Sort Join)

소트 머지 조인에서 인덱스를 이용한 소트 연산 대체 대상은 1st 테이블에만 국한
   (단, 위와 같은 경우 2nd 테이블의 Sort 연산에 의한 부하 ↓)

  • 소트 머지 조인에서의 부분 범위 처리 활용
   2_5.jpg


(4) 조인할 1st 집합이 이미 정렬되어 있을 시

group by, order by, distinct 연산 등이 사용되어 1st 집합이 이미 정렬 된 상태에서
조인을 위해 다시 정렬하지 않아도 되기때문에 소트 머지 조인이 유리

Outer(=1st) 테이블이 group by 하여도 Sort Join 오퍼레이션 발생 경우
select /*+ ordered use_merge(d) */ d.deptno, d.dname, e.avg_sal
from  (select deptno, avg(sal) avg_sal from emp group by deptno) e
     , dept d
where  e.deptno = d.deptno;


∵ 10gR2의 hash group by 사용

인라인 뷰에 order by절 명시로 sort group by 유도 시 Sort 연산 생략
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;


--
--
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;


--

2_6.jpg


(5) 조인 조건식이 등치(=)조건이 아닐 시 
2_7.jpg


  • 오라클 고도화 원리와 해법 2 (bysql.net 2011년 1차 스터디)
  • 작성자: 위충환 (실천하자)
  • 최초작성일: 2011년 03월 19 일
  • 본문서는 bysql.net 스터디 결과입니다 .본 문서를 인용하실때는 출처를 밝혀주세요. http://www.bysql.net
  • 문서의 잘못된 점이나 질문사항은 본 문서에 댓글로 남겨주세요. ^^