PostgreSQL: Merge Join

※ PostgreSQL: Merge Join.

 

안녕하세요. 듀스트림입니다.

 

오늘 포스팅은 머지 조인에 대해 조금 더 풀어서 설명한 내용입니다.

 

조인에 대한 내용은 한번 포스팅한 적이 있는데 아래 링크 참고 부탁드립니다.

PostgreSQL: 조인 알고리즘과 유형

---

Merge Join + 추가 정렬은 비용이 큰 시나리오 중 하나로 반드시 튜닝해야합니다.

특히, 인덱스 미비로 양쪽 테이블 풀 스캔 후 Sort 비용(O(n log n)) 발생 + 디스크 스필 시나리오,
조인 후 추가 ORDER BY 키가 조인 키와 불일치하여 추가 정렬이 필요한 시나리오에서는 비용이 급격히 증가합니다.

---

 

1. Merge Join이란?

Merge Join은 두 테이블을 조인할 때, 조인 키(join key)를 기준으로 양쪽 테이블을 정렬한 뒤 병합(merge) 방식으로 매칭해 나가는 방식입니다. 

1. 먼저 조인 조건의 키 컬럼 기준으로 두 입력을 정렬 (필요할 경우)
2. 정렬된 상태에서 두 포인터(pointers)를 이동시키면서 일치하는 키를 찾아 결과를 출력
3. 정렬된 상태이므로 한 번씩만 순차적 스캔하면서 매칭 가능

이 방식은 특히 입력값이 이미 정렬되어 있거나 정렬 비용이 크지 않을 때 유리합니다.

---

2. 동작 흐름

두 테이블을 A, B라 하고, 조인 조건이 A.key = B.key (등가 조인)이라고 가정하겠습니다.

SELECT * FROM A JOIN B ON A.key = B.key;

 

1. 정렬 단계 (Sort phase)
   • A를 key 기준으로 정렬
   • B를 key 기준으로 정렬
   • 이 정렬은 인덱스 스캔을 이용해 이미 정렬된 상태로 가져오는 경우가 있으면 정렬 비용이 줄어듭니다. 
2. Merge 단계 (Merge / Scan phase)
   • 두 포인터 pa (A 쪽 현재 행), pb (B 쪽 현재 행)를 각각 처음(최소 key 값)부터 시작
   • 반복:
     • 만약 A[pa].key < B[pb].key 라면, pa를 다음으로 이동 (A 쪽 포인터 증가)
     • 반대로 A[pa].key > B[pb].key라면, pb를 다음으로 이동
     • 같다면 (A[pa].key == B[pb].key), 조인 가능한 레코드들을 매칭해 결과에 포함 → 이때 양쪽에 동일한 키를 가진 여러 행들이 있을 수 있으므로, 포인터 이동과 재매칭 전략이 필요
   • 이 과정을 한 쪽 테이블이 끝날 때까지 반복
3. 중복 키 처리 / 멀티 매칭 처리
   • 조인 키가 동일한 여러 행이 존재할 경우, 한 쪽 포인터는 고정해두고 다른 쪽 포인터를 움직이면서 모든 조합을 매칭해야 할 수 있습니다.
   • 예: A 쪽에 key=5인 행이 3개, B 쪽에 key=5인 행이 2개면, 3×2 조합을 모두 매칭해야 함
   • 이 경우, 포인터 동작 제어 또는 내부 버퍼링이 필요할 수 있습니다.
4. 출력은 정렬된 순서 유지
   • Merge Join 방식은 결과가 키 기준으로 정렬된 상태로 나옵니다. 정렬된 입력을 가정하고 있기 때문에 추가 정렬 없이도 순서가 유지됩니다.

---

3. Merge Join의 장단점

장점

 

• 메모리 부담이 비교적 낮음: 해시 조인처럼 전체 해시 테이블을 메모리에 구축할 필요가 없고, 단순한 포인터 이동만 하므로 메모리 오버헤드가 낮습니다.
• 정렬된 입력이 있을 경우 유리: 이미 인덱스 스캔 결과가 키 정렬된 상태라면 정렬 비용을 줄일 수 있습니다.
• 출력이 정렬된 상태로 나옴: 결과를 다시 정렬할 필요가 없는 경우가 많아 추가 비용 절감 가능합니다.
• 큰 테이블 조인 시 유리할 수 있음: 특히 해시 조인이 메모리 제약 또는 배치 처리로 비효율적일 경우 대체 전략이 될 수 있습니다.
• 조인 순서(outer/inner) 구분이 덜 중요: Merge Join은 어느 쪽을 Outer/Inner로 택해도 동작 가능하므로 조인 테이블 선택 부담이 덜합니다.

---

단점/제약 조건

 

• 정렬 비용: 입력이 미정렬 상태라면 정렬 비용(O(n log n))이 추가됨 → 이 비용이 크면 해시 조인이 더 유리할 수 있습니다.
• 조인 조건 제약: 기본적으로 등가 조인(=) 조건에 적합하며, 비등가 조인(<, > 등)에는 잘 맞지 않습니다.
• 데이터 타입이 정렬 가능해야 함: 키 컬럼이 정렬 가능해야 하며, 정렬 가능한 인덱스가 존재해야 더 유리합니다.
• 입력이 매우 불균형적일 경우 비효율적일 수 있음: 한쪽이 매우 크고 다른 쪽은 작을 경우, 정렬 비용 또는 포인터 스캔 비용이 비효율이 될 수 있습니다.
• 정렬이 외부 저장소(spill)로 이어질 수 있음: 정렬할 데이터가 work_mem 등의 제한을 초과하면 디스크 스왑(spill) 비용이 증가할 수 있습니다.

---

4. PorstgreSQL 옵티마이저에서 Merge Join 선택 기준

PG 옵티마이저는 NL Join, Hash Join, Merge Join 중 비용 기반(cost-based) 판단을 통해 적절한 조인 방식을 선택합니다.

 

Merge Join이 선택되기 위한 조건 및 고려사항:

 

• 조인 조건에 등가 조건(=)이 포함되어 있어야 함.
• 양쪽 입력이 크고 해시 조인으로 처리하기에는 부담이 있을 때(해시 테이블이 work_mem에 들어가지 않을 때).
• 입력의 정렬 비용이 낮다고 판단되거나, 이미 정렬되어 있거나 인덱스를 통해 정렬된 상태로 제공 가능할 때.
• 출력이 정렬된 상태로 나오는 것이 유용한 경우 (후속 조인이나 정렬이 필요한 경우).

옵티마이저는 이 조건들을 비용 모델(cost model)에 반영하여 가능한 실행 계획들의 비용을 비교한 뒤 가장 낮은 비용의 계획을 선택합니다.

---

 

튜닝은 재밌고 도파민 터지지만, 그만큼 많은 스터디를 필요로 하는 거 같습니다.

 

오늘은 여기까지~