이 세상 모든 Join 알고리즘에 대하여(다는 아님)

관계형 데이터베이스에서 제공하는 연산 중 가장 유용한 것은 조인(join) 연산이라고 해도 과언이 아닌데요. 아이러니하게도 조인은 시간이 매우 오래 걸리는 연산 중 하나입니다. 이번 글에서는 조인 연산의 알고리즘을 알아보며 어떤 식으로 연산 시간을 개선하는지 알아보도록 하겠습니다.

참고 자료는 아래와 같습니다.

• Nested-loop join - IBM Documentation
• Sort Merge Join - Yeshwanth N

데이터베이스 가정

본격적으로 조인 알고리즘에 대해 알아보기 전에 예시로 사용할 테이블에 대해 설명하도록 하겠습니다. 예시 데이터베이스는 은행에서 사용되며 고객과 예금자 정보를 저장하는 테이블로 구분됩니다.

또한, 각 테이블의 메타데이터는 다음과 같습니다.

• 고객(Customer): 전체 레코드 10,000개, 블럭당 레코드 25개 (= 전체 블럭 400개)
• 예금자(Depositor): 전체 레코드 5,000개, 블럭당 레코드 50개 (= 전체 블럭 100개)

Nested loop join

처음에 소개할 알고리즘은 nested loop join입니다. 해당 알고리즘은 outer table을 스캔한 다음 조건에 맞는 각 행을 innert table의 행과 조인합니다. 알고리즘의 pseudo code는 아래와 같습니다.

for each tuple s in S do
  for each tuple r in R do
    test s.join_attribute == r.join_attribute
    if they do, arr r•s to the result
  end
end

알고리즘 분석

Nested loop join에서 outer table와 inner table에 대한 접근 횟수는 레코드 단위로 이루어집니다.

\[blocks\ of\ outer\ +\ records\ of\ outer\ \times\ blocks\ of\ inner\]

따라서 예시 데이터베이스 환경에서는 다음과 같이 동작합니다.

• Customer가 outer table이고 Depositor가 inner table인 경우: 400 + 10,000 * 100 = 1,000,400
• Depositor가 outer table이고 Customer가 inner table인 경우: 100 + 5,000 * 400 = 2,000,100

Nested loop join의 특징은 다음과 같습니다.

• 👍 인덱스가 필요없으며 모든 조인 조건에 사용 가능하다.
• 👎 레코드 단위의 조인을 수행하므로 연산량이 매우 높다.

Block nested loop join

다음으로 소개할 알고리즘은 block nested loop join입니다. 해당 알고리즘은 nested loop join을 개선한 것으로 블럭 단위로 조인을 수행합니다.

알고리즘의 pseudo code는 아래와 같습니다.

for each block Bs in S do
  for each block Br in R do
    for each tuple s in Bs do
      for each tuple r in Br do
        test s.join_attribute = r.join_attribute
        if they do, add r • s to the result
      end
    end
  end
end

알고리즘 분석

Block nested loop join에서 outer table와 inner table에 대한 접근 횟수는 블록 단위로 이루어집니다.

\[blocks\ of\ outer\ +\ blocks\ of\ outer\ \times\ blocks\ of\ inner\]

따라서 예시 데이터베이스 환경에서는 다음과 같이 동작합니다.

• Customer가 outer table이고 Depositor가 inner table인 경우: 400 + 400 * 100 = 40,100
• Depositor가 outer table이고 Customer가 inner table인 경우: 100 + 100 * 400 = 40,400

Block nested loop join의 특징은 다음과 같습니다.

• 👍 블럭을 메모리에 저장하여 디스크 I/O를 줄일 수 있다.
• 👎 메모리와 블럭 크기에 영향을 많이 받는다. (메모리가 작을수록, 블럭이 작을수록 많은 디스크 I/O 발생)

Index nested loop join

만약 조인 컬럼에 대하여 인덱스가 존재한다면 index nested loop join을 적용할 수 있습니다. 해당 알고리즘은 nested loop join을 개선한 것으로 inner table에 대하여 파일을 스캔하는 것이 아닌 인덱스를 스캔합니다.

알고리즘의 pseudo code는 아래와 같습니다.

for each tuple s in S do
  find matching tuples r in R using index on join attribute
  for each tuple r in matching tuples do
    add r • s to the result
  end
end

알고리즘 분석

