[DB] Query Evaluation

기초DB에서 다룬 관계대수 연산자를 사용한 query들에 대해 query evaluation을 통해 cost를 최소화 하는 qeury를 작성하고자 하는 것. "쿼리 최적화"(Query Optimization)

• 조인과 관련된 Query Evalutation은 아래 링크를 참고
  -Join query evaluation

• 기본 관계 대수 연산자

  셀렉트
  프로젝트
  카티션 프로덕트
  합집합
  교집합

• 쿼리 최적화는 다음 두 가지 이슈가 존재

1. 가장 저렴한 plan을 선택한다. (I/O cost가 가장 적은 plan)

2. 그렇다면 plan의 cost는 어떻게 추정하는가?

   => 기본적으로 candidate plan을 먼저 추림

Best plan을 찾는 것보다 worst plan을 피하려고 노력해야함.

1. Statics and Catalogs

: 릴레이션과 인덱스 정보가 필요하며, 이에 statics와 catalog를 사용

이러한 정보는 데이터베이스 시스템에서 쿼리 실행 계획을 최적화하고 쿼리 성능을 향상시키는 데 도움이 됩니다.

1) Catalogs

: Catalog는 인덱스와 릴레이션에 관한 정보를 가지고 있으며 주기적으로 업데이트 된다.

왜 즉시 바꾸지 않는가?
: 비싸

• 각 릴레이션 튜플 수 (NTuples) 및 페이지 수 (NPages).
• 각 인덱스의 고유한 키 값 수 (NKeys) 및 페이지 수 (NPages).
• 각 트리 인덱스의 인덱스 높이, Low/High key values

2. Access Path

: Data 접근 경로. 즉 쿼리가 요청한 data에 어떻게 접근하는가?

• 1) File Scan
• 2) index
  ① tree index
  e.g. <a,b,c> 에 대해 tree index를 생성
  => SELECT a=5 and b=3 : 가능
  => SELECT a=5 b>6 : 가능
  => b=3 : 불가
  ② hash index

(day<8/9/94 AND rname='Paul') OR bid=5 OR sid=3

셀렉트 조건은 CNF로 먼저 변환된다.
CNF(conjunctive normal form)
논리곱 정규형
: 논리합 절들이 논리곱으로 연결되어 있는 논리식. 즉 논리합으로 이뤄진 절들이 곱해진다.

CNF형식으로 변환된 쿼리는 다음과 같다.

(day<8/9/94 OR bid=5 OR sid=3) AND (rname='Paul' or bid=5 or sid=3)

위 쿼리는 앞의 논리합으로 이뤄진 절을 만족하지 않는 튜플들에 대해 뒤의 절을 검사할 필요가 없으므로 더 빠른 연산이 가능하다.

3. Selections

1) find the most selective access path

= an index or file scan that we estimate will require the fewest page I/Os

e.g rate : 1~10

① $σ_{rate>5}$(R)
② $σ_{rate=5}$(R)

위 예시에서 ②연산이 더 적은 I/O를 수행하게 된다.

①의 경우 5개의 튜플을 읽어와야 하는 반면 ②는 한 개의 튜플만 반환하기 떄문.

2) clustering

: clustering 된 index에 대해 검색 하는 것이 unclusterd index보다 더 빠르다.

4. Projection

: 중복 제거(DISTINCT)또한 expensive하다.
다음의 접근에서 중복 제거 비용이 어떻게 발생하는지 확인해보자.

sid	bid	name
1	2	kim
2	3	Lee
1	2	Kim
3	1	Park
2	3	Lee

SELECT DISTINCT R.sid, R.bid FROM Reserves R

1) Sorting Approach

• sid와 bid에 대해 정렬하여 중복 제거
  => 2 x N X # of pass

  pass : 입력 데이터를 읽어오는 과정
  한번에 모든 입력데이터를 읽을 수 없기에 여러 번의 pass에 걸쳐 입력 데이터를 읽어오게 됨.

2) Hashing Approach

3) B+ Tree

5. Join

foreach tuple r in R do
	foreach tuple s in S where ri==sj do
    	add <r,s> to result

R : 10000 tuples, 100 Pages (100 tuples/pages)
S : 4000 tuples, 50 pages(80 tuples/pages)

1) Nested Loop join

R-① 튜플과 S의 4000개의 튜플과 비교
=> 50 I/Os
R-② 튜플과 S의 4000개의 튜플과 비교
=> 50 I/Os

cost = 50 I/O per tuple X 10000pages = 500,000 I/O

2) page orient nested loop

R-① 페이지의 100개의 tuple을 모두 비교하기 전까지는 disk로 내보내지 않음
=> R의 page당 50 I/O

cost = 50 I/O per page x 100pages = 5000 I/O

3) block orient nested loop

• 10개의 page를 block으로 가정
• block 내 10개 page가 모두 비교 되기 전까지 dist로 내보내지 않음

=> R의 block(10page)당 50 I/O

cost = 50 I/O per block x 10 blocks = 500 I/O

4) Sort and Merge join

: 조인 속성으로 R, S를 정렬한 후 병합