[DB] Query Processing + query cost

-  DBMS 에서 query를 처리하는 과정

 

1. 입력받은 쿼리를 parser와 translator 가 relational-algebra 형태로 변환한다,(query -> relational - algebra)

 

2. optimizer가 데이터의 통계정보를 바탕으로 쿼리 실행 계획을 세운다

 

3. evaluation engine이 세워진 계획을 바탕으로 쿼리를 실행하여 결과를 반환한다.

 

- Query Optimization : 모든 평가 계획 들 중 가장 적은 금액을 선택한다. 가격은 tuple의 개수 , tuple의 사이즈 같은 정보들로 결정된다.

 

 

- Query Cost : Cpu, network도 가격에 영향을 주지만 영향을 주는 범위가 매우적다 ,  seek의 개수, seek-cost, block -read의 개수 , block-read-cost, block-written , block-write-cost로 query cost를 계산한다.

 

* Focus on

1.Seek(쿼리를 탐색할 떄 걸리는 시간,  비용)

2.transfer(쿼리데이터를 전달할 때 걸리는 시간, 비용)

 

 

- selection

튜플이 하나의 파일에 함께 저장되는 관계에 대한 선택 작업을 고려한다. A1 ~ A6까지 6개의 알고리즘이 있다

 

알고리즘 A1(선형 검색) : 각 파일 블록을 스캔하고 모든 레코드를 테스트하여 선택 조건을 충족하는지 확인합니다.

 

Linear search는 selection condition, ordering of records in the file, availability of indices에 영향을 받지 않습니다.

cost estimate : br, 만약 검색하는 attribute가 key이면 평균적으로 br/2가 됨

 

->  Cost =  ts(seek 하는데 걸리는 시간) + br(파일 안에 있는 block의 개수) * tT

     Cost =  ts + (br/2) * tT(block을 transfer하는데 걸리는 시간) (attribute가 key일 때) 

 

 

A2(primary index , equality on key, ) : relation의 key를 기준으로 생성한 index기 때문에 index 

entry 수와 tuple 수가 같다. (Primary B+ Tree Index (equality on key))

- > Cost = (hi(인덱스 높이) + 1) * (tT + tS)

 

A3 (primary index, equality on nonkey) : relation의 key가 아닌 속성을 기준으로 생성한 index이기 떄문에 같은 속성 값을 가진 tuple을 모두 봐야 한다. 따라서 T값이 클 경우 T 만큼의 tuple들을 linear search로 탐색해야한다

 

-> Cost = hi * (tT + ts) + b(match record를 갖고 있는 block의 개수) * tT + ts

 

 

A4 (secondary index, equality) : secondary index는 기본적으로 index와 tuple의 정렬 순서가 다르기 때문에 block 단위로 I/O 수행이 불가능하다. candidate key가 search key가 된다

 

-> Cost = (hi + 1) * (tT + ts)  -> secondary index가 Equality on Key일때(Primary index와 비슷하다) -> A2 Algorithm일때와 계산이 같음

    Cost = (hi + n(fetch되는 records의 개수)) * (tT + ts) -> secondary index가 Equality on Nonkey일때(굳이 사용할 필요가 없다)

 

A5 (primary index, comparison)

-> Cost = hi * (tT + ts) + b * tT + ts -> A3 Algorithm 과 계산이 같다

 

A6 (secondary index, comparison) 

-> Cost = (hi + n) * (tT  +ts) -> A4 nonkey 일때와 계산이 같다