[Database] JOIN 알고리즘 종류

Nested Loop Join

• 2개 이상의 테이블에서 하나의 테이블을 기준으로 다른 테이블의 Row를 순차적으로 탐색하여 원하는 결과를 조합하는 조인 방식
• 조인할 데이터가 적은 경우에 주로 사용

• Outer 테이블 (Driving 테이블)
  • Nested Loop Join에서 가장 먼저 스캔하는 테이블
  • Outer 테이블의 스캔 건수가 적을수록 효율적
• Inner 테이블 (Drivien 테이블)
  • Nested Loop Join에서 두 번째로 스캔하는 테이블
  • Inner 테이블의 건수은 Outer 테이블의 건수가 많아야 효율적

<적절한 Outer 테이블 선정>

• 어떤 테이블이 먼저 액세스 되는 지에 따라 속도의 차이가 크게 날 수 있음
• Outer 테이블의 row 수가 많다면, 그만큼 반복해서 Inner 테이블에 접근해야 하므로 성능은 안 좋아짐
• Outer 테이블은 WHERE 절로 최대한의 데이터를 거를 수 있는 테이블이나 데이터의 양이 적은 테이블로 선정

<Nested Loop Join 과정>

• outer 테이블에서 첫 번째 값을 읽고, Inner 테이블을 full scan하며 동일한 값을 찾음
• outer 테이블에서 두 번째 값을 읽고, Inner 테이블을 full scan하며 동일한 값을 찾음
• 다음의 과정을 반복하며 outer 테이블을 모두 스캔하고 동일한 값의 데이터를 Join

Sort Merge Join

• join column을 기준으로 조인 대상 테이블을 모두 정렬 후 순차적으로 스캔하며 조인하는 방식
• 조회의 범위가 많을 때 주로 사용하는 조인
• 대상 테이블을 모두 정렬하기 때문에 많은 메모리를 사용

<Sort Merge Join 과정>

• Outer 테이블과 Inner 테이블을 join column을 기준으로 정렬
• outer 테이블의 첫 번째 값를 읽고, Inner 테이블을 순차적으로 스캔하며 동일한 값을 찾음 → 이때 다른 값이 나오면 멈춤
• outer 테이블의 두 번째 값를 읽고, Inner 테이블에서 마지막으로 읽은 지점부터 다시 순차적으로 스캔하며 동일한 값을 찾음 → 마찬가지로 다른 값이 나오면 멈춤
• 다음의 과정을 반복하며 outer 테이블을 모두 스캔하고 동일한 값의 데이터를 Join

Hash Join

<HashTable 이란?>

• (Key, Value) 형태로 데이터를 저장하는 자료구조
• key값에 hash function을 적용해 buckets(배열)의 고유한 hash를 생성하고, 이 hash를 활용해 값을 저장하고 조회함
• “key”: 고유한 값으로 hash function의 input
• “value”: buckets에 최종적으로 저장되는 값으로 key와 매칭되어 저장
• “hash”: buckets의 고유한 index
• “buckets”: 실제 값이 저장되는 장소

• “Separtate Chaining”: 동일한 버킷의 hash를 가지는 데이터들을 연결 리스트로 저장, 다음 데이터의 주소 값을 가짐

<Hash Join>

• 두 테이블 중  작은 테이블을 HashTable을 메모리에 올린 후 큰 테이블을 스캔 하면서 메모리에 로딩된 테이블과 비교, 매칭되는 데이터를 추출하는 방식의 조인
• ‘=’ 비교를 통한 Join에서만 사용될 수 있음
• 두 테이블의 크기 차이가 클수록 성능이 좋음
• Hash Join은 probe input이 작을 때 Nested Loop join보다 효과적임

• Build Input: Hash Join 시 해시 영역에 저장하는 테이블, 보통 작은 테이블을 지정
• Probe Input: 순차적으로 스캔하며 해시 테이블과 비교하는 테이블, 보통 큰 테이블을 지정

<Hash Join 과정>

1. Build Input(작은 테이블)을 읽어 해시테이블 생성
2. Probe Input(큰 테이블)을 스캔

 

 

참고:

http://www.gurubee.net/lecture/3984

https://github-wiki-see.page/m/llighter/database/wiki/019.-%EC%A1%B0%EC%9D%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%EC%84%B1%EB%8A%A5

https://goodbyeanma.tistory.com/64

https://hudi.blog/db-index-and-indexing-algorithms/

https://leejungyeoul.tistory.com/36

http://www.gurubee.net/lecture/3268

https://minokuma.tistory.com/149