중첩 루프 조인

1. 개요

중첩 루프 조인은 관계형 데이터베이스에서 두 개의 관계를 조인하는 알고리즘이다. 기본 중첩 루프 조인은 두 관계의 모든 튜플 쌍을 비교하여 조인 조건을 만족하는 튜플을 찾으며, 블록 중첩 루프 조인은 메모리를 효율적으로 사용하여 성능을 개선한다. 인덱스 조인은 내부 관계에 조인 속성에 대한 인덱스가 있는 경우 사용되며, 인덱스를 활용하여 조인 조건을 만족하는 튜플을 빠르게 검색하여 시간 복잡도를 개선한다.

2. 알고리즘

두 개의 관계 $R$과 $S$는 아래와 같이 조인된다.
* 각 튜플 r in R 에 대해 반복
* 각 튜플 s in S 에 대해 반복
* 만약 r과 s가 조인 조건을 만족한다면
* yield 튜플 <r,s>

이 알고리즘은 n_r*b_s+ b_r 개의 블록 전송과 n_r+b_r 회의 검색을 발생시킨다. 여기서 b_r 과 b_s 는 관계 $R$과 $S$ 각각의 블록 개수, 그리고 n_r 은 관계 $R$의 튜플 개수를 의미한다.

이 알고리즘은 $O(|R||S|)$ 의 I/O를 시행한다. $|R|$과 $|S|$는 $R$과 $S$각각에 포함된 튜플 개수를 의미하고, 이는 조인을 통해 발생될 관계의 개수를 통해 쉽게 계산할 수 있다.

블록 중첩 루프 조인 알고리즘은 관계 $S$가 스캐닝 되는 횟수를 줄이는 것으로 추가적인 메모리 이득을 보는 중첩 반복 조인의 일반화 된 알고리즘이다. 관계 R의 큰 덩어리를 메인 메모리에 로드합니다. 각 덩어리에 대해 S를 스캔하고 현재 메모리에 있는 모든 튜플 쌍에 대해 조인 조건을 평가합니다. 이렇게 하면 S를 스캔하는 횟수가 덩어리당 한 번으로 줄어듭니다.

2.1. 기본 중첩 루프 조인

기본 중첩 루프 조인(Nested Loop Join)은 두 관계 R과 S의 모든 튜플 쌍을 비교하여 조인 조건을 만족하는 튜플을 찾는다. 이 알고리즘은 다음과 같이 동작한다.

* 각 튜플 r in R 에 대해 반복
* 각 튜플 s in S 에 대해 반복
* 만약 r과 s가 조인 조건을 만족한다면
* 튜플 <r,s> 를 출력

이 알고리즘은 n_r*b_s+ b_r 개의 블록 전송과 n_r+b_r 회의 검색을 발생시킨다. 여기서 b_r 과 b_s 는 관계 R과 S 각각의 블록 개수이고, n_r 은 관계 R의 튜플 개수를 의미한다.

이 알고리즘의 시간 복잡도는 O(|R||S|)이다. 여기서 |R|과 |S|는 R과 S 각각에 포함된 튜플 개수를 의미한다.

2.2. 블록 중첩 루프 조인

블록 중첩 루프 조인은 기본 중첩 루프 조인의 성능을 개선하기 위해 메모리를 효율적으로 사용하는 방법이다. 관계 R의 일부를 메모리에 로드하고, S를 스캔하면서 조인 조건을 검사한다.

관계 R의 큰 덩어리를 메인 메모리에 로드하고, 각 덩어리에 대해 S를 스캔하여 현재 메모리에 있는 모든 튜플 쌍에 대해 조인 조건을 평가하면 S를 스캔하는 횟수가 덩어리당 한 번으로 줄어든다.

3. 인덱스 조인 (Index Join)

내부 관계(inner relation)에 조인에 사용되는 속성에 대한 인덱스가 있다면, 단순 중첩 루프 조인(naive nest loop join) 대신 인덱스 조인을 사용할 수 있다. 인덱스 조인은 인덱스를 사용하여 조인 조건에 맞는 튜플을 빠르게 찾는다.

알고리즘 `index_join`은 다음과 같다.

* 각 튜플 *r* in *R* 에 대해
* 인덱스 조회에서 각 튜플 *s* in *S* 에 대해
* 결과값 튜플 <*r*, *s*>

이 방식을 통해 시간 복잡도를 $O(|R||S|)$에서 $O(|R|\backslash log|S|)$로 개선할 수 있다.