[DB] Nested Loop Join, Hash Join

출처: http://jjekr.egloos.com/3129366

옵티마이저를 공부하기에 앞에서 반드시 알아야 할 것 중 한가지
Nested Loop Join 과 Hash Join은 각각 어떤 경우에 사용해야 하는가? 이다.


조인에는 두가지의 대표적인 조인이 있다. Neseted Loop Join 과 Sort Merge Join
이전에 Rule based optimizer 시절에는 sort merge가 없었다. 
다량의 데이터를 조인하기에서는 NL loop 는 random i/o가 많다.
또 조인 조건에 해당되는 컬럼에 인덱스가 없을 경우 NL loop에서는 full scan 하게 되므로 엄청난 오버헤드를 가지게 된다. 
옵티마이저가 진화하면서 이를 해결하기 위해 단 두번의 scan으로 처리가 가능한 Sort merge, Hash Join이 생기게 되었다.


Nested Loop Join
어느 한쪽이 먼저 드라이빙 되서 거기서 나오는 상수값으로 다른쪽으로 읽어나가는 조인 방법

select a.fld1, ....., b.fld1,...
from tab1 a, tab2 b
where a.key1 = b.key2
and a.fld1 = 'AB'
and b.fld2 = '10' -> b테이블의 조건이 없어도 처리량에 영향을 주지 않음.

1. 순차적이다. 
2. 부분범위 처리가 가능하다.
3. 종속적이다. 드라이빙 테이블의 처리범위에 따라 처리량 및 속도가 결정된다.
4. Random access 위주, single block , random i/o가 많이 일어난다.
5. 연결고리 상태에 민감하다. 
inner table 검색시에는 인덱스를 사용하므로 inner 테이블의 인덱스 효율이 좋아야 한다.
6. 좁은 범위처리에 유리하다. (쿼리 수행결과가 전체 row의 15% 이내일 경우 유리) 
7. 인덱스의 효율이 좋다면 가장 최적의 성능을 발휘하는 조인기법이다.
8. 드라이빙테이블이 아닌 테이블의 조건이 없어도 일의 량에 별로 영향을 주지 않으므로 NL loop가 유리하다.
예) 주문처리


Sort Merge Join
조인이 되는 각각의 테이블 자료를 스캔방식으로 읽어 들이거나 인덱스를 사용하여 메모리로 읽어들인다. 
읽혀진 두 테이블의 조인 집합은 연결 고리 컬럼에 대하여 각각 정렬을 수행한 후 비교하여 조인 작업이 수행된다.
정렬을 수행하기 위하여 sort_area_size 크리 만큼 메모리를 할당 받아 사용하게 되며, 메모리가 부족하다면
temporary tablespace 를 이용하여 정렬을 수행하게 된다.
그러므로 튜닝시 Sort를 얼마나 효과적으로 하느냐, SORT_AREA_SIZE를 적절한 크기로 지정하는 것이 관건이다.

1. 동시적이다.
부분범위 처리가 불가능하다. 소트가 끊나야 이루어 지므로 무조건 전체범위처리
전체 데이터를 리턴받는 시간이 NL loop보다 빠르다. 주로 넓은 범위 처리에 유리
2. 추가적인 sort memory 비용이 필요하다. 메모리 공간이 부족하다면 temp tablespace를 사용하게 된다.
3. 독립적이다. 자기의 처리범위만으로 처리량을 결정한다.
NL loop의 경우 드라이빙 테이블이 아닌 테이블에 조건이 없으면 체크조건이 없으므로 운반단위가 빨라져 응답속도가 빨라진다. 
하지만 sort merge의 경우 조건이 없으면 풀스캔해야 하므로 느려진다.
4. 스캔 액세스 위주
5. 연결고리 상태에 영향이 없음. 
6. 정렬작업이 전체 성능에 많은 영향을 미치므로 select 절에서 불필요한 컬럼은 제거해서 정렬 작업시 부하를 줄여 주어야 한다.
7. sort를 요구하지 않는 경우 Hash Join이 유리하다.
8. 두 결과 집합의 크기가 많이 차이나는 경우에는 Sort merge join 이 비효율적이다.
어느 한쪽이라도 정렬 작업이 종료되지 않으면 조인이 시작될 수 없으므로 두 테이블 조인 집합의 크기가 많이 차이 난다면 
한쪽에 '대기' 상태가 발생하여 비효율적으로 처리가 된다. 
이렇게 크기가 비슷하지 않은 집합의 조인을 위해서는 hash조인을 사용할 수 있다.
예) 배치프로그램, 통계


Hash Merge Join
해쉬조인은 대용량 처리의 선결조건인 랜덤과 정렬에 대한 부담을 해결 할 수 있는 대안으로서 등장했다.
*해쉬함수 : 데이터의 컬럼에 있는 상수값을 입력으로 받아 '위치값'을 리턴한다.
*해싱 : 하나의 문자열을 원래의 것을 대신하는 보다 짧은 길이의 값이나 키로 변화하는 것이다.

Hash Join Method만을 이용하는 것보다 Parallel Processing을 이용한 Hash Join은 대용량 데이터를 처리하기 위한 최적의 솔루션을 제공해주고 있다.

<특징>
- CBO(Cost based optimization) 에서만 가능하며, CPU Power에 의존적이다.
- Hash Join은 equal만 가능
- Hash Join은 두개의 조인 테이블 중 small rowset을 가지고 hash_area_size에 지정된 메모리 내에서 hash table을 만든다.
- Hash Table을 만든 이후부터는 Nested_Loop의 장점인 순차적인 처리 형태로 수행된다.
Hash Joindms Nested Loop와 Sort Merge의 장점을 가지고 있다.
- 기존에 미리 생성되어 있는 인덱스를 전혀 사용하지 않는다.
먼저 수행되는 집합이 어느것인지 확인할 필요가 있다.
옵티마이저가 해쉬조인을 너무 과신한 나머지 소량의 데이터의 경우에도 모두 해쉬조인으로 처리하려는 경향이 많으므로 실전에서는 이러한 면을 반드시 주의깊게 살펴봐야 할 것이다.
- 초대형 조인이라면 반드시 해쉬조인을 적용해야 한다고 생각할 수 있다.
대용량의 데이터를 조인한다면 상당히 큰 해쉬 영역을 필요로 하므로 수많은 프로세스가 공동으로 사용하는 귀중한 메모리를 함부로 차지한다는 것은 시스템 전체 시각에서 볼 때는 커다란 오버헤드가 될 수 있다. 온라인 처리에서 함부로 해쉬조인을 적용하는 것은 문제를 발생시킬 소지가 충분히 있다.

<수행방법>
1. 인덱스 스캔을 통해 제공받은 rowid를 통해 테이블에 random Access를 한다.
2. 추출한 테이블의 컬럼값에 Hash Function을 적용한 후 해쉬값을 제공받아 Hash Table을 구성
3. 2번에서 추출한 Hash Table을 PGA에 구성하게 된다. 이때 Hash_area_size로 정의된 Parameter의 값만큼 구성
4. 조인하기 위한 테이블과 해쉬 테이블을 조인하여 성공 여부를 규명