Query Processing 의 기본 단계(2)

---

Optimization(계속)

Query Processing의 기본 단계(1) 에서 이어지는 내용입니다.

Selection Operation

File scan 이 대표적

• linear search
  처음부터 끝까지 selection condition에 부합하는 모든 파일블록을 스캔하고 모든 레코드를 테스트한다

  • 탐색하는 테이블이 연속된 $b_{r}$ 개의 블럭으로 구성된다 가정하면,
    $b_{r}$블럭의 맨 처음으로 가는 1번의 seek 가 필요하다. Cost 값은 '$b_{r}$개의 블럭을 읽는 횟수 + seek 횟수'로 추정할 수 있다.

    $b_{r}$ block transfers + $1$seek

  • key attribute 으로 selection 연산을 하고 있다 가정하면,
    (ex) 학생테이블에서 key attribute값 인 학번 기준으로 selection 수행)
    키값은 중복된 것이 없음으로 찾으면 바로 탐색 종료가 가능.
    평균적으로 절반정도의 tuple을 살펴보았을 때 record를 찾는다 생각

    $b_{r}/2$block transfers + $1$seek

  • Linear search는

    • selection 조건을 어떻게 쓰든지,
    • 어떤 형태로 tuple들이 저장되어 있든지,
    • 색인(index) 유무

    와 관계없이 적용 가능한 것이 장점

    참고사항

  • binary search 는 데이터가 정렬된 형태를 가정하기 때문에 selection op에서 고려사항이 아닐 뿐 더러, 각 이진트리의 왼쪽/오른쪽 노드로 이동할때 발생하는 seek횟수가 오히려 늘어나는 단점이 있다. (오버헤드)

Sorting Operation

• index를 기준으로 정렬(sorting)한 relation 을 읽을 경우, 매 tuple을 읽을 때 마다 디스크 암을 인덱스 위치로 옮겨야 한다. (seek 횟수가 늘어나 비효율적, 오버헤드) 실제 tuple을 sorting 하는 것이 더 효율적이다.

• relation의 크기가 memory 에 적합한 경우 quick sort, 크기가 커서 memory에 적합하지 않은경우 external sort-merge 등이 사용된다. 아래 그림이 external sort-merge를 나타낸다.
  

Join Operation

join 수행 가능한 알고리즘들

알고리즘명	특징	pesudo code ($r\Join \,_{\theta}s$ )	비고
Nested-loop join	for-loop을 2번		$r$은 join의 outer relation, $s$는 join의 inner relation 라 불림 어떤 join condition 이라도 사용 가능 모든 조합에 대해서 확인하기 때문에 cost 비쌈
Block nested-loop join	nested loop를 블록 단위로 실행		블록 단위로 메모리에 올린 순간, 내부적으로 튜플끼리 모든 경우의 수를 따지는 것은 메모리상의 일이기 때문에, 추가비용이 들지 않는다.
Indexed nested-loop join
Merge-join
Hash-join

다음 예시로 각 join 알고리즘의 cost를 추정한다.

student - takes join 예시

• Number of records(튜플) of student(학생) : 5,000 / takes(수강내역): 10,000
• Number of blocks(블록) of student(학생) : 100 / takes(수강내역) : 400
  $=$ 한 블록당 50명의 학생, 25개의 수강내역 튜플 저장
  

Nested-loop join

Worst case 가정 : memory가 충분치 않아 딱 '한 블록' 만 메모리에 올릴 수 있다 하면 추정 코스트는,

$n_{r} * b_{s} + b_{r}$ block transfers + $n_{r}+ b_{r}$seeks

• $r$은 outer relation, $s$는 inner relation, $b=$ 블록 개수, $n=$ 튜플의 총 개수
• 만약, worst case가 아니고 둘 중 작은(smaller)테이블이 모두 메모리 안에 들어간다 하면, 그걸 inner relation으로 사용
  $=b_{r}+b_{s}$의 block transfers + $2$ seeks

따라서 student가 outer relation 이면,
$5000 * 400 + 100=2,000,100$ 의 block transfers
$5000 + 100=5100$ 의 seeks 가 발생하고

takes가 outer relation이면,
$10000 * 100 + 400=1,000,400$ 의 block transfers
$10000 + 400=10400$ 의 seeks 가 발생

Block nested-loop join

Indexed nested-loop join

Merge-join

Hash-join