조인은 카티션 프로덕트를 수행 후 셀렉션과 프로젝션을 수행하는 데이터베이스의 연산으로, 관계형 데이터베이스에서 공통적으로 사용하고 있는 조인 기법(Join Technique)에는 Nested loops 조인, Sort merge 조인, Hash 조인 등이 있다. 이 이외에도 일부 데이터베이스에서는 Hybrid 조인, Star 조인과 Semi 조인 등을 지원한다.

조인은 위에서 언급한 조인을 수행하는 내부적인 매카니즘으로 구분을 할 수도 있지만, 조인을 기술한 조인 조건의 연산자를 기준으로 조인의 종류를 나누기도 한다. 예를 들어, 조인 조건이 (=)로 정의되었다 면 equi 조인이라 하며, >=, <=, between 등이 조인 조건에 기술되었다면 between 조인이라 한다.

마지막으로 조인을 분류하는 방법은 조인의 결과가 어떤 집합에 의하여 결정되느냐에 따라 분류하는 방법으로, 조인의 결과가 Outer 집합에 의하여 결정되는 Outer 조인과 Inner 집합에 의하여 결정되 는 Inner 조인으로 구분할 수 있다. 아래 조인의 결과를 나타내기 위한 밴 다이어그램을 보면 Inner 조인의 결과는 B 집합이 되고, 사원 집합을 Outer 집합으로 하여 Outer 조인을 수행한 결과는 A + B 집합이 된다. 그런데 Inner 조인의 결과인 집합 B는 사원과 부서의 교집합으로, Inner 집합인 부서를 액세스하여야만 결정될 수 있다. 그리고 Outer 조인의 결과인 A + B 집합은 Outer 집합인 사원과 동 일한 집합이므로 Outer 조인의 결과는 Outer 집합을 액세스할 때 이미 결정된다.

위에서 조인을 분류한 내용들을 이해하려면 Nested Loop 조인의 알고리즘을 이해하여야 한다. 이 알고리즘을 보면 두 개의 Loop가 중첩되어 조인이 수행되고 있는 것을 알 수 있다. 여기에서 EMP 테 이블을 Outer 집합이라 하고, DEPT 테이블을 Inner 집합이라 한다. 그 이유는, EMP 테이블은 바깥 쪽 루프에서 액세스되고 DEPT 테이블은 안쪽 루프에서 액세스되는 테이블이기 때문이다. 즉, Outer 집합이란 Nested Loop 조인에서 바깥쪽 루프에서 액세스되는 집합을 의미하고, Inner 집합은 안쪽 루프에서 액세스되는 집합을 의미한다. 그런데 Outer 집합이라는 용어가 Nested Loop 조인에서만 사용되는 것은 아니다. 조인 연산이 가지는 특성상 어떤 조인 기법을 사용하더라도 항상 Outer 집합과 Inner 집합이 나타나게 된다. 물론 다른 조인 기법에서는 Nested-Loop 조인처럼 Outer 집합과 Inner 집합의 구분이 명확하지 않아 이 용어의 사용이 적절하지 않다고 주장하는 사람들도 있지만 이 러한 용어가 나타난 배경을 이해하고 사용한다면 굳이 사용하지 못할 이유가 없다고 생각한다.

Outer 집합과 Inner 집합은 조인을 수행하는 각 단계에 그 집합이 참여하는 위치로 구분을 한 것이 므로 조인 각 단계마다 정의될 수 있다. 그러나 드라이빙 집합은 조인 전 과정에서 하나의 집합만이 가 질 수 있는 특징으로 조인에 참여하는 집합 중 최초로 액세스되는 집합을 의미한다. 예를 들어, 아래 알 고리즘에서 사원 테이블은 Loop의 바깥쪽에 있고 최초로 액세스되므로 Outer 집합이면서 드라이빙 집합도 된다.

Nested-Loop 조인

