2. 소트 머지 조인

조회 수 6796 추천 수 0 2011.03.22 20:17:16
오예스 *.182.62.197

02. 소트 머지 조인

(1) 기본 메커니즘
NL 조인을 효과적으로 수행하려면 조인 컬럼에 인덱스가 필요하다. 만약 적절한 인덱스가 없다면 Inner 테이블을 탐색할 때마다 반복적으로 Full Scan을 수행하므로 매우 비효율적이다. 그럴 때 옵티마이저는 소트 머지 조인이나 다음 절에서 설명할 해시 조인을 고려한다. 소트 머지 조인(Sort Merge Join)은 이름이 의미하는 것처럼 두 테이블을 각각 정렬한 다음에 두집합을 머지(Merge)하면서 조인을 수행한다. 소트 머지 조인은 아래 두 단계로 진행된다.

1. 소트 단계 : 양쪽 집합을 조인 컬럼 기준으로 정렬한다.
2. 머지 단계 : 정렬된 양쪽 집합을 서로 머지(Merge)한다.

아래는 소트 머지 조인의 처리 메커니즘을 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)
 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;

 

 

7782 : CLARK      : ACCOUNTING
7839 : KING       : ACCOUNTING
7934 : MILLER     : ACCOUNTING
7369 : SMITH      : RESEARCH
7566 : JONES      : RESEARCH
7788 : SCOTT      : RESEARCH
7876 : ADAMS      : RESEARCH
7902 : FORD       : RESEARCH
7499 : ALLEN      : SALES
7521 : WARD       : SALES
7654 : MARTIN     : SALES
7698 : BLAKE      : SALES
7844 : TURNER     : SALES
7900 : JAMES      : SALES



소트 머지  조인은 outer루프와 inner 루프가  Sort Area에 미리 정렬해 둔 자료구조를 이용한다는 점만 다를 뿐, 실제 조인 오퍼레이션을 수행하는 과정은 NL 조인과 다르지 않다. NL 조인과 마찬가지로 outer 조인할 때 순서가 고정된다는 점도 이 사실을 방증한다.
Sort Area는 PGA 영역에 할당되므로 SGA를 경유해 인덱스와 테이블을 액세스할 때보다 휠씬 빠르다 . PGA는 프로세스만을 위한 독립적인 메모리 공간이어서 데이터를 읽을 때 래치 획득 과정이 없기 때문이다. (p.64 그림 1-14와 설명참조)

참고 : PGA(Program Global Area) : 프로세스들이 공유하여 사용 할 수 있는 SGA와는 달리, 개별 프로세스들이 독립적으로 사용하는 비공유        메모리 영역으로, 서버프로세스를 위한 데이터와 제어정보를 저장. 프로세스가 생성될 대 할당 되며 프로세스가 종료될때 해제.
1. PGA  구성요소 : 정렬공간(Sort Area), 세션 정보(Session Information), 커서 상태 정보(Cursor      Stats),  변수 저장 공간(Stack Space)
2.  PGA의 상태확인
SELECT *  FROM V$PROCESS;
PGA_USED_MEM : 프로세스가 현재 사용하는 PGA크기
PGA_ALLOC_MEM : 프로세스가 할당된 PGA크기(사용 완료 후 시스템 메모리에 반환하지 않는 메모리 포함)
PGA_MAX_MEM : 프로세스가 사용한 최데 PGA 크기



Outer 테이블, Inner 테이블
NL 조인에서 Outer와 Inner 테이블에 대한 개념을 설명하였다. 해시 조인과 달리 소트 머지 조인은 Outer와 Inner의 개념을 사용해도 부자연스럽지 않다. 따라서 편의상  First 테이블과 Second 테이블을 각각 Outer 테이블, Inner 테이블로 명명하기로 한다. 그리고 문맥에 따라 두 가지 방식을 혼용해 설명할 것이다.
소트 머지 조인은 use_merge 힌트를 가지고 유도할 수 있다. 아래 SQL에 사용된 힌트는 dept테이블을 기준으로 emp 테이블과 조인할 때 소트 머지 조인 방식을 사용하라고 지시하고 있다.

