조인 선택률(Join selectivity), 조인 선택도, 조인 카디널리티(cardinality)

▣ 조인 선택률(Join selectivity), 조인 선택도, 조인 카디널리티(cardinality)

선택도 → 카디널리티 → 비용 → 액세스 방식, 조인 순서, 조인 방법 등 결정

 

히스토그램이 있는 경우	히스토그램이 없거나, 있더라도 조건절에서 바인드 변수를 사용할 경우
히스토그램으로 선택도 산정 단일 컬럼에 대해서는 정확도도 비교적 높음	옵티마이저는 데이터 분포가 균일하다고 가정한 상태에서 선택도 구함

 

- 조인 선택도(selectivity) 전체 레코드 중에서 특정 조건에 의해 선택될 것으로 예상되는 레코드 비율

조인 선택도 = 조인 조건에 만족하는 튜플수 / 전체 튜플 수 (비동등 조건인 경우)

                = 1 / Distinct Value 개수  (동등 <=> 조건인 경우)

                = [(num_rows(R) - num_nulls(R.A)) / num_rows(R)) * ((num_rows(S) - num_nulls(S.B)) / num_rows(S)] / greater(num_distinct(R.A), num_distinct(S.B))

                = 1 / greater(num_distinct(R.A), num_distinct(S.B)) (Null이 없는 경우 분자값은 항상 1, 수식 단순화)

 

- 조인 카디널리티(Cardinality) : 특정 엑세스 단계를 거치고 나서 출력될 것으로 예상되는 결과 건수

조인 카디널리티 = card(R) * card(S) * 조인 선택도

 

---

 

2017년 66번

 

조인 선택률은 조인 조건을 만족하는 튜플수를 전체 조합가능한 튜플수로 나눈값임

 

R ⋈ D1 < D4 S 조인 조건에 따라 D1 이 D4 보다 작은 투플들에 대해 조인을 수행하면 

총 5 개의 튜플이 생성됨 D4=4 -> D1={1}, D4=5 -> D1={1}, D4=10 -> D1={1,6,9}

 

R 과 S 의 조인 가능한 전체 튜플의 수는 카티션 곱이므로 3 X 3 = 9

 

조인 선택률 (join selectivity)= 5 / 9

 

---

2018년 65번

정답 : 4번

- 히스토그램 통계정보가 수집되지 않았으므로 모든 속성은 균등하게 분포되어 있다고 가정

 

* 히스토그램이 없거나, 있더라도 조건절에서 바인드 변수를 사용할 경우

: 옵티마이저는 데이터 분포가 균일하다고 가정한 상태에서 선택도 구함

 

조인 선택도 = 1 / Distinct Value 개수  (동등 <=> 조건인 경우)

 

조인 카디널리티(Cardinality) : 특정 엑세스 단계를 거치고 나서 출력될 것으로 예상되는 결과 건수

조인 카디널리티 = card(R) * card(S) * 조인 선택도

 

- job=‘manager’ 인 투플은 전체의 1/5인 200개로 예상됨
(president, manager, salesman, clerk, analyst 총 5개 속성 중 1개) 

 

- deptname=‘sales’ 인 투플은 전체 1/4인 250개로 예상됨

(general, accounting, marketing, sales 총 4개 속성 중 1개)

 

- job= 'manager' OR deptname= ‘sales‘ 조건의 경우 250 + 200 = 450 개 중 중복되는 투플을 제외해야 함

 

- 중복 투플은 deptname=‘sales’ 인 투플 250 중 1/5 확률로 중복될 것으로 예상되므로, (250 x 1/5) = 50개

 

- 전체 조회 조건식의 조회결과는 250 + 200 - 50 = 400개

 

---

2020년 60번

정답 : 2번

조인 조건이 R.A=S.B이고 |R|=8, |S|=3

R, S의 A, B값이 Null인지 아닌지는 별도 주어져 있지 않으므로 없다고 가정

조인 선택도의 분자 값은 8/8*3/3이므로 항상 1이다.

 

여기서, 조인 선택도 수식을 단순화 하면,

js = 1 / greater(num_distinct(R.A), num_distinct(S.B))

 

1) B가 S의 기본키일 때 js의 최대값

js = 1/ greater(num_distinct(R.A), num_distinct(S.B)) = 1/ greater(num_distinct(R.A), 3)

이때, 1<= num_distinct(R.A) <= 8 이므로, js의 최대값은 1/3

 

2) A가 R의 기본키일 때 js의 최대값

js = 1/ greater(num_distinct(R.A), num_distinct(S.B)) = 1/ greater(8, num_distinct(S.B))

이때, 1<= num_distinct(S.B) <= 3 이므로, js의 최대값은 1/8

 

3) R.A의 유일한 값의 수가 2, S.B의 유일한 값의 수가 3일 경우 js의 값

js = 1/ greater(num_distinct(R.A), num_distinct(S.B)) = 1/ greater(2, 3) = 1/3

 

4) B가 S의 기본키일 때 조인 결과 테이블의 카디널리티

조인 카디널리티 = card(R) * card(S) * 조인 선택도 = |R|*|S|*js

이때, 1번에서처럼 js의 범위구간은 1/8 <= js <= 1/3이므로,

카디널리티 범위는 3<= jc(8*3*js)<=8