조인 연산은 두 집합을 카티션 프로덕트 형태로 모든 튜플을 열거한 다음, 조인에 만족하지 않는 튜플 을 제거하는 두 가지 기본 알고리즘으로 구성되어 있다. 특히 Simple Nested-Loop 조인은 이러한 기 본 개념만 가지고 구성되었기 때문에 인덱스를 필요로 하지 않을 뿐만 아니라 어떠한 조인 조건에서도 사용할 수 있는 조인 알고리즘이다. 그러나 조인을 수행하기 위해 두 집합의 모든 튜플을 카티션 프로덕 트 형태로 검사하므로 비용이 매우 많이 든다. 예를 들어, 사원과 부서 테이블이 Nested-Loop 조인을 수행한다고 가정해 보자. 사원 테이블은 10,000개의 로우를 가지고 있고 부서 테이블은 200개의 로우 를 가지고 있다면 이 조인에서 액세스되어야 하는 튜플의 개수는 10,000 * 200 이다. 즉, 모든 사원이 모든 부서를 스캔해야 한다. 이처럼 처리해야 하는 대상 집합이 커지면 탐침해야 하는 일량도 급속하게 증가해 수행 속도가 저하된다. 그리고 Outer 집합에 추출된 로우의 수만큼 Inner 집합을 반복적으로 액세스하므로 Inner 집합을 메모리로 읽어 들인 횟수가 증가할수록 수행 속도는 더욱더 저하된다.

위의 두 가지 성능 저하 조건이 모두 충족된다면 최악의 시나리오가 나올 가능성이 높기 때문에 옵티 마이저는 Nested-Loop 조인으로 수행하는 것을 포기하게 될 것이다.

그러나 Inner 집합에 조인 조건으로 기술된 속성에 인덱스가 존재한다면 옵티마이저는 테이블 스캔을 하지 않고 인덱스를 통해 조인 조건을 만족시키는 튜플을 얻어낼 수 있다. 이러한 조인 기법을 Indexed Nested-Loop 조인이라 한다. 이 조인 기법에서는 이미 구축되어 있는 인덱스를 사용할 수 도 있고 조인을 수행하기 위해 임시로 인덱스를 만들어 사용할 수도 있다.

다음은 Indexed Nested-Loop 조인에 대한 몇 가지 사례를 도식화한 것이다.

CASE1의 경우라면 다음과 같은 절차로 수행을 하게 될 것이다.

1. 1. ① CASE1의 경우 사원 테이블을 드라이빙 테이블로 선정하였다. 그런데 사원 테이블은 주어진 조건 중에서 사용 가능한 인덱스가 없으므로 테이블 스캔으로 전체 데이터를 검색한다.
   2. ② 사원 테이블에서 추출되는 로우의 수만큼 반복해 부서.부서코드 인덱스를 탐침한다. 부서.부서코 드는 부서 테이블의 PK이므로 탐침 시에는 인덱스 Unique scan을 한다.
   3. ③ 부서 테이블의 ROWID를 이용해 부서 테이블을 액세스한다.
   4. ④ 부서 테이블에서 SELECT-LIST에 포함된 속성을 추출하여 결과 집합을 완성한다.
   5. ⑤ 완성된 결과 집합을 일정한 크기로 사용자에게 반환한다.

조인 조건

Indexed nested-loop 조인으로 수행되려면 Inner 테이블에 조인 조건으로 사용된 칼럼에 반드 시 인덱스가 존재해야만 한다. Inner 테이블에 인덱스가 존재하지 않는다면 Outer 테이블에서 추 출된 로우의 수만큼 Inner 테이블을 반복해서 테이블 스캔하게 된다. 이러한 비효율을 없애기 위 해 옵티마이저는 드라이빙 조건의 범위가 넓거나 Inner 테이블의 사이즈가 크면 Sort-merge 조 인이나 Hash 조인으로 실행 계획을 유도하려oop 조인에서 결과 집합이 출력되는 순서는 드라이빙 테이블을 액세스한 순서와 동일하 다. 즉, 드라이빙 테이블을 Full Scan했다면 드라이빙 테이블의 데이터 저장 순서로 출력되고, 드 라이빙 테이블 액세스 시에 인덱스를 이용했다면 이용한 인덱스의 순서로 결과 집합이 출력된다.

1. 1. • CASE 1인 경우 사원 테이블에 데이터가 저장된 순서
      • CASE 2인 경우는 사원.직급인덱스 순서
      • CASE 3인 경우는 부서.지역 순서

조인 순서