Indexed nested loop join에서 outer table에 대한 접근 횟수는 블록 단위로 이루어지며, inner table에 대한 접근은 인덱스를 통해 이루어집니다. 따라서 외부 테이블의 블록 접근 횟수는 동일하지만 내부 테이블에 대한 레코드 접근 횟수가 줄어들게 됩니다.

\[blocks\ of\ outer\ +\ records\ of\ outer\ \times\ (index\ access\ of\ inner + 1)\]

마지막에 추가적인 1이 붙는 이용은 인덱스를 탐색하고 난 후 실제 블럭에 접근하는 비용입니다.

또한, Customer와 Depositor의 인덱스가 B+ 트리일 경우 인덱스에 접근하는 비용은 다음과 같습니다.

• Customer의 인덱스 검색 비용: $log_{25}10000=2.8613=3$
• Depositor의 인덱스 검색 비용: $log_{50}5000=2.1771=3$

따라서 예시 데이터베이스 환경에서는 다음과 같이 동작합니다.

• Customer가 outer table이고 Depositor가 inner table인 경우: 400 + 10,000 * 4 = 40,400
• Depositor가 outer table이고 Customer가 inner table인 경우: 100 + 5,000 * 4 = 25,100

Indexed nested loop join의 특징은 다음과 같습니다.

• 👍 인덱스를 사용하여 내부 테이블에 대한 접근 횟수를 줄여 성능을 향상시킨다.
• 👎 인덱스의 생성 및 유지 비용이 추가로 발생할 수 있으며, 내부 테이블에 대한 인덱스가 필요하다.

Sort merge join

만약 테이블이 이미 정렬되어있다면 sort merge join을 이용하여 효율적으로 조인을 수행할 수 있습니다. 해당 알고리즘은 두 테이블을 조인하는 과정에서 정렬된 순서를 유지하며 결과를 구합니다.

이름에서 알 수 있듯이 이 알고리즘은 두 단계로 나누어져있습니다.

• 정렬(sort) 단계: 주어진 조인의 조건에 따라 정렬
• 병합(merge) 단계: 조인 조건이 일치하는 행을 결과에 추가

알고리즘의 pseudo code는 다음과 같습니다.

sort S and R by join attribute

point_s, point_r = 0, 0
while point_s < length(S) and point_r < length(R)
  s, r = S[point_s], R[point_r]
  
  if s.join_attribute == r.join_attribute
    add s • r to result
    point_r++
  else if s.join_attribute > r.join_attribute
    point_r++
  else
    point_s++

알고리즘 분석

Sort merge join의 성능은 정렬하는 비용과 조인하는 비용에 따라 결정됩니다. 외부 파일의 정렬 알고리즘을 2PMM으로 사용한다고 가정했을 때 정렬 비용은 다음과 같습니다.

\[cost\ of\ 2PMM = 2(block\ of\ S\ +\ block\ of\ R)\]

조인의 경우 각 테이블의 블록을 한 번씩 접근하므로 최종 시간 복잡도는 다음과 같습니다.

\[3(block\ of\ S\ +\ block\ of\ R)\]

Sort merge join의 특징은 아래와 같습니다.

• 👍 인덱스의 유무에 관계없이 동작한다.
• 👍 각 테이블을 한 번씩만 스캔하므로 효율적이다.
• 👍 테이블이 정렬되어 있는 경우 대량의 데이터에서도 빠르게 조인을 수행할 수 있다.
• 👎 데이터의 크기에 따라 정렬에 필요한 비용이 많이 필요할 수 있다.
• 👎 테이블 간의 크기 차이가 클 경우 다른 테이블의 정렬이 완료될 때까지 대기해야한다.

Hash join

또한, 해시 알고리즘을 이용하여 조인을 수행할 수도 있습니다. 기본적으로 하나의 테이블의 조인 컬럼에 대한 해시 테이블을 생성한 후 다른 테이블에서 해시 값을 이용하여 조인하는 방식으로 이루어집니다.

Simple hash join

가장 간단한 구현 방법인 Simple hash join은 기본적인 해시 조인 알고리즘을 그대로 구현한 것입니다.

• 생성(build) 단계: 두 테이블 중 작은 테이블을 메모리로 읽어 해시 테이블을 생성
• 탐색(probe) 단계: 다른 테이블을 읽어 조인 값을 해싱하고 해시 테이블에서 매칭되는 값을 찾아 결과에 추가

이 알고리즘은 구현이 가장 간단하지만 해시 테이블을 메모리에 저장하기 때문에 테이블의 크기가 큰 경우 사용할 수 없습니다.

Grace hash join

