RDBMS 조인 알고리즘 : Nested Loop Join

RDB(Relational Database 관계형 데이터베이스)를 사용할 때 Join이 빠질 순 없다. Join은 서로 다른 테이블을 결합하는 과정이며, 이 결합의 과정은 Join Key라고 하는 두 테이블의 컬럼에서 매칭되는 값을 찾고, 매칭되는 row를 이어 붙이는 과정이라 할 수 있다. 두 테이블의 컬럼을 매칭시키는 방법은 아주 다양할 수 있다. 이 방법들을 조인 알고리즘이라 부른다. 아래에선 조인 알로리즘 중 가장 보편적으로 활용되는 Nested Loop Join에 대해 설명하겠다. 

 

개념

 

Nested Loop Join는 Loop라는 단어를 그 속에 가진 것처럼 프로그래밍 언어의 For문과 같은 반복적(iterable) 과정을 가진다. Nested라는 단어는 '중첩된'이라는 뜻인데, 여기서 말하는 중첩이란 기준 테이블(Driving, Outer Table)의 컬럼을 순회하는 For 문 속 조인 테이블(Driven, Inner Table)의 컬럼을 순회하는 For 문이 있다는 뜻이다. 

 

이름에서부터 그 실행 구조가 명료하게 나타난다. Nested Loop Join은 기준 테이블의 컬럼의 값을 순회하며 그 컬럼값과 연결되는 조인 테이블의 row를 찾는 방식으로 두 테이블의 row를 연결하는 방식을 가진 Join 알고리즘이다.

 

도식

 

아래와 같은 SQL이 주어진다고 하자. 

select
  Out.*,
  In.*
from 
  outer Out, inner In
where
  Out.jcol = In.jcol

 

이 Join을 Nested Loop Join으로 한다면 DB 프로세스는 아래와 같은 도식으로 두 테이블의 row를 매칭한다. 

동작 순서는 다음과 같다. 

 

1️⃣ [외부 Loop] 기준 테이블의 조인 컬럼의 값을 순차적으로 Scan한다. 

2️⃣ [내부 Loop] Scan된 기준 테이블의 조인 컬럼의 값과 매칭되는 컬럼값을 가진 조인 테이블의 row를 찾는다. 찾는 과정은 Random Access 방식으로 이루어지고, 일치된 값을 찾으면 반환 객체에 해당 값을 넣고 찾지 못하면 1️⃣로 돌아간다. 

 

 

인덱스와 Nested Loop Join 

 

Nested Loop Join은 매우 직관적이면서 파워풀한 조인 알고리즘이다. 이 파워풀함을 전적으로 잘 활용하려면 인덱스와 함께 병행해야 한다. 인덱스를 두지 않은 경우나 둘 수 없는 경우에는 Nested Loop Join이 아닌 Sort Merge Join, Hash Join을 사용함이 옳다. 

 

앞서의 Nested Loop Join의 동작 구조를 설명하는 부분에서 내부 Loop의 과정이 Random Access 방식으로 이루어진다고 했는데, 이는 엄밀하게 말해 조인 테이블(inner table)의 조인컬럼이 인덱스로 되어 있어야만 가능한 이야기다. 인덱스가 없으면 inner Table에 대한 Full-scan을 통해 매칭되는 row를 찾아야 한다. 이런 경우는 없어야하기에 인덱스가 있는 것을 가정하고 Random Access 방식으로 이루어진다고 한 것이다. 요약하자면 Nested Loop Join을 사용할 땐 조인 테이블의 조인 컬럼을 인덱스로 만들어야 한다. 

 

반면 기준 테이블의 조인 컬럼은 어쨌거나 전체 컬럼의 값을 모두 읽어야하기 때문에 인덱스의 유무가 부하에 큰 영향을 주지 않는다. 기준 테이블의 경우엔 인덱스보다는 그 처리 범위에 대한 고려가 더욱 중요하다. 

 

 

기준 테이블의 처리범위와 Nested Loop Join의 성능

 

도식만 두고보자면 Nested Loop Join의 과정에선 기준 테이블의 row 수(외부 Loop Read Count) X 조인 테이블의 row 수(내부 Loop Read Count MAX)만큼의 데이터 읽기가 발생한다. 내부 Loop의 읽기는 Random Access 이므로 그 값이 정해져있진 않지만 외부 Loop Read Count는 고정된 값이다. 그렇기에 조인의 성능 향상을 위해선 이 고정된 값을 최대한 줄이는 것이 중요하겠다. 

 

가령, 조인 컬럼에서 일부의 값을 필터링하려고 한다고 하자. 

 

첫번째는 기준 테이블의 조인 컬럼에 조건을 거는 경우다. 

select
  Out.*,
  In.*
from 
  outer Out, inner In
where
  Out.jcol = In.jcol
  and Out.jcol not in ('H', 'L')

 

두번째는 조인 테이블의 조인 컬럼에 조건을 거는 경우다. 

select
  Out.*,
  In.*
from 
  outer Out, inner In
where
  Out.jcol = In.jcol
  and In.jcol not in ('H', 'L')

 

논리적으로 보아 두 SQL은 동일한 작업을 요청하는 것이고, 그 결과도 동일할 것이라는 것을 알 수 있다. 하지만 SQL 구문에 따라 처리 과정에 상당한 차이가 발생한다. 

 

첫번째 쿼리의 경우, 외부 Loop 에서 해당 값들이 걸러지면서 Scan에서 제외된다. 따라서 필터링된 값에 대해서는 내부 Loop가 애초에 돌지 않는다. 

두번째 쿼리의 경우, 조건에 따른 필터링이 내부 Loop 까지 다 돈 후 반환 객체에 넣어지는 단계에서 이루어진다. 따라서 조인 컬럼에 대한 필터링이 있음에도 데이터를 읽는 횟수는 조건이 없는 경우와 동일하다. 

 

물론 최근의 RDBMS는 옵티마이저의 성능이 워낙 좋아, 예시 정도의 상황에 대해선 적정한 쿼리 변형 처리를 하겠지만 요점은 기준 테이블의 처리 범위를 줄여주는 것이 Nested Loop Join의 성능의 주요한 요인이라는 것이다.

 

 

Cursor문으로 구현한 Nested Loop Join

 

Nested Loop Join의 동작 방식을 좀 더 직관적으로 알기 위해 cursor문으로 그 동작 과정을 구현해보았다. 엄밀하게 부합되는 개념은 아니니 참고만 하시길. 

 

-- OUTER TABLE 커서
DECLARE cur_outer CURSOR FOR
SELECT j_col, ...
FROM outer;  -- 바깥 테이블

-- Outer Loop
OPEN cur_outer;

outer_loop:
LOOP
    FETCH cur_outer INTO v_j_col, ...;
    IF done THEN
        LEAVE outer_loop;
    END IF;

    -- Inner Loop
    DECLARE cur_inner CURSOR FOR
    SELECT j_col, ...
    FROM inner
    WHERE j_col = v_j_col;  -- 인덱스 탐색 or 풀스캔

    OPEN cur_inner;

    inner_loop:
    LOOP
        FETCH cur_inner INTO v_j_col_inner, ...;
        IF done_inner THEN
            LEAVE inner_loop;
        END IF;

        -- JOIN 결과 처리
        INSERT INTO join_result (...)
        VALUES (...);

    END LOOP inner_loop;

    CLOSE cur_inner;
END LOOP outer_loop;

CLOSE cur_outer;