1. Nested Loop Join

가. 기본 메커니즘

프로그래밍을 해 본 독자라면 누구나 아래 중첩 루프문(Nested Loop)의 수행 구조를 이해할 것이고, 그렇다면 Nested Loop Join(이하 NL Join)도 어렵지 않게 이해할 수 있다.

위 중첩 루프문과 같은 수행 구조를 사용하는 NL Join이 실제 어떤 순서로 데이터를 액세스하는지 아래 PL/SQL문이 잘 설명해 준다.

위 PL/SQL문은 아래 쿼리와 100% 같은 순서로 데이터를 액세스하고, 데이터 출력순서도 같다. 내부적으로(=Recursive하게) 쿼리를 반복 수행하지 않는다는 점만 다르다.

사실 뒤에서 설명할 Sort Merge Join과 Hash Join도 각각 소트 영역(Sort Area)과 해시 영역(Hash Area)에 가공해 둔 데이터를 이용한다는 점만 다를 뿐 기본적인 조인 프로세싱은 다르지 않다.

나. NL Join 수행 과정 분석

이제 NL Join의 기본 메커니즘을 이해했으므로 아래 조인문에서 조건절 비교 순서가 어떻게 되는지 분석해 보자.

인덱스 상황은 다음과 같다.

사용되는 인덱스는 dept_loc_idx와 emp_deptno_idx 인 것을 위 실행계획을 보고 알 수 있다. 

그럼 조건비교 순서는? SQL 조건절에 표시한 번호로 ② → ③ → ① → ④ 순이다. 

실행계획을 해석할 때, 형제(Sibling) 노드 간에는 위에서 아래로 읽는다. 

부모-자식(Parent-Child) 노드 간에는 안쪽에서 바깥쪽으로, 즉 자식 노드부터 읽는다. 

위 실행계획의 실행 순서를 나열하면 다음과 같다.

1. dept_loc_idx 인덱스 범위 스캔(ID = 4) 

2. 인덱스 rowid로 dept 테이블 액세스(ID = 3) 

3. emp_deptno_idx 인덱스 범위 스캔(ID = 6) 

4. 인덱스 rowid로 emp 테이블 액세스(ID = 5) 

5. sal 기준 내림차순(desc) 정렬(ID = 1)

위 실행계획을 그림으로써 표현해 보면 그림 Ⅲ-4-26과 같다.

1. dept.loc = ‘SEOUL’ 조건을 만족하는 레코드를 찾으려고 dept_loc_idx 인덱스를 범위 스캔한다. 

2. dept_loc_idx 인덱스에서 읽은 rowid를 가지고 dept 테이블을 액세스해 dept.gb = ‘2’ 필터 조건을 만족하는 레코드를 찾는다. 

3. dept 테이블에서 읽은 deptno 값을 가지고 조인 조건을 만족하는 emp 쪽 레코드를 찾으려고 emp_deptno_idx 인덱스를 범위 스캔한다. 

4. emp_deptno_idx 인덱스에서 읽은 rowid를 가지고 emp 테이블을 액세스해 sal >= 1500 필터 조건을 만족하는 레코드를 찾는다.

5. 1~4 과정을 통과한 레코드들을 sal 칼럼 기준 내림차순(desc)으로 정렬한 후 결과를 리턴한다.

여기서 기억할 것은, 각 단계를 완료하고 나서 다음 단계로 넘어가는 게 아니라 한 레코드씩 순차적으로 진행한다는 사실이다.

단, order by는 전체 집합을 대상으로 정렬해야 하므로 작업을 모두 완료하고서 다음 오퍼레이션을 진행한다. 아래는 SQL Server에서의 실행계획이다.

SQL Server에서 제공하는 그래픽 모드 실행계획은 그림 Ⅲ-4-27과 같다.

그림 Ⅲ-4-28을 보면 지금까지 설명한 NL Join의 수행 절차를 좀 더 명확히 이해할 수 있다.

11, 19, 31, 32는 스캔할 데이터가 더 있는지 확인하는 one-plus 스캔을 표시한 것이다. 

