SORT MERGE, HASH, SEMI, NESTED LOOP JOIN

조인 수행 원리 ★★★ 4문제 나옴

• NL JOIN : 랜덤 엑세스, 대용량 SORT 작업 시 유리
• SORT MERGE : JOIN KEY 기준 정렬, 등가/비등가 조인
• HASH JOIN : 등가 조인 only, 함수처리, 선행테이블이 작음, 별도 저장 공간 필요 (은근히 데이터 잡아먹음)
• Sort merge join

- 조인의 대상범위가 넓을 경우 발생하는 Random Access를 줄이기 위한 경우나 연결고리에 마땅한 인덱스가 존재하지 않을 경우 해결하기 위한 조인 방안
- 양쪽 테이블의 처리범위를 각자 Access하여 정렬한 결과를 차례로 Scan하면서 연결고리의 조건으로 Merge하는 방식

• hash join

- 해싱 함수(Hashing Function) 기법을 활용하여 조인을 수행하는 방식(해싱 함수는 직접적인 연결을 담당하는 것이 아니라 연결될 대상을 특정 지역(partition)에 모아두는 역할만을 담당
- 해시값을 이용하여 테이블을 조인하는 방식
- Sort-Merge 조인은 소트의 부하가 많이 발생하여, 이를 보완하기 위한 방법으로 Sort 대신 해쉬값을 이용하는 조인

• semi join

- 조인과 매우 유사한 데이터 연결 방법을 뜻한다.
- 다시 말해서 서브쿼리를 사용했을 때 메인쿼리와의 연결을 처리를 의미

• Nested loop join : 두 개의 집합을 두 개의 중첩된 루프를 사용해 조인하는 알고리즘

- 2개 이상의 테이블에서 하나의 집합을 기준으로 순차적으로 상대방 Row를 결합하여 원하는 결과를 조합하는 방식
- 먼저 선행 테이블의 처리 범위를 하나씩 액세스하면서 추출된 값으로 연결할 테이블을 조인한다

Q) Driving 과 driven을 결합하고 row를 걸러내고 Index 쓰면 더 내가 원하는 것만 검색 가능
모수를 좀 작은걸 driving으로 선택하면 더 효율적이다.
1. Sort merge join 2. hash join
3. Nested loop join 4. semi join
https://insight-bgh.tistory.com/500

[Database] Nested Loop 최적화

https://needjarvis.tistory.com/162

Nested Loop, Sort-Merge, Hash Join 조인연산

http://wiki.gurubee.net/pages/viewpage.action?pageId=1966761

2.3.5. 세미(Semi) 조인 - [종료]구루비 DB 스터디 - 개발자, DBA가 함께 만들어가는 구루비 지식창고!

NL(Nested Loop) join

두개 이상의 테이블에서 하나의 테이블을 기준으로 각 row에 추출할때마다 순차적으로 상대편의 테이블에 연관있는 모든 row를 추출해 조인하는 방법



튜닝 포인트

테이블 간 조인 횟수의 최소화 => 조인 순서의 최적화

연결고리 칼럼의 인덱스 사용 => 모든 row를 full scan 할 필요가 없어짐



특징

인덱스에 의한 random 액세스 이기 때문에 대용량 데이터 작업에는 효율이 좋지 않음

Driving table의 데이터의 용량이 적거나 where절의 조건으로 적절하게 row를 제어할 수 있어야 함

Driven table에서는 조인시 사용할 연결고리 칼럼에 대한 적절한 인덱스가 있어야 함



-> 연결고리 칼럼에 인덱스가 없거나 대용량 작업을 해야하는 경우 Sort Merge, Hash join이 고려된다.

Sort Merge join

조인하고자 하는 테이블에 대해 데이터를 각각 읽어들이고, 연결고리 컬럼을 기준으로 정렬 후에 조인하는 방법



튜닝 포인트

처음에 읽어들이는 데이터를 어떻게 더 빨리 읽어 들일 것인가

읽어 들인 데이터를 연결컬럼을 기준으로 정렬할때 얼마나 빠를게 할 것인가



특징

연결고리 컬럼에 인덱스가 생성되어 있지 않은 경우에 빠른 조인을 위해 사용

조인하고자 하는 각 테이블에 대해 독립적으로 데이터를 읽어들일때, 이를 얼마나 빠르게 할 것 인가가 중요함

각 테이블로부터 읽은 데이터를 연결고리에 대해 정렬을 수행할때, 이를 얼마나 빠르게 할 것인가가 중요함

각 테이블의 액세스, 정렬작업 속도를 맞춰주는 것이 좋음

Hash join

먼저 크기가 작은 테이블을 메모리로 가져와 연결고리 컬럼의 데이터를 hash 함수에 넣어 나온 hash 값으로 테이블을 생성합니다. 그후 남은 테이블을 읽어 해쉬 테이블을 탐색하면서 조인하는 방법



튜닝 포인트

메모리에 올라가는 작은 테이블이 HASH_AREA_SIZE보다 작은지 확인할 것

=> 그렇지 않을시 디스크에 위치하게 될 수 도 있기 때문에



특징 해쉬 함수를 적용한 실제 값은 어떤 값으로 해슁될지 알 수 없지만 같은 값에 대해서는 항상 같은 값으로 해슁된다. 따라서 동등 조인에서만 사용할 수 있다.

수행빈도가 낮고 쿼리 수행시간이 오래 걸리는 대용량 테이블 작업에 유리하다.

https://m.blog.naver.com/dnjswls23/222272796166