NL 조인, Hash Join

* 무조건적인 비교보다는 어떤 상황에서 유리한 방식인지를 중점으로 정리해봤다.

 

1. NL 조인 방식

1) 두 개의 테이블을 선행 테이블과 후행 테이블로 분류(힌트를 걸어 임의로 조종할 수도 있음)

2) 선행 테이블에서 조건에 맞는 칼럼을 추출

3) 후행 테이블과의 비교 연산을 통해 최종 출력

 

2. NL 조인 특징

선행 테이블, 후행 테이블에서 비교 연산을 할 때 인덱스에 의한 랜덤 액세스 방식으로 수행한다.

인덱스를 참조하는 조회인 경우엔 효과적으로 작동할 수 있다.

 

3. NL 조인 한계

대용량 데이터를 접근하는데엔 치명적이다.

랜덤 액세스는 하나의 레코드를 읽어도 블록을 통째로 읽어야 하는 방식을 가지기 때문이다.

또한 인덱스 구성에 대해 조인 효율이 크게 달라질 수 있다.

이에 대해, oracle 11g부터는 prefetch 및 배치 I/O 라는 기능을 도입했는데 그 배경은 다음과 같다.

 

4. 인덱스에 의존적인 NL 조인과 극복 방안

랜덤 액세스 방식으로 메모리에서 원하는 칼럼을 찾지 못하는 경우 디스크를 참조해야 한다.

prefetch, 배치 I/O는 이러한 디스크 참조를 효율적으로 하기 위해 도입됐다.

prefetch 방식은 NL 조인에서 디스크를 참조하는 경우가 발생하면 미리 다음 블록을 가져오는 방식이다.

배치 I/O 방식은 일정량을 모아두었다가 한 번에 디스크 I/O call을 하는 것이다.

하지만 이런 방법 말고도 해시 조인을 사용해서도 NL 조인의 한계를 극복할 수 있다.

 

5. 해시 조인 방식 및 특징

볼륨이 더 작은 테이블에 대해 해시 테이블을 생성한 후

해시 함수에서 리턴 받은 버킷(테이블) 주소를 찾아가 해시 체인을 스캔하면서 데이터를 출력한다.

고유한 값을 가지는 해시 테이블은 O(1)이라는 엄청난 조회 속도를 가진다.

수행시간이 길게 느껴진다고 하는 경우 해시 조인을 사용하는 방법을 고려해봐야 한다.

 

6. 해시 조인 한계

NL 조인에 비해 무조건적으로 우수하다고 볼 수 없다. 결정적인 차이는 수행빈도에 있다.

수행빈도가 높을수록 NL 조인이 유리한데 그 이유에 대해선 다음과 같다.

 

NL 조인에 사용되는 인덱스는 거의 영구적으로 유지되면서 재사용되기 때문이다.

반면에 해시 조인의 경우, 단 하나의 쿼리를 위해 해시 테이블을 만들고 곧바로 메모리에서 소멸시킨다.

해시 테이블을 생성하는데 걸리는 시간도 적지 않다는 점을 감안해야 한다.

해시 테이블이 지나치게 커지는 경우 해시 충돌에 의한 탐색 속도가 N배 만큼 지연될 수 있다.

심지어 한 쪽 테이블이 가용 메모리에 담길 정도로 작아야 하는데

가용 용량보다 초과되는 경우 디스크 영역에서 추가적인 파티셔닝 단계를 수행하기 때문이다.