1. NL(Nested Loops) 조인

1. 기본 메커니즘

for (i=0; i<100; i++){          -- outer loop
	for (j = 0; j<100; j++){    -- inner loop
    ...
    }
 }

위 Java 이중 for 문 처럼 NL 조인은 'outer 테이블의 하나의 레코드에 inner 테이블의 모든 레코드를 방문한다' 라고 생각하면 된다.

2. 힌트로 NL 조인 제어

select /*+ ordered use_nl(e) */ *
from dept d, emp e
where e.deptno = d.deptno

위 쿼리에서 ordered 힌트는 from 절의 테이블을 기술된 순서대로 조인하라는 의미이고,
use_nl(e) 힌트는 'NL 방식으로 조인하는데 emp 테이블을 사용해라' 이다.
실행계획에서는 위쪽이 outer 테이블이다.

10g 부터는 leading 힌트를 사용해 테이블 조인 순서를 정할 수 있다.

3. NL 조인 수행 과정 분석

실행계획을 해석할 때, 형제 노드간데는 위에서 아래로 읽는다.
부모 자식 노드간에는 안쪽에서 바깥쪽으로, 즉 자식 노드부터 읽는다.

OLTP 환경에서는 조인을 튜닝할 때는 일차적으로 NL 조인부터 고려하는 것이 올바른 순서이다.
우선, NL 조인 메커니즘을 따라 각 단계의 수행 일량을 분석해 과도한 Random 액세스가 발생하는 지점을 파악한다.
조인 순서를 변경해 Random 액세스 발생량을 줄일 수 있는 경우가 있고, 그렇지 못할 때는 인덱스 컬럼 구성을 변경하거나 다른 인덱스 사용을 고려해야 한다.

모두 검토했을 때 NL 조인이 효과적이지 못하다고 판단되면 해시 조인이나 소트 머지 조인의 선택을 검토한다.

4. NL 조인의 특징

1. Random 액세스 위주의 조인 방식이다.

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

2. 조인을 한 레코드씩 순차적으로 진행한다.

아무리 대용량이라도 부분범위 처리가 가능한 상황에 극적인 응답 속도를 낼 수 있다.
outer 테이블의 처리 범위에 따라 전체 일량이 정해진다.

3. 인덱스 구성 전략이 특히 중요한 조인 방식이다.

조인 컬럼에 대한 인덱스가 있느냐 없느냐, 있다면 컬럼이 어떻게 구성됐느냐에 따라 조인 효율이 크게 달라진다.

NL 조인은 소량의 데이터를 주로 처리하거나 부분범위처리가 가능한 OLTP 환경에 적합한 조인 방식이라고 할 수 있다.

테이블을 액세스한 후에 필터링되는 비율이 높다면 인덱스에 테이블 필터 조건 컬럼을 추가하는 것을 고려해 볼 필요가 있다.

만약 조인 시 outer 테이블의 레코드 건수가 많고 inner의 레코드 건수가 적을 때 조인 순서를 바꾸는 것을 고려해볼 수 있다.

5. 테이블 Prefetch

오라클 9i부터 NL 조인 실행계획에 변화가 생겼다.
인덱스 rowid에 의한 inner 테이블 액세스가 Nested Loops 위쪽에 표시되곤 하는데, 이는 해당 테이블 액세스 단계에 Prefetch 기능이 활성화되었음을 표현한 것이다.
실행계획이 바꼈지만 내부적으로 비활성화되었을 수도 있다.

테이블 Prefetch를 제어하는 파라미터 중 하나인 _table_lookup_prefetch_size를 0으로 설정하면 다시 전통적인 NL조인의 실행계획으로 돌아간다.

Prefetch 기능이 실제로 작동하면 db file sequential read 대기 이벤트 대신
db file parallel reads 대기 이벤트가 나타난다.

Prefetch는 디스크 I/O를 수행하는데 한 번 I/O Call이 필요한 시점에, 곧이어 읽을 가능성이 큰 블록들을 캐시에 미리 적재해 두는 기능이다.
한 번의 I/O Call로써 여러 Single Block I/O를 동시에 수행한다.

6. 배치 I/O

오라클 11g에서 시작된 배치 I/O 메커니즘은 Inner 쪽 인덱스만으로 조인을 하고 나서 테이블과의 조인은 나중에 일괄처리하는 메커니즘이다.

테이블 액세스를 나중에 하지만 부분범위처리는 정상적으로 작동한다.
따라서 인덱스와의 조인을 모두 완료하고 나서 테이블을 액세스하는 것이 아니라 일정량씩 나누어 처리하는 것을 알 수 있다.

