Nested Loops Join with Optimizer

Nested Loops Join은 조인을 수행할 때 모든 데이터를 JOIN 후에 필터링하는 것이 아니라,

미리 WHERE 절로 필터링한 후 테이블을 JOIN 때리는 방식이다

 

이때 옵티마이저는

인덱스, WHERE 절에서 사용하는 칼럼 등을 고려하여

어떤 테이블이 드라이빙 테이블로 적합할지 선정한다

 

---

[왜 WHERE 절의 인덱스가 중요할까?]

 

옵티마이저는 JOIN을 먼저 수행하고 WHERE로 필터링하는 것이 아니라, WHERE 절의 조건을 미리 활용해서 인덱스를 타고 JOIN을 진행할 수 있어.

 

SQL 실행 계획을 보면, 옵티마이저는 가능한 한 먼저 데이터를 줄인 후 조인하려고 해.
즉, WHERE 조건을 만족하는 데이터만 가져와서 조인을 수행하는 것이 훨씬 빠름.

 

1. 인덱스를 활용하는 경우

SELECT * 
FROM A 
JOIN B ON A.id = B.a_id
WHERE A.status = 'active';

 

만약 A.status가 인덱스 컬럼이라면:

1. 옵티마이저는 A 테이블에서 status = 'active'인 행만 먼저 가져옴.
2. 이렇게 필터링된 소수의 행만 B와 조인 진행.
3. 즉, WHERE 조건을 미리 반영해서 불필요한 데이터는 아예 읽지도 않음.

반면, A.status에 인덱스가 없으면:

• A 테이블을 풀스캔(FTS)한 후 status = 'active'를 필터링하고, 조인을 진행해야 함.

 

2. WHERE 절 없이 풀스캔이 발생하는 경우

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

• 여기서는 WHERE 조건이 없으므로
• 옵티마이저는 A 테이블을 전체 스캔해야 할 수도 있음.
• 이후 B 테이블과 매칭하면서 인덱스를 탈 수도 있지만,
  A에서 불필요한 데이터를 너무 많이 가져오면 비효율적.

결론

✔ WHERE 절에서 사용되는 칼럼이 인덱스를 타면, 옵티마이저는 이를 활용해서 JOIN 전에 미리 필터링할 수 있다.
✔ 즉, JOIN 전에 WHERE 조건을 만족하는 데이터만 가져와서, 불필요한 풀스캔을 방지할 수 있음.
✔ WHERE이 없거나 인덱스를 활용할 수 없으면 풀스캔이 발생할 가능성이 높아짐.

 

---

[Nested Loops JOIN 수행 원리 with 옵티마이저]

 

SQL은 선언형 프로그래밍 언어이기 때문에

작성된 SQL 구문을 데이터베이스가 그대로 순서대로 실행하지 않음

대신, DB 엔진(query optimizer)가 다음과 같은 단계를 통해 최적화된 실행 계획을 생성하고 수행함

 

1. SQL 파싱

• DBMS는 SQL을 읽고 구문 분석을 수행하여 올바르게 작성된 SQL인지 확인함
• 구문에 문제가 없으면 SQL을 Parsing Tree 라는 데이터 구조로 변환함

2. 옵티마이저 최적화

 

DB 엔진의 옵티마이저는 실행계획을 평가하여 가장 비용이 적게 드는 실행 계획을 선택함

1. 전체 쿼리문을 보고 드라이빙 테이블 선정
2. 조인 순서 결정
3. 사용할 인덱스 선택

 

이때 DB 엔진은 드라이빙 테이블 선정이나 조인 순서를 자신이 자동으로 바꿀 수 있지만

인덱스를 자신의 판단 아래 생성할 수 는 없다

 

따라서 인덱스는 개발자가 생성해줘야하는데

인덱스가 많으면 그만큼 B-Tree가 많아지니 메모리를 그만큼 많이 잡아먹는다는 뜻이므로

적절하게 선별하여 인덱스를 생성해놓을 필요가 있다

 

---

[Nested Loops JOIN 동작 예시]

SELECT
       E.EMPNO, 
       E.ENAME, 
       D.DNAME, 
       E.JOB, 
       E.SAL
