11/19

🔹 Nested Join이란?

Nested Loop Join은 DB에서 두 테이블을 조인할 때 가장 기초적이고 단순한 알고리즘을 말한다.

이름 그대로 바깥 테이블의 각 행에 대해, 안쪽 테이블을 반복(loop) 돌면서 매칭되는 행을 찾는 방식이기 때문에 “Nested Loop Join” 또는 “Nested Join”이라고 불린다.

가장 직관적인 조인 방식이지만, 성능은 데이터량에 따라 크게 달라진다.

---

🔹 동작 방식(근거 기반 상세 설명)

예를 들어, 두 테이블 A(outer), B(inner)가 있다고 했을 때,

1. A 테이블에서 첫 번째 행을 가져온다.
2. 해당 행과 매칭되는 행을 찾기 위해 B 테이블 전체를 훑는다.
3. 매칭되면 결과에 추가한다.
4. 다음 A 행으로 이동해서 동일한 작업 반복.
5. A의 모든 행이 끝날 때까지 반복.

즉, 중첩 for-loop 형태로 동작한다.

for each row in A:
    for each row in B:
        if A.key == B.key:
            output row

🔸 시간 복잡도

• 최악의 경우 A × B
• A가 10,000건이고 B가 100,000건이면
  → 최대 10,000 × 100,000 = 10억 번 비교

그래서 인덱스 유무가 성능의 핵심이다.

---

🔹 왜 아직도 실제 DB에서 많이 쓰일까?

근거 있는 이유는 크게 다음 3가지로 볼 수 있는 것 같다:

① 인덱스가 있으면 매우 빠르다

특히 Inner 테이블의 조인 컬럼에 인덱스가 있으면,
루프 한 번당 Index Seek가 가능하므로 비용이 크게 줄어든다.

예)

SELECT * 
FROM orders o
JOIN customers c 
    ON o.customer_id = c.id;

customers.id에 인덱스가 있으면
outer row 하나당 O(log N)으로 매칭 검색 가능.

② 작은 테이블 + 큰 테이블 조인에 유리

작은 테이블이 outer, 큰 테이블이 inner이면 비용이 매우 낮아진다.

③ 조건이 복잡해도 안정적으로 동작

Nested Loop Join은 WHERE 조건이나 함수가 있어도 성능이 일정하다.
Hash Join/SORT-MERGE Join은 정렬/해시테이블이 필요하지만,
Nested Loop는 그런 비용이 없다.

---

🔹 다른 Join 알고리즘과 비교

Join 방식	특징	언제 유리?
Nested Loop Join	단순한 중첩 반복	작은 테이블 + 인덱스 존재
Hash Join	해시 테이블 생성 후 매칭	대용량 테이블 조인, 인덱스 없음
Merge Join	두 테이블을 정렬 후 동시에 스캔	이미 정렬돼 있거나 인덱스 기반 범위 스캔 가능

Nested Loop는 가장 범용적이라 옵티마이저가 자주 선택한다.

---

🔹 실제 예시 (PostgreSQL 기준 실행 계획)

EXPLAIN SELECT *
FROM orders o
JOIN customers c ON o.customer_id = c.id;

결과 예시:

Nested Loop
  -> Seq Scan on orders
  -> Index Scan using customers_pkey on customers

• Outer: orders
• Inner: customers (Index Scan 사용)

→ 인덱스 때문에 빠르게 동작하는 형태.

---

🔹 요약

• Nested Join = Nested Loop Join.
• 두 테이블 조인을 중첩 반복 구조로 수행하는 알고리즘.
• 작은 테이블 + 인덱스 조건에서는 매우 빠름.
• 큰 테이블끼리 조인하면 성능이 좋지 않음.
• DB 옵티마이저가 가장 자주 선택하는 조인 방식 중 하나.