배치 I/O의 메커니즘 작동 힌트는 nlj_batching 이다.
원치 않을 때는 no_nlj_batching 또는 nlj_prefetch 힌트를 사용하면 된다.
그러면 테이블 Prefetch 방식으로 전환된다.

배치 I/O를 사용할 때 Inner 쪽 테이블 블록이 모두 버퍼 캐시에서 찾아지지 않으면
(버퍼 캐시 히트율 < 100%) 데이터 정렬 순서가 달라질 수 있다.

모두 버퍼 캐시에서 찾을 때 (버퍼 캐시 히트율 = 100%) 라면 똑같은 정렬 순서를 보인다.

7. 버퍼 Pinning 효과

1. 버퍼 Pinning - 오라클 8i

테이블 블록에 대한 버퍼 Pinning 기능이 작동하기 시작했다.
하나의 버퍼 블록만 Pinning 한다. 하나의 Fetch Call을 완료하는 순간 Pin을 해제한다.

하나의 outer 레코드에 대한 inner 쪽과의 조인을 마치고 다른 레코드를 읽기 위해
outer 쪽으로 돌아오는 순간 Pin을 해제한다.

2. 버퍼 Pinning - 오라클 9i (테이블 Prefetch)

9i 부터는 inner 쪽 인덱스 루트 블록에 대한 버퍼 Pinning 효과가 나타난다.
inner 쪽이 Non-Unique 인덱스일 때는 실행계획 상 테이블 액세스가 항상 NL 조인 위쪽에 올라가므로(테이블 Prefetch) 이때는 항상 버퍼 Pinning 효과가 나타나는 것이다.

3. 버퍼 Pinning - 오라클 10g

inner 쪽 테이블을 index range scan을 거쳐 NL 조인 위쪽에서 액세스할 때는, 하나의 outer 레코드에 대한 inner 쪽과의 조인을 마치고 outer 쪽으로 돌아오더라도 테이블 블록에 대한 Pinning 상태를 유지한다.

4. 버퍼 Pinning - 오라클 11g (배치 I/O)

11g에서는 User Rowid로 테이블 액세스할 때도 버퍼 Pinning 효과가 나타난다.
또한 NL 조인에서 inner 쪽 루트 아래 인덱스 블록들도 Pinning하기 시작했다.
브런치 블록도 Pinning 한다는 의미이다.

---

2. 소트 머지 조인

1. 소트 머지 조인 메커니즘

소트 머지 조인은 이름처럼 두 테이블을 소트(정렬)하고 머지(병합)하면서 조인을 수행한다.

1. 소트 단계 : 양쪽 집합을 조인 컬럼 기준으로 정렬한다.

2. 머지 단계 : 정렬된 양쪽 집합을 서로 머지한다.

소트 머지 조인은 outer loop 와 inner loop 가 PGA 영역에 할당된 Sort Area의 미리 정렬해 둔 자료구조를 사용하기 때문에 SGA를 경우해 인덱스와 테이블을 액세스할 때보다 훨씬 빠르다.

=> PGA는 프로세스만을 위한 독립적인 메모리 공간이어서 데이터를 읽을 때 래치 획득 과정이 없기 때문이다.

소트 머지 조인은 use_merge 힌트를 가지고 유도할 수 있다.

2. 소트 머지 조인의 특징

소트 머지 조인은 양쪽 집합을 정렬한 다음에는 NL 조인과 같은 방식으로 진행하지만 PGA 영역에 저장된 데이터를 이용하기 때문에 빠르다.
따라서 소트 부하만 감수한다면, 건건이 버퍼 캐시를 거치면서 조인하는 NL 조인보다 유리하다.

NL 조인은 조인 컬럼에 대한 인덱스 유무에 따라 크게 영향을 받지만 소트 머지 조인은 영향을 받지 않는다.
그리고 양쪽 집합을 개별적으로 읽고 나서 조인한다.
따라서 인덱스가 없는 상황에서 두 테이블을 독립적으로 읽어 조인 대상 집합을 줄일 수 있을 때 아주 유리하다.

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

대용량 데이터 처리에서 해시 조인 보다 소트 머지 조인을 사용해야 될 때

1. Outer 테이블에 소트 연산을 대체할 인덱스가 있을 때

소트 머지 조인은 inner 테이블은 전체범위 처리이고, outer 테이블도 보통 전체범위 처리이지만,
Outer 테이블 조인 컬럼에 인덱스가 있을 때 outer 테이블의 일부만 읽고 멈출 수 있다.
Outer 테이블에만 부분 범위 처리가 가능하다는 의미이다.

만약 이렇게 처리할수 있다면 OLTP성 업무에서 소량의 테이블과 대량의 테이블을 조인할 때 소트 머지 조인을 유용하게 사용할 수 있다.