옵티마이저는 조인 시에 먼저 드라이빙 테이블을 결정하고 나머지 집합의 조인 순서를 결정한다. 드라이빙 테이블은 드라이빙의 범위가 가장 작은 집합, 즉 가장 작은 작업량을 가지고 드라이빙할 수 있는 집합을 선정하고 조인의 순서를 정할 때에는 조인의 효율이 좋은 집합을 먼저 조인에 참여시키려고 노력한다. 여기에서 조인의 효율이 좋다는 의미는 조인의 결과로 출력하는 로우의 수가 작다는 것을 의미한다. 이것은 Nested Loop 조인의 경우 선행 집합의 결과가 다음 집합을 액세스 하는 작업량을 결정하기 때문이다.
CASE 3과 같이 사원.부서 코드에 인덱스가 있다면 옵티마이저는 사원을 드라이빙 테이블로 선정 할 수도 있다. 그리고 SQL문의 조건절에 부서.지역=.제주’AND 사원.직급 LIKE ‘A%’가 추가 된 경우는 CASE 2나 CASE 3로 실행 계획이 작성될 수 있다.

1. 1. • CASE 2 인 경우 : 사원.직급이.A’로 시작되는 사원을 검색하고 검색된 결과 집합으로 부서 테이블을 탐침한다. 직급이.A’로 시작되는 사원 100명이 검색되었다면 100명을 대상으로 부서를 탐침하게 되고, 이들 중 부서.지역이.제주’인 대상을 최종 결과 집합으로 출력하게 된다.
      • CASE 3 인 경우 : 부서.지역이.제주’인 부서를 검색하고 검색된 결과 집합으로 사원 테이블을 탐침한다. 만약, 2개의 부서가 검색되었다면 2개의 부서를 대상으로 모든 사원을 탐침하면서 사원.직급이.A’로 시작되는 사원을 최종 결과 집합으로 출력하게 된다. 위에서 언급한 것처럼 Nested-Loop 조인은 드라이빙 테이블의 선정과 조인 순서가 작업과 성능에 많은 영향을 미친다. 그리고 응답 시간에 대한 성능은 다음과 같은 규칙을 가지고 있다.
      • 드라이빙 조건의 범위가 좁은 경우는 항상 성능이 양호하다.
      • 드라이빙 조건의 범위가 넓은 경우는 체크 조건도 검색 범위가 넓어야 성능이 양호하다.

Sort-Merge 조인

Sort-merge 조인은 조인하려는 두 집합을 조인 속성으로 정렬하여 sorted lists를 만든 후 이들 을 merge하는 조인 기법으로, 인덱스가 없을 때 Simple Nested-Loop 조인으로 수행하는 비효율 을 개선하기 위한 방안으로 연구되었기 때문에 Inner 집합에 인덱스가 존재하지 않을 경우 수행하는 Simple Nested-Loop 조인보다 훨씬 더 좋은 성능을 나타낸다. Sort-merge 조인은 Simple Nested-Loop 조인의 가장 큰 비효율인 카티션 프로덕트를 해결하 기 위해 모든 튜플들이 조인 속성에 대해 같은 값을 갖도록 파티션함으로써 조인해야 하는 대상 튜플 들의 그룹들을 쉽게 검색이 가능하도록 구성하였다.

Sort-merge 조인이 동등 조인 조건에 대해서만 수행이 가능한 것은 이러한 파티션 기반의 방식 을 지원하고 있기 때문이다.

[그림 5-3-8]을 보면 Sort-Merge 조인은 다음과 같은 절차로 수행되고 있는 것을 알 수 있다.

1. 1. 1. ① 정렬 단계 : 조인에 참여하는 두 집합을 조인 조건에서 사용되는 속성을 기준으로 정렬한다.
      2. ② 머지 단계 : 정렬된 두 집합 중에서 하나의 집합을 차례로 검색하면서 다른 나머지 하나의 집합 에서 검색 조건에 맞는 튜플을 찾아 결과 집합에 포함시킨다. 머지 단계의 기본 알고리즘은 Nested-Loop 조인의 기본 알고리즘과 매우 흡사하다. 차이가 있다면 두 집합이 조인 속성으 로 정렬되어 있고 머지는 동등 조인 조건에서만 가능하므로 동등 조건이 아니면 머지를 시도하 지 않는다는 것이다. 동등 조건을 찾는 알고리즘이 인덱스의 머지 알고리즘과 비슷하여 머지 단 계가 인덱스 머지의 알고리즘과 동일하다고 이야기를 하는 경우도 있지만 그것은 절대 그렇지 않다.
      3. ③ 머지를 수행해 가면서 처음 동등 조건이 나타나면 Inner 집합을 하나씩 증가하면서 동등 조건인 경우 계속해서 머지를 수행한다. Inner 집합이 더 큰 값을 가지게 되면 검색을 멈추고 Outer 집합으로 회귀하여 Outer 집합에서 포인트를 증가시키고 다음 데이터를 읽는다.
      4. ④ ②, ③ 단계를 반복 수행한다.

