[ch15] 중간고사 이후~

Join Operation

• join 알고리즘
  • Nested-loop join
  • Block nested-loop join
  • Indexed nested-loop join
  • Merge-join
  • Hash-join

 

• cost를 추정해서 선택
  • 예시
  • student 테이블의 레코드 수: 5000, student 테이블의 block 수: 100
  • takes 테이블의 레코드 수: 10000, takes 테이블의 block 수: 400
    
    • bf_s = 5000/100 = 50
    • bf_t = 10000/400 = 25

 

• Nested-Loop Join
  • $takes \Join_{\theta} student$
    • $takes$: outer relation
    • $student$: inner relation
  • for each tuple $t_r$ in $r$ do begin
    • for each tuple $t_s$ in $s$ do begin
      • test pair $(t_r, t_s)$ to see if they satisfy the join condition $\theta$
      • if they do, add $t_r * t_s$ to the result
    • end
  • end
  • index를 필요로 하지 않음
  • 두 table의 모든 짝을 다 탐색하기 때문에 cost가 셈
  • 최악의 경우는 각 테이블의 한 block만이 memory에 올라갈 수 있는 경우임
    • 추정 cost: $n_t * b_s + b_t$
      • t의 레코드와 맞는 짝을 읽기 위해 s의 모든 block을 읽어와야함
      • t의 모든 레코드에 대해서 위의 연산이 일어나야하기 때문에 $b_t$ 추가
  • 버퍼를 많이 쓸 수 있으면 한 번에 여러 block을 메모리에 올릴 수 있기 때문에 IO를 줄일 수 있음
    • 예를 들어, student 테이블의 모든 block과
    • takes 테이블의 block, join 연산의 결과를 쓸 block을 동시에 버퍼에 올릴 수 있으면
    • 추정 cost는 $b_s + b_t$
      • 처음에 student 테이블의 block을 다 적재시키는데 $b_s$ IO 소모
      • 그 다음 takes 테이블의 block을 하나씩 다 불러 올리는데 $b_t$ IO 소모

 

• Block Nested-Loop Join
  • inner 테이블의 모든 block이 outer 테이블의 모든 block과 짝지어지는 경우로 nested-loop join의 변종 중 하나
  • for each block $b_r$ of $r$ do begin
    • for each block $b_s$ of $s$ do begin
      • for each tuple $t_r$ in $b_r$ do begin
        • for each tuple $t_s$ in $b_s$ do begin
          • Check if $(t_r, t_s)$ satisfy the join condition
          • if they do, add $t_r * t_s$ to the result
        • end
      • end
    • end
  • end
  • 최악의 경우는 각각 테이블의 한 block만이 memory에 올라갈 수 있는 경우임
    • 추정치: $b_t * b_s + b_t$
    • takes 테이블의 한 block이 student 테이블의 모든 block을 읽어와야함
    • takes 테이블의 모든 block을 읽어와야 해서 $b_t$ 추가
  • 제일 좋은 경우는 student table의 모든 block과 takes 테이블의 한 block, 연산 결과를 쓸 block을 동시에 버퍼에 올릴 수 있는 경우임
    • 추정치: $b_s + b_r$
  • nested loop와 block nested loop 알고리즘의 cost 일반형
    • M개의 buffer가 주어져있을 때
    • 추정치 = $[b_r/(M-2)] * b_s + b_r$
      • []는 ceiling

 

• Indexed Nested-Loop Join
  • $takes \Join_{ID=ID} student$
    • 테이블에 ID의 인덱스가 존재하는 경우를 예시로 들 수 있음
  • 추정치: $b_t + n_t * c$
    • outer table인 takes의 모든 block 조회
    • c: takes의 레코드와 일치하는 짝을 찾기 위해 index를 탐색하는 비용
    • takes의 모든 레코드들에서 수행되어야하기 때문에 n_t * c
  • 예시
    • $takes \Join student$를 계산해보자
    • 여기서 outer table은 student이다
    • takes는 ID column에 대한 primary B+tree index를 가지고 있다. 각 index의 node에는 20개의 entry가 있다.
    • takes는 10000개의 레코드를 가지고, B+tree index의 높이는 4이다.
      • 실제 데이터를 찾기 위해서는 한 번의 IO가 더 필요하다.
    • student는 5000개의 레코드를 가지고 있다.
    • block nested loops join의 cost 추정치
      • $b_s * b_t + b_s$ = 100 * 400 + 100 = 40100
    • indexed nested loops join의 cost 추정치
      • 100 + 5000 * 5 = 25100

 