(O)는 테이블 필터 조건에 의해 레코드가 걸러지지 않은 것을 의미하고, 반대로 

(X)는 테이블 필터 조건에 의해 걸러진 것을 의미한다. 

여기서는 단일 칼럼 인덱스를 ‘=’ 조건으로 스캔했으므로 비효율 없이 6(=5+1)건을 읽었고, 그만큼 테이블 Random 액세스가 발생했다. 

 이 부분이 NL Join의 첫 번째 부하지점이다.

 두 번째 부하지점은 emp_deptno_idx 인덱스를 탐색하는 부분이며, Outer 테이블인 dept를 읽고 나서 조인 액세스가 얼만큼 발생하느냐에 의해 결정된다. 

 세 번째 부하지점은 emp_deptno_idx를 읽고 나서 emp 테이블을 액세스하는 부분이다. 여기서도 sal >= 1500 조건에 의해 필터링되는 비율이 높다면 emp_deptno_idx 인덱스에 sal 칼럼을 추가하는 방안을 고려해야 한다. 

다. NL Join의 특징

대부분 DBMS가 블록(또는 페이지) 단위로 I/O를 수행하는데, 하나의 레코드를 읽으려고 블록을 통째로 읽는 Random 액세스 방식은 설령 메모리 버퍼에서 빠르게 읽더라도 비효율이 존재한다. 

 NL Join의 첫 번째 특징이 Random 액세스 위주의 조인 방식이라는 점이다.

따라서 인덱스 구성이 아무리 완벽하더라도 대량의 데이터를 조인할 때 매우 비효율적이다.

두 번째 특징은, 조인을 한 레코드씩 순차적으로 진행한다는 점이다.

첫 번째 특징 때문에 대용량 데이터 처리 시 매우 치명적인 한계를 드러내지만, 반대로 이 두 번째 특징 때문에 아무리 대용량 집합이더라도 매우 극적인 응답 속도를 낼 수 있다.

부분범위처리가 가능한 상황에서 그렇다. 그리고 순차적으로 진행하는 특징 때문에 먼저 액세스되는 테이블의 처리 범위에 의해 전체 일량이 결정된다. 다른 조인 방식과 비교했을 때 인덱스 구성 전략이 특히 중요하다는 것도 NL Join의 중요한 특징이다.

조인 칼럼에 대한 인덱스가 있느냐 없느냐, 있다면 칼럼이 어떻게 구성됐느냐에 따라 조인 효율이 크게 달라진다. 이런 여러 가지 특징을 종합할 때, NL Join은 소량의 데이터를 주로 처리하거나 부분범위처리가 가능한 온라인 트랜잭션 환경에 적합한 조인 방식이라고 할 수 있다.

2. Sort Merge Join

NL Join은 조인 칼럼을 선두로 갖는 인덱스가 있는지가 매우 중요하다. 만약 조인 칼럼을 선두로 갖는 인덱스가 없으면 Outer 테이블에서 읽히는 건마다 Inner 테이블 전체를 스캔하기 때문이다. 그럴 때 옵티마이저는 Sort Merge Join이나 다음 절에서 설명할 Hash Join을 고려한다. Sort Merge Join은 이름이 의미하는 것처럼 두 테이블을 각각 정렬한 다음에 두 집합을 머지(Merge)하면서 조인을 수행한다. Sort Merge Join은 아래 두 단계로 진행된다.

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

만약 조인 칼럼에 인덱스가 있으면(Oracle의 경우 Outer 테이블에만 해당) ①번 소트 단계를 거치지 않고 곧바로 조인할 수도 있다. Oracle은 조인 연산자가 부등호이거나 아예 조인 조건이 없어도 Sort Merge Join으로 처리할 수 있지만, SQL Server는 조인 연산자가 ‘=’ 일 때만 Sort Merge Join을 수행한다는 사실에도 유념하기 바란다.

가. 기본 메커니즘

