블록 중첩 루프

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

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

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

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

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

각주 

데이터베이스 알고리즘