[ch15] Query Processing

Basic Steps in Query Processing

• 1. parsing and translation
  • sql문을 파싱해서 관계대수식으로 바꿈
  • parser는 syntax를 체크하고, 테이블을 검증함
• 2. optimization
• 3. evaluation 
  • optimizer가 만들어준 처리전략 그대로 실행 후 결과를 얻음

 

Statistical Information for Cost Estimation

• n_r : table 속 레코드 수
• b_r: block 수
• l_r: 레코드 사이즈
• f_r: blocking factor. 블록 하나당 레코드 수
• V(A, r): r테이블의 A column 나열
• b_r = [n_r/f_r]

 

Basic Steps in Query Processing: Optimization

• 하나의 결과를 얻기 위해 여러 방법 존재
• 구체적인 처리 전략을 만들어야 함 --> 가장 비용이 낮은 것 선택
• 이 챕터에서는 다음을 다룸
  • 질의처리 전략 비용
  • 관계대수 연산 알고리즘
  • 관계대수 연산 알고리즘을 합치는 방법

---

Measures of Query Cost

• cost
  • response time: 질의가 나온 후부터 결과가 나오기 전까지의 경과시간
  • resource consumption
    • CPU, disk I/O, network communication 등 존재
• disk I/O만 고려할 것임
  • 근데 질의 결과를 disk에 저장하는 비용은 제외함
• disk cost
  • seek 수
  • read 수
  • write 수
• 계산식
  
  • b*t_타우 + S*t_s
    • t_타우: 입출력하는데 걸리는 시간
    • t_s: seek time
    • b: 블럭 수
    • S: seek 수
• b 만 고려 --> 추정
  • 이미 block이 buffer에 존재하는 경우
  • worst case: 항상 buffer에 없는 경우

 

Selection Operation

• File scan
• A1: linear search
  • 조건 p를 충족하는 record 모두 select
    • cost = b_r block transfer
  • 고유식별자에 대해 selection 하는 경우는 겹치는게 없어서 찾으면 바로 멈출 수 있음
    • cost = b_r/2 transfer

 

• index scan
  • 조건 column이 search-key index
• A2 (clustering index, equality on key): 레코드 1개 return
  • cost = h+1
• A3 (clustering index, equality on non-key): 레코드 여러 개 return
  • cost = h + b
• A4 (secondary index, equality on key/non-key)
  • 레코드 1개 return
    • cost = h + 1
  • 레코드 여러 개 return
    • cost = h +n

 

• range query
  • linear file scan
  • or
• A5 (clustering index, comparison)
  • A>=v: v를 search-key로 해서 탐색, 테이블에서 뒤에 있는 거 쭉 순차적으로 스캔
  • A<=v: 처음부터 v보다 큰 값이 나올때까지 테이블에서 scan --> index 사용 x
• A6 (non-clustering index, comparison)
  • A>=v: v를 search-key로 해서 탐색, leaf node 그 뒤에 있는 거 쭉 순차적으로 스캔
  • A<=v:  처음 leaf node부터 v보다 큰 값이 나올때까지 scan

---

External sort-merge

• run은 디스크에 있다
• pass: 전체 테이블을 처음부터 끝까지 쭉 읽어서 디스크에 쓰는 과정
• disk I/O
  • b(2*[log_{M-1}(b/M)] + 1)
  • M: buffer page 수
  • M-1: merge 수
  • b/M: 초기 run 수
• 1. 초기 run을 만들자!
  • M개의 block read
  • 내부정렬
  • Disk로 wirte
• 2. Merge
  • 각 run의 첫번째 block을 buffer로 읽음
  • buffer가 가득차면 정렬할 순서대로 disk로 내보냄
  • input buffer page로부터 내보낸 레코드 삭제
    • buffer에 올라온 레코드들이 다 비면, run의 다음 block 가져옴
  • 모든 input buffer page가 빌 때까지 반복