FROM DEPT D
INNER JOIN EMP E
ON D.DEPTNO = E.DEPTNO                 -- ① JOIN 조건
WHERE 
    D.LOC = 'SEOUL'                    -- ② 필터 조건
    AND D.GB = '2'                     -- ③ 필터 조건
    AND E.SAL >= 1500                  -- ④ 필터 조건
ORDER BY E.SAL DESC;

DEPT 테이블의 LOC칼럼에 인덱싱이 되어있고
EMP는 DEPT의 PK키인 DEPTNO를 외래키로 가지고 있다고 하자

여기서 외래키는 인덱싱이 자동으로 되므로 EMP도 DEPTNO에 대한 인덱싱이 걸려있다고 가정하자

 

1. Driving Table의 선정

 

옵티마이저는 실행 계획을 수립할때, 테이블의 크기와 WHERE 조건절을 분석한다

 

WHERE 절의 D.LOC에 인덱싱이 되어있고 D.GB = 2 조건을 먼저 적용하여 테이블을 줄일 가능성이 높다.

 

따라서 DEPT를 드라이빙 테이블로 선택할 가능성이 높다

 

2. Driven Table과의 조인

 

DEPT에서 필터링된 데이터와 EMP 테이블을 조인한다

 

EMP의 외래키인 DEPTNO에 인덱스가 있다면, 인덱스 B-Tree를 타서 더 효율적으로 매칭되는 DEPTNO row를 찾아 조인한다

 

여기서도 SAL에 인덱싱이 걸려있으면 미리 WHERE 조건의 E.SAL >= 1500으로 필터링한 후 조인을 때린다.

 

3. JOIN 후 작업 실행 (ORDER BY)

 

조인된 데이터를 E.SAL DESC로 정렬한다.

이때도 E.SAL에 인덱스가 있는 경우 더 빠르게 정렬될 수 있다.

 

---

[그림 설명]

 

• (O):테이블 필터 조건에 의해 레코드가 걸러지지 않은 것을 의미하고, (X): 테이블 필터 조건에 의해 걸러진 것을 의미
• 결국 전체 일량은 dept_loc_idx 인덱스를 스캔하는 양이다
• 이 그림에서는 단일 칼럼 인덱스를 '=' 조건으로 스캔(Non Unique Scan)했으므로 비효율 없이 6(=5+1)건을 읽었고,
  • 그만큼 테이블 Random 액세스가 발생했으며 이 부분이 NL Join의 첫 번째 부하지점이다.
• 만약 dept 테이블로 많은 양의 Random 액세스가 있었는데 gb = '2' 조건 필터링 비율이 높다면 dept_loc_idx에 gb 칼럼을 추가하는 방안을 고려해야 한다.
• 두 번째 부하지점은 emp_deptno_idx 인덱스를 탐색하는 부분이며, Outer 테이블인 dept를 읽고 나서 조인 액세스가 얼마만큼 발생하느냐에 의해 결정된다.
• 이것 역시 Random 액세스에 해당하며, 그림에서는 gb = '2' 조건을 만족하는 건수만큼 3번의 조인시도가 있었다.
• 만약 emp_deptno_idx의 높이(height)가 3이면 매 건마다 그만큼의 블록 I/O가 발생하고, 리프 블록을 스캔하면서 추가적인 블록 I/O가 더해진다.
• 세 번째 부하지점은 emp_deptno_idx를 읽고 나서 emp 테이블을 액세스하는 부분이다. 여기서도 sal >= 1500 조건에 의해 필터링되는 비율이 높다면 emp_deptno_idx 인덱스에 sal 칼럼을 추가하는 방안을 고려해야 한다.
• OLTP 시스템에서 조인을 튜닝할 때는 일차적으로 NL Join부터 고려하는 것이 올바른 순서다. 우선, NL Join 메커니즘을 따라 각 단계의 수행 일량을 분석해 과도한 Random 액세스가 발생하는 지점을 파악한다. 조인 순서를 변경해 Random 액세스 발생량을 줄일 수 있는 경우가 있지만, 그렇지 못할 때는 인덱스 칼럼 구성을 변경하거나 다른 인덱스의 사용을 고려해야 한다. 여러 가지 방안을 검토한 결과 NL Join이 효과적이지 못하다고 판단될 때 Hash Join이나 Sort Merge Join을 검토한다.