예제 :
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테이블인 dept를 deptno 기준으로 정렬한다.
2. Inner테이블인 emp를 deptno 기준으로 정렬한다.
3. Sort Area에 정렬된 dept 테이블을 스캔하면서, 정렬된 emp 테이블과 조인한다.

P.237 그림 2-3에서 주목할 점은, emp 테이블이 정렬돼 있기 때문에 조인에 실패하는 레코드를 만나는 순간 멈출수 있다는 사실이다. 예를 들어, dept_no=10인 레코드를 찾기 위해 1번 스캔을 진행하다가 20을 만나는 순간 멈춘다.
또 한 가지는, 정렬된 emp에서 스캔 시작점을 찾으려고 매범 탐색하지 않아도 된다는 점이다. 예를 들어, deptno=20인 레코드를 찾는 2번 스캔은 1번에서 스캔하다가 멈춘 지점을 기억했다가 거기서부터 시작하면 된다. Outer 테이블인 dept도 같은 순서로 정려돼 있기 때문에 가능한 일이다.

(2) 소트 머지 조인의 특징
소트  머지 조인은 조인을 위해 실시간으로 인덱스를 생성하는 것과 다름없다.(실제 인덱스 오브젝트를 생성하는 것은 아니지만).양쪽 집합을 정렬한 다음에는 NL 조인과 같은 방식으로 진행하지만 PGA 영역에 저장된 데이터를 이용하기 때문에 빠르다고 설명하였다. 따라서 소트 부하만 감수한다면 건건이 버퍼 캐시를 거치면서 조인하는 NL 조인보다 유리하다.
(참고 :    NL 조인 시 버퍼 캐시에서 같은 블록을 반복적으로 액세스할 때 발생하는 비효율을 없애려고 Buffer Pinning 기능이 점점 확대 적용되고 있고, 이 때문에 버전이 올라갈수록 NL 조인이 조금씩 유리해지고 있다.)

NL 조인은 조인 컬럼에 대한 인덱스 유무에 따라 크게 영향을 받지만 소트 머지 조인은 영향을 받지 않는다.(뒤에서 살펴보겠지만 인덱스가 미리 만들어져 있으면 소트 머지 조인을 좀 더 빠르게 수행할 수는 있다.)
그리고 양쪽 집합을 개별적으로 읽고 나서 조인한다는 것도 특징이다. 따라서 조인 컬럼에 인덱스가 없는 상황에서 두 테이블을 독립적으로 읽어 조인 대상 집할수 줄일 수 있을 때 아주 유리하다.

스캔 위주의 액세스 방식으 사용한다는 점도 소트 머지 조인의 중요한 특징이다. 하지만 모든 처리가 스캔 방식으로 이루어지는 것은 아니다. 양쪽 소스 집합에서 정렬 대상 레코드를 찾는 작업만큼은 인덱스를 이용해 Random 액세스 방식으로 처리될 수 있고, 그때 발생하는 Random 액세스량이 많다면 소트 머지 조인의 이점이 사라질 수도 있음에 유의하자.  해시 조인할 때도 마찬가지다.

예를 들어, 아래 쿼리에서 loc = 'CHICAGO', job = 'SALESMAN' 이 두 조건에 해당하는 레코드를 찾을 때는 인덱스를 이용할 수 있다.

