[기술면접] DB | Nested Loop, Sort-Merge, Hash Join

💡 Nested Loop, Sort-Merge, Hash Join

 

JOIN연산 SQL명령문에 의해 여러 테이블에 저장된 데이터를 한 번에 조회할 수 있게 해주는 DBMS의 기능

 

 

Nested-Loop Join

2개 이상의 테이블에서 하나의 집합을 기준으로 다른 row를 조합하는 방식

선행 테이블의 row를 하나씩 액세스하여 연결된 값을 조인한다

 

⭐️특징 :

• 좁은 범위에 유리한 성능
• 순차처리, random access위주
• 후행 테이블에는 조인을 위한 인덱스가 생성된다
• 실행 속도 = 선행테이블 크기 * 후행 테이블 접근횟수

 

📌주의 :

• 데이터 랜덤 액세스 = 결과가 많으면 느려짐
• Join index가 없거나, 검색 조건이 join범위를 줄여주지 않으면 비효율적임
• row가 적은 쪽을 선행(Driven)테이블로 설정해 동작하는 것이 유리함

 

 

 

Sort-Merge Join

join의 대상 범위가 넓을 경우에 random access를 줄이기 위한 경우, 연결고리로 사용할 마땅한 index가 없을때 해결하기 위한 방안

양쪽 테이블의 처리 범위를 각각 access, 정렬한 결과를 차례로 scan하여 조건(=연결고리)으로 merge함

 

⭐️특징 :

• 연결을 위해 스캔 (randon X)
• 선행집합 개념이 없고, 두 테이블이 동등함
• 정렬을 위한 영역(Sort Area Size)에 따라 효율에 큰 차이가 발생함
• join연산자가 “=”이 아닌 경우 nested-loop보다 유리한 경우가 많음

 

📌주의 :

• 두 결과 집합 크기 차이가 많이 나면 비효율적임
• sorting메모리에는 join key, select list가 포함되므로 불필요한 select 항목을 제거하고 사용해야함

 

 

Hash Join

해싱 함수를 활용하여 조인을 수행함. 해싱함수는 연결될 대상을 특정지역(partition)에 모아두는 역할을 수행함

Sort-Merge Join은 sort부하가 많이 발생하는데, 이를 보완하기위해 해시값을 사용하는 것임

 

⭐️특징 :

• 대용량 처리의 선결조건인 random access와 sort 부담을 해결하는 대안!
• 대용량 데이터를 처리하기 위한 최적의 방법임(parallel processing으로 hash join)
• 2개의 조인 테이블 중 small rowset(더 작은 데이터셋)을 가지고 해시를 위한 영역(Hash-area-Size)에 지정된 매모리 내에서 hash table을 생성함
• CPU성능에 의존적임
• hash table 생성 후에는 Nested-Loop처럼 순차적인 처리 형태로 수행됨

 

📌주의 :

• 대용량 데이터 처리에서 hash area가 그만큼 크게 필요하므로, 메모리의 지나친 사용으로 오버헤드 발생 가능성이 있음
• 연결 조건 연산자가 “=”인 경우에만 가능함

 

 

참고 :

https://needjarvis.tistory.com/162

https://myjamong.tistory.com/238