아래 SQL은 dept 테이블을 기준으로 emp 테이블과 조인할 때 Sort Merge Join 방식을 사용하라고 힌트로 지시하고 있다.

Sort Merge Join의 수행 과정을 그림으로 도식화하면 그림 Ⅲ-4-29와 같다.

그림 Ⅲ-4-29에서 주목할 점은, Inner 집합인 emp 테이블이 정렬돼 있기 때문에 조인에 실패하는 레코드를 만나는 순간 멈출 수 있다는 사실이다.

예를 들어, deptno=10인 레코드를 찾기 위해 ①번 스캔을 진행하다가 20을 만나는 순간 멈춘다.

또 한 가지는, 정렬된 emp에서 스캔 시작점을 찾으려고 매번 탐색하지 않아도 된다는 점이다.

예를 들어, deptno=20인 레코드를 찾는 ②번 스캔은 ①번에서 스캔하다가 멈춘 지점을 기억했다가 거기서부터 시작하면 된다. Outer 집합인 dept 테이블도 같은 순서로 정렬돼 있기 때문에 가능한 일이다. 아래는 Sort Merge Join이 머지하는 방식을 pseudo 코드로 작성한 것이다.

 위 pseudo 코드를 잘 살펴보면, 실제 조인 수행 과정이 NL Join과 크게 다르지 않다. outer 집합과 inner 집합을 미리 정렬해 둔다는 점만 다르다. 다시 말하지만, 양쪽 집합을 먼저 정렬해 두었기 때문에 위와 같은 처리 로직이 가능하다.

나. Sort Merge Join의 특징

Sort Merge Join은 다음과 같은 특징을 가진다.

• 조인 하기 전에 양쪽 집합을 정렬한다.

NL Join은 정렬 없이 Outer 집합을 한 건씩 차례대로 조인을 진행하지만, Sort Merge Join은 양쪽 집합을 조인 칼럼 기준으로 정렬한 후에 조인을 시작한다. 대량 집합 조인은 Random 액세스 위주의 NL Join의 경우 비효율이 있고, 이 비효율을 줄이고자 나온 조인 방식이 Sort Merge Join이다. 만약 정렬해야 할 집합이 초대용량 테이블이면 정렬 자체가 큰 비용을 수반하기 때문에 성능 개선 효과를 얻지 못할 수도 있다. 하지만, 일반 인덱스나 클러스터형 인덱스처럼 미리 정렬된 오브젝트를 이용하면 정렬작업을 하지 않고 바로 조인을 수행할 수 있어 Sort Merge Join이 좋은 대안이 될 수 있다.

• 부분적으로, 부분범위처리가 가능하다.

Sort Merge Join은 양쪽 집합을 정렬해야 함으로 부분범위처리가 불가능할 거 같지만, 부분적으로는 가능하다. Outer 집합이 조인 칼럼 순으로 미리 정렬된 상태에서 사용자가 일부 로우만 Fetch 하다가 멈춘다면 Outer 집합은 끝까지 읽지 않아도 되기 때문이다.

• 테이블별 검색 조건에 의해 전체 일량이 좌우된다.

NL Join은 Outer 집합의 매 건마다 Inner 집합을 탐색한다. Outer 집합에서 조인 대상이 되는 건수에 의해 전체 일량이 좌우되는 이유다. 그러나 Sort Merge Join은 두 집합을 각각 정렬한 후에 조인함으로 각 집합의 크기, 즉 테이블별 검색 조건에 의해 전체 일량이 좌우된다.

• 스캔(Scan) 위주의 조인 방식이다.

NL Join이 Random 액세스 위주의 조인 방식이라면 Sort Merge Join은 스캔 위주의 조인 방식이다. Inner 테이블을 반복 액세스하지 않으므로 머지 과정에서 Random 액세스가 발생하지 않는 것이다. 하지만, Random 액세스가 전혀 없는 것은 아니다. 각 테이블 검색 조건에 해당하는 대상 집합을 찾을 때 인덱스를 이용한 Random 액세스 방식으로 처리될 수 있고, 이때 발생하는 Random 액세스량이 많다면 Sort Merge Join의 이점이 사라질 수 있다.

