Holik in everything!

이 글은 Sachin Arora의 Nested loops, Hash join and Sort Merge joins – difference? 라는 글에 기초하여 약간의 수정을 가한 것입니다.

1. Nested loop join (loop over loop)

이 알고리즘은 외부 루프와 내부 루프로 구성된다. 외부 루프는 몇몇의 엔트리로 구성되며, 외부 루프의 각 엔트리마다 내부 루프가 수행된다.

예)

이 SQL문은 다음과 같이 수행된다.

Nested loop join의 수행에 포함되는 단계들은 다음과 같다.

1) 외부 테이블 확인한다 (identify).

2) 내부 테이블을 외부 테이블에 할당한다.

3) 외부 테이블의 각 행마다 내부 테이블의 전체 행들을 접근한다.

Optimizer는 언제 nested loop join을 사용하는가?

효율적인 join 조건으로 적은 수의 행을 담고 있는 테이블을 조인할 때 optimizer가 nested loop join을 사용한다. 외부 테이블의 각 행 마다 매번 내부 테이블의 전체 행을 확인하기 때문에 내부 테이블을 색인하는 것이 중요하다.

다음의 경우에는 nested loop join을 사용하지 않는다.

1. 조인하려는 테이블들의 크기가 클 때
2. 내부 질의가 항상 같은 결과를 낼 때
3. 내부 테이블의 접근 경로가 외부 테이블의 데이터에 독립적일 때

2. Hash join

Hash join은 큰 데이블을 조인할 때 사용된다. Optimizer는 2개의 테이블 중 더 작은 테이블을 사용하여 메모리에 해쉬 테이블을 생성하고, 큰 테이블 전체를 스캔하면서 해쉬 값을 비교한다.

Hash join 알고리즘은 다음의 두 단계로 구성된다.

1. Build 단계: 두 테이블 중 더 작은 테이블로 해쉬 테이블을 메모리에 생성한다.
2. Probe 단계: 큰 테이블을 스캔하면서 해쉬 값을 비교하여 join 되는 행을 찾는다.

간단하게 알고리즘을 적으면 다음과 같다.

Build 단계

Probe 단계

Optimizer는 언제 hash join을 사용하는가?

Optimizer는 조인하려는 테이블의 크기가 큰 경우에 사용한다. Nested loop와 다르게, hash join은 해쉬 테이블 생성 후에 join이 이루어지기 때문에 결과가 즉시 나오지 않는다.

3. Sort merge join

Sort merge join은 두 개의 독립적인 데이터 소스를 조인하는 경우에 사용된다. 이 방법은 일반적으로 데이터의 크기가 큰 경우에 nested loop보다 성능이 좋지만 hash join만큼 좋지는 않다.

이 방법이 hash join보다 좋을 때는 join 조건으로 사용되는 열이 이미 정렬되어 있거나 정렬될 필요가 없을 때이다.

알고리즘은 다음과 같다.

중요한 점은 외부 테이블의 행의 개수만큼 내부 테이블에 접근하여야 하는 nested loop join과는 다르게, sort merge join 알고리즘은 테이블의 각 행을 단 한 번씩만 접근한다. 따라서 데이터의 크기가 클 때 nested loop join보다 더 좋은 성능을 보인다.

Optimizer는 언제 sort merge join을 사용하는가?

1. join 조건이 부등 조건일 경우 (<, <=, >=)에 사용한다. hash join은 부등 조건에 사용될 수 없고, 데이터의 크기가 큰 경우 nested loop join은 고려의 대상이 아니다.
2. “order by”와 같이, 만약 어떤 속성에 대하여 항상 정렬해야하는 경우, hash join보다 sort merge join이 더 좋은 성능을 보이기 때문에 optimizer는 sort merge join을 사용한다.