[SQL Join 시리즈1] 데이터베이스 Nested Loop Join

SQL 에는 크게 3가지 조인 방식이 있다.

 

 

1. nested loop join

2. merge join

3. hash join

 

 

이번에는 그 중에서 nested loop join에 대해 살펴볼 것이다.

 

---

Nested loop join

 

nested loop join는 말 그대로 중첩 반복 조인이다.

 

pseudocode를 살펴보자

테이블  r의 tuple을 반복하고, 테이블 s의 tuple을 반복해서 join이 가능한지 확인한다.

 

 

여기서 테이블 r을 바깥쪽이기 때문에, outer table(driving table)

테이블 s는 안쪽이기 때문에, inner table(driven table) 이라고 부른다.

 

 

매번 튜플들에 대해서 join 조건이 만족하는지 확인하기 때문에 비싼 연산이다.

 

 

Cost를 계산해보자

(참고로, SQL 쿼리 성능에서 block transfers 비용이 매우 크기 때문에 여기서는 block transfer 비용으로 비교한다)

 

 

최악의 경우, 메모리에 각 relation의 한개의 블럭만 들어갈 수 있다고 가정해보면 예상되는

cost는 nr * bs + br block transfer이다.

(nr은 record의 개수,  br, bs는 block의 개수이다.)

 

 

만약 더 작은 relation 전체가 메모리에 들어갈 수 있다면, 그 relation을 inner relation으로 사용해서

cost를 br + bs block transfer로 줄일 수 있다.

 

 

예시를 통해 살펴보자

예시에 사용할 relation은 아래와 같다.

depositor를 outer table로 한다면

cost는 5000 * 400 + 100 = 2,000,100 block transfers이다

 

 

customer를 outer table로 한다면

cost는 10000 * 100 + 400 = 1,000,400 block transfers이다

 

 

customer를 outer table로 했을때 비용이 더 작은 것을 알 수 있다.

 

 

만약에 records가 더 작은 depositor relation 전체가 메모리에 들어간다면 비용은 

100 + 400 = 500 block transfers이다

 

 

이러한 join 방식은 비효율적이기 때문에 약간 개선시킨 block nested loop join이 등장하게 되었다.

---

Block nested loop join

Block nested loop join pseudocode는 아래와 같다.

nested loop join에서는 relation r과 s의 각 튜플에 대해서 비교하였지만

Block nested loop join에서는 relation r과 s를 각각 block Br, Bs로 나누고 Br과 Bs의 각 튜플에 대해서 비교하였다.

 

 

Cost를 계산해보자

최악의 경우, 메모리가 너무 작아 inner relation인 s의 block이 매 outer relation의 block마다 불러와져야 한다고 가정해보면 예상되는 cost는 br * bs + br block transfer이다.

 

 

최선의 경우, 메모리에 전체를 다 올리면 되기 때문에 br+bs block transfer이다.

 

 

여기서 index를 활용하여 성능을 더 개선시킬 수 있다.

---

Indexed nested loop join

만약 equi join이나 natural join일 때, index를 통해 더욱 빠르게 join할 수 있다.

 

 

outer table인 relation r의 매 튜플 tr마다 tr과 join이 될 만한 tuple을 s에서 index를 활용해서 빠르게 찾는 것이다!

 

 

Cost를 계산해보자

 

최악의 경우를 생각해보면, 메모리에 공간이 r을 위한 공간, s를 위한 공간 딱 두개만 있다고 가정하는 것이다.

 

 

그럼, br + nr * c block transfer이다.

(여기서 c는 index에서 찾고 join이 가능한 모든 튜플을 fetch하는 cost이다)

 

 

위에서 사용했던 예시로 한번 cost를 계산해보자

 

depositor가 outer table이고 customer가 inner table로 B+Tree index를 가지고 있으며, 각 index node는 20개의 entry를 가지고 있다고 가정해보자.

그렇게 되면 customer relation은 records가 10000이기 때문에 tree의 높이는 약 4이다. 그리고 실제 데이터를 찾아가기 위한 과정이 한 번 더 필요해서 c는 4+1 = 5가 된다.

 

 

최악의 경우를 가정했을 때

block nested loop join의 경우에는

cost가 100 * 400 + 100 = 40,100 block transfers 이다.

 

 

indexed nested loop join의 경우에는

cost가 100 + 5000 * 5 = 25,100 block transfers 이다.

 

 

따라서 index가 있을 경우 indexed nested loop join를 사용하는 게 빠를 수 있다.

 

 

 

nested loop join를 PostgreSQL 15, MySQL 8.0, Oracle 19c에서 모두 지원하고 있다.

더 알고 싶다면 아래 글을 참고하자!

https://durumiss.tistory.com/30

MySQL, Oracle, PostreSQL 비교 분석하기

 

 

 

또한, MySQL에서는 nested-loop join 알고리즘의 동작 방식에 대해 아래 링크에서 설명하고 있다.

https://dev.mysql.com/doc/refman/8.0/en/nested-loop-joins.html

MySQL :: MySQL 8.0 Reference Manual :: 8.2.1.7 Nested-Loop Join Algorithms

 

 

참고 :

Database System Concepts 7th edition