[db] query optimization

https://codenme.tistory.com/22

데이터베이스 참고자료

위의 자료를 기반으로 작성한 내용입니다. 페이지 별로 관련 내용을 정리한 것이니, 해당 자료와 함께 보는 것을 권장 드립니다.

 

(update at 23-08-09)

Query Optimization

실제로 특정 데이터를 얻기 위한 요청을 처리할 때 해당 요청에 부합하는 쿼리는 여러가지가 있다. 이들 중, 최적의 query 찾아서 연산 시간을 줄이는 것을 query optimization 이라고 한다. 

동일한 결과를 내는 Relation, operation 조합들 중, 해당 상황에서 최적의 대안 쿼리를 찾아서 수행하는 것으로 이를 줄일 수 있다.  한번 특정 상황에서 어떤 것이 좋다고 검증이 되었다면, 계속 해당 상황에서 해당 대안 쿼리를 사용하는 것이 좋은 해결책일 수 있다.

하지만 가능한 모든 조합을 조사해서 최적의 쿼리 조사하는 건 쉽지 않다(사용자가 느끼는 response time 나빠짐) . 

[ 쿼리 최적화로 걸리는 시간 > 최적화로 줄어든 시간 ]  이라면 쿼리 최적화는 하지 않느니만 못하다. 

 
왼쪽 과 오른쪽 쿼리는 다른 방식을 사용하지만, 동일한 결과 도출한다.
하지만 오른쪽은 왼쪽에 비해 수행시간을 확실하게 줄일 수 있다.  (select, projection 등을 최대한 빨리 수행했기에, tuple, attribute 수를 미리 줄이고 전달할 수 있다.)

Evaluation plan

위와 같이, 어떠한 요청에 대한 쿼리 수행 플랜을 다이어그램으로 만든 것을 
Evaluation plan이라고 한다. 각 연산에 사용된 알고리즘도 표현해야 한다. ( hash join, sort to remove duplicates 등)


우리는 Evaluation plan을 통해 알고리즘, Cost(input, output data size) 에 영향을 고려하여 가장 Cost가 적은 걸 찾을 수 있다. 실제 수행에서는, Original plan 과 동일한 plan 들을 찾고, 그들의 Cost를 estimate하여 Cost가 가장 낮은plan을 수행하는 것으로 최적화가 진행된다. 


Cost 예측

기본적으로 data size로 한다. 해당 relation에 대해 DB가 관리하는 정보 (쿼리 관리 통계 정보 tuple의 개수 등)들을 통해 더욱 정확한 예측 가능해진다. (하지만, 복잡한건 여전히 계산해서 구해야한다.)

Relational Expressions 변경으로 최적화하기.

Equivalent
2개의 expression이 모든 legal database instance에 대해 같은 tuple set을 생성할 시, 두 expression이
Equivalent 하다고 한다. ( 튜플의 순서는 상관없다, integrity constraint( ref, key const,etc…) 등 고려x ) 

RA(Relation Algebra)에는, 어떠한 plan과 Equivalet하면서도, 더 나은 코스트를 가지는 plan으로 변경할 수 있는 'Equivlalence Rule 이란 것이 존재한다.  아래와 같은 플랜들이 있다.

• ..........
  2: select 순서 바꿔서 더 많이 줄이는 걸 먼저
  4: 밖의 select를 세타 조인 안에 넣어서 미리 줄이기.
  5: nat, seta join은 순서 변경 가능
• 6. natural join은 join 순서를 바꿔도 된다. ( A Nat Join B) Nat  Join C ==  A Nat  Join B ( Nat  Join C )
  7: select 조건이 특정 relation에만 적용시, 해당 relation에 미리 적용시켜 튜플 수 감소
• .................
  
  

Equivalent Rule 을 사용 하면, 아래의 예시들과 같이, original plan에서 최적화를 완료한 equivalent한 plan 을 찾을 수 있다.

  Rule 5

Inner, outer table을 바꿔도 결과는 동일하다. 