만약 메모리에 올리지 못하는 큰 테이블을 해시로 조인하려면 Grace hash join 알고리즘을 사용할 수 있습니다. 이 알고리즘은 큰 테이블을 여러 파티션으로 나눈 후 파티션 단위로 해시 조인을 수행합니다.

• 분할(partition) 단계: 큰 테이블을 메모리에 올릴 수 있는 크기의 파티션으로 분할
• 생성(build) 단계: 각 파티션을 메모리로 읽어 해시 테이블을 생성
• 탐색(probe) 단계: 다른 테이블을 읽어 파티션 단위로 해시 테이블에서 매칭되는 값을 찾아 결과에 추가

Hybrid hash join

다음으로 hybrid hash join은 위 두 방법을 적절하게 선택한 알고리즘입니다. 메모리 공간이 충분할 경우 메모리 기반 해시 조인을 수행하고 메모리가 부족할 경우 디스크 기반 조인을 수행할 수 있습니다.

• 생성(build) 단계: 메모리에 올릴 수 있는 테이블을 읽어 해시 테이블에 생성. 만약 메모리가 부족한 경우 디스크를 이용하여 해시 테이블을 생성
• 탐색(probe) 단계: 다른 테이블을 읽어 조인 값을 해싱하고 해시 테이블에서 매칭되는 값을 찾아 결과에 추가. 만약 메모리가 부족한 경우 디스크를 사용

성능 비교

일반적으로 해시 조인 알고리즘은 메모리의 크기에 영향을 받습니다. 각 알고리즘 별 메모리 크기에 따른 실행 시간은 아래와 같습니다.

Simple hash join의 경우 테이블의 크기가 메모리 크기보다 작을 경우 일반적인 해시와 동일한 성능을 보여주지만 그렇지 않을 경우 빈번한 overflow로 인하여 실행 시간이 급격히 높아집니다.

Grace hash join의 경우 디스크를 이용하기 때문에 메모리 크기에 따라 성능 차이가 크지 않습니다. 그러나 고정적으로 디스크 I/O가 발생합니다.

Hybrid hash join의 경우 메모리의 크기가 클수록 simple hash join과 유사한 성능을 나타내고 메모리의 크기가 작을 수록 grace hash join과 유사한 성능을 나타냅니다.

Sorted merge join과 Hash join의 비교

Sorted merge join의 특징은 다음과 같습니다.

• 조인 결과가 정렬되어있다.
• 조인 조건 연산의 종류에 관계없이 동작한다.
• 병렬 처리를 할 수 없다.

Hash join의 특징은 다음과 같습니다.

• 테이블의 데이터 순서에 영향을 받지 않는다.
• 조인 조건이 =일 때만 사용 가능하다. (비교 연산도 가능하나 해시의 장점을 누릴 수 없음)
• Partitioning을 이용하여 작은 메모리에서도 가능하며 병렬 처리를 할 수 있다.

N-way join

지금까지 두 테이블의 조인에 대한 알고리즘에 대해 살펴보았습니다. 그렇다면 세 개 이상의 테이블에 대한 조인은 어떻게 이루어질까요?

우선 세 개 이상의 테이블에 대한 조인을 N-way join으로 부릅니다. 그러나 동작 방식은 일반적인 조인과 동일합니다.

1. 두 테이블을 조인하여 중간 결과 테이블을 만든다.
2. 중간 결과 테이블과 세 번째 테이블을 조인한다.
3. N개의 테이블에 대하여 반복한다.

결과적으로 N개의 테이블에 대하여 조인을 반복하는 것이기 때문에 어떤 테이블을 먼저 조인하는 지에 따라 조인 시간이 달라질 수 있습니다. 또한, 각 조인마다 사용할 알고리즘을 선택하는 것도 성능에 영향을 줄 수 있겠죠. 이때 단계별 조인 대상 테이블과 조인 알고리즘은 쿼리 옵티마이저(query optimizer)에 의해 결정됩니다.

다만, 조인 대상 테이블의 크기가 커지면 커질수록 실행 계획을 수립하는 것이 어려워지므로 실행 계획을 확인하고 이를 최적화하는 것이 중요합니다.

마무리하며

이번 글에서는 조인 알고리즘이 어떻게 동작하는 지 알아보고 성능과 특징까지 분석하였습니다. 전체적인 흐름을 한 글에 담아내려다보니 글이 꽤나 길어졌는데요. 이번 글이 조인 알고리즘에 대한 이해를 높였길 바랍니다! 감사합니다 ☺️