NL Join / Sort Merge Join / Hash Join

1. NL Join(Nested Loops Join)

- 2개 이상의 테이블에서 하나의 집합을 기준으로 순차적으로 상대방 Row를 결합하여 원하는 결과를 조합하는 조인 방식이며, 데이터가 많지 않은 경우에 유용하게 사용한다.

- 실행계획에서 먼저 실행되는 테이블이 Driving Table, 나중에 실행되는 테이블이 Driven Table이라고 한다.

Driving Table : DEPT / Driven Table : EMP

기본 메커니즘

/* C, JAVA */
for(i=0; i<100; i++){
	for(j=0; j<100; j++){
    	....
    }
}

# PL/SQL
for outer 1..100 loop
	for inner in 1..100 loop
    	dbms_output.put_line(outer || ':' || inner);
    end loop;
end loop;

Nested Loops Join은 위와 같은 중첩 루프문과 동일한 원리이다.

NL Join 특징

● 랜덤 액세스(Random Access)방식으로 데이터를 읽는다. 많은 양의 데이터를 조인 시 Random Access가 증가하기 때문에 대량의 데이터 처리 시 적합하지 않다. 그래서 데이터 양이 적을때 사용하면 효과적이다.

● Driving Table은 데이터가 적거나 where 조건으로 row수를 줄일 수 있는 테이블이어야한다.

● Driven Table에는 조인을 위한 인덱스가 생성되어 있어야 함

● 조인을 한 레코드씩 순차적으로 진행

● 선행 테이블의 결과를 통해 후행 테이블을 액세스 할 때 랜덤 I/O가 발생함

 

NL 수행방식

1) 선행 테이블에서 조건을 만족하는 첫 번째 행을 찾음 > 조건을 만족하지 않는 경우 해당 데이터는 필터링 된다. 2) 선행 테이블의 조인 키를 가지고 후행 테이블에 조인 키가 존재하는지 찾으러 감 > 조인 시도 3) 후행 테이블의 인덱스에 선행 테이블의 조인 키가 존재하는지 확인 > 선행 테이블의 조인 값이 후행 테이블에 존재하지 않으면 선행 테이블 뎅디터는 필터링 됨 4) 인덱스에서 추출한 레코드 식별자를 이용하여 후행 테이블을 액세스 > 후행 테이블에 주어진 조건까지 모두 만족하면 해당 행을 추출버퍼에 넣음

 

2. Sort Merge Join

- 조인 컬럼을 기준으로 데이터를 정렬하여 조인을 수행함, 조인 칼럼의 인덱스가 존재하지 않는 경우에도 사용할 수 있음

- Full Table Scan 방식으로 데이터를 읽는 기법이다. 

- NL Join에서의 랜덤 액세스로는 부담이 되던 넓은 범위의 데이터를 처리할 때 이용하는 조인 기법이다. 그러나 정렬할 데이터가 많아 메모리에서 모든 정렬 작업을 수행하기 어려운 경우에는 임시 영역(디스크)을 사용하기 때문에 성능이 감소할 수 있다.

- 성능상 Hash Join이 성능한 유리하지만 Sort Merge Join은 동등 조인뿐만 아니라 비동등 조인에 대해서도 조인 작업이 가능하다.

 

기본 메커니즘

● 두 테이블을 각각 정렬한 다음에 두 집합을 Merge하면서 조인을 수행한다.

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

        ● Merge단계 : 정렬된 양쪽 집합을 서로 Merge 한다.

● Sort Merge Join은 Outer Loop와 Inner Loop가 Sort Area에 미리 정렬해둔 데이터를 이용할 뿐, 실제 조인과정은 NL 조인과 동일하다.

● Sort Area가 PGA영역에 할당되므로 Latch획득 과정이 없기 때문에 SGA를 경유하는 것 보다 훨씬 빠르다.                       

SELECT /*+ ordered use_merge(e) */ D.DEPTNO, D.DNAME, E.EMPNO, E.ENAME
FROM DEPT D, EMP E
WHERE D.DEPTNO = E.DEPTNO;

Sort Merge Join

처리과정

1) Outer(=First) Table인 DEPT를 DEPTNO 기준으로 정렬한다. 2) Inner(=Second) Table인 EMP를 DEPTNO 기준으로 정렬한다. 3) Sort Area에 정렬된 DEPT테이블을 스캔하면서, 정렬된 EMP 테이블과 조인한다.

- EMP 테이블이 정렬되어 있으므로 조인에 실패하는 레코드를 만나는 순간 멈출 수 있다.

