Hash 조인

🧛‍♀️ Hash 조인이란?

Hash 조인은 인덱스나 정렬이 없어도 효과적으로 조인할 수 있도록 설계된 방식입니다. 특히 대용량 데이터에서 Merge가 부담스러울 때 유용하며, 내부적으로는 Hash Table(해시 테이블) 을 만들어서 데이터를 효율적으로 매칭합니다.

---

🔧 실습 준비 (테스트 테이블 생성)

-- Test 테이블 복사 생성
SELECT * INTO TestOrders FROM Orders;
SELECT * INTO TestCustomers FROM Customers;

-- 데이터 개수 확인
SELECT COUNT(*) FROM TestOrders;       -- 830개
SELECT COUNT(*) FROM TestCustomers;    -- 91개

두 테이블 모두 CustomerID 컬럼을 가지고 있으며, 이 컬럼을 기준으로 조인할 수 있습니다.

---

🔍 Hash 조인 기본 쿼리

SELECT *
FROM TestOrders AS o
INNER JOIN TestCustomers AS c
ON o.CustomerID = c.CustomerID;

해당 쿼리의 실행 계획을 보면 Hash Match Join이 사용된 것을 확인할 수 있습니다.
여기서 주의할 점:

• 작은 테이블(TestCustomers)을 기준으로 해시 테이블을 생성
• 큰 테이블(TestOrders)을 스캔하며 해시 값을 비교

---

🔄 다른 조인 방식과 비교

-- NL 조인 (내부에 인덱스 없음)
SELECT *
FROM TestOrders AS o
INNER JOIN TestCustomers AS c
ON o.CustomerID = c.CustomerID
OPTION (FORCE ORDER, LOOP JOIN);

-- Merge 조인
SELECT *
FROM TestOrders AS o
INNER JOIN TestCustomers AS c
ON o.CustomerID = c.CustomerID
OPTION (FORCE ORDER, MERGE JOIN);

• NL 조인: 인덱스가 없는 상황에서는 느림
• Merge 조인: 정렬 비용이 발생하고, Many-to-Many면 비효율적
• Hash 조인: 정렬도 필요 없고, 인덱스도 없어도 됨

---

🧠 C#으로 보는 Hash 조인 개념

class Player { public int playerId; }
class Salary { public int playerId; }

해시 조인 예시 코드

Random rand = new Random();
List<Player> players = new List<Player>();
List<Salary> salaries = new List<Salary>();

for (int i = 0; i < 10000; i++) {
    if (rand.Next(0, 2) == 0) continue;
    players.Add(new Player() { playerId = i });
}
for (int i = 0; i < 10000; i++) {
    if (rand.Next(0, 2) == 0) continue;
    salaries.Add(new Salary() { playerId = i });
}

// 해시 테이블 구축
Dictionary<int, Salary> hash = new Dictionary<int, Salary>();
foreach (var s in salaries)
    hash[s.playerId] = s;

List<int> result = new List<int>();
foreach (var p in players)
{
    if (hash.ContainsKey(p.playerId))
        result.Add(p.playerId);
}

NL과 달리 Hash 조인은 내부적으로 해시 테이블을 만들어 빠르게 탐색합니다.
우리가 평소 자주 쓰는 Dictionary<TKey, TValue> 자료형이 바로 해시 구조입니다.

---

🧪 해시 테이블 직접 구현

class HashTable
{
    int _bucketCount;
    List<int>[] _buckets;

    public HashTable(int bucketCount = 100)
    {
        _bucketCount = bucketCount;
        _buckets = new List<int>[bucketCount];
        for (int i = 0; i < bucketCount; i++)
            _buckets[i] = new List<int>();
    }

    public void Add(int value)
    {
        int key = value % _bucketCount;
        _buckets[key].Add(value);
    }

    public bool Find(int value)
    {
        int key = value % _bucketCount;
        return _buckets[key].Contains(value);
    }
}

해시 테이블은 공간을 희생하고 속도를 얻는 구조입니다.

• 동일한 값은 항상 같은 버킷으로 향함
• 하지만 같은 버킷에 다른 값도 들어갈 수 있음 (해시 충돌)

---

🧠 SQL 실행계획에서 해시 테이블은?

SELECT *
FROM TestOrders AS o
INNER JOIN TestCustomers AS c
ON o.CustomerID = c.CustomerID;

실행 계획을 보면 작은 쪽인 TestCustomers에서 해시 테이블을 만들고,
큰 쪽인 TestOrders를 순회하며 값을 매칭하는 방식으로 처리됩니다.

---