---

[인덱싱 여부에 따른 드라이빙 테이블 FULL SCAN]

 

SELECT A.name, B.age
FROM A
JOIN B ON A.id = B.id
WHERE B.age > 28;

위 쿼리에서는 WHERE 절에 A에 대한 조건이 없다
따라서 A가 드라이빙 테이블이된다면 무조건 풀스캔이 될 것이다.
따라서 옵티마이저는 WHERE 조건절이 있는 B를 드라이빙 테이블로 선정하고
WHERE 절로 필터링 후 조인을 진행할 가능성이 높다는 것을 예측할 수 있다

 

1. 만약 A가 드라이빙 테이블이라면?

1. WHERE 조건이 드라이빙 테이블에 없으므로 인덱스 없이 모든 행을 FULL TABLE SCAN으로 읽게됨
2. B에서는 A.id = B.id 조건을 만족시키기 위해 id 열에 대한 인덱스를 활용
3. 추가로 B.age > 28 조건이 있기 때문에, age 칼럼에 대한 인덱스가 존재하면 더 빠르게 필터링 가능. 효율성 증가

2. 만약 B가 드라이빙 테이블이라면?

1. WHERE 조건이 드라이빙 테이블에 존재하므로 B.age로 필터링 후 JOIN 진행
2. age 칼럼에 인덱싱이 되어있으면 더 빠르게 필터링 가능
3. A와 JOIN 시 A.id = B.id 조건을 만족시키기 위해 id 열에 대한 인덱스를 활용

 

---

[Driving Table and Driven Table]

 

Driving Table / Driven Table 개념은 Nested Loop Join에서만 사용됨!
Sort Merge Join과 Hash Join은 양쪽 테이블을 동시에 활용하는 방식이라 Driving Table 개념이 없음.
즉, Nested Loop Join에서 "어떤 테이블을 먼저 읽을지" 결정하는 게 중요하기 때문에 이런 용어가 생긴 거야!

 

DRIVING TABLE 이란?

JOIN시 먼저 엑세스 되어 Access path(접근 경로)를 주도하는 테이블을 드라이빙 테이블(OUTER TABLE)이라고 한다. 

 

DRIVEN TABLE 이란?

DRIVEN TABLE 엑세스 된 후 나중에 액세스 되는 테이블을 드리븐 테이블(DRIVEN TABLE, INNER TABLE)이라고 한다. 

 

옵티마이저의 DRIVING TABLE 결정 시 영향을 미치는 것은?

인덱스(INDEX)의 존재 및 우선순위 혹은 WHERE 절에 조건이 걸린 칼럼에 영향을 받으며,

어느 테이블이 먼저 엑세스 되느냐에 따라 속도의 차이가 크게 날 수 있으므로

많은 양의 데이터를 다룰 때 드라이빙 테이블은 매우 중요하다.

 

예를 들어,

조건을 만족하는 100건의 데이터인 A 테이블과 조건을 만족하는 5000건인 B 테이블과 조인 시

드라이빙 순서에 따라 속도의 확연한 차이가 있다.

 

예를 들어, A를 드라이빙 테이블로 선택하면:

 

A의 데이터 100개를 순차적으로 인덱스 검색 (O(log 100))

각 A의 행에 대해 B에서 인덱스 검색 (O(log 5000))

총 연산: 100 × log(5000) ≈ 100 × 13 = 1300번 검색

 

반대로 B를 드라이빙 테이블로 선택하면:

 

B의 데이터 5000개를 순차적으로 인덱스 검색 (O(log 5000))

각 B의 행에 대해 A에서 인덱스 검색 (O(log 100))

총 연산: 5000 × log(100) ≈ 5000 × 7 = 35000번 검색 → 훨씬 비효율적!

 

즉, 작업 대상이 되는 행(rows)의 수가 적은, 작은 테이블부터 액세스 되어야 전체 탐색이 줄어든다.