3. Hash Join

가. 기본 메커니즘

Hash Join은 NL Join이나 Sort Merge Join이 효과적이지 못한 상황을 해결하고자 나온 조인 방식이다. 아래는 Oracle과 SQL Server 각각에서 Hash Join으로 유도했을 때의 실행계획이다.

Hash Join은 둘 중 작은 집합(Build Input)을 읽어 해시 영역(Hash Area)에 해시 테이블(= 해시 맵)을 생성하고, 반대쪽 큰 집합(Probe Input)을 읽어 해시 테이블을 탐색하면서 조인하는 방식이다.(그림 Ⅲ-4-30 참조)

해시 함수는, 출력값을 미리 알 순 없지만, 같은 입력값에 대해 같은 출력값을 보장하는 함수다. 다른 입력값에 대한 출력값이 같을 수는 있는데, 이를 ‘해시 충돌’이라고 한다.

• 1단계 : 해시 테이블 생성두 집합 중 작다고 판단되는 집합을 읽어 해시 테이블을 만든다. 해시 테이블을 만들 때 해시 함수를 사용한다. 해시 테이블은 해시 버킷으로 구성된 배열이라고 생각하면 된다. 해시 함수에서 리턴받은 해시 값이 같은 데이터를 같은 해시 버킷에 체인(연결 리스트)으로 연결한다.
• 
  
• 2단계 : Probe Input을 스캔해시 테이블 생성을 위해 선택되지 않은 나머지 데이터 집합(Probe Input)을 스캔한다.
• 
  
• 3단계 : 해시 테이블 탐색Probe Input에서 읽은 데이터로 해시 테이블을 탐색할 때도 해시 함수를 사용한다. 즉, 해시 함수에서 리턴받은 버킷 주소로 찾아가 해시 체인을 스캔하면서 데이터를 찾는다.

나. Build Input이 가용 메모리 공간을 초과할 때 처리 방식

1) 파티션 단계

조인되는 양쪽 집합(→ 조인 이외 조건절을 만족하는 레코드) 모두 조인 칼럼에 해시 함수를 적용하고, 반환된 해시 값에 따라 동적으로 파티셔닝을 실시한다. 독립적으로 처리할 수 있는 여러 개의 작은 서브 집합으로 분할함으로써 파티션 짝(pair)을 생성하는 단계다. 파티션 단계에서 양쪽 집합을 모두 읽어 디스크 상의 Temp 공간에 일단 저장해야 하므로 In-Memory Hash Join보다 성능이 크게 떨어지게 된다.

2) 조인 단계

파티션 단계가 완료되면 각 파티션 짝(pair)에 대해 하나씩 조인을 수행한다. 이때, 각각에 대한 Build Input과 Probe Input은 독립적으로 결정된다. 즉, 파티션하기 전 어느 쪽이 작은 테이블이었는지에 상관없이 각 파티션 짝(pair)별로 작은 쪽 파티션을 Build Input으로 선택해 해시 테이블을 생성한다. 해시 테이블이 생성되고 나면 반대 쪽 파티션 로우를 하나씩 읽으면서 해시 테이블을 탐색하며, 모든 파티션 짝에 대한 처리가 완료될 때까지 이런 과정을 반복한다. Grace Hash Join은 한마디로, 분할 정복(Divide & Conquer) 방식이라고 말할 수 있다. 실제로는 DBMS 벤더마다 조금씩 변형된 형태의 하이브리드(Hybrid) 방식을 사용하지만 두 개의 큰 테이블을 Hash Join하는 기본 알고리즘은 Grace Hash Join에 바탕을 두고 있다.

• Recursive Hash Join(=Nested-loops Hash Join)

디스크에 기록된 파티션 짝(pair)끼리 조인을 수행하려고 ‘작은 파티션’을 메모리에 로드하는 과정에서 또다시 가용 메모리를 초과하는 경우가 발생할 수 있다. 그럴 때는 추가적인 파티셔닝 단계를 거치게 되는데, 이를 ‘Recursive Hash Join’이라고 한다.

