Merge 조인

🧠 Merge 조인이란?

Merge 조인은 다음과 같은 특징을 가진다:

• Sort Merge Join이라고도 부른다.
• 두 집합(테이블)을 조인 키를 기준으로 정렬(Sort)하고, 정렬된 결과를 병합(Merge)한다.
• 성능은 정렬 여부, 인덱스, 데이터 중복 여부에 크게 영향을 받는다.
• Random Access 위주가 아닌, 스캔 기반의 조인 방식이다.

---

✅ Merge 조인 실행 계획 보기

SELECT *
FROM players AS p
INNER JOIN salaries AS s
ON p.playerID = s.playerID;

• 실행 계획 확인 시:
  • Clustered Index Scan
  • Sort
  • Merge Join
• salaries, players 각각 정렬된 후 병합되는 모습을 확인할 수 있다.

---

⚙️ Merge 조인 구조 분석 (C# 코드 기반)

정렬 → 병합의 개념을 이해하기 위해 C# 코드로 먼저 직관적인 Merge Join을 구현해보자.

▶ 클래스 정의

class Player : IComparable<Player>
{
    public int playerId;
    public int CompareTo(Player other) => playerId.CompareTo(other.playerId);
}

class Salary : IComparable<Salary>
{
    public int playerId;
    public int CompareTo(Salary other) => playerId.CompareTo(other.playerId);
}

▶ 리스트 초기화 및 정렬

List<Player> players = new List<Player> { new(0), new(9), new(1), new(3), new(4) };
List<Salary> salaries = new List<Salary> { new(0), new(5), new(0), new(2), new(9) };

players.Sort();   // O(n log n)
salaries.Sort();  // O(m log m)

▶ Merge 알고리즘 구현 (One-To-Many 기준)

int p = 0, s = 0;
List<int> result = new List<int>();

while (p < players.Count && s < salaries.Count)
{
    if (players[p].playerId == salaries[s].playerId)
    {
        result.Add(players[p].playerId);
        s++;
    }
    else if (players[p].playerId < salaries[s].playerId)
        p++;
    else
        s++;
}

• 시간 복잡도: O(n + m)
• Merge Join은 정렬되어 있다는 전제 하에 효율적인 병합 가능

---

🔀 Many-To-Many vs One-To-Many

❗ Many-To-Many (최악)

players  = [0, 0, 0, 0, 0]
salaries = [0, 0, 0, 0, 0]

• 매칭할 경우의 수가 많아지므로 O(n * m) 의 시간 복잡도 발생
• Join 대상이 중복이 심한 경우, Merge Join 성능 하락

---

📊 SQL 실습

▶ 통계 옵션 켜기

SET STATISTICS TIME ON;
SET STATISTICS IO ON;
SET STATISTICS PROFILE ON;

▶ Merge Join 실행

SELECT *
FROM players AS p
INNER JOIN salaries AS s
ON p.playerID = s.playerID;

🔎 실행 계획 해석

• Many-To-Many 병합 발생
• players/salaries 모두 정렬 필요 → Sort 연산 발생
• Merge Join은 정렬 이후 수행됨

▶ 왜 정렬이 필요했을까?

• players: PK가 lahmanID에 있음
• salaries: 복합 PK (year, teamID, lgID, playerID)
• 조인 키 playerID에는 정렬된 인덱스 없음 → Sort 필요

---

💡 Merge Join을 빠르게 만들기 위한 조건

• One-To-Many 구조 → 외부 테이블이 Unique해야 좋다
• 외부 테이블에 PK / UNIQUE 제약 조건이 있으면 더 빠르다
• 조인 키에 Clustered Index 또는 정렬된 인덱스가 있어야 좋다

---

✅ 정렬이 생략된 Merge Join

SELECT *
FROM schools AS s
INNER JOIN schoolsplayers AS p
ON s.schoolID = p.schoolID;

• 실행 계획에서 Sort 생략됨
• schools 테이블은 Clustered Index가 정렬된 상태라서 정렬 단계 SKIP
• schoolsplayers는 Non-Clustered 인덱스를 통해 Join 됨
• One-To-Many 병합으로 처리됨 → 가장 이상적인 Merge Join

---