블록 중첩 루프

블록 중첩 루프(BNL, Block nested loop) 이란 관계형 데이터베이스에서 두 개의 관계를 조인하는데 쓰이는 알고리즘이다.

이 알고리즘은 각각 outer와 inner로 표시할 수 있는 두 개의 관계 $R$과 $S$를 조인하는데 사용하는 중첩 루프 조인의 심플한 종류 중 하나이다. 관계의 크기는 보통 $|R|<|S|$로 제안된다. 전통적인 중첩 루프 조인에서는, $S$는 $R$의 모든 튜플에 대해 최소 한 번씩 스캔된다. 만약 조인을 하기 위해 검증해야할 $R$ 튜플의 개수가 많고, 특별히 조인 키를 위해 사용할 인덱스가 $S$에 존재하지 않는다면, 이 작업은 굉장히 무거울 것이다.

블록 중첩 루프 조인 알고리즘은 기존의 중첩 루프 조인을 개선해서, $S$의 튜플들을 $R$ 튜플의 그룹에 대해 한 번씩 스캔되도록 제한할 수 있다. 예시를 들자면, 하나의 다른 블록 중첩 루프 조인이 일어날 때 모든 $R$ 튜플들을 페이징해서 메모리로 읽어들이고(조인을 위해 페이징한 $R$ 튜플들을 조인 버퍼라고 부르기도 한다), 이를 해시 테이블에 올려놓는다. 이건 그러면 $S$를 스캔하면서, 현재 페이지에 올라간 $R$튜플에 매치되는 $S$ 튜플이 있는 지를 해시 테이블에서 조사한다. 이렇게 하는 것으로 원래 중첩 루프 조인을 시행할 때 필요한 $S$스캔 횟수를 줄여준다.

좀 더 진취적인 블록 중첩 루프 조인 알고리즘은 $R$의 페이지를 메모리가 가능한 만큼 최대한 맞게 메모리로 올리고, 메모리에 올라온 모든 튜플들을 해시 테이블에 넣은 뒤에, $S$를 스캔하는 행동을 반복한다. 이렇게 하는 것으로 $S$를 스캔하는 횟수를 더욱 줄일 수 있다. 사실, 이 알고리즘의 핵심 내용은 클래식 해시 조인 알고리즘의 특수한 케이스라고 볼 수 있다($R$의 튜플 $r$을 메모리 내의 해시 테이블에 추가하고, 메모리 크기 한계까지 올리는 측면이 동일하다).

블록 중첩 루프는 $O(P_{r}P_{s}/M)$회의 I/O 동작을 시행한다. 여기서 $M$은 내장 메모리에 생성할 수 있는 페이지의 개수이고, $P_{r}$과 $P_{s}$는 $R$과 $S$ 각각의 페이지 사이즈이다. 만약 $R$의 크기가 가용한 내장 메모리의 크기보다 작다면, 블록 중첩 루프는 $O(P_{r}+P_{s})$ 회의 I/O 동작이 시행되는 것을 눈치챌 수 있을 것이다.