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

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하여 데이터를 반환합니다.

 

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

 

 

 

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 할 데이터를 찾아서 반환합니다.

 

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

 

 

 

💡 나올 수 있는 질문

1. 중첩 루프 조인(Nested Loop Join)에 대해서 설명해보세요.