select /*+ use_merge(d 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'



Random 액세스 위주의 NL 조인이 대용량 처리에 한계를 보일 때마다 소트 머지 조인이 해결사로서 인기를 누리던 시절이 있었다. 하지만 다음 절에서 설명할 해시 조인의 등장으로 소트 머지 조인의 위상은 예전만 못하다. 대부분 해시 조인보다 느린 성능을 보이기 때문이다. 하지만 아래와 같은 상황에서는 여저히 소트 머지 조인이 유용하다.

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

(3) First 테이블에 소트 연산을 대체할 인덱스가 있을 때
소트 머지 조인은 무조건 전체범위처리 방식이라고 알려졌지만 항상 그렇지는 않다. 해시 조인과 마찬가지로 한쪽 집합(Second 테이블)은 전체범위를 처리하고 다른 한족(First 테이블)은 일부만 읽고 멈추도록 할 수 있다. First 테이블 조인 컬럼에 인덱스가 있을 때 그렇다. 만약 그렇게 처리할수 있다면 OLTP성 업무에서 소량의 테이블과 대량의 테이블을 조인할 때 소트 머지 조인을 유용하게 사용할 수 있다. 이에 대해서는 잠시 후에 살펴보기로 하고 , First 테이블에 있는 인덱스로 소트 연산을 대체하는 간단한 예제부터 시작하자.

예제 :
create index dept_idx on dept(loc, deptno);
create index emp_idx on emp(job, deptno);



dept_id는 loc + deptno 순으로 정렬돼 있다. 따라서 이 인덱스를 loc = 'CHICAGO' 조건으로 스캔하면서 얻어진 결과집합은 이미 dept 순으로 정렬돼 있다. 따라서 dept 테이블이 소트머지 조인을 위한 First 집합으로 선택된다면 소트 연산이 생략될 수 있다. 아래 실행계획에서 dept테이블에 별도의 Sort Jin 오퍼레이션을 수행하지 않으 것을 확인하기 바란다.

예제 :
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;

--------------------------------------------------------------------------------------
| Id  | Operation                     | Name     | E-Rows |  OMem |  1Mem | Used-Mem |
--------------------------------------------------------------------------------------
|   1 |  MERGE JOIN                   |          |      1 |       |       |          |
|   2 |   TABLE ACCESS BY INDEX ROWID | DEPT     |      1 |       |       |          |
|*  3 |    INDEX RANGE SCAN           | DEPT_IDX |      1 |       |       |          |
|*  4 |   SORT JOIN                   |          |      3 |  2048 |  2048 | 2048  (0)|
|   5 |    TABLE ACCESS BY INDEX ROWID| EMP      |      3 |       |       |          |
|*  6 |     INDEX RANGE SCAN          | EMP_IDX  |      3 |       |       |          |
--------------------------------------------------------------------------------------
  3 - access("D"."LOC"='CHICAGO')
  4 - access("D"."DEPTNO"="E"."DEPTNO")
      filter("D"."DEPTNO"="E"."DEPTNO")
  6 - access("E"."JOB"='SALESMAN')



같은 원리로 job + deptno 순으로 정렬된 emp_idx 인덱스를 job = 'SALESMAN' 조건으로 스캔하면서 얻어지는 결과 집합도 deptno 순으로 정렬된다. 따라서 emp 테이블을 다시 정렬할 필요가 없을 것 같지만 위 실행계획에서는 Sort Join 오퍼레이션이 나타났다. 소트 머지 조인에서 인덱스를 이용해 소트 연산을 대체할 수 있는 대상은 First 테이블에만 국한된다는 사실을 알수 있다. 결과집합이 이미 deptno 순으로 정렬돼 있기 때문에 order by를 위한 추가 Sort 오퍼레이션이 발생하지 않은 것도 눈여겨볼 필요가 있다.

위 실행계획에 표시된 순서상 dept 가 First 테이블이고 emp가 Second 테이블이지만 항상 First 테이블을 먼저 읽는 것은 아니다. First 테이블은 이미 정렬된 인덱스를 사용할 것이므로 그대로 두고, 먼저 Second 집합인 emp 테이블을 읽어 정렬한 결과를 Sort Area에 담는다. 조인 연산을 진행할 대는 dept_idx 인덱스부터 읽기 시작한다.

소트 머지 조인에서의 부분범위 처리 활용.
p.242 그림 2-5는 아래 쿼리의 수행과정을 도식화한 것이다. 그림에 표시하지 않았지만 먼저 emp 테이블의 정렬 결과를 Sort Area에 담는다. 그리고 dept_pk 인덱스로부터 dept테이블을 읽고 이어서 Sort Area에 정렬된 emp 테이블을 탐색하면서 조인하는 과정이다.
그림 2-5를 유심히 살펴보면 소트 머지 조인도 부분적으로 부분범위처리가 가능하다. Second 테이블은 항상 정렬을 수행하므로 전체범위처리가 불가피하지만 First 테이블만큼은 중간에 읽다가 멈출 수 있다는 뜻이다.

부분범위처리 원리에 의한 효과 테스트.(사용자가 명시적으로 스크롤할 때만 Fetch Call을 수행하는 쿼리 툴을 사용. Toad, Orange등)

예제 :
create table t_emp
as
select * from scott.emp, (select rownum no from dual connect by level <= 100000);
create index t_emp_idx on t_emp(deptno);

exec dbms_stats.gather_table_stats(user, 'dept');
exec dbms_stats.gather_table_stats(user, 't_emp', no_invalidate=>false);



emp 테이블을 100,000번 복제한 t_emp 테이블을 만들었다. emp 테이블이 14건이므로 t_emp테이블에는 1,400,000건이 담겼을 것이다.
그리고 dept 테이블과 조인하기 위해 deptno 컬럼에 인덱스를 만들었다.
아래는 작은 dept 테이블이 First 테이블이 되도록 소트 머지 조인을 수행한 결과다. Second 테이블은 조인 컬럼에 인덱스가 있더라도 정렬을 수행한다고 했다.

select /*+ leading(d) use_merge(e) full(d) full(e) */ *
from   t_emp e, dept d
where  d.deptno = e.deptno;



