[Database] DBA급 개발자로 - #14 비용 기반 쿼리 최적화

이전 포스팅에서는 규칙 기반(heuristics / rules) 쿼리 최적화에 대해 살펴봤습니다. 이번 포스팅에서는 비용 기반 쿼리 최적화에 대해 살펴보겠습니다. 

Cost Model Component 

쿼리 수행 비용에는 어떤 항목이 포함되는지 살펴보겠습니다. 

• Physical cost 
  • CPU cycle
  • I/O 횟수 
  • RAM 사용량 
• Logical cost
  • 각 operator에 의해 반환되는 데이터의 크기 
  • 여러 operator가 독립적으로 실행될 수 있는지 여부 
• Algorithm
  • 알고리즘의 복잡도 

위의 항목 외에도 다양한 요인에 의해 쿼리를 실행하는 비용에 포함될 수 있습니다. DBMS는 데이터베이스의 통계(statistics)를 통해서 논리적인 비용(logical cost)을 측정할 수 있습니다. DBMS의 통계는 테이블, 칼럼 그리고 인덱스 등과 관련된 통계 정보를 포함합니다. 비용을 측정하는 방법을 알아보기 전에 사용할 용어 대해 알아보겠습니다. 

$$ N_r:\,테이블에\,포함된\,튜플의\,개수 $$ 

$$ V(A, R):\,A 컬럼에\,포함된\,데이터\,중\,고유한(unique)\,데이터의\,수 $$ 

$$ SC(A, R)= \frac{N_r}{V(A, R)}:\,selection\,cardinality의\,약자로\,A값을\,가진\,튜플의\,평균\,갯수 $$ 

$$ P(predicate)의\,selectivity(sel)\,=\,필터링\,된\,데이터\,수/탐색한\,전체\,데이터\,수$$

 

Join Result Estimation 

조인의 결과 데이터 셋의 크기는 다음의 방법을 통해 예측할 수 있습니다. 테이블 R과 S가 있고 이 두 테이블이 A라는 칼럼을 대상으로 조인이 가능할 때(단, A는 두 테이블의 어떠한 key도 아니라고 가정합니다), 예상되는 조인 결과의 크기는 다음과 같습니다. 

R이 outer table인 경우:

$$ N_R * N_S / V(A,\,S) $$

S가 outer table인 경우: 

$$ N_S * N_R / V(A,\,R) $$ 

따라서 예상되는 최적의 조인 결과의 크기는 다음과 같습니다. 

$$ (N_R * N_S)\,/\,max(V(A,\,R), V(A,\,S)) $$ 

 

Cost Estimation 

여태까지 살펴본 상황은 테이블 내의 모든 데이터가 특정 칼럼을 기준으로 균일하게 분포돼있음을 가정한 상황이었습니다. 하지만 실제 데이터베이스의 테이블이 특정 칼럼을 기준으로 균등하게 분포되지 않을 확률이 높기 때문에 균등하지 않은 상황도 함께 고려해야 합니다. 

특정 컬럼을 기준으로 균등분포를 가정함

실제로는 분포가 균등하지 않을 수 있음

균등하지 않은 테이블에 대해 쿼리 비용을 계산하기 위해서는 간략하게나마 데이터가 어떻게 분포됐는지 파악해야합니다. 첫 번째 방법은 테이블의 특정 칼럼 기준으로 유일한 값이 몇 개 있는지 저장하는 겁니다. 하지만 이는 데이터의 수 또는 유니크한 데이터의 수가 많아질수록 저장 오버헤드가 증가합니다. 이를 어느 정도 최적화할 수 있는 방법으로는 Bucket ranges 또는 Equi-depth histogram 기법이 있습니다. Bucket ranges는 일정한 범위로 컬럼을 나누는 방식이고 equi-depth histogram은 일정한 버킷 크기를 가지도록 컬럼을 나누는 방식입니다. 

Bucket ranges

Equi-depth histogram

그 외에도 특정 값을 가진 데이터의 분포를 파악하기 위한 기법으로는 sketch, sampling 기법이 존재하지만 이번 포스팅에서는 넘어가도록 하겠습니다. 여태까지 살펴본 다양한 방법을 통해서 비용 기반 옵티마이저는 특정 값을 가진 row를 추출할 때 얼마나 큰 비용이 드는지 예상할 수 있습니다. 

 

Query Planning

대상이 오직 하나의 테이블이라면 쿼리 비용 산정은 비교적 쉽습니다. 순차 탐색, 인덱스를 통한 binary search 또는 인덱스 스캔 등 다양한 방법 중 최적의 방법을 찾아 수행하면 됩니다. 

만약 테이블 간의 조인이 필요한 쿼리의 경우 어떻게 최적의 방법을 찾을 수 있을까요? 이런 경우 우리가 알고리즘을 학습하면서 자주 활용했던 dynamic programming을 통해 최적의 방법을 효율적으로 찾을 수 있습니다. 

SELECT * 
FROM R, S, T
WHERE R.a = S.a 
AND S.b = T.b

dynamic programmic query planning

위의 그림에서 가장 비용이 적은 경로를 선택해서 쿼리를 실행하게 됩니다. 

 

마무리 

이번 포스팅을 통해 비용 기반 쿼리 최적화에 대해 살짝 맛만 봤습니다. 워낙 어려운 분야이기 때문에 아직도 활발히 연구가 이뤄진다고 합니다. 다음 포스팅에서는 트랜잭션 concurrency control에 대해 살펴보겠습니다.