다. Build Input 해시 키 값에 중복이 많을 때 발생하는 비효율

잘 알다시피 해시 알고리즘의 성능은 해시 충돌(collision)을 얼마나 최소화할 수 있느냐에 달렸으며, 이를 방지하려면 그만큼 많은 해시 버킷을 할당해야만 한다. 그림 Ⅲ-4-30에는 개념적으로 설명하기 위해 하나의 버킷에 여러 키 값이 달리는 구조로 표현하였지만, DBMS는 가능하면 충분히 많은 개수의 버킷을 할당함으로써 버킷 하나당 하나의 키 값만 갖게 하려고 노력한다. 그런데 해시 버킷을 아무리 많이 할당하더라도 해시 테이블에 저장할 키 칼럼에 중복 값이 많다면 하나의 버킷에 많은 엔트리가 달릴 수 밖에 없다. 그러면 해시 버킷을 아무리 빨리 찾더라도 해시 버킷을 스캔하는 단계에서 많은 시간을 허비하기 때문에 탐색 속도가 현저히 저하된다. Build Input의 해시 키 칼럼에는 중복 값이 (거의) 없어야 Hash Join이 빠르게 수행될 수 있음을 이해할 것이다.

라. Hash Join 사용기준

Hash Join 성능을 좌우하는 두 가지 키 포인트는 다음과 같다.

• 한 쪽 테이블이 가용 메모리에 담길 정도로 충분히 작아야 함
• Build Input 해시 키 칼럼에 중복 값이 거의 없어야 함

• 조인 칼럼에 적당한 인덱스가 없어 NL Join이 비효율적일 때
• 조인 칼럼에 인덱스가 있더라도 NL Join 드라이빙 집합에서 Inner 쪽 집합으로의 조인 액세스량이 많아 Random 액세스 부하가 심할 때
• Sort Merge Join 하기에는 두 테이블이 너무 커 소트 부하가 심할 때
• 수행빈도가 낮고 조인할 때

4. Scalar Subquery

쿼리에 내장된 또다른 쿼리 블록을 서브쿼리라고 하는데, 그 중에서 함수처럼 한 레코드당 정확히 하나의 값만을 리턴하는 서브쿼리를 ‘Scalar Subquery’라고 한다. Scalar Subquery는 주로 select-list에서 사용되지만 몇 가지 예외사항을 뺀다면 칼럼이 올 수 있는 대부분 위치에서 사용 가능하다.

Scalar Subquery를 사용한 위 쿼리 문장은 아래 Outer 조인문과 100% 같은 결과를 낸다. 즉, dept와 조인에 실패하는 emp 레코드가 있다면 dname으로 null 값이 출력된다.

위에서 예시한 쿼리는 결과만 같은 것이 아니라 조인을 수행하는 처리 경로도 동일한데, NL 방식으로 수행되도록 힌트를 사용했기 때문이다. 다만 Scalar Subquery에는 내부적으로 캐싱 기법이 작용된다는 점이 다르고, 이를 이용한 튜닝이 자주 행해진다.

가. Scalar Subquery의 캐싱 효과

아래 쿼리는 위치가 ‘CHICAGO’인 부서(dept)만 대상으로 급여 수준을 집계하려는 것인데, 사원(emp) 테이블 전체를 다 읽어야 하는 비효율이 있다.

아래와 같이 바꿀 수 있으면 좋겠지만 스칼라 서브쿼리는 한 레코드당 하나의 값만 리턴한다는 특징 때문에 그럴 수가 없다.

그렇다고 아래와 같이 쿼리한다면 emp에서 같은 범위를 반복적으로 액세스하는 비효율이 생긴다.

이럴 때, 아래 처럼 구하고자 하는 값들을 모두 결합하고서 바깥쪽 액세스 쿼리에서 substr 함수로 분리하는 방법이 유용하게 쓰인다.