SQL 빠르게 하기 - Optimazation 이론

Query 는 비절차적 언어이며 유저가 사용하는 언어이다.

​

SQL 은 Query 를 절차적 언어인 Relation Algebra 로 번역한다.

​

이 과정에서 직역만이 이루어지는 것이 아닌 최적화도 이루어진다.

​

비용

​

Disk Access Time, CPU, Net-work Communication ...

=> CPU 계산 시간은 매우 작은 비용

=> 나 아직 서버 운영 안함

=> Disk Access Time 이 중요한 기준

​

Disk Access Time 을 Block Seek Time + Block Transfer Time 으로 극히 단순화

$Access\ Time\ Cost$Access Time Cost​

$=\ b\ \cdot \ \combi{t}_r\ +\ s\ \cdot \ \combi{t}_s\ \ \ \ \ \left(nBlock\ \cdot \ Transfer\ Time\ +\ nSeek\ \cdot Seek\ Time\right)$= b · tr​ + s · ts​     (nBlock · Transfer Time + nSeek ·Seek Time)​

​

​

1. Relation Algebra Operator 최적화

​

σ, Π 같은 operator 도 구현하는 방식에 따라 최적화 할 여지가 크다.

​

​

1. Linear Search

​

모든 operator 가 linear scan 하면서 적용 될 수 있음.

​

Transfer

=> nBlock (선형 탐색인데 그냥 블럭 갯수만큼 봐야지)

=> Select 의 계산인 경우 끝가지 갈 필요 없으니까 평균내서 nBlock / 2

nSeek => 1 (맨 첨만 보면 되니까)

​

2. Index Scan

​

인덱스로 순차검색하는 건 미친짓이고, 각 operator 에 어떻게 되는지 살펴봄

​

Index 는 where 문에 들어가는 애들이 적용되므로,

equal, compare, 그리고 이런 조건들의 교집합, 합집합, 여집합이 고려됨

​

1. primary index + equal

nTransfer => bTree Height + 1 ( bTree 때 봤음)

nSeek => bTree Height + k ( k 는 같은 키의 record 갯수, primary key 면 k = 1 이 됨)

​

2. secondary index + equal

​

nTransfer => bTree Height + k ( k 는 같은 키의 record 갯수, primary key 면 k = 1 이 됨)

nSeek => bTree Height + k ( k 는 같은 키의 record 갯수, primary key 면 k = 1 이 됨)

​

3. primary index + compare

특정 값보다 작은걸 검색하는 경우는 순차검색을 사용하고

큰걸 검색하는 경우만 인덱스 사용.

근데 이경우도 selected 되는 record 갯수가 많으면 순차랑 별로 다른게 없음.

​

nTransfer => bTree Height + 1 ( bTree 때 봤음)

nSeek => bTree Height + k ( k 는 같은 키의 record 갯수, primary key 면 k = 1 이 됨)

​

4. secondary index + compare

​

사용하면 안됨.

디스크 연속성을 사용하지 않기 때문에 그냥 순차검색이 나음.

​

5. Conjunction

​

ex) select * from A where a = 1 and b = 2 and c = 2;

​

=> 인덱스 하나 사용해서 만든 Relation 에 나머지 조건을 순차검색하면서 확인

=> 모두 인덱스가 있으면, 인덱스 별로 Relation 을 만들어서 합침

=> Composite Search Key 의 경우

=> Index 정렬은 앞에 것이 우선도가 높도록 정렬됨..

=> (dept_name, salary) 경우 dept_name 먼저.

=> Where dept_name = “A” and salary = 80000 은 매우 효과적임

=> Where dept_name = “A” and salary < 80000 은 괜찮음

=> Where dept_name < “A” and salary = 80000 은 사용할 수 없음.

​

6. Disjunction, Negation

​

안쓰는게 나음

​

​

3. Sorting

​

메모리에 데이터가 다 안들어가므로, External Merge Sort 을 사용함.

M-1 인 이유는 output buffer 때문에 하나를 빼야하기 때문.

​

$nTransfer\ =\ 2\cdot nRecord\ +\ nRecord\left(2\cdot \left\lceil \combi{\log _{M-1}\combi{\frac{nRecord}{M}}}\right\rceil \ -\ 1\right)$nTransfer = 2·nRecord + nRecord(2·⌈logM−1​nRecordM​⌉ − 1)​

$nSeek\ =2\cdot \left\lceil \combi{\combi{\frac{nRecord}{M}}}\right\rceil \ +\ \left\lceil \combi{\combi{\frac{nRecord}{nBuffer}}}\right\rceil \left(2\cdot \left\lceil \combi{\log _{M-1}\combi{\frac{nRecord}{M}}}\right\rceil \ -\ 1\right)$nSeek =2·⌈nRecordM​⌉ + ⌈nRecordnBuffer​⌉(2·⌈logM−1​nRecordM​⌉ − 1)​

4. Join

​

r ⨝ s 를 계산하는 경우.

​

r 이 outer relation, s 가 inner relation

​

