23. 14장 : EVALUATING RELATIONAL OPERATORS (1) - Nested Loops Join

14.4에서 소개하는 Join Operation에 대해 배운다

join을 어떻게 구현해야 I/O를 줄일 수 있을지에 대해 알아보자!!

---

사용할 예제 테이블 정리

• [릴레이션이름] : 해당 릴레이션 (테이블)을 저장하는데 필요한 페이지 수

• $P_{릴레이션이름}$ : 해당 릴레이션에서, 하나의 페이지에 들어가는 레코드 개수

• |릴레이션이름| : 해당 릴레이션에 있는 레코드 개수

  $[릴레이션이름] \cdot P_{릴레이션이름}$ 로 계산할 수 있다

Reserves : R

(sid: int, bid: int, day: date, rname: string)

• [R] = 1000

• $P_{R}$ = 100

• |R| = 100000

Sailors : S

(sid: int, sname: string, rating: int, age: real)

• [R] = 500

• $P_{R}$ = 80

• |R| = 40000

  
  

---

Simple Nested Loops Join

단순히 반복문으로 처리하기

방법1 : R이 outer 반복으로

foreach record r in R do
    foreach record s in S do
        <ri, sj> buffer로 보내기

출력비용은 고려하지 않고, 디스크에서 읽어오는것만 고려한다.

각 R에 대해 (즉 R 레코드 하나), S를 가져와서 합치니까 -> |R| * [S] (s는 페이지단위로 읽어온다)

맨 처음 R을 메모리로 올리기 위해 [R]의 I/O가 또 필요하다

결론 : [R] + |R| * [S] = 1000 + 100000 * 500 = 50,001,000

방법2 : S를 outer로

foreach record s in S do
    foreach record r in R do
        <ri, sj> buffer로 보내기

이번에는 각 S레코드 하나당, R페이지 하나씩 가져오니까 -> |S| * [R]로 바뀐다

결론 : [S] + |S| * [R] = 500 + 40000 * 1000 = 40,000,500

반복문 순서를 바꾸는것만으로도 I/O횟수를 약간 줄일 수 있다!

방법3 : 페이지단위로 가져와서 처리하자!

for each rpage in R: 
    for each spage in S: 
        for each rtuple in rpage: 
            for each stuple in spage: 
                if join_condition(rtuple, stuple): 
                    조건에 맞으면 버퍼로 올리기

4중 반복으로 구현한다.

밖에 있는 두개의 루프에서 페이지를 가져온다.

그리고 안쪽에 있는 두개의 루프에서 각 페이지에 대해 join을 해준다.

=> I/O 자체는 페이지를 가져오는 외부루프에서만 필요함!!

즉 [R] * [S] 로 계산된다

결론 : [R] + [R] * [S] = 501,000

방법4 : Block단위로 가져오자!

강의에서는, 페이지 == 블럭 이라고 가정했다. 대충 "청크단위"로 생각하면 될것같다

S 한페이지랑 join할 때, R 한페이지씩 가져와서 하는게 아니라 한 청크씩 가져와서 하자는것!

for each rchunk of B-2 pages of R: 
    for each spage of S: 
        for all matching tuples in spage and rchunk:
             버퍼로 올리기

메모리 용량이 B페이지라고 가정하면, 하나의 청크를 B-2개의 페이지로 가정한다.

(S 페이지 한개, 결과를 저장할 페이지 총 2개의 페이지가 여유공간으로 필요함)

메모리에 전부다 안올리는 이유

테이블 전체 크기가 메모리 크기보다 작아서 이런 삽질을 하고있는거여서

그냥 전부다 메모리로 올려서 처리한다,,, 는 생각 자체가 의미 없는거당!

요점은 메모리를 최대한 활용해서 I/O 횟수를 줄이는것

이렇게 되면, 특정 청크에 S가 한페이지씩 로드된다.

즉 ([R] / (B-2)) * [S] 로 정리할 수 있다.

결론 : [R] + ([R] / (B-2)) * [S] = 1000 + (1000 / (B-2)) * 500

B가 102라고 생각하면, 1000 + 5000 = 6000 이 된다.

Index Nested Loops Join

테이블 중 하나에 index가 있는경우 (즉 앞에서 배운 B+트리든 뭐든, index기준으로 정리되어 있는 테이블인 경우)

인덱스 중첩조인을사용하면 된다.

 foreach tuple r in R do
     foreach tuple s in S where ri == sj do
         버퍼에 올리기

여기서 중요한점은 s in S where ri == sj 부분이다.

S에서 튜플을 가져오기전에 (그러니까 I/O가 생기기 전에?) 먼저 index로 조건에 맞는지 확인한다.

즉 조건에 안맞는건 그냥 안가져와버린다는것 (== I/O가 없다는것)

Cost

비용계산은,,, 복잡하다!! 매번 index가 맞는지 확인하는 과정이 추가되는데, 여기에 드는 cost도 고려해야하기 때문이다.

근데 인덱스 저장 방식에 따라 cost가 달라진다.

참고 : 15. 10장 : TREE-STRUCTURED INDEXING (2)

인덱스에서 데이터를 표현하기 위한 방법으로는

1. value

2. reference : clustered

3. reference : unclustered

3가지가 있고,,, 각각 고려해줘야한다.

1. value : index tree를 탐색하는 cost만 고려하면됨

2. clustered : index tree를 탐색하고 + 해당 주소의 힙파일에서 value를 찾음 (튜플 페이지당 1 I/O)

   특정 R튜플에 대해, 매칭되는 튜플마다가 아니라,

   매칭테이블 개수가 |R|에 곱해준다 (unclustered보다 간편)

3. unclusered : inex tree를 탐색하고 + 해당 주소의 힙파일에서 value찾기 (튜플당 1 I/O)

   반대로 매칭튜플 개수가 그대로 |R|에 곱해진다.

다만 sid로 join을 했다고 가정하면, R에 대해 S 릴레이션 전체에 매칭되는 sid는 한개만 존재한다.

즉, 이런 예제에서는 clustered랑 unclustered랑 cost가 같다,

• [R] + |R| * (Search + 매칭개수)

  • clustered : [R] + |R| * (Search + # 매칭 페이지)

    예제에서는,,,, 1000 + 100000 * (3 + 1) = 401,000

  • clustered : [R] + |R| * (Search + # 매칭 튜플)

    예제에서는,,,, 1000 + 100000 * (3 + 1) = 401,000

• 차이가 있는 예제를 생각하자면,,,,

  join조건으로 매칭되는 튜플이 총 10개가 있다고 생각해보자. (한 페이지에 튜플 10개가 들어간다고 생각)

  • unclustered : 각 튜플마다 따로따로 튜플에 접근해야 하므로 10번의 I/O코스트

  • clustered : 매칭된것끼리 모여있으니까, 한 페이지만 접근하면 되므로 1번의 I/O코스트

  이런 차이가 있다!