Rule 6

E1,E2 join 후 E3 join 하는 것과  E2,E3 join 후 E1 join 하는 것은 동일하다. 

Rule 7

만약 E1에만 존제하는  attribute 만 select한다면, join 하기전에 E1에서 해당 attribute만 추출하여 테이블 크기를 줄일 수 있다.

아래는 실제 RA 가 어떻게 위와 같은 Equivalent Rule을 통해 최적화 되는 지 보여주는 예시이다. 참고하자.

Equivalent Rule을 통한 쿼리 최적화.

 
2번째 쿼리는 1번째 쿼리와 동일한 결과를 반환하지만, selection을 일찍 수행하여 테이블을 줄인 뒤 전달할 수 있는 가능성을 제공한다. 

 

이와 같은 Rule 외에도, 기본적으로 수행하면 더 좋은 성능을 발휘하는 '기본 최적화 전략' 이 존재한다.

Projection

우리는 최대한 빨리 Projection을 수행하는 equivale plan을 사용해서 cost 줄일  수 있다. 
최종적으로 필요한 데이터 가 name, title ( select할 데이터) 일시, 
Name, title 외의 데이터 중 쓸모 없는 attribute는 달고 다닐 필요 없다. 만약 join 에서 F.K로 쓰이는 경우와 같이, 특정 attribute 가 필요한 경우를 제외하면, 최대한 빨리 Projectoin으로 제거하자.

Join 순서 변경

join 순서를 바꾸어 크기가 작은 테이블 부터 join하는 것으로도 쿼리 최적화가 가능하다.

크기가 큰 테이블 부터 join한 다면, 해당 테이블이 계속해서 상위에 사용 되며 비효율이 발생한다.

따라서 최대한 적은 데이터가 남는 join을 먼저 수행하는 것이 좋다. 이에 더해서, join 전에 selction, projection을 통해 불필요한 데이터는 미리 사이즈를 줄여 놓는 것 역시 많은 도움이 된다.

 

 

실제 쿼리 Optimization 수행 방법

 

⦁ Transformation based approach

transformation(Equivalent) rule로 최적화 set 을 만들고, 그 안에서 최적의 대안 플랜을 찾는다. 이 방법 '최적' 에 가까운 플랜을 찾을 수 있지만, 들어가는 Cost가 너무 많다.

⦁ Heuristic based approach

selection, projection, join만 가지고 쿼리 만들어서 그 안에서 찾기 select 를 최대한 일찍해서 attribute 줄이고, 불필요한 attribute는 바로바로 projection으로 제거하고, 크기가 작은거 부터 join하는 방식이다.

 

앞서 언급한 Transformation based approach 는 최적값을 찾을 수 있지만, 들이는 Cost가 너무 높다.

즉, '가성비' 가 떨어진다.  성능 개선을 위해서는, 이러한 방식 보단 앞서 배운 '미리 projection 하기', '작은 테이블 부터 Join 하기'와 같은, 기본 전략을 통해 대략적인 근사치를 찾아서 빠르게 반환하는 것이 효율적인 경우가 많다. 

이 개념은 '최대한 초기 시점에서 연산을 줄여놓는 것이 최적화에 도움이 된다' 라는 생각에서 나온 것이다.

 

Estimating Statistics of Expression Results

이번엔 Query의 Cost를 측정하는 법을 살펴보자. Query의 경우, 여러가지 변수와 요인으로 인해 '정확한 측정' 이 불가능하다. 따라서, 쿼리의 Cost를 Data Size로 '예측' 하거나, 이전의 통계를 기준으로 해당 쿼리의 성능을 판단해야한다. 

 

histogram (통계 기반 추측)

 
쿼리 수행 중에 조금씩 모아 놓은 정보를 기준으로 Histogram을 형성하여 어떠한 쿼리가 수행 되면, 해당 통계자료를 기반으로 Cost를 추정할 수 있다.  여기서 주의할 점은, '실제 수행 시간' 을 통계 자료로 쌓는다는 것이다. 어떠한 Query를 과거 자료 기반으로 Cost Estimation을 진행한 뒤, 해당 Query의 실제 수행 시간을 기록해야한다.

 

 

 

 

 