소트 머지 조인에서 인덱스를 이용해 소트 연산을 대체할 수 있는 대상은 Outer 테이블 뿐이다.

2. 조인할 Outer 집합이 이미 정렬돼 있을 때

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

3. 조인 조건식이 등치(=)가 아닐 때

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

조인 조건식의 부등호와 반대로 order by 절을 기술하면 소트 오퍼레이션이 나타난다.
예를 들어
d.deptno >= e.deptno 조인 조건일 때 order by d.deptno 나 e.deptno를 정렬이나
d.deptno <= e.deptno 조인 조건일 때 order by d.deptno desc 나 e.deptno를 정렬하면 소트 오퍼레이션이 나타난다.

---

3. 해시 조인

1. 기본 메커니즘

해시 조인은 둘 중 작은 집합(Build Input)을 읽어 Hash Area에 해시 테이블을 생성하고, 반대쪽 큰 집합(Probe Input)을 읽어 해시 테이블을 탐색하면서 조인하는 방식이다.

해시 테이블을 생성할 때 해시 함수를 사용한다.
즉, 해시 함수에서 리턴받은 버킷 주소로 찾아가 해시 체인에 엔트리를 연결한다.

해시 테이블을 탐색할 때도 해시 함수를 사용한다.
즉, 해시 함수에서 리턴받은 터밋 주소로 찾아가 해시 체인을 스캔하면서 데이터를 찾는다.

해시 조인은, NL 조인처럼 조인 과정에서 발생하는 Random 액세스 부하가 없고, 소트 머지 조인처럼 조인 전에 미리 양쪽 집합을 정렬하는 부담도 없다.
다만, 해시 테이블을 생성하는 비용이 커서 Build Input이 작을 때 효과적이다.
PGA 메모리에 할당되는 Hash Area에 담길 정도로 충분히 작아야 된다.
만약 Build Input이 Hash Area 크기를 초과한다면 디스크에 썼다가 다시 읽어 들이는 과정을 거치기 때문에 성능이 많이 저하된다.
또 Build Input의 해시 키 값으로 사용되는 컬럼에 중복 값이 거의 없을 때 효과적이다.

해시 테이블을 만드는 단계에서 전체범위처리가 불가피하지만 반대쪽 Probe Input을 스캔하는 단계는 NL 조인처럼 부분범위처리가 가능하다.

해시 조인이 인덱스 기반의 NL 조인 보다 빠른 결정적인 이유는, 해시 테이블이 PGA 영역에 할당된다는 이유이다.

=> 소트 머지 조인과 같이 PGA 공간을 활용하므로 래치 획득 과정을 생략해 빠르게 데이터를 탐색한다.

2. 힌트를 이용한 조인 순서 및 Build Input 조정

힌트를 지정하지 않으면 옵티마이저가 통계 정보를 보고 더 작은 테이블을 Build Input 으로 지정한다.
Build Input 을 사용자가 직접 지정하려면 swap_join_inputs 힌트를 사용하면 되지만, 단 2개의 테이블을 해시 조인할 때는 ordered나 leading 힌트를 사용해도 된다.

3. Build Input이 Hash Area를 초과할 때 처리 방식

1. Grace 해시 조인

1. 파티션 단계

조인되는 양쪽 집합 모두 조인 컬럼에 해시 함수를 적용하고, 반환된 해시 값에 따라 동적으로 파티셔닝을 실시한다.
=> 파티션 짝을 생성하는 단계

파티션 단계에서 양쪽 집합을 모두 읽어 디스크 상의 Temp공간에 일단 저장해야 하므로 In-Memory 해시 조인보다 성능이 크게 떨어진다.

2. 조인 단계

파티션 단계가 완료되면 각 파티션 짝에 대해 하나씩 조인을 수행한다.
이때, 각각에 대한 Build Input과 Probe Input은 독립적으로 결정된다.
즉, 파티션하기 전 어느쪽이 작은 테이블이었는지 상관없이 각 파티션 짝별로 작은 쪽 파티션을 Build Input으로 선택해 해시 테이블을 생성한다.

해시 테이블이 생성되고 나면 반대 쪽 파티션 로우를 하나씩 읽으면서 해시 테이블을 탐색하며, 모든 파티션 짝에 대한 처리가 완료될 때까지 반복한다.

Grace 해시 조인은 분할-정복 방식이라고 말할 수 있다.
실제로는 벤더마다 조금씩 변형된 Hybrid 방식을 사용하지만 두 개의 큰 테이블을 해시 조인하는 기본 알고리즘은 Grace 해시 조인에 바탕을 두고 있다.

2. Hybrid 해시 조인

Grace 해시 조인에 따른다면 디스크 I/O 부하가 심할 것이다.
이런 단점을 보완하기 위해 오라클은 Hybride 해시 조인을 제공한다.

