009. DB JOIN의 종류

1. Nested Loop Join

• 2개 이상의 테이블에서 하나의 집합을 기준으로 순차적으로 상대방 Row를 결합하여 원하는 결과를 조합하는 방식
• 먼저 선행 테이블의 처리 범위를 하나씩 액세스하면서 추출된 값으로 연결할 테이블을 조인한다
• 순차적으로 처리된다.
• 바깥 테이블과 일치하는 값을 안쪽 테이블에서 찾아야 하므로 안쪽 테이블의 해당 열에 인덱스가 필요하다.
• 메모리 사용량은 가장 적다.
• 바깥 테이블과 안쪽 테이블의 크기는 성능과 관련이 없다.
• 첫 테이블 필터링 -> 두테이블간의 연결 -> 최종운반 단위 산출가지 반복적, 순차적으로 진행됩니다.
• 선행 테이블의 처리 범위가 전체 일의 양을 결정합니다.
• 후행 테이블의 필터링 조건은 선행 테이블에서 나온 결과를 한번 더 걸러주는 체크 조건 역할을 할 뿐 전체 처리량을 좌우하지 않습니다.
  
  

 

2. Sort Merge Join

양쪽 테이블의 처리 범위를 각자 액세스하여 정렬한 결과를 차례로 스캔하며, 연결고리 조건으로 Merge하는 방식을 말합니다.
이 방식은 경우에따라 Loop Join 보다 훨씬 빨라지는 경우도 많이 있으며, 랜덤 액세스가 줄어들어 시스템 부하를 감소 시킵니다.
하지만 일반적으로 Loop Join보다는 사용빈도가 적습니다.

 

장점

• 처리량이 많을때 성능상 이점이 있다.
• 중첩반복(Nested Loops)은 연결고리의 상태가 굉장히 중요하다. 한쪽 연결고리에 이상이 발생하면 중첩반복은 심히 고려해야한다. 이때 연결고리에 영향을 받지않는 Sort Merge를 쓰면 좋다.

단점

• 정렬에 따른 부담 (메모리 사용 증가)정렬은 tempdb를 사용한다. 정렬양이 극도로 많아 tempdb의 임계치를 넘었을때 순간 전체 데이터베이스에 페이지잠금이 발생하는등 DB성능에 심각한 영향을 줄 수 있다.물론 가공없이 Clustered Index를 그대로 사용하게 되면 정렬은 안해도 되니 이때만큼은 정렬의 부담에서 해방된다.

3. Hash Join

Hash Join은 Hash Table을 생성하여 Hash Function에 의한 탐색을 하여 조인합니다. 주로 대용량의 데이터를 사용할 때 사용되며 일반적으로 Nested Loop Join이나 Sorted Merge Join보다 빠르다고합니다. 알고리즘에서 시간 복잡도의 개념으로 봤을 때도 Hash Function을 사용하게 되면 O(1)의 시간 복잡도를 갖게되니까 빠를수 밖에 없는 것 같습니다. 하지만, 해시 충돌을 방지나 해시 체인의 크기가 커지는 것을 막기 위해 중복되는 데이터가 적은 경우에 사용되어하고 Hash Table을 생성하는데 Hash Area에 충분히 담길 정도로 데이터 양이 작아야합니다.

 

HASH JOIN의 사용처

1. JOIN 컬럼에 적당한 인덱스가 없어 NL JOIN이 비효율적일 때

2. JOIN Access량이 많아 Random Access 부하가 심하여 NL JOIN이 비효율적일 때

3. Sort Merge Join을 하기에는 두 테이블이 너무 커 Sort 부하가 심할 때

4. 수행빈도가 낮고 쿼리 수행 시간이 오래 걸리는 대용량 테이블을 JOIN 할 때

1. 둘 중 작은 집합(Build Input)을 읽어 Hash Area에 해시 테이블을 생성한다. (해시 함수에서 리턴 받은 버킷 주소로 찾아가 해시 체인에 엔트리를 연결)

2. 반대쪽 큰 집합(Probe Input)을 읽어 해시 테이블을 탐색하면서 JOIN 한다.

3. 해시 함수에서 리턴 받은 버킷 주소로 찾아가 해시 체인을 스캔하면서 데이터를 찾는다.

 

출처: https://coding-factory.tistory.com/758

출처: https://needjarvis.tistory.com/162 [자비스가 필요해]

출처: https://blog.sonim1.com/108

[MSSQL] JOIN의 방식 - Nested loop Join / Merge Join / Hash Join