조인 조건

Sort-Merge 조인은 조인 속성인 사원.부서코드와 부서.부서코드 칼럼에 인덱스가 없는 경우에 주로 발생한다. 조인은 위에서 언급한 것처럼 정렬 단계와 머지 단계로 나누어 수행된다.

출력 및 연결 순서

정렬된 결과를 순차적으로 비교하여 머지를 수행하므로 Outer 집합의 정렬 순서와 Inner 집합의 정렬 순서가 머지되어 출력된다. 그리고 조인에 참여하는 집합이 3개 이상이라면 조인의 순서가 조인 성능에 영향을 미칠 수 있다. Sort-Merge 조인도 조인의 순서를 결정하는 원리는 다른 조인 기법처럼 조인 효율이 좋은 집합을 조인에 먼저 참여시킨다. 즉, 선행 집합의 조인 결과가 다음 조 인에 참여하는 집합의 작업량에 영향을 미치므로 조인 효율이 좋은 집합을 조인에 먼저 참여시켜 야 전체적인 조인 성능이 좋아지게 된다.

조건절

조건절이 부서.지역='제주' AND 사원.직급 LIKE 'A%'가 추가된 경우는 사원.직급 LIKE 'A%'를 만족하는 100건을 정렬하고, 부서.지역이 제주인 2개 부서를 정렬하여 만족하는 5명을 출력한다. Sort-merge 조인은 소트에 참여하는 로우의 수에 의해 수행 속도가 결정된다. 정렬할 로우의 수 가 많은 경우는 정렬하는 데 수행되는 시간이 길어지므로 OLTP 환경에서 사용할 수 없다. 배치 작 업인 경우에도 정렬 작업이 메모리 내 정렬 영역(Sort area)을 초과할 경우는 스와핑이 발생하고 수행 속도가 더욱 느려진다. 필요시 정렬 영역을 추가 할당하는 것을 고려해야 한다.

이용

1. 1. 1. • 독립적으로 처리 범위를 줄인 후 조인에 참여하므로 테이블 각각의 조건에 의해 대상 집합을 줄일 수 있을 때 유리하다.
         • 처리 대상이 전체 테이블일 때 랜덤 IO 부하가 큰 Nested-Loop 조인보다 유리하다.
         • 조인 속성에 인덱스가 없을 때 Simple Nested-Loop 조인보다 성능이 우수하다.
         • 효과적인 수행을 위해서는 적정한 SORT AREA 사이즈가 확보되어야 한다.
         • 정렬에 대한 부하가 많이 발생하므로 대용량 처리 시 수행 속도가 저하될 수 있다.

Hash 조인

Hash 조인은 관계형 데이터베이스에서 비용이 가장 많이 들어가는 조인 방법이지만 대용량의 데 이터 조인 시에 Sort-merge 조인이나 Nested-Loop 조인보다 더 좋은 성능을 나타낸다. 이러한 이 유는 Sort-merge 조인의 경우 데이터량이 증가할수록 양쪽 집합을 정렬해야 하는 비용 부담이 커지 고, Nested-Loop 조인은 Inner 집합을 반복 탐침해야 하는 비효율이 더욱더 증가하기 때문이다. Hash 조인의 기본 알고리즘은“조인에 참여한 두 집합 중에서 작은 집합의 해쉬 테이블을 메모리 상에 만들고 큰 집합은 조인을 위해 해쉬 테이블을 탐침한다”는 것이다. Hash 조인은 이용 가능한 Hash area가 작은 집합을 유지할 만큼 충분히 클 경우에 만족할 정도로 좋은 성능을 나타내지만 이 용 가능한 메모리가 작은 집합을 유지할 정도로 충분하지 않다면 Hash area는 오버플로우가 발생 한다. Hash 조인은 이 문제를 다루기 위해 두 집합을 좀 더 작은 단위로 나누게 되는데, 이를 파티션 이라 한다.