트레이스 결과를 보면 140만 건의 t_emp 테이블을 정렬하는 과정에서 많은 I/O를 일으켰고,
대부분 소요시간도 그 부분에서 발생한 것을 알 수 있다. 두 번 Fetch하면서 11건을 읽기 위해 총 19.6초의 수행 소요시간을 보였다.
그리고 T_emp 소트 과정에서 많은 디스크 읽기와 쓰기가 발생한 것에도 주목하기 바라다.

이제 큰 t_emp 테이블이 First 테이블이 되도록 소트 머지 조인을 수행해 보자. 부분범위처리 효과를 얻기 위해 t_emp_id를 이용하도록 index 힌트를 명시했다.

select /*+ ordered use_merge(d) full(d) index(e t_emp_idx) */ *
from   t_emp e, dept d
where  d.deptno = e.deptno;


똑같이 두 번 Fetch하면서 11건을 읽었지만 많은 시간이 단축되었다.

(4) 조인할 First 집합이 이미 정렬돼 있을 때
소트 머지 조인할 때,  First쪽 집합이 조인 컬럼 기준으로 이미 정렬된 상태일 수 있다. group by, order by, distinct 연산 등을 먼저 수행한 경우인데, 그때는 조인을 위해 다시 정렬하지 않아도 되므로 소트 머지 조인이 유리하다.
여기서도 First 집합이 정렬돼 있을 때만 소트 연산이 생략되며, Second 집합은 설사 정렬돼 있더라도 Sort Join 오퍼레이션을 수행한다.

(5)조인 조건식이 등치(=) 조건이 아닐때
해시 조인은 조인 조건식이 등치(=) 조건일 때만 사용할 수 있지만 소트 머지 조인은 등치 조건이 아닐 때도(between, < <=, >, >=) 사용될 수 있다.

select /*+ ordered use_merge(e) */ d.deptno, d.dname, e.empno, e.ename
from dept d, emp e
where d.deptno <= e.deptno


위 조인문은 p.247 그림 2-6과 같이 처리되므로 dept 테이블 deptno 기준으로 오름차순(asc) 정렬하도록 order by절을 추가하더라도 sort order by 오퍼레이션이 나타나지 않는다. 반면 내림차순 정렬또는 emp 테이블 deptno 기준으로 정렬하도록 order by 절을 추가하면 sort order by  오퍼레이션 단계가 추가된다.
부등호 방향을 아래와 같이 바꾸면 오라클은 Sort Join을 위해 두 집합을 내림차순으로 정렬한다. 쿼리를 수행했을때 deptno가 큰 값부터 출력되는 것을 통해 이 사실을 알 수 있다.

select /*+ ordered use_merge(e) */ d.deptno, d.dname, e.empno, e.ename
from dept d, emp e
where d.deptno >= e.deptno



  • 오라클 고도화 원리와 해법 2 (bysql.net 2011년 1차 스터디)

  • 작성자: 윤용정 (sirason1)

  • 최초작성일: 2011년 3월 20일

  • 본문서는 bysql.net 스터디 결과입니다 .본 문서를 인용하실때는 출처를 밝혀주세요. http://www.bysql.net

  • 문서의 잘못된 점이나 질문사항은 본문서에 댓글로 남겨주세요. ^^