Nested-Loop Join 이란

이 포스팅은 Database System Concepts(Abraham) 책을 참조하여 작성하였습니다.

Nested-Loop Join 은 하나의 릴레이션을 outer 다른 하나의 릴레이션을 inner loop 로 만들어 join 을 수행하는 방식입니다.
단순히 표현하면 다음과 같습니다.

for each tuple tr in r do begin 
	for each tuple ts in s do begin
    test pair (tr , ts ) to see 
	  if they satisfy the join condition θ
    if they do, add tr ⋅ ts to the result; 
	end
end

릴레이션 r 과 s 이 있고, 각 튜플을 $t_r,t_s$ 라 합시다.
임의로 r 을 정해서, outer loop 를 만듭니다. 이 r 을 outer relation 이라고 합니다.
내부에서 loop 를 만드는 s 는 inner relation 이라고 합니다.
2중 loop 를 돌면서 join 조건을 만족시키는 튜플 쌍을 찾고,
그 쌍들을 모아서 결과로 출력합니다.

이 Join 작업은 select 의 linear scan 과 같이,
index 가 필요없고, join 조건과는 상관없이 사용할 수 있습니다.
그리고 쉽게 확장 될 수 있습니다.
natural join 과 같은 경우 반복되는 속성을 제거해야하는데,
이는 두번째 루프에서 중복만 검사해주기만 하면 됩니다.

Nested-Loop Join 은 $t_r$, 과 $t_s$ 의 2중 loop 를 사용하므로,
$n_r * n_s $ (r, s 의 튜플 수 ) 만큼의 연산을 수행합니다.
그러나 이는 모든 튜플을 메모리 상에 올릴 수 있을 때에만 가능합니다.

실제 쿼리 연산에는 Block IO 연산이 많은 비중을 차지합니다.
그래서 Block IO 가 몇번 수행되는지가 중요하고 이를 고려해야합니다.

각 r 의 레코드에 대해, s 전체를 스캔한다고 생각해 봅시다.
최악의 경우는, r 하나마다 모든 s 의 블록 $b_s$ 를 가져와야합니다.
그래서 block IO 가 $n_r * b_s + b_r$ 만큼 수행됩니다.
베스트 케이스는, 메모리가 두 릴레이션의 블록을 모두 유지할 수 있는 경우로,
$b_r+b_s$ 가 됩니다.

두 릴레이션 중 하나만 메모리에 맞는다면,
inner relation 에 해당하는 것을 메모리에 올리는 것이 효율적입니다.
만약 s 가 메모리에 들어갈 수 있을 정도로 작은 경우,

@@@