[DB] Nested loop join, Merge join, Hash join 알아보기

 

 

Nested loop join, Merge join, Hash join 알아보기

 

 

Nested loop join

첫번째 데이터 테이블을 순환하면서, 첫번째 데이터 테이블 데이터 1개당, 두번째 데이터 테이블 전체를 순환하는것.

반복문으로 한테이블을 여러번 풀테이블 스캔을 하는 것.

1. 인덱스가 필수적이다.

2. 작은데이터에 적합하다.

3. 작은 데이터 집합에 빠르게 처리할 수 있기 때문에 실시간성인 OLTP시스템에 적합하다.

OLAP시스템에서는 데이터양이 매우 크기 때문 에 적합하지않다.

작업량

T1 * T2

특징

1. 작은 데이터 세트나 매우 큰 테이블의 작은 부분만 결합할 때 가장 적합하다.

(T1 * T2가 작은 경우에 유리하다. 즉 조인하고자하는 작은 테이블은 더 작게 큰 테이블은 더 클때 유리하다. )

(작업량이 M * N 이기 때문이다.)

2. 하지만 T1에서 더 많은데이터들을 가져와서 T2에서 조인할 수록 성능이 급격히 떨어진다. 어느순간부터는 해시조인이 유리하다.

 

 

 

 

 

Merge join

두 데이터 테이블을 조인 컬럼을 기준으로 정렬한 뒤, 조인.
 첫번째 데이터 테이블을 순환하면서 조인할때, 첫번째 데이터 테이블 데이터 1개당 두번째 테이블을 해당 값보다 작은것부터 큰 값까지 일부만 조회하면 된다.

Nested loop join보다 데이터 탐색 범위가 줄어든다

즉, 반복문으로 인덱스 레인지 스캔을 하는 것과 비슷하다

하지만 정렬되어 있지 않은 경우 정렬비용이 발생한다. 정렬비용이 크다

 

 

작업량

T1logT1 + T2logT2

 

 

 

Hash join

첫번째 테이블에 대해 해시함수를 적용하여 해시테이블을 구축한다.
두번째 테이블의 모든 행을 순환하면서 동일한 해시함수를 적용하고 해시테이블에 일치하는 값이 있는지 확인한다.

 

해시함수

같은 입력값에대해 같은 출력값을 보장하는 함수

 

 

장점

각 행을 최대 1번만 읽을 수 있다.

 

 

작업량

T1+T2

(T1에서는 해시함수로 해시테이블을 만들고
T2에서는 해시함수로 해시테이블에 있는지 조회)

 

특징

1. 데이터 테이블 2개를 1번씩 읽어야 한다. 

2. 테이블의 모든 행을 조인할 때나 대규모 데이터 세트를 조인할 때 가장 효율적이다. 인덱싱되지 않았을때 효율적이다

3. 해시테이블을 사용하여 메모리 사용량이 크다

4.동등조건(=)가 필요하다

 

양쪽의 테이블이 둘다 크다면 hash조인이 가장 효율적이다. 그렇다면 nested loop조인과 merge join은 왜 쓰는걸까?

해시조인을 쓰기위한 조건으로는 조인조건이 =이어야한다.

그외 조인 조건이 범위 비교인경우(<,>,!=)등일 경우 옵티마이저는 해시조인을 쓰지않는다


조인조건이 =이어도 nested loop조인과 merge조인이 해시조인보다 더 빠른 경우도 있다.

-> 해시조인의 특성상 첫번째, 두번째 테이블의 모든 데이터를 1번씩 읽어야하고, 인덱스를 사용할 수 없기 때문이다.

때문에 아주 일부의 데이터만을 조인한다면 해시조인이 오히려 비효율적이다 

 

한 테이블의 행중 일부만 찾아지고, 그 각각이 다른 테이블 행들과 일치하는 경우, 중첩루프 조인이 가장 빠를 수 있다.