[Database] DBA급 개발자로 - #10 Join Algorithm

이전 포스팅을 통해 Sorting과 Aggregation이 어떻게 동작하는지 살펴봤습니다. 이번 포스팅에서는 Join algorithm에 대해서 살펴보겠습니다. 

Join

DBMS는 정규화를 통해 데이터의 중복을 제거합니다. 연관된 데이터가 정규화로 인해 서로 다른 테이블에 있다면 join을 통해 함께 조회할 수 있습니다. 어떤 join 알고리즘이 존재하는지 살펴보고 각각의 join 알고리즘 성능을 비교해보겠습니다. Join 알고리즘의 성능은 join 시 수행되는 전체 I/O 비용을 기준으로 측정합니다. 사용할 테이블과 join을 수행하는 쿼리는 다음과 같습니다. 

예시 테이블

select s.name, c.name 
from student s 
join class c on s.class_id = c.id

위 사진은 student, class 테이블의 일부 데이터만 표시한 것이라 가정하겠습니다(M = 1000, m = 100,000, N = 500, n = 40,000). 그리고 1회의 I/O cost 당 0.1 millisecond가 걸린다고 가정하겠습니다. 

 

Nested Loop Join 

Nested Loop Join은 2중 for 문과 유사합니다. Outer table과 inner table을 2중 for문으로 순회하면서 매칭 되는 튜플을 묶어서 반환합니다. 

Simple / Stupid 

for s in student:
  for c in class:
    emit if s.class_id = c.id

아무런 최적화가 없는 nested loop join은 student 테이블의 튜플을 읽고, 각각의 student 튜플과 매칭 되는 class 튜플을 찾기 위해 full table scan(class 테이블을 대상으로)을 수행합니다.  따라서 총 I/O cost는 다음과 같이 계산할 수 있습니다. 

(모든 student table의 튜플 조회를 위한 I/O cost) + (모든 class table의 튜플 조회를 위한 I/O cost) * (student table tuple의 수) 
= M + (N * m) 
= 1000 + (500 * 100,000) 
= 50,001,000

총 50,001,000회의 I/O가 수행되며 쿼리를 처리하는데 대략 83분이 소요됩니다. 만약 더 작은 테이블(student table)을 outer table로 처리하면 어떻게 될까요? 

(모든 class table의 튜플 조회를 위한 I/O cost) + (모든 student table의 튜플 조회를 위한 I/O cost) * (class table tuple의 수) 
= N + (M * n) 
= 500 + (1000 * 40,000)
= 40,000,500

작은 테이블을 outer table로 사용하니 더 적은 I/O가 발생하는 걸 확인할 수 있습니다(약 66분 소요). 따라서 join을 수행할 때 더 작은 테이블을 outer table로 설정하면 I/O 비용을 줄을 수 있습니다. 

 

Block Nested Loop Join 

최적화되지 않은 nested loop join에서 각각의 inner table 튜플을 읽는 횟수는 outer table의 튜플의 수와 같습니다. Block nesged loop join은 inner table의 튜플을 읽는 빈도수를 줄일 수 있도록 최적화한 기법입니다. 

사용할 수 있는 버퍼의 수를 B라고 가정했을 때, outer table을 읽는데 B-2개의 버퍼를 사용하고 1개는 inner table, 그리고 마지막 1개는 join 결과를 저장하는 데 사용한다고 가정하겠습니다. 그러면 Block Nested Loop Join은 다음과 같이 동작합니다. 

for (B-2 Blocks) in (Outer table = Student table):
  for (Single Block) in (Inner table = Class table):
    for Ts(tuple student) in (B-2 Blocks):
      for Tc(tuple class) in (Single Block):
        emit, if s.class_id = c.id

Block Nested Loop Join

Block nsted loop join의 총 I/O 비용은 다음과 같이 계산됩니다. 