- 스캔하다가 멈춘 시작점을 기억했다가 거기서부터 시작하면 되므로, 정렬된 EMP에서 스캔 시작점을 찾으려고 매번 탐색하지 않아도 된다.

 

Sort Merge Join 특징

● PGA 영역에서 저장된 데이터를 이용하기 떄문에 빠르므로 Sort부하만 감수하면 NL조인보다 유리하다.

● 인덱스 유무에 영향을 받지 않는다.

● 스캔위주의 액세스방식을 사용한다.

● 대부분 Hash Join보다 느린 성능을 보이나, 아래와 같은 상황에서는 Sort Merge Join이 더 유용하다

      ■ First Table에 Sort연산을 대체할 인덱스가 있을 때

      ■ 조인할 First 집합이 이미 정렬되어 있을 때

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

● 두 결과 집합의 크기가 많이 차이나는 경우에는 Sort Merge Join이 비효율적

Sort Merge Join 수행 방식

Sort Merge Join

1) 선행 테이블에서 주어진 조건을 만족하는 행을 찾는다. 2) 해당 행들에 대해서, 선행 테이블의 조인 키(칼럼)를 기준으로 데이터를 정렬 3) 후행 테이블에서 주어진 조건을 만족하는 행을 찾는다. 4) 해당 행들에 대해서, 후행 테이블의 조인 키(칼럼)를 기준으로 데이터를 정렬 5) JOIN을 수행 6) 조인에 성공하면 추출버퍼에 넣는다.

 

3. Hash Join

- 두 테이블 중 하나를 해시 테이블로 선정하여 조인될 테이블의 조인 키값을 해시 알고리즘으로 비교하여 매치되는 결과값을 얻는 방식 

- 동등 조인에서만 사용할 수 있다. 

- CPU 작업 위주로 데이터를 처리하며, NL Join의 랜덤 액세스 문제점과 Sort Merge Join의 문제점인 정렬 작업의 부담을 해결 위한 대안으로 등장함

 

기본 메커니즘

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

Hash Join

작은 집합(Build Input)을 읽어 해시맵 생성

> 해시테이블을 생성할 때 해시함수를 사용하고, 해시함수에서 리턴받은 버킷주소(A,B,C,D)로 찾아가 해시체인에 엔트리를 연결한다.

 

큰 집합(Probe Input)을 스캔

> 해시테이블을 탐색할 떄도 해시함수를 사용하며, 해시함수에서 리턴받은 버킷주소(A,B,C,D)로 찾아가 해시체인을 스캔하면서 데이터를 찾는다.

SELECT /*+ use_hash(d e) */ 
D.DEPTNO, D.DNAME, E.EMPNO, E.ENAME
FROM DEPT D, EMP E
WHERE D.DEPTNO = E.DEPTNO;

 

Hash Join 특징

● NL Join처럼 조인시 발생하는 Random Access 부하가없다.

● Sort Merge Join 처럼 조인 전에 양쪽 집합을 정렬해야 하는 부담이 없다.

● Build Input이 작을 때 효과적이다.(PGA에 할당되는 Hash Area에 담길 정도로 충분히 작아야함)

● 해시키 값으로 사용되는 컬럼에 중복값이 거의 없을 경우 효과적이다.

● Inner Loop로 Hash Area에 생성해둔 해시테이블을 이용한다는 것 외에 NL Join과 유사하다

● Hash Table 만들 때는 전체범위처리가 불가피하나, Prob Input을 스캔하는 단계는 부분범위 처리가능하다.

● Hash Join은 Hash Table이 PGA영역에 할당 되므로, NL 조인보다 빠르다. Hash Join은 Latch 획득 과정없이 PGA에서 빠르게 데이터를 탐색할 수 있다.

 

Hash Join 수행 방식

Hash Join

1) 선행 테이블에서 주어진 조건을 만족하는 행을 찾는다 2) 해당 행들에 대해서, 선행 테이블의 조인 키(칼럼)를 기준으로 Hash 함수를 적용하여 Hash Table을 생성 3) 후행 테이블에서 주어진 조건을 만족하는 행을 찾는다. 4) 해당 행들에 대해서, 후행 테이블에 Hash 함수를 적용하여 선행 테이블의 Hash Table에서 맞는 버킷을 찾음 5) Join을 수행 & 조인에 성공하면 추출버퍼에 넣는다. 6) 후행 테이블의 조건을 만족하는 모든 행에 대해서 3~5번 반복

 

 

 

반응형

 

 

 

 

참고 : http://wiki.gurubee.net/pages/viewpage.action?pageId=4948020&

          https://hoon93.tistory.com/46