• Merge-Join
  • 1. join할 attribute를 양쪽 테이블에서 모두 sort
  • 2. join하기 위해 정렬된 relation을 merge
  • cost 추정치: $b_r + b_s$
    • relation이 정렬되지 않았다면, 정렬에 드는 cost도 추가
    • 정렬에 드는 비용: $b_r(2[log_{(M-1)}(b_r/M)] + 1)$, $b_s(2[log_{(M-1)}(b_s/M)] + 1)$
    • total: $b_r * 2[log_{(M-1)}(b_r/M)] + b_s * 2[log_{(M-1)}(b_s/M)] + 3* b_r + 3*b_s $
      • b_r, b_s가 한번씩 추가로 드는 이유: 정렬된 값들을 디스크에 쓰는 비용
      • 디스크에 쓰고, merge-join 수행

 

• Hash-Join
  • equi-join과 자연조인에만 해당
  • hash함수 h는 각 테이블의 레코드를 partition하는데 사용됨
  • $takes \Join_{\theta} student$
    • 양쪽 테이블의 레코드에 같은 해시함수를 적용해서 partitioning을 함
    • takes table의 i번째 partition에 있는 값은 student table의 i번째 partition에 있는 값과 join될 것
  • 알고리즘
    • 테이블 s를 해시함수 h로 파티셔닝함.
      • 한 block = 한 파티션에 대한 output buffer
    • 테이블 t를 해시함수 h로 파티셔닝함
    • 파티션 i에 대해
      • 메모리에 $s_i$를 전부 다 로드하고 join column에 대한 in-memory hash index를 생성함. 이 해시인덱스는 파티셔닝에 사용한 index랑은 다른 친구임
      • 메모리에 $r_i$를 하나씩 로드함. 윗 단계에서 만든 hash index로 레코드와 매치되는 $s_i$를 찾고 결과를 output buffer에 작성
    • s: build input / r: probe input
  • cost: $3(b_r+b_s)$
  • 예시
    • $instructor \Join teaches$
      • memory size = 20 blocks
      • $b_i$ = 100, $b_t$ = 400
      • instructor: build input
        • 5 개의 partition으로 나누고, partition의 size는 20 blocks이다
      • teaches
        • 5개의 partition으로 나누고, partition size는 80이다
    • cost: $3(b_i+b_t)$ = 1500

 

• Other Operations: Aggregation
  • group by, having 절과 같이 사용되는 경우가 많은 keyword
  • Sorting or hashing와 같이 조건에 맞는 값을 같은 그룹으로 모아야 함. Sorting이나 hashing에서 사용한 중복처리와 비슷한 방식으로 사용하면 됨
  • 최적화: Partial Aggregation
    • buffer의 크기에 따라 일부분만 group을 짓고, group에 대한 집계를 미리 진행
    • count, min, max, sum
    • avg

 

• Other Operations: Set Operations
  • Set operations: 1) sorting 후 merge-join, 2) hash-join의 변형된 형태
  • hashing을 사용한 Set operations 예시
    • 1. 같은 해시함수를 사용해서 table들을 partition
    • 2. partition i에 대해 r union s 진행
      
      • 2-1. $r_i$는 hash index 형태로 빠른 검색이 가능하도록 함
      • 2-2. $s_i$는 한 block을 가져와서 $s_i$ 내의 레코드가 $r_i$ 쪽에 있는지 check
      • 2-3. 만약 없다면, $r_i$의 hash index에 $s_i$ 내의 레코드 추가

 

• Evaluation of Expressions
  • sql 질문은 여러 연산들을 조합해서 사용함
  • 질의문은 expression tree에 저장
  • expression tree를 처리하는 방식
    • Materilization(실체화)
      • 자식노드 or 중간노드일 때 연산을 수행해 결과를 생성
      • 결과는 중간 결과일수도 있고 최종결과 일수도 있음
      • 결과를 디스크에 저장함
      • 위 과정을 반복
    • Pipelining
• Materialization
  • leaf --> root까지 연산 수행
    • leaf node: base table
    • non-leaf node: 연산
  • 한번에 한 연산 수행 후, 중간 결과 임시테이블(disk)에 저장
  • Ex)
    • select name
    • from dept, inst
    • where building = "Watson" and dept.dept_name = inst.dept_name

• Pipelining
  • expression tree의 연산들을 동시에 진행
  • 중간 결과의 일부를 얻을 때마다 저장하지 않고 부모노드 레벨로 바로바로 넘김
    • 연산을 진행할 때 레코드를 전부 얻을 때까지 기다리는 것이 아니라,
    • 생기는대로 바로바로 join연산으로 투입함
  • materialization보다 cost가 적음
    • 중간 결과를 저장하지 않아 IO수가 적기 때문
  • 모든 연산에 적용가능하지 않음
    • sort, hash-join 등에는 불가능