Post

<오라클 성능 고도화 원리와 해법2> Ch02-02 소트 머지 조인

Posted Updated
By Mijong Go 17 min read

오라클 성능 고도화 원리와 해법2 - Ch02-02 소트 머지 조인

(1) 기본 메커니즘

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

소트머지조인(Sort Merge Join)은 이름이 의미하는 것처럼 두 테이블을 각각 정렬한 다음에 두 집합을 머지(Merge)하면서 조인을 수행한다. 소트머지조인은 아래 두 단계로 진행된다.

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

소트머지조인은 outer 루프와 inner 루프가 Sort Area에 미리 정렬해둔 자료구조를 이용한 다는 점만 다를 뿐, 실제 조인 오퍼레이션을 수행하는 과정은 NIL조인과 다르지 않다. NIL조인과 마찬가지로 outer 조인할 때 순서가 고정된다는 점도 이 사실을 방증한다.

Sort Area는 PGA 영역에 할당되므로 SGA를 경유해 인덱스와 테이블을 액세스 할 때 보다 훨씬 빠르다. PGA는 프로세스만을 위한 독립적인 메모리 공간이어서 데이터를 읽을 때 래치 획득과 재이없기 때문이다.

Outer 테이블, Inner 테이블
NL 조인에서 Outer와 Inner 테이블에 대한 개념을 설명하였다. 해시조인과 달리 소트머지조인은 Outer와 Inner의 개념을 사용해도 부자연스럽지 않다. 따라서 편의상 First 테이블과 Second 테이블을 각각 Outer 테이블, Inner 테이블로 명명하기로 한다. 그리고 문맥에 따라 두 가지 방식을 혼용해 설명할 것이다.

소트머지조인은 use merge 힌트를 가지고 유도할 수 있다. 아래 SQL에 사용된 힌트는, dept 테이블을 기준으로 emp 테이블과 조인할 때 소트머지조인 방식을 사용하라고 지시하고 있다.

1
2
3

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 테이블과 조인한다.

그림2-3은 3번 조인 수행 단계를 표현한 것이다.

그림2-3에서 주목할 점은, emp 테이블이 정렬되어 있기 때문에 조인에 실패하는 레코드를 만나는 순간 멈출 수 있다는 사실이다. 예를 들어, deptno=10인 레코드를 찾기 위해 1번. 스캔을 진행하다가 20을 만나는 순간 멈춘다.

또한 가지는, 정렬된 emp에서 스캔 시작점을 찾으려고 매번 탐색하지 않아도 된다는 점이다. 예를 들어, deptno=20인 레코드를 찾는 스캔은 한 번에서 스캔하다가 멈춘 지점을 기억했다가 거기서부터 시작하면 된다. Outer 테이블인 dept도 같은 순서로 정렬되어 있기 때문에 가능한 일이다.

만약 M:M 조인이라면 어떨까? 그림2-4에서 알 수 있듯이 M:M 조인에서도 스캔 도중에 멈추는 것은 가능하지만 시작점을 찾는 작업은 단순해 보이지가 않는다.

두 가지 방법을 생각해볼 수 있는데, 시작점을 찾으려고 매번 이진(inany) 탐색을 수행하는 방식과 변수를 하나 더 선언해 앞에서 스캔했던 시작점까지 기억해두는 방식이다. 둘 중 어떤 방식이 맞는지는 증명할 길이 없다. 다만, 소트머지조인 시 Outer 테이블까지 정렬한다는 사실을 통해 후자일 것이라고 추측할 수는 있다. 전자의 방식을 사용한다면 굳이 Outer 테이블까지 정렬할 이유는 없기 때문이다.

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

소트머지조인은 조인을 위해 실시간으로 인덱스를 생성하는 것과 다름없다(실제 인덱스 오브젝트를 생성하는 것은 아니지만). 양쪽 집합을 정렬한 다음에는 NL조인과 같은 방식으로 진행하지만 PGA 영역에 저장된 데이터를 이용하기 때문에 빠르다고 설명하였다. 따라서 소트부하만 감수한다면, 건건이 버퍼캐시를 거치면서 조인하는 NI조인보다 유리하다.

NL조인은 조인 컬럼에 대한 인덱스 유무에 따라 크게 영향을 받지만 소트머지조인은 영향을 받지 않는다. (뒤에서 살펴보겠지만 인덱스가 미리 만들어져 있으면 소트머지조인을 좀 더 빠르게 수행할 수는 있다.)

그리고 양쪽 집합을 개별적으로 읽고 나서 조인한다는 것도 특징이다. 따라서 조인 컬럼에 인덱스가 없는 상황에서 두 테이블을 독립적으로 읽어 조인 대상 집합을 줄일 수 있을 때 아주 유리하다.

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

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

1
2
3
4

select */+ use merge (de) */ 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 테이블에만 국한된다는 사실을 알 수 있다.

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

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

그림 2-5는 아래 쿼리의 수행 과정을 도식화 한 것이다. 그림에 표시하지 않았지만 먼저 emp 테이블 정렬 결과를 Sort Area에 담는다. 그리고 deptpk 인덱스로부터 dept 테이블을 읽고, 여기서 Sort Area에 정렬된 emp 테이블을 탐색하면서 조인하는 과정이다.

1
2
3
4

select /*+ ordered use merge (e) index d(dept pk) */
       d.aname, e.emono, e.ename
from dept d, emp e
where e.deptno = d.deptno;

그림 2-5를 유심히 살펴본 독자라면 소트머지조인도 부분적으로 부분 범위 처리가 가능하다는 것을 느꼈을 것이다. Second 테이블은 항상 정렬을 수행하므로 전체 범위 처리가 불가피하지만 First 테이블만큼은 중간에 읽다가 멈출 수 있다는 뜻이다.

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

소트머지조인할 때, First 쪽 집합이 조인 컬럼 기준으로 이미 정렬된 상태일 수 있다. group by, order by, distinct 연산 등을 먼저 수행한 경우인데, 그 때는 조인을 위해 다시 정렬하지 않아도 되므로 소트머지조인이 유리하다.

여기서도 First 집합이 정렬돼 있을 때만 소트 연산이 생략되며, Second 집합은 설사 정렬돼 있더라도 Sort Join 오퍼레이션을 수행한다.

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

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

위 조인문은 그림 2-6과 같이 처리되므로 dept 테이블 deptno 기준으로 오름차순(asc) 정렬하 도록 order by 절을 추가하더라도 sort order by 오퍼레이션이 나타나지 않는다. 반면 내림차순 (desc) 정렬 또는 emp 테이블 deptno 기준으로 정렬하도록 order by 절을 추가하면 sort order by 오퍼레이션 단계가 추가된다. (지면을 절약하기 위해 SQL과 실행계획을 표시하지 않지만 직접 테스트를 통해 확인하기 바란다.)

부등호 방향을 아래와 같이 바꾸면 오라클은 Sort Join을 위해 두 집합을 내림차순(desc)으로 정렬한다(그림2-7. 쿼리를 수행했을 때 deptno가 큰 값부터 출력되는 것을 통해 이 사실을 알 수 있다).

1
2
3

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

따라서 dept 테이블의 deptno를 기준으로 내림차순 정렬하도록 order by 절을 추가하더라도 sort order by 오퍼레이션이 나타나지 않는다. 반면 아래와 같이 오름차순 정렬 또는 emp 테이블의 deptno를 기준으로 정렬하도록 order by 절을 추가하면 sort order by 오퍼레이션 단계가 추가된다.

Database, SQL Tuning
SQLP
This post is licensed under CC BY 4.0 by the author.