[Query Processing]Join Operation

nested-loop join

compute r teath-join s

 

index가 존재하지 않을 때 block을 각각 가져와서 일치하는 tuple들을 찾아낸다.

 

최악의 경우

메모리에 블락이 2개 가능하다고 하자.

r 튜플 하나를 기준으로 s의 테이블과 비교하기 때문에 r테이블은 br이면 된다. s는 r의 튜플마다 다 가져오므로 nr * bs이다. (ns= n의 튜플 개수, bs = s의 블락 개수)

transfer time: br + nr*bs 

 

block이 다른 실린더에 있다고 가정.

r 테이블에는 br개의 block이 있으므로 br번. 

seek time: br + nr*bs 

 

최상의 경우

두 개의 테이블을 메인 메모리에 다 올릴 수 있는 경우 

transfer : br + bs

 

특수한 경우

inner table을 메모리에 올릴 수 있는 경우

transfer: br + bs

 

running example

block transfer

nr*bs + br = 5000*400 + 100

seek 

2*br = 2* 100

 

block nested-loop join

r join s할 때 r의 한 튜플 씩 s를 join하는 것이 아니라 r의 한 블락씩 s를 join하는 방식이다. 이렇게 하면 transfer 비용이 br*bs + br로 바뀐다.

 

memory에서 사용할 수 있는 블락의 수를 M인 경우

(M-2)    (1)     (1)

M-2는 outer relation을 위해 사용.

(1) s를 위해 사용

(1) output을 위해 사용

 

indexed neted loop join

index가 존재하는 경우 r join s를 하면 s를 찾을 때 b+ tree index같은 것을 사용한다.이 때 equi-join이나 natural join만 가능하다.

r의 블락 하나르 읽어와서 각각의 튜플에 대해서 B+ tree을 이용하여 join 조건에 맞는 튜플을 검색한다. 

cost: br * (Tt + Ts)  + nr * c

 

100은 블락에 대한 io 횟수

5000* 5 에서 5는 b+ tree를 탐색하여 leaf까지 간 후 record를 찾아가는 비용

 

Merge join

join attribute에 대해서 정렬이 되있는 경우, 이를 이용하는 방식이다.

 

a - a

b - c

d - c

d - d

여기서 attribute 값이 중복되는 경우도 고려해서 진행해야 한다.

 

equi-join and natural join만 사용할 수 있다.

정렬이 안되어 있다면 정렬하는 비용도 포함된다.

 

hybrid merge join

r : sorted

s : B+ tree index 

B+ tree index도 leaf에 대해서 sort되어 있으므로 이를 이용한다.