(모든 student table의 튜플 조회를 위한 I/O cost) + 
(class table의 튜플은 B-2개의 버퍼에 저장된 student tuple(page 단위로 저장됨에 주의)에 대해서 디스크 I/O가 1번만 발생) 
= M + ((M / (B-2)) * N) 
= 1000 + ((1000 / (B-2)) * 500)

만약 버퍼의 수가 충분해서 B-2개의 버퍼에 M개의 student 테이블 페이지를 모두 저장할 수 있으면(B >= M + 2) 총 I/O 비용은 M + N이 됩니다. 즉 버퍼의 수만 충분하다면 I/O 비용을 최소화할 수 있습니다. 만약 I/O 비용이 M + N이라면 총 I/O 횟수는 1500회가 되므로 join을 수행하는데 약 0.15초가 소요됩니다. 

 

Index

Nested loop join의 성능이 좋지 않은 이유 중 하나는 테이블에 대한 sequential scan을 수행하기 때문입니다. Index를 활용해서 튜플을 빠르게 찾을 수 있으면 성능을 높일 수 있습니다. 

for s in student:
  for c in Index(class):
    emit

Index를 활용하면 s.class_id = c.id 조건을 만족하는 class table의 튜플을 B-Tree를 통해 찾을 수 있습니다. 따라서 class table에 대한 불필요한 sequential scan을 수행할 필요가 없습니다. Class table의 인덱스를 조회하는데 비용을 C라고 가정하면 총 I/O 비용은 다음과 같습니다. 

$$ M + (m * C) $$ 

 

정리

Nested Loop Join 최적화 방법 
- 작은 테이블을 outer 테이블로 설정
- Outer table을 최대한 버퍼에 저장
- Index를 활용 

 

Sort Merge Join

Sort merge join은 join 대상의 두 테이블을 join key를 기준으로 정렬 후 join을 수행하는 방법입니다. 이때 external merge sort를 활용해 정렬한다고 가정하겠습니다. Sorting과 관련된 I/O 비용은 아래 포스팅을 참고해주세요. 

2022.09.09 - [Database/DBA급 개발자로] - [Database] DBA급 개발자로 - #9 Sorting & Aggregation

[Database] DBA급 개발자로 - #9 Sorting & Aggregation

Sort mege join의 I/O의 비용은 다음 작업에 필요한 총 I/O 비용의 합입니다. 

Outer table external merge sort에 필요한 I/O 비용: $$ 2M * (1 + log_{B-1}(M/B)) $$

Inner table external merge sort에 필요한 I/O 비용: $$ 2N * (1 + log_{B-1}(N/B)) $$

정렬된 테이블을 merge 하는데 필요한 I/O 비용: $$ (M + N) * \alpha $$

 

정렬된 테이블을 merge 할 때 발생하는 비용에서 알파 값은 join key의 중복 비율에 비례해서 커지게 됩니다. 극단적인 예를 들어 양쪽 테이블의 join key값이 모두 동일하면 각각의 outer table tuple은 모든 inner table tuple과 매핑됩니다. 이 경우 정렬된 테이블을 merge 하는 데 있어 (M + m * N)만큼의 비용이 발생합니다. 

알파 값이 1이라 가정하고 계산해보면 대략 7,500번의 I/O가 발생하고 약 0.75초가 소요됨을 알 수 있습니다. 

 

Hash Join 

Hash join은 다음과 같이 동작합니다. 

Hash Join

우선 outer table의 join key를 활용해 해시 테이블을 생성합니다. 해시 테이블이 생성되면 inner table을 순회하면서 inner table의 join key에 해시 함수를 적용합니다. 해시 결괏값을 이용해 해시 테이블에서 매칭 되는 outer table의 join key를 찾습니다. 

 

마무리 

이번 포스팅을 통해 join 알고리즘에 대해 살펴봤습니다. 다음 포스팅에서는 요청된 쿼리가 어떻게 처리되는지 살펴보겠습니다.