theta join 이면 여러 조건을 합칠 수 있을 텐데, 아래것은 조건이 하나만 있는 경우라고 봄.

​

1. nested loop join

​

완전 루프를 도는건데, outer relation 이 바깥쪽 loop 가 되는 거임.

​

* 각 relation 마다 Block 1개만 버퍼에 남는다는 가정.

$nTransfer=\combi{b}_r\ +\ \combi{n}_r\cdot \combi{b}_s\ $nTransfer=br​ + nr​·bs​ ​

$\ \left(nBlock\ of\ r\ +\ nRecord\ of\ r\ \cdot \ nBlock\ of\ s\right)$ (nBlock of r + nRecord of r · nBlock of s)​

$nSeek=\combi{b}_r\ +\ \combi{n}_r$nSeek=br​ + nr​​

* inner relation 인 s 가 메모리에 다 들어가는 경우 달라짐.

$nTransfer=\combi{b}_r\ +\ \combi{b}_s\ $nTransfer=br​ + bs​ ​

$nSeek=2$nSeek=2​

​

2. Block Nested Loop

​

* 각 relation 마다 Block 1개만 버퍼에 남는다는 가정.

$nTransfer=\combi{b}_r\ +\ b_r\cdot \combi{b}_s\ $nTransfer=br​ + br​·bs​ ​

$nSeek=\combi{b}_r\ +\ \combi{b}_r$nSeek=br​ + br​​

* 마찬가지로 inner relation 이 메모리에 다 들어가는 경우 위랑 똑같다.

​

* 메모리에 여러 블럭이 들어가는 경우.

$nTransfer=\combi{b}_r\ +\ \left\lceil b_r/,\left(M-2\right)\right\rceil \cdot \combi{b}_s\ $nTransfer=br​ + ⌈br​/,(M−2)⌉·bs​ ​

$nSeek=\ \left\lceil b_r/,\left(M-2\right)\right\rceil \ +\ \ \left\lceil b_r/,\left(M-2\right)\right\rceil $nSeek= ⌈br​/,(M−2)⌉ +  ⌈br​/,(M−2)⌉​

M-2 는 inner relation 용 buffer 와 결과 산출용의 output buffer 때문임.

​

​

3. Indexed Nested Loop

​

s 의 데이터를 index 로 찾는 거심.

equal join 이나 natural join 외에는 쓸 수가 없음.

​

*B+Tree 경우

$nTransfer=\combi{b}_r\ +\ b_r\cdot \left(height\ +nFinded\ Data\ \right)$nTransfer=br​ + br​·(height +nFinded Data )​

$nSeek=\combi{b}_r\ +\ \left(height\ +\ 1\right)$nSeek=br​ + (height + 1)​

4. Complex Join

​

theta join 에서 조건이 복잡한 경우 => nested join ,block nested join 을 사용함.

conjunction 의 경우 주어진 조건 하나만 사용해서 순차탐색 하기도 함.

​

​

​

2. Relation Algebra Expression 최적화

​

​

같은 표현을 다 찾아서 그 중에 cost 가 가장 작은 걸 사용함

=> 공간적, 시간적 비용이 큼.

=> Sub Expression Sharing, Dynamic Programing 으로 해결하려함

​

휴리스틱 접근

=> Push Selection = select 는 가능한 빨리 하도록

=> Join Ordering = join 은 가능한 빨리 하도록 ( 뒤에 index 사용해서 이득보는 경우 안좋을 수도)

=> Selectivity 가 작은 select 를 먼저 처리함.

​

Equivalent Rule

​

어떠한 db instance 에도 같은 결과 값을 가져오는 식들의 관계

​

보통 앞에걸 뒤로 바꿈.

​

1. Conjunction Select <-> Select 연쇄

$\combi{\sigma }_{\theta 1\ \&\theta 2}\left(E\right)\ =\combi{\sigma }_{\theta 1}\left(\combi{\sigma }_{\theta 2}\left(E\right)\right)\ $σθ1 &θ2​(E) =σθ1​(σθ2​(E)) ​

2. Select 연쇄 조건 Commutative

$\ \combi{\sigma }_{\theta 2}\left(\combi{\sigma }_{\theta 1}\left(E\right)\right)\ =\combi{\sigma }_{\theta 1}\left(\combi{\sigma }_{\theta 2}\left(E\right)\right)$ σθ2​(σθ1​(E)) =σθ1​(σθ2​(E))​

3. Projection 합치기

$\ \Pi _{\theta 2}\left(\Pi _{\theta 1}\left(E\right)\right)\ =\Pi _{\theta 2}\left(E\right)\ \ \ \left(\theta 2\ is\ fittest\ \right)$ Πθ2​(Πθ1​(E)) =Πθ2​(E)   (θ2 is fittest )​

4. Selection 을 Join, Cartesian 곱에 합치기

$\ \combi{\sigma }_{\theta }\left(E_1\ \times \ E_2\right)\ =E_1\ \Join _{\theta }\ E_2$ σθ​(E1​ × E2​) =E1​ ⋈θ​ E2​​