Cost  근사치 계산

이번엔, 과거 데이터가 존재하지 않아, Cost의 추정 수치를 직접 계산해야하는 경우, 어떻게 수치를 구하는지 살펴보자.

앞서 말했듯이, 쿼리 코스트는 다양한 변수로 정확한  측정이 불가하기에, 아예 대략적인 근사치만 빠르게 계산하여 적용하는 방식을 사용한다. 이 근사치는, upper bound (worst case) 를 가정하는 것으로 계산을 단순화한다.

Selectivity

 해당 연산에서 얼마나 걸러낼 수 있는가? 에 대한 짗표이다. 
조건 c에 대해, r에서 만족하는 튜플 개수가 s일시
S / Nr 이  조건 c 의 selectivity 이다.( 기존 데이터의 몇 % 를 선별 가능한지) 
 이를 활용하여 다양한 연산의 근사치를 추정할 수 있다.

Conjunction(교집합) : 정확한 계산을 알 수 없지만, 각각이 발생할 확률들 근사치 구하기
추정 튜플 개수: Nr* 각 조건의 selectivity

Disjunction(합집합):  
추정 튜플 개수:   Nr * ( 1-  (각 조건에 대해   1-selectivity) )  
(1-각 조건에서 걸러진 튜플들의 교집합)

,,,,,

 

이처럼, 매우 간략하게 만든 '근사치' 만 구하는 것으로, 최대한 가성비 좋게 코스트를 측정할 수 있다. ( 어차피 실제 수행 시간은 변수가 많아서 정확한 계산을 해도 정확한 수행 시간을 얻을 수 없다.) 

이외에도 많은 연산들의 근사치를 구하는 공식이 있지만, 이 글에선 생략하겠다. 

요약 

쿼리 optimizer가 초기 플랜에 대한 대안 플랜 찾고, 대략적으로 cost 찾아서 더 나은 대안 플랜을 대략적으로 찾는 것이 Query Cost를 측정하는 방법이다.
⦁ Data size 로 근사치 찾기 (data size 크면 나쁜 성능일 것)
⦁ 통계 기반(Histogram)
⦁ Heuristic(대충 어림짐작 proj, join, select만)으로 플랜 찾기 (대안 Rule에 따라 트리를 대안트리로 조금씩 변경해나가는 heuristics로 연산량 줄이는 방법>> 확실 x) 
⦁ 모든 대안 플랜 찾고 best plan 찾기.(모든 대안 플랜을 하나씩 보며 best 찾기는 너무 낭비( 이러면 쿼리 수행 빠르게 하려했는데 오히려 느려질 수 도) 

이를 또다시 요약하자면, Cost 추정이 완벽하지 않다는 소리.
Cost를 재활용해서 최적의 Cost 찾는데 드는 시간을 최소화 할 수 있지만, 여전히 대안트리들이 너무 많을 수 있다. 

그래서 우리는 적절한 Evaluation Plan을 'Choose' 하는 방법을 알아야한다. 

 

Choice of Evaluation Plans

Cost 예측은 정확하지 않다.

Ex) 아래와 같이, join Plan 만으로도 Cost 변화 가능하기에 정확한 Cost 추정이 어려울 수 있다. 

Nested loop join : 성능이 좋지 않다. 
Hash, merge는 pipleline 불가 ( hash: hash partion, merge: sort 준비단계 필요)

 

따라서, 전체 plan을 계산할 때 이전 operation에서 미리 계산해서 다음번에 더 쉽게 계산 가능하다. 

또한 어떠한 연산은 순서에 따라 극명하게 Good/ Bad 가 나뉘기도 한다. 

