28. 15장 : A TYPICAL RELATIONAL QUERY OPTIMIZER (3)

query optimization의 전체 동작이 어떻게 이루어지는지 살펴본다

1. plan space

2. cost extimation

3. search algorithm

---

Plan Space

Query를 블락단위로 쪼갠다 (중첩쿼리면, sub쿼리를 빼서 2개의 블럭으로 만드는등등)

그리고 각 연산자들의 제한사항을 확인할 필요가 있다.

-> 데이터들은 물리적으로 "아무것도 아님" "sort order" "hash grouping" 상태를 가진다.

• 결과로 나오는 테이블이 특정 형태를 띄는것

  • Index scan : 결과가 sort

  • Sort : 결과가 sort

  • Hash : 결과가 hash grouping

• input으로 특정 형태의 테이블이 필요한것

  • Sort Merge Join : input으로 sort된 데이터가 들어오는걸 가정함

• input으로 들어온 데이터의 형태를 유지함

  • Sort Merge Join : sort 데이터를 받고, sort 결과물을 냄

  • Nest Loop Join ; left input이 정렬되어 있으면, 결과물도 정렬되어있음

  
  

  아무튼 이런저런 이렇게 바꿔도 결과는 동일함!! 생각을 가지고 앞에서 똑같은 sql에서 여러개의 query plan을 만들어냈다.

  
  

  Cost Estimation

  단순히 연산에 드는 cost만 고려하는게 아니라, 결과물의 사이즈 도 같이 고려해야한다.

  (각 연산의 결과로 나오는 테이블의 튜플 하나하나에 cpu가 드는데,,, 옛날에는 cpu도 좀 느렸다는듯)

시스템 카탈로그에는 이런 정보들이 담겨있다

Statistic	Meaning
NTuples	# of tuples in a table (cardinality, 원소개수)
NPages	# of disk pages in a table
Low/High	min/max value in a column
Nkeys	# of distinct values in a column
IHeight	the height of an index
INPages	# of disk pages in an index

아무튼 이 정보들 가지고,,, 결과물의 사이즈를 계산해볼 수 있다.

Selectivity

• Selectivity(Reduction Factor, RF) = |output| / |input|

selectivity를 계산해서 사이즈가 얼마나 효율적인지를 판단한다.

selective가 높다는것은, 숫자가 작다는것!! (헷갈리지말것)

요 selectivity를 이용해서 결과물의 크기를 알 수 있다 (RF * 최대 튜플 개수)

select 에서 사용하는 조건에 따라,,,,

조건	selectivity
c = v	1 / (c의 index key 개수)
c1 = c2	1 / MAX(c1의 key개수, c2의 key개수)
c < v	(v - min(c)) / (max(c) - min(c) + 1)
c > v	(max(c) - v) / (mac(c) - min(c) + 1)
c <= v	(v - min(c)) / (max(c) - min(c) + 1) + 1 / |c|
c >= v	(max(c) - v) / (mac(c) - min(c) + 1) + 1 / |c|
c <= v (float)	(v - min(c)) / (max(c) - min(c))
c >= v (float)	(max(c) - v) / (mac(c) - min(c))
p1 AND p2	S(p1) * S(p2)
p1 OR p2	S(p1) + S(p2) - S(p1 AND p2)
NOT p	1 - S(p)

S(어쩌구) == selectivity(어쩌구)
c에 대한 조건이 없으면 1/10으로 고정한다.

Search Algorithm

최적의 cost를 가지는 쿼리플랜은 어떻게 찾을까? -> dp를 이용한다.

 SELECT S.sid, COUNT(*) AS number
     FROM Sailors S, Reserves R, Boats B
 WHERE S.sid = R.sid
   AND R.bid = B.bid
   AND B.color = “red”
 GROUP BY S.sid

• Sailors:
  Hash, B+ on sid
• Reserves:
  Clustered B+ tree on bid
  B+ on sid
• Boats
  B+ on color

Pass 1

각각의 FROM에 있는 테이블을 SCAN해오는 알고리즘 중, 조건에 는 알고리즘 몇개를 미리 생각해본다.

• Hash, Clustered가 있으니까 sailor랑 reserves는 그냥 파일스캔을 해오고

• B+트리가 있는 애들은 B+트리를 이용해서 찾는 알고리즘을 생각해본다

Pass 2

위에서 생각한 테이블들을 JOIN해본다.

이 때 겹치는 key가 없어서 join이 의미 없는애들 (그니까 equi join이 힘든애들)은 무시한다.

이렇게 JOIN한 경우으의수를 정리해본다!

Pass 3, 4, ...

pass 2에서 나온 계획들에, 연산자를 하나씩 추가하면서 cost를 계산한다.

마지막에는 cost가 가장 싼 애를 고르면됨!