중첩 루프 조인

중첩 반복 조인은 N 개의 집합을 N 개의 중첩된 반복문을 사용해 조인하는 알고리즘으로, 데이터베이스 관리에 중요하게 사용된다.^[1]

알고리즘

두 개의 관계 $R$ 과 $S$ 는 아래와 같이 조인된다.

For each tuple r in R do
  For each tuple s in S do
    If r and s satisfy the join condition
      Then output the tuple <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$ 가 스캐닝 되는 횟수를 줄이는 것으로 추가적인 메모리 이득을 보는 중첩 반복 조인의 일반화 된 알고리즘이다.