Ex) merge join> data가 sort 되어있나 안 되어있나 따라 Cost가 달라진다. 
어차피 Sort한 결과를 사용자한테 보여줘야 된다고 치면,
Sort를 앞으로 빼고 merge join쓰면 연산 Cost를 줄일 수 있다.

Query Optimizer는 수 많은 Evaluation Plan 들 중, 어떤 것을 선택할지 판단한다. 어떠한 기준으로 선택이 이루어지는지 살펴보자.

Tree의 형태를 기반으로 선택

Query Optimizer는 모든 절차가 pipeline 사용 가능하다면 left deep tree를 우선적으로 선택한다.

A(한쪽에 쏠림== left deep join tree )

 바로바로 사용 가능 Left는 unbalance해서 tree 높이가 높아지고, 연산이 길어져서 연산시간이 늘어나지만, 리소스를 적게 차지한다. ( pipeline 구조에서, r1 nat join r2 값 r* >> r* nat join r4 >> 여기서 r1은 더 이상 필요없다( r* 가 r1 담고 있기에)

B(Non-left depp join tree)

중간에 연산결과를 다른 곳에 저장해야한다.
연산시간 자체는 빠르지만, 연산 결과를 저장하기 위한 resource를 많이 차지한다.

 

why left-depp join tree?

 DB에서는 여러 사용자가 접근 가능한 Shared 환경이 기본 전제이다. 따라서 정확히 구하지 못하는 '연산 속도'에 중점을 두기 보다는,  리소스 위주로 최적화를 진행하는 것이 좋은 접근이다.

그렇기 때문에 쿼리 optimizer에서는 left deep tree만 우선적으로 고려하여 설계한다.

+@: 찾아야할 대안 트리의 범위를 줄여주는 방법. 
Sort Order: 특수한 sort order로 이후의 연산 비용 줄일 수 있다.
Ex) sort 미리하고 Merge join
주로 sort order에서 고려할 대상은 적기에 적은 비용으로 시간, 공간 복잡도를 크게 개선가능.

heuristic

엄청 많은 data 중 실제 필요한 것은 몇 개 정도 일 때, 일일이 연산하는 것은 효율이 좋지 않다. 
Depress, empress를 통해 더 적은 비용 들이는 쿼리로 변경할 수 있다.
-> select와 projection 최대한 빨리해 사이즈 미리 줄여 놓고, select,join 조건을 최대한 엄격하게 걸어서 원하는 값을 손상하지 않는 선에서 많이 줄일 수 있게 만들고,  join 사이즈 작은 것부터 수행하는 것, 즉 앞서 배운 기본 전략을 기반으로 '대략적인' 최적화를 수행하는 것을 Heuristic이라고한다.

Real Application

• 대부분의 optimizer은 주로 left-deep join만 염두한다.
• 또한 heuristic으로 proj, select를 최대한 빨리( 최대한 하위 트리로 ) 적용하거나 테이블 사이즈가 작은 것을 먼저 Join하여  대략적인 초적화를 진행한다.
• 이후 pipeline이 적용 가능하다면 적용하여 성능을 개선한다. (Sort와 같이, 전체가 수행되야 Valid한 연산 제외)

 

위와 같은 대략적인 과정으로 Optimize된 Plan을 선택하되, 만약 이 과정에서 정해진 optimization cost budget(예산) 초과시 optimize 찾기를 멈춘다.( 상한선)

또한, 각 쿼리에 대한 Optimize 플랜을 찾을 때, 좋은 개선책 찾으면 budget을 감소하고, 좋은 개선안을 찾지 못하면 budget 증가하는 것으로 budget을 조율한다.

+@: Plan caching
이번에 계산한 대안 쿼리의 cost를 저장해서 나중에 재사용하는 것으로, 쿼리 Cost 추산을 빠르게 진행하는데 도움이된다.

여기까지, 쿼리의 예측값을 추정하고, 이를 기반으로 가장 나은 Evaluation Plan을 찾는 Query Optimization에 대해 알아보았다.