SQLP - 조인 수행 원리

@markdown

## NL Join

____

- NL 조인은 프로그래밍 이중 Loop와 유사한 방식으로 조인을 수행

<pre><code class="java" style="font-size:14px">for 선행테이블(외부테이블)

for 후행테이블(내부테이블)

...

</code></pre>

- 먼저 선행 테이블의 조건을 만족하는 행을 추출하여 후행 테이블을 읽으면서 조인을 수행

- 선행테이블의 조건을 만족하는 모든 행의 수만큼 반복수행

- 결과 행의 수가 적은 테이블을 조인 순서상 선행 테이블로 선택하는것이 전체 일량을 줄일 수 있음

- 랜덤 방식으로 데이터를 액세스하기 때문에 처리 범위가 좁은 조건이 먼저 선택되는게 유리하다.

- NL Join 기법은 성공하면 바로 결과를 사용자에게 보여주므로 온라인 프로그램에 적당한 기법이다.

### NL Join 수행 방법

- 1) 선행 테이블에서 주어진 조건을 만족하는 행을 찾음

- 2) 선행 테이블의 조인 키 값을 가지고 후행 테이블에서 조인 수행

- 3) 선행 테이블의 조건을 만족하는 모든 행에 대해 1번 작업 반복 수행


- 1) 선행 테이블에서 조건을 만족하는 첫번째 행을 찾음

→ 이때 선행 테이블에 주어진 조건을 만족하지 않는 경우 해당 데이터는 필터링됨

- 2) 선행 테이블의 조인 키를 가지고 후행 테이블에 조인 키가 존재하는지 찾는다

→ 조인시도

- 3) 후행 테이블의 인덱스에 선행 테이블의 조인 키가 존재하는지 확인

→ 선행 테이블의 조인 값이 후행 테이블에 존재하지 않으면 선행 테이블 데이터는 필터링됨(조인작업x)

- 4) 인덱스에서 추출한 레코드 식별자를 이용하여 테이블을 액세스

→ 인덱스 스캔을 통한 테이블 액세스

- 5) ~ 11) 반복 수행

<br/>

## Sort Merge Join

____

- Sort Merge Join은 조인 칼럼을 기준으로 데이터를 정렬하여 조인을 수행

- 주로 스캔 방식으로 데이터를 읽는다.

- 랜덤 액세스로 부담이 되는 넓은 범위의 데이터를 처리할 때 사용

- 정렬할 데이터가 많아 메모리에 모든 정렬 작업을 수행하기 어려운 경우에는 임시영역을 사용하므로 성능이 떨어질 수 있다.

- Hash Join과는 달리 동등 조인 뿐만 아니라 비동등 조인에 대해서 조인 작업이 가능

### Sort Merge Join 수행 방법


- 1) 선행 테이블에서 주어진 조건을 만족하는 행을 찾음

- 2) 선행 테이블의 조인 키를 기준으로 정렬 작업을 수행(1 ~ 2번 작업을 선행 테이블의 조건을 만족하는 모든 행에 대해 반복 수행)

- 3) 후행 테이블에서 주어진 조건을 만족하는 행을 찾음

- 4) 후행 테이블의 조인 키를 기준으로 정렬 작업을 수행(3 ~ 4번 작업을 후행 테이블의 조건을 만족하는 모든 행에 대해 반복 수행)

- 5) 정렬된 결과를 이용하여 조인을 수행하며 조인에 성공하면 추출버퍼에 넣음

<br/>

## Hash Join

____

- `Hashing` 기법을 이용하는 조인 방법

- 조인 칼럼을 기준으로 Hash 함수를 수행하여 서로 동일한 Hash 값을 갖는 것들 사이에서 실제 값이 같은지 비교하면서 조인을 수행

- NL Join의 랜덤액세스와 Sort Merge Join의 문제점인 정렬 작업의 부담을 해결하기 위한 대안으로 등장

### Hash Join 수행 방법


- 1) 선행 테이블에서 주어진 조건을 만족하는 행을찾음

- 2) 선행 테이블의 조인 키를 기준으로 해쉬 함수를 적용하여 해쉬 테이블을 생성(조인 칼럼과 SELECt 절에서 필요로 하는 칼럼도 함께 저장)

(1 ~ 2번 작업을 선행 테이블의 조건을 만족하는 모든 행에 대해 반복수행)

- 3) 후행 테이블에서 주어진 조건을 만족하는 행을 찾음

- 4) 후행 테이블의 조인 키를 기준으로 해쉬 함수를 적용하여 해당 버킷을 찾음(조인 키를 이용해서 실제 조인될 데이터를 찾음)

- 5) 조인에 성공하면 추출버퍼에 넣음(3 ~ 5번 작업을 후행 테이블의 조건을 만족하는 모든 행에 대해서 반복수행)

### Hash Join 특징

- 조인 칼럼의 인덱스가 존재하지 않을 경우에도 사용할 수 있는 기법

- Hash 함수를 이용하여 조인을 수행하기 때문에 `==`으로 수행하는 조인, 동등조건에만 사용할 수 있다.

- Hash 함수가 적용될 때 동일한 값을 항상 같은 값으로 Hashing 되는 것이 보장된다.

- 메모리에 적재할 수 있는 영역에 크기보다 커지면 임시 영역에 Hash 테이블을 저장한다.

- Hash 조인을 할 때는 결과 행의 수가 적은 테이블을 선행 테이블로 사용하는 것이 좋다.

- 선행 테이블을 `Build Input`, 후행 테이블은 `Prove Input`

> SQL 전문가 가이드 : 제3장 SQL 최적화 기본 원리 - 제3절 조인 수행 원리(p.461 ~ p.465)

> 사진 출처 : 구루비넷