데이터베이스 주요 개념 2. Nested loop, Sort Merge, Hash join

 

 

 

 

1. Nested Loop Join

---

바깥 테이블의 처리 범위를 하나씩 엑세스하면서 그 추출된 값으로 안쪽 테이블을 조인하는 방식

 

1) 특징 및 장점

• 순차적으로 처리
• 바깥 테이블과 일치하는 값을 안쪽 테이블에서 찾아야 하므로 테이블의 해당 열에 인덱스 필요
• 메모리 사용량은 가장 적음
• 선행 테이블의 처리 범위가 전체 일의 양을 결정
• 좁은 범위에서 유리한 성능을 보여줌
• 순차적으로 처리하며, Random Access 위주
• 후행 테이블에는 조인을 위한 인덱스 생성 필요
• 실행속도 = 선행 테이블 사이즈 * 후행 테이블 접근 횟수

 

2) 단점 및 주의사항

• 데이터를 랜덤으로 엑세스하므로 결과 집합이 많으면 속도가 느려짐
• join index 가 없거나, 조인 집합을 구성하는 검색 조건이 조인 범위를 줄이지 못할 경우 비효율

 

 

3) 적용 방법

 

각 DB 마다 적용하는 방법은 다르기 때문에 자주 사용하는 부분만 추후 재사용을 위해 기록해둔다.

 

- Ms SQL

SELECT *
FROM Test.testdata1 AS a
     INNER LOOP JOIN Test.testdata2 AS b ON a.test1ID = b.test1ID

 

- MySQL

 SELECT /*+ USE_NL ( TABLE_NAME, TABLE_NAME2 ... ) */ COLUMN ..

 

 

 

 

 

2. Sort Merge Join

---

외부 또는 내부 테이블에서 조거에 만족하는 레코드를 검색한 후, 조인 키를 기준으로 정렬작업을 수행하는 Join

 

1) 특징 및 장점

• 정렬한 결과를 차례로 스캔하여 연결고리 조건으로 Merge
• Loop Join 보다 훨씬 빨라지는 경우 있음
• 랜덤 엑세스가 줄어들어 시스템 부하 감소
• 조인 연산자가  '=' 이 아닌 경우 nested loop 조인보다 유리한 경우 많음
• 테이블의 스캔수는 한번만 이루어짐
• 양 테이블 모두 조인키에 의해 정렬되어야 함
•  

 

 

2) 단점 및 주의사항

• 일반적으로 Loop Join 보다는 사용 빈도가 적음
• 정렬을 위한 영역(Sort Area Size) 에 따라 효율에 큰 차이 발생
• 두 결과집합의 크기가 차이가 많이 나는 경우 비효율
• 정렬에 따른 부담 발생(메모리 사용 증가)

 

 

3) 적용방법

- MSSQL

SELECT *
FROM Test.testdata1 AS a
     INNER MERGE JOIN Test.testdata2 AS b ON a.test1ID = b.test1ID

-MySQL

 SELECT /*+ USE_MERGE ( TABLE_NAME, TABLE_NAME2 .. ) */ COLUMN ..

 

 

 

 

 

3. Hash Join 

---

외부 테이블 전체를 읽어 결합 키를 기준으로 해시 테이블을 만들어 연결될 대상을 특정 지역(Partition) 에 모아두는 역할을 담당하는 Join

 

1) 특징 및 장점

• 해시값을 이용하여 테이블을 조인
• 부하가 많이 발생하는 sort merge 조인을 보완하기 위한 방법으로 sort 대신 hash 를 이용
• 랜덤 엑세스와 정렬에 대한 부담을 해결할 수 있음
• 대용량 데이터 처리를 위한 최적의 솔루션
• 해시 테이블 생성 후, nested loop 처럼 순차적으로 처리 수행
• 조인의 결과는 정렬하지 않은 상태로 출력

 

2) 단점

• 대용량 데이터 처리시 큰 hash area 필요함으로 메모리의 지나친 사용으로 오버헤드 가능성
• 연결조인 연산자가 '=' 인 경우에만 가능

 

 

 

3) 적용 방법

 

- MSSQL

SELECT *
FROM Test.testdata1 AS a
     INNER HASH JOIN Test.testdata2 AS b ON a.test1ID = b.test1ID

- MySQL

SELECT /*+ USE_HASH ( TABLE_NAME, TABGLE_NAME2 ... ) */ COLUMN ..

 

 

 

 

 

 

 

 

4. 참고링크

---

https://needjarvis.tistory.com/162

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

https://blog.sonim1.com/108

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

https://mozi.tistory.com/168

[MySQL] NL, Sort Merge, Hash Join 최적의 결합 방법 선택하기