[데이터베이스] 조인의 원리

1. 중첩 루프 조인 (NLJ, Nested Loop Join)

중첩 for 문과 같은 원리로 조건에 맞는 조인을 하는 방법을 말합니다.
Index에 의한 Random Access 비용이 많이 증가하기 때문에 대용량 데이터를 다루기에는 적절하지 않습니다.

중첩 루프 조인의 작동

# CS 전공지식 노트 226 page

for each row in t1 matching reference key {
    for each row in t2 matching reference key {
        if row satisfies join conditions, send to client
    }
}

위에 있는 코드는 중첩 루프 조인을 사용하여 t1 테이블과 t2 테이블을 조인하는 의사 코드입니다.
t1 테이블에서 행을 한 번에 하나씩 읽고, t2 테이블에서도 행을 하나씩 읽으며 조건에 맞는 데이터를 찾아서 반환하게 됩니다.
여기서 t1을 Driving Table이라고 하며, t2를 Driven Table이라고 합니다.
중첩 루프 조인에서는 Driving Table을 적절하게 선택해야 합니다. 처음 Driving Table에 해당되는 row가 너무 많다면, 그만큼의 반복을 해줘야하기 때문에 Driving Table에서 Where절로 row 수를 최대한 줄일 수 있어야 합니다.
Driving Table의 Join Column에 index가 존재하는지도 확인해봐야 합니다. 존재하지 않는다면 Random Access가 아닌 Full Table Scan을 통해서 모두 비교해야 하기 때문에 index를 생성하는 것이 좋습니다.

[출처] https://dataonair.or.kr/db-tech-reference/d-guide/sql/?mod=document&uid=356

* Driving Table : Join 할 때, 먼저 Access되어 Access Path를 주도하는 테이블
* Driven Table : Join 할 때, 나중에 Access되는 테이블

2. 정렬 병합 조인 (Sort Merge Join)

각각의 테이블을 조인할 필드 기준으로 정렬한 후 조인 작업을 수행하는 조인 방법입니다.
조인할 때 사용할 적절한 인덱스가 존재하지 않고, 대용량 테이블을 조인하는 데 사용됩니다.
조인 조건으로 비교 연산자(>, <, >=, <=)가 있을 때도 사용됩니다.
조회 범위가 좁을 때 유리했던 Nested Loop Join과는 다르게 조회 범위가 많을 때 주로 선택되어 사용합니다.

정렬 병합 조인의 작동

각 테이블에 대해서 독립적으로 데이터를 읽어옵니다. 인덱스가 존재하는 컬럼의 테이블은 Random Access, 인덱스가 존재하지 않는 컬럼의 테이블은 Full Table Scan을 사용합니다.
읽힌 각 테이블의 데이터를 조인을 위한 연결고리에 대하여 정렬을 수행합니다.
정렬이 모두 끝난 뒤 정렬된 데이터를 차례로 Scan 하면서 연결고리의 조건으로 Merge하여 데이터를 반환합니다.

3. 해시 조인 (Hash Join)

조인할 두 테이블 중 하나를 해시 테이블로 선정하여 조인에 사용되는 컬럼 값을 해시 알고리즘으로 비교하여 조인하는 방법입니다.
동등(=) 조인에서만 사용할 수 있습니다.
Sort Merge Join을 할 때, 테이블 크기가 너무 커서 Sort에 드는 부하가 너무 클 때 해시 조인가 사용됩니다.
조인에 사용되는 컬럼에 적절한 index가 존재하지 않아서 Nested Loop Join을 사용하기에 효율적이지 못할 때 사용됩니다.

해시 조인의 작동

A 테이블과 B 테이블을 조인할 때, 둘 중 바이트가 더 작은 테이블을 읽어서 Hash Area에 해시 테이블을 생성합니다. 이때 해시 테이블의 Key는 조인에 사용되는 필드가 됩니다.
만약 A 테이블이 해시 테이블로 생성되었다면, A 테이블은 Build Input이라고 하고, B 테이블은 Probe Input이라고 합니다.
B 테이블을 스캔하며 조인 컬럼을 해시 함수에 넣고, 반환되는 버킷 주소로 찾아가 해시 체인을 스캔하며 Join 할 데이터를 찾아서 반환합니다.