DBMS 비용 계산 - 용어/수식 정의 및 기본

표기 및 정의

• Duplicate Elimination
  • 말그대로 중복 제거(DISTINCT)
  • 표기: \(\delta(R)\) 
• Projection
  • 특정 컬럼(애트리뷰트)만을 추출
  • 표기: \(\Pi_{L}(R)\)
  • \(L\)은 다음중 하나
    • \(R\)의 애트리뷰트, \( a_1, a_2, a_3 \dots , a_n \)
    • \(E\) → \(a'\)
      • \(a'\)는 rename된 컬럼
      • \(E\)는 다음 중 하나
        • 수식: (ex. \(( 3 * a_1 )\))
        • \(R\)의 애트리뷰트

일때,

• \(M\): 연산 실행 시 가용 메모리 버퍼의 크기
• \(B(R)\)
  • \(R\)의 레코드를 저장하기 위해 필요한 디스크 블록 수
• \(T(R)\)
  • \(R\)의 전체 튜플 수
  • 한 블록에 저장되는 레코드 수 = \(T(R)/B(R)\)
• \(V(R, a)\)
  • \(R\)의 애트리뷰트 \(a\)에 나타나는 상이한 튜플들의 수 (Cardinality)
  • \(V(R, [a_1 , a_2 , …, a_n ])\)는 \(T(\delta(\Pi_{a_{1}, a_{2}, … ,a_{n}}(R))) \)와 동치

이때 , 컬럼 \(a\)에 대한

• Selectivity는 1/V(R, a)
• Selection Cardinality(SC)는 T(R)/V(R, a)    ( = T(R) * <a 에 대한 Selectivity>)
   ⟹ 릴레이션 R에서 a로 조회되는 cardinality의 추정치라고 할 수 있다. 

이다.

 

예시로 보는 Selection Cardinality의 의의, 그리고 한계

예를 들어 다음을 가정해보자.

• 릴레이션 \(R(a_{1})\) 이 있으며, \(a_{1}\)에 인덱스가 있다.
• \(T(R)\)이 10,000 이며, \(a_1\) 에 대한 값이 1, 2, 3 이 있는데, 각각 10, 100, 9890개의 튜플이 있다.

이 때, 실제 Cardinality \(V(R, a_1) = 3\) 이며, selectivity는 0.333 이다. 따라서, Selection Cardinality는 3,330이 된다.

 

쿼리 종류나 DBMS 마다 다르겠지만, 특정 쿼리를 실행할 때, 인덱스가 있다하더라도 테이블 풀스캔을 하는 경우가 있다.
즉, 테이블 접근에 대한 근거 중 하나로, seletivity를 이용한다.

다시 말해, seletivity가 정의된 threshold 값 보다 크다고 판단되면, 인덱스를 타기보단 풀스캔을 선택할 가능성이 있다.

 

더 쉽게 얘기해볼자.

 

SELECT * FROM TBL_R WHERE A = 1; 이라고 하면,

- 실제 검출될 튜플: 한개

- 옵티마이저가 저장하고 있는 a에 대한 SELECTIVITY: 0.333

- SC 추정치: 3,330

셀렉션 카디널러티는 T(R)의 20%를 넘어가므로 인덱스 선택보다, 풀스캔 혹은 인덱스 스캔을 선택.

이라는 것이다.

대안

DBMS는 히스토그램에 통계치를 저장, 이를 이용하여 selectivity에 대한 좀 더 정확한 근사값을 추출한다.

히스토그램의 종류는 두가지가 있다.

• 도수 분포도
• 높이 균형 분포도(Height-BalanceHistogram)

히스토그램을 이용하지 않는다고 가정할 때, \(\sigma_{a_1 = 1}(R)\)은 Selectivity가 0.333이므로 일반적인 DBMS는 풀스캔을 할 가능성이 높다. 반면, 도수분포도가 있으면, 도수가 10개이며, selectivity는 0.001이 되므로 인덱스를 이용할 것이다.