1. 두 테이블 중 작은 쪽은 Build Input으로 선택하고 Hash Area에 해시 테이블을 생성하기 시작한다.
   이 때 두 개의 해시 함수를 적용하는데, 첫 번째 해시 값으로는 레코드를 저장할 파티션을 결정하고,
   두 번째 해시 값은 나중에 실제 조인할 때를 위해 레코드와 함께 저장해 둔다.

2. 해시 테이블을 생성하는 도중에 Hash Area가 꽉 차면 그 중 가장 큰 파티션을 디스크에 기록한다.

3. 해시 테이블을 완성하기 위해 Build Input을 계속 읽는 동안 이미 디스크에 기록된 파티션에 해당되는 레코드는 디스크 파티션에 기록한다.

4. 다시 Hash Area가 다 차면 가장 큰 파티션을 디스크에 기록한다.

5. 이렇게 첫 번째 테이블에 대한 파티셔닝 단계가 끝나면 파티션 크기가 작은 순으로 메모리를 채운다.

6. 이제 두 번째 테이블을 읽기 시작하는데, 이때도 두 개의 해시 함수를 사용한다. 읽혀진 레코드의 첫 번째 해시 값에 해당하는 파티션이 현재 메모리에 있다면 그 파티션을 스캔하고, 거기서 조인 레코드를 찾으면 곧바로 결과집합에 포함시킨다. 이때 첫 번째 해시 값으로 곧바로 파티션을 스캔하는 것이 아니라 비트-벡터 필터링을 거쳐 선택된 레코드만 파티션을 스캔하고, 선택되지 않은 레코드는 그냥 버린다.

7. 비트-벡터 필터링을 통과했지만 메모리에서 매칭되는 파티션을 찾지 못하면 Build Input을 파티셔닝할 때와 같은 방식으로 해시 파티셔닝한다.
   즉, 첫 번째 해시 값으로 레코드가 저장될 파티션을 결정하고, 두 번째 해시 값과 함께 디스크로 저장된다.
   여기서, 6번 단계에서 비트-벡터 필터링을 거친 레코드만 디스크에 기록하게 된다.

8. 7번 과정을 마치고 나면 양쪽 테이블 모두 같은 해시 함수로써 파티셔닝했기 때문에 같은 해시 값을 갖는 레코드끼리는 같은 파티션 짝에 놓이게 되었다.
   이제 각 파티션 짝에 대해 하나씩 조인을 수행하기만 하면 되는데, 각 파티션 짝 별로 작은 쪽 파티션을 Build Input으로 선택해 해시 테이블을 생성한다. 이때, 1번과 7번 단계에서 저장해 둔 두 번째 해시 값이 이용된다.

9. 모든 파티션에 대해 8번 과정을 반복함으로써 해시 조인을 마친다.

3. Recursive 해시 조인

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

Recursive 해시 조인을 'Multipass 해시 조인' 이라고도 하며, 디스크 쓰기가 발생했지만 Multipass 오퍼레이션을 거치지 않는 경우를 'Onepass 해시 조인' 이라고 한다.
디스크를 전혀 사용하지 않은 In-Memory 해시 조인을 'Optimal 해시 조인' 이라고 한다.

4. 비트-벡터 필터링

조인 성공 가능성이 없는 파티션 레코드는 아예 디스크에 기록되지 않게 하기 위해 비트-벡터 필터링을 사용한다.
비트-벡터 필터링을 사용해 나중에 조인 단계에서 실패할 수 밖에 없는 레코드를 디스크에 기록하지 않고 버린다면, 이를 다시 읽어 조인하지 않아도 되므로 Grace 해시 조인의 성능을 크게 향상시킬 수 있다.

4. 해시 조인 사용 기준

• 한쪽 테이블이 Hash Area에 담길 정도로 작아야 함

• Build Input 해시 키 컬럼에 중복 값이 거의 없어야 함

해시 조인의 효과적인 상황

• 조인 컬럼에 적당한 인덱스가 없어 NL 조인이 비효율적일 때

• 조인 컬럼에 인덱스가 있더라도 NL 조인 드라이빙 집합에서 Inner 쪽 집합으로의 조인 액세스량이 많아 Random 액세스 부하가 심할 때

• 소트 머지 조인하기에는 두 테이블이 너무 커 소트 부하가 심할 때

• 수행빈도가 낮고 쿼리 수행 시간이 오래 걸리는 대용량 테이블을 조인할 때

  => 해시테이블은 단 하나의 쿼리를 위해 생성하고 조인이 끝나면 사라지는 자료구조인데,
  수행빈도가 높으면 CPU와 메모리 사용률이 크게 증가함