이 포스팅은 SQL Query Optimization: Why Is It So Hard To Get Right?(David J.DeWitt) 강의를 참조하여 작성하였습니다.

Selectivity Esitimation

selectivity 란 릴레이션의 한 튜플에서 selection 조건을 만족하는 확률입니다.
이를 추정해야 몇개의 튜플을 가져올지 알 수 있고, 이를 통해 query plan 의 cost 를 추정할 수 있습니다.
튜플 모두를 메모리에 둘 수 있다면, 몇개인지 확인하고 cost 를 예측할 수 있지만,
모든 튜플을 메모리에 올릴 수 없기 때문에 다음과 같은 방법등을 사용하여 추정(estimation) 을 합니다.

• Statistics
• Histogram
• Sampling

Statistics

DBMS 는 테이블. 어트리뷰트, 인덱스 등에 대한 통계량(statistics)을 보유하고 있으며,
이를 사용하여 selectivity를 추정할 수 있습니다.

DBMS 는 릴레이션에 대해 다음과 같은 정보(catalog)를 갖고 있습니다.

• $n_r$ : 릴레이션 r 의 튜플의 수
• $b_r$ : 릴레이션 r 의 튜플을 포함하는 블록의 수
• $l_r$ : 릴레이션 r 의 바이트
• $f_r$ : 릴레이션 r 의 blocking factor (하나의 block 에 들어가는 튜플의 수)
• $V(A,r)$ : 릴레이션 r 에서 어트리뷰트 A 의 distinct 한 값의 수

V(A,R) 과 $n_r$ 을 사용하여 간단하게 selectivity 를 추정해봅시다.

Selection Cardinality, $SC(A,r)$ 은 하나의 distinct 한 값의 평균 레코드의 수 입니다.
이는 $n_r / V(A,r)$ 로 계산할 수 있습니다.
전체 튜플의 수 / distnct 한 값의 수 이므로 평균 레코드의 수가 됩니다.

SC 를 사용해 어떤 predicate P 에 대한 selectivity 를 구할 수 있습니다.
SC 는 특정 어트리뷰트, 특정 조건에 해당하는 튜플의 평균 수 입니다.
이를 전체 튜플 수 $n_r$ 으로 나누면, 그 조건에 해당하는 튜플의 기대 확률이 됩니다.
식으로 표현하자면
$sel(P) = SC(P,r)/N_r$ 입니다.

selection 쿼리의 종류별로 어떻게 selectivity 를 계산하는지 확인해보겠습니다.

• Equality : $sel(A=constant) = SC(P) / n_r$
• Range : $sel(A \geq a ) = (A_{max} - a) / (A_{max} - A_{min} )$
• Negation : $sel(! P) = 1 - sel(P)$
• Conjunction : $sel(P1 \cap P2) = sel(P1) \cdot sel(P2)$
• Disjunction : $sel(P1 \cup P2 ) = sel(P1) + sel(P2) - sel(P1) \cdot sel(P2)$

이런식으로 통계량을 사용하여 selectivity 를 추정할 수 있습니다.

그러나 이 방식은 다음과 같은 3가지 가정하에서 수행됩니다.

• Uniform Data : 값들의 분포가 동일합니다. 단순히 distinct 한 값의 수와 전체 튜플 수를 가지고 평균을 추정합니다.
• Independent predicate : Conjunction 이나 Disjunction 시, 두개의 조건이 독립적이라 봅니다. $(P1 \cap P2 = P1 \cdot P2)$
• Inclusion Principle : 두 릴레이션을 조인할 때 inner 와 outer 의 key 가 겹칩니다. 위의 join 연산에 selectivity 를 구할 때 필요한 가정입니다.(책 참조)

실제 상황에서는 위 3가지 가정이 성립하지 않기 때문에 에러가 발생하게 됩니다.
이것들 중 Uniform data 가정으로 발생하는 에러는 histogram 을 사용하여 어느정도 줄일 수 있습니다.

Histogram

히스토그램을 사용하면

이와 같은 분포를 다음과 같이 표현할 수 있습니다.

임의의 범위를 지정하여, 해당 범위의 합으로 그 범위의 값들을 표현합니다.(버킷)
범위는 일정하게 설정하는데,
이 경우 그 범위 안에 값들의 편차가 클수록 에러가 많이 발생하게 됩니다.

이를 보완하기위해 사용하는 것이
Quantitles Histogram 입니다.

범위를 특정 상수로 지정하는 것이 아니라,
각 버킷의 값이 대략적으로 비슷하도록 설정하는 것 입니다.

그림@@

버킷이 어디까지 포함하는지에 대한 정보를 추가로 유지해야하긴하지만,
기존 히스토그램의 에러를 많이 줄일 수 있습니다.

Sampling

테이블을 샘플링 하여 selectivity 를 추정할 수 있습니다.
기존 테이블에서 일부만 가져와서 유지를 하고,
그 샘플에서만 selectivity 를 구합니다.
샘플이 기존 데이터를 잘 반영하는 경우, 좋은 성능을 보입니다.

기존 테이블이 수정되는 경우 샘플 업데이트가 필요합니다.