[MySQL] 조인 알고리즘 (Nested Loop Join, Hash Join)

1. Nested Loop Join

MySQL 서버에서 사용되는 대부분의 조인은 Nested Loop Join이다.

조인의 연결 조건에 인덱스가 있는 경우 가장 일반적으로 사용되는 방식이다.

이는 중첩된 반복 명령을 사용하는 것처럼 작동한다.

for (row1 IN A) {
  for (row2 IN B) {
    if (condition_matched) return (row1, row2);
  }
}

2개 이상의 테이블에서 하나의 집합을 기준으로 순차적으로 상대방 row를 결합하여 원하는 결과를 조합한다.

드라이빙 테이블(조인을 시작하는 외부 루프 테이블)에서 한 row씩 꺼내서 드리븐 테이블(내부 루프에서 탐색 대상이 되는 테이블)에서 그에 맞는 row들을 찾는 구조이다.

✅ 드라이빙 테이블의 row 수가 많을 경우 비효율적이다. (N * M 반복)

✅ 드리븐 테이블에 인덱스가 없으면 테이블 풀 스캔이 일어나 매우 느리다.

---

2. Hash Join

MySQL 8.0 버전 이후 도입된 알고리즘으로 많은 양의 데이터를 조인해야 하는 경우에 주로 사용된다.

비용 기반 옵티마이저를 사용할 때만 사용될 수 있는 조인 방식이며, = 조건을 사용하는 INNER JOIN에서만 사용될 수 있다.

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

두 테이블을 조인할 때, 한쪽 테이블의 데이터를 해시 테이블로 만들어 놓고, 다른 테이블을 순회하면서 해시로 빠르게 매칭시키는 조인 방식이다.

1. 작은 테이블(드리븐 테이블)을 메모리에 올린다.
2. 조인 키를 기준으로 해시 테이블을 만든다.
3. 다른 테이블(드라이빙 테이블)을 한 row씩 읽으면서 해시 테이블에서 매칭되는 row를 찾는다.

✅ 조인 조건에 인덱스가 없어도 빠른 조인이 가능하다.

✅ 해시 테이블 생성으로 인해 메모리 사용량이 크다.

✅ 범위 조건(<, >, BETWEEN)에서는 사용할 수 없다.