메뉴 건너뛰기

bysql.net

2. 소트 머지 조인

2011.03.22 18:54

실천하자 조회 수:5792

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
  • 문서의 잘못된 점이나 질문사항은 본 문서에 댓글로 남겨주세요. ^^


번호 제목 글쓴이 날짜 조회 수
60 Front Page file 운영자 2011.02.16 149417
59 3. 인덱스 파티셔닝 darkbeom 2011.06.20 53806
58 3. 다양한 인덱스 스캔 방식 file 멋진넘 2011.02.19 33798
57 8. 통계정보 Ⅱ [1] 멋진넘 2011.04.30 31051
56 2. 파티션 Pruning 실천하자 2011.06.22 26013
55 3. 뷰 Merging 실천하자 2011.05.15 23377
54 3. 해시 조인 file darkbeom 2011.03.21 21526
53 2. 서브쿼리 Unnesting darkbeom 2011.05.16 19691
52 4. 통계정보 Ⅰ darkbeom 2011.04.26 18083
51 7. 인덱스 스캔 효율 [1] 휘휘 2011.03.09 16878
50 7. Sort Area 크기 조정 실천하자 2011.06.14 15059
49 4. 테이블 Random 액세스 부하 [1] file darkbeom 2011.02.24 14672
48 4. 조인 순서의 중요성 운영자 2011.03.28 14232
47 1. 인덱스 구조 [1] file 실천하자 2011.02.16 14183
46 1. 기본 개념 멋진넘 2011.06.28 13385
45 8. 고급 조인 테크닉-1 [1] file darkbeom 2011.04.04 13259
44 9. 비트맵 인덱스 file 실천하자 2011.03.06 12335
43 1. 옵티마이저 file 실천하자 2011.04.18 11203
42 6. 히스토그램 실천하자 2011.04.25 10910
41 6. Sort Area를 적게 사용하도록 SQL 작성 file 실천하자 2011.06.14 8851