$\ \ \combi{\sigma }_{\theta 1}\left(E_1\ \Join _{\theta 2}\ E_2\right)\ =E_1\ \Join _{\theta 1\ \&\theta 2}\ E_2$  σθ1​(E1​ ⋈θ2​ E2​) =E1​ ⋈θ1 &θ2​ E2​​

5. Theta Join Commutative

$E_2\ \Join _{\theta }\ E_1=E_1\ \Join _{\theta }\ E_2$E2​ ⋈θ​ E1​=E1​ ⋈θ​ E2​​

$\ $ ​

6. Natural Join 결합법칙

$\left(E_1\ \Join \ E_2\ \right)\Join \ E_3=E_1\ \Join \ \left(E_2\ \Join \ E_3\right)$(E1​ ⋈ E2​ )⋈ E3​=E1​ ⋈ (E2​ ⋈ E3​)​

$\left(E_1\ \Join _{\theta 1}\ E_2\ \right)\Join _{\theta 2\ \&\ \theta 3}\ E_3=E_1\ \Join _{\theta 1\ \&\ \theta 2}\ \left(E_2\ \Join _{\theta 3}\ E_3\right)$(E1​ ⋈θ1​ E2​ )⋈θ2 & θ3​ E3​=E1​ ⋈θ1 & θ2​ (E2​ ⋈θ3​ E3​)​

$\ $ ​

수식이 좀 복잡한데, 메시지는 어렵지 않다.

원래 theta join 시에는 where 문과 똑같은 일을 하는 자기 자신의 relation 만 거르는 조건이 있다.

그런 조건들은 순서를 바꿔도 상관 없다는 것이다.

​

7. Selection Distribute

$\combi{\sigma }_{\theta }\left(E_1\ \Join \ E_2\ \right)=\left(\combi{\sigma }_{\theta }\left(E_1\right)\right)\ \Join \ E_2\ $σθ​(E1​ ⋈ E2​ )=(σθ​(E1​)) ⋈ E2​ ​

$\combi{\sigma }_{\theta 1\&\theta 2}\left(E_1\ \Join \ E_2\ \right)=\left(\combi{\sigma }_{\theta 1}\left(E_1\right)\right)\ \Join \ \left(\combi{\sigma }_{\theta 2}\left(E_2\right)\right)\ $σθ1&θ2​(E1​ ⋈ E2​ )=(σθ1​(E1​)) ⋈ (σθ2​(E2​)) ​

$\ $ ​

join 시에는 selection 조건을 relation 중에 아무거나 하나 잡고 돌려도 상관 없나는 이야기다.

​

​

8. Projection Distribute

$\combi{\Pi }_{L1\cup L2}\left(E_1\ \Join \ E_2\ \right)=\left(\combi{\Pi }_{L1}\left(E_1\right)\right)\ \Join \ \left(\combi{\Pi }_{L2}\left(E_2\right)\right)$ΠL1∪L2​(E1​ ⋈ E2​ )=(ΠL1​(E1​)) ⋈ (ΠL2​(E2​))​

$\combi{\Pi }_{L1\cup L2}\left(E_1\ \Join \ E_2\ \right)=\combi{\Pi }_{L1\cup L2}\left(\combi{\Pi }_{L1\cup L3}\left(E_1\right)\right)\ \Join _{\theta }\ \left(\combi{\Pi }_{L2\cup L3}\left(E_2\right)\right)$ΠL1∪L2​(E1​ ⋈ E2​ )=ΠL1∪L2​(ΠL1∪L3​(E1​)) ⋈θ​ (ΠL2∪L3​(E2​))​

$\ $ ​

join 시에는 projection 도 맞는 relation 에 하나 잡고 돌려도 상관 없다는 이야기다.

아래줄은 복잡해 보이지만, theta join 시 필요한 조건이 있다면 그걸 남겨놓고, 그때 사용한 조건을 마지막에 쳐낸다는 이야기이다.

​

9. Selection and 교집합, 차집합

$\combi{\sigma }_{\theta }\left(E_1-\ E_2\ \right)=\left(\combi{\sigma }_{\theta }\left(E_1\right)\right)-\left(\combi{\sigma }_{\theta }\left(E_2\right)\right)$σθ​(E1​− E2​ )=(σθ​(E1​))−(σθ​(E2​))​

$$​

$\ \combi{\sigma }_{\theta }\left(E_1-\ E_2\ \right)=\left(\combi{\sigma }_{\theta }\left(E_1\right)\right)-E_2$ σθ​(E1​− E2​ )=(σθ​(E1​))−E2​​

교집합 차집합 시 하나만 select 해도 상관없다. 둘대 해도 됨.

​

10. Projection and Union

$\combi{\Pi }_L\left(E_1\cup \ E_2\ \right)=\left(\combi{\Pi }_L\left(E_1\right)\right)\cup \left(\combi{\Pi }_L\left(E_2\right)\right)$ΠL​(E1​∪ E2​ )=(ΠL​(E1​))∪(ΠL​(E2​))​

$\ $ ​

합집합 시, Projection 하고 해도 상관 없다.