블록 중첩 루프 문서 원본 보기

{{위키데이터 속성 추적}}
'''블록 중첩 루프'''('''BNL''', Block nested loop) 이란 [[관계형 데이터베이스]]에서 두 개의 관계를 [[Join_(SQL)|조인]]하는데 쓰이는 [[알고리즘]]이다.<ref name=mysql>{{웹 인용|title=8.2.1.14 Block Nested-Loop and Batched Key Access Joins|url=http://dev.mysql.com/doc/refman/5.6/en/bnl-bka-optimization.html|website=MySQL 5.6 Reference Manual|publisher=Oracle Corporation|accessdate=2 August 2015}}</ref>

이 알고리즘<ref name=MariaDB>{{웹 인용|title=Block Nested Loop Join|url=https://mariadb.com/kb/en/mariadb/block-based-join-algorithms/|website=MariaDB|publisher=MariaDB Corporation Ab|accessdate=2 August 2015}}</ref>은 각각 outer와 inner로 표시할 수 있는 두 개의 관계 <math>R</math>과 <math>S</math>를 조인하는데 사용하는 [[중첩 루프 조인]]의 심플한 종류 중 하나이다. 관계의 크기는 보통 <math>|R| < |S|</math>로 제안된다. 전통적인 [[중첩 루프 조인]]에서는, <math>S</math>는 <math>R</math>의 모든 튜플에 대해 최소 한 번씩 스캔된다. 만약 조인을 하기 위해 검증해야할 <math>R</math> 튜플의 개수가 많고, 특별히  조인 키를 위해 사용할 인덱스가 <math>S</math>에 존재하지 않는다면, 이 작업은 굉장히 무거울 것이다.

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

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

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

== 각주 ==
{{각주}}

{{전거 통제}}
{{기본정렬:블록 중첩 루프}}
[[분류:데이터베이스 알고리즘]]