Large DB (데이터베이스)의 Sort-Merge Join

Large DB (데이터베이스)의 Sort-Merge Join (소트-머지 조인)

 

 

[BigData의 Join 기초]
- DBMS Join
- Large DB (데이터베이스)의 Hash Join
- Large DB (데이터베이스)의 Nested Loop Join
- Large DB (데이터베이스)의 Sort-Merge Join

 

 

 

DB (데이터베이스)의 **Sort-Merge 조인(소트-머지 조인)**은 두 테이블을 조인하는 대표적인 알고리즘 중 하나입니다. 이름 그대로 '정렬(Sort)' 단계와 '병합(Merge)' 단계를 거쳐 조인을 수행합니다.

⚙️ Sort-Merge 조인의 개념과 특징

Sort-Merge 조인은 두 단계로 작동합니다.

1. 정렬 (Sort) 단계:
   • 조인에 사용할 두 개의 테이블(A, B)을 **조인 키(Join Key)**를 기준으로 각각 독립적으로 정렬합니다.
   • 예: A.id와 B.id를 기준으로 조인한다면, A 테이블을 id 기준으로 정렬하고, B 테이블도 id 기준으로 정렬합니다.
2. 병합 (Merge) 단계:
   • 정렬된 두 테이블을 마치 '지퍼'를 올리듯이 처음부터 스캔합니다.
   • 두 테이블의 포인터(현재 위치)를 비교하며 조인 키가 일치하는지 확인합니다.
   • 일치할 경우: 조인 결과를 생성하고, 두 포인터를 모두 다음으로 이동시킵니다. (만약 중복 키가 있다면 한쪽 포인터는 고정하고 다른 쪽 포인터를 계속 이동하며 매칭합니다.)
   • 일치하지 않을 경우: 키 값이 더 작은 쪽의 포인터만 다음 행으로 이동시킵니다. (이미 정렬되었으므로, 더 작은 값은 뒤에 일치하는 값이 나올 수 없기 때문입니다.)

---

🌟 주요 특징

• 정렬된 결과: 조인 결과가 조인 키 기준으로 정렬된 상태로 나옵니다. 만약 ORDER BY 절이 조인 키와 같다면 추가 정렬 비용이 발생하지 않습니다.
• 등가/부등가 조인 가능: 대부분의 조인 알고리즘(특히 해시 조인)은 등가 조인(=)에 최적화되어 있지만, Sort-Merge 조인은 정렬된 순서를 이용하므로 **부등가 조인(>, <, >=, <=)**도 효율적으로 처리할 수 있습니다.
• 성능: 전체 성능은 정렬 비용이 지배합니다. 데이터가 이미 정렬되어 있거나(예: 인덱스), 정렬 비용이 크지 않다면 매우 빠릅니다.

---

💾 메모리 사용: 외부 정렬 (External Sort)

Sort-Merge 조인의 핵심은 '정렬'이며, 대용량 데이터베이스에서는 이 정렬이 메모리 내에서 불가능한 경우가 많습니다.

• 메모리 부족 시 (일반적인 경우):
  • 데이터베이스는 **'외부 정렬(External Merge Sort)'**을 사용합니다.
  • 이는 데이터를 메모리에 할당된 'Sort Area' (또는 'Work Area') 크기만큼 나눠서 읽어옵니다.
  • 메모리에 올라온 데이터(이를 **'런(Run)'**이라고 함)를 정렬하여 디스크의 임시 공간에 씁니다.
  • 이 과정을 모든 데이터에 대해 반복하여 여러 개의 정렬된 '런' 파일을 만듭니다.
  • 마지막으로, 이 '런' 파일들을 다시 읽어오면서 병합(Merge)하여 최종적인 하나의 정렬된 테이블을 만듭니다.
• 메모리 영향:
  • 'Sort Area'에 할당된 메모리가 클수록, 한 번에 정렬할 수 있는 '런'의 크기가 커집니다.
  • '런'의 크기가 크면 전체 '런'의 개수가 줄어들고, 이는 디스크 I/O 횟수(특히 병합 단계)를 줄여 성능이 향상됩니다.
  • 메모리가 데이터 전체 크기보다 작아도 디스크 I/O를 통해 안정적으로 대용량 데이터 정렬을 완료할 수 있다는 것이 핵심입니다.

---

📊 다른 조인 (Join) 과의 비교

 

조인 방식	핵심 원리	메모리 사용	장점	단점
Sort-Merge Join (소트-머지 조인)	정렬 후 병합 (Sort & Merge)	Sort Area 사용. (외부 정렬)	- 대용량 데이터에 안정적 - 부등가 조인(>,<) 가능 - 조인 결과가 정렬됨	- 정렬 비용이 비쌈 - 양쪽 테이블 모두 정렬 필요
Hash Join (해시 조인)	해시 테이블 생성 후 탐색 (Build & Probe)	Hash Area 사용. (Build 테이블)	- 등가 조인(=)에서 가장 빠름 - 정렬이 필요 없음	- 등가 조인만 가능 - 해시 테이블이 메모리에 맞지 않으면 (Disk Spill) 성능 급격히 저하
Nested Loop Join (중첩 루프 조인)	다중 반복문 (Outer Loop, Inner Loop)	매우 적게 사용	- 한쪽 테이블이 매우 작고 - Inner 테이블에 인덱스가 있을 때 극도로 빠름	- 인덱스가 없거나 양쪽 다 크면<I/O 재앙</I> (최악의 성능)

 

---

요약

• Nested Loop Join: (작은 테이블) * (인덱스가 있는 큰 테이블) = 빠름
• Hash Join: (큰 테이블) * (큰 테이블) 이고 **등가 조인(=)**일 때 = 빠름 (메모리 충분 시)
• Sort-Merge Join: (큰 테이블) * (큰 테이블) 이고 **부등가 조인(>,<)**이거나 메모리가 부족할 때, 또는 정렬된 결과가 필요할 때 = 안정적

 

 

https://bigtechinterviews.com/sql-joins-a-complete-guide/

https://medium.com/@milhamsuryapratama/sql-join-algorithms-nested-loop-merge-and-hash-join-f264a34194e3