Hash 조인은 다음과 같은 여러 단계로 나누어 조인을 수행한다.

Step 1 - 파티션 수

파티션의 개수가 많으면 I/O 효율을 떨어뜨리고 적으면 메모리 적중률을 떨어뜨리기 때문에 이를 적절하게 가져가는 것이 가장 중요하다.

Step2 - 해쉬 함수

조인에 참여한 두 집합 중에서 작은 집합을 드라이빙 테이블로 선택하여 메모리로 읽어 들인다. 이 때 해쉬되는 로우가 파티션에 골고루 분산되게 하기 위해 해쉬 함수1을 사용하여 해당 파티션에 매핑하고, 해쉬 함수2를 사용하여 생성된 해쉬 값은 다음 단계를 위하여 조인키와 함께 저장한다.

Step3 - 비트맵 벡트

비트맵은 2차원 버켓으로 이루어져 있으며 해쉬 함수 1,2를 통과하여 만든다. 즉, 파티션이 100개 라면 100*100의 10000개의 셀로 이루어지게 된다.

Step 4 - 디스크에 파티션 쓰기

Hash area가 모두 차면 가장 큰 파티션이 디스크로 내려간다. 디스크의 파티션은 파티션에 할당 되는 로우에 의해 디스크에서 갱신된다. Hash area의 부족으로 하나의 파티션만이 메모리에 올 라간다면 나머지 파티션은 모두 디스크에 놓여진다.

Step5 - 메모리에 적재 가능한 최대 파티션

Step5.1 - 최대 파티션 수를 정하고 크기순으로 파티션을 정렬한다.

Step5.2 - 파티션 번호가 가장 작은 것부터 선택하여 메모리에 로드한다.

Step5.3 - 나머지는 디스크에 저장한다.

Step6 - 작은 집합의 해쉬 테이블 생성

이미 생성된 해쉬 값을 사용하여 해쉬 테이블을 생성한다.

Step7 - 비트 벡트 필터링

조인 수행 시 비트맵과 대조하여 1이면 조인을 해야 하는 로우로 인식하고 아니면 조인이 필요 없 는 로우이므로 버린다. 이러한 과정을 비트 벡트 필터링이라고 하며, 조인되는 칼럼의 카디날리티 가 아주 적고 probe input 대부분이 일치하지 않을 때 아주 효과적이다.

Step8 - 처리되지 않은 파티션 쌍을 디스크로부터 읽어오기

큰 집합의 파티션이 끝나면 작은 집합의 수행되지 않은 파티션들이 최대한 메모리로 올려지고 해 쉬 테이블이 생성된다. 그리고 그에 대응되는 큰 집합의 파티션이 다시 읽혀져 메모리 조인이 실행 된다. 최초 파티션 조인에서 옵티마이저는 작은 집합을 build input으로 사용하고 큰 집합은 probe input으로 사용하지만 그 이후에는 파티션 쌍에서 작은 파티션을 build input으로 사용하 고 큰 파티션은 probe input으로 사용하는 동적 역할 전환(dynamic role reversal)이 일어난다.

Hybrid 조인

하이브리드 조인은 이름이 의미하는 것처럼 Nested-Loop 조인과 Sort-merge 조인의 알고리즘 을 혼합한 개념이다.

Indexed Nested-Loop 조인에서 Inner 테이블의 조인 속성이 non-clustered index로 되어있 을 경우 각 데이터 엔트리는 서로 다른 페이지를 가리키므로 Outer 테이블에서 반환되는 로우의 수만큼 Inner 테이블의 페이지를 탐침하여야 한다.

하이브리드 조인은 이러한 비효율을 개선하기 위해 Inner 테이블의 인덱스를 탐침할 때마다 테이 블을 검색하는 것이 아니라 Inner 테이블의 인덱스를 탐침한 후 그 결과를 중간 집합으로 생성하여 중복이 없는 Rowid 리스트를 만들고, 그 결과를 가지고 Inner 테이블의 페이지를 탐침하는 조인 방 식이다.