Estimation the Size of a Join

1. 용어 정리

T(R) - R relation 의 총 튜플 수

T(S) - S relation 의 총 튜플 수

 

V(relation,attribute) - relation 에서 해당 attribute 의 distinct value 값의 개수 ex) V(R,a)

 

R ⋈ S - R 과 S 를 자연조인

 

Optimizer 가 Join Cost 계산을 위해서는 조인시에 생기는 결과 집합의 크기를 산출해야 한다.

해당 정보는 Join Order 계산에 사용하게 된다.

R, S 가 Join R(X,Y) ⋈ S(Y,Z) 한다고 가정하자.

Y 값으로 R, S 가 Join 된다고 가정하였을때, Y 값이 R 과 S 둘다 관련이 있다고 해당 정보만을 가지고는 확인할수가 없다.

 

몇가지 가정을 해보자..

1. 두 릴레이션이 Y 값에 대한 disjoing set 이라면,  T(R ⋈ S) = 0 이다.

2. S 릴레이션의 키가 Y 이고 R 의 외래키와 대응된다면,

   정확히 S 의 각 튜플 하나는 R 의 각 튜플들과 Join 하게 된다. 따라서 T(R ⋈ S) = T(R) 이다.

3. 거의 모든 R 과 S 의 Y 값들이 같은 값을 가진다면, T(R ⋈ S) = T(R)T(S) 이다.

 

 

위의 경우 외에도 여러가지 상황이 존재하지만, 일반적인 경우를 가정하여, 간단히 가정을 해보자.

1. Containment of Value Sets

    만일 R 과 S 가 attribute Y 를 가지고 있고, V(R,Y) ≦ V(S,Y) 라면, 모든 R 의 Y 값들은 S 의 Y 값들에 포함된다.

 

2. Preservation of Value Sets

    만일 R 의 attirbure A 가 S 에 포함되지 않을때, V(R ⋈ S, A) = V(R,A) 이다.

 

사실 1번 가정은 아마도 모순일수 있다. 하지만, Y 가 S 의 Key 이고, R 의 외래키에 대응된다면, 조건을 만족한다. 또한 거의 많은 다른 케이스에서도 거의 1번의 조건을 만족한다.

왜냐하면, 직관적으로 S 가 많은 Y의 값들을 가지고 있고,  R 도 Y 값을 가지고 있다면, R 의 Y 값은 S 에도 존재할 가능성이 충분이 있다고, 기대 가능하기 때문이다.

 

2번가정 또한 아마도 모순일수 있다. 하지만, R ⋈ S 의 join attribute 들이 S 의 key 값이고, R 의 외래키와 대응된다면 2번의 조건을 만족한다.

사실상, R 이 "dangling tuples ( join 조건에 불필요한 튜플들 ) " 를 가지고 있다면, R 의 튜플들은 S 의 튜플과 join 되지 않게 된다. 하지만 dangling tuples 를 가지고 있더라도 2번의 가정은 여전히 유효하다.

 

위 2개의 가정을 기반으로하여  R(X,Y) ⋈ S(Y,Z) 의 join 크기를 추정할수 있다.

 

r 을 R 에 속하는 튜플이라고하고, s 는 S 에 속하는 튜플이라고 하자.

V(R,Y) ≥ V(S,Y) 라고 가정하면, 1번의 가정에 의해서 s 의 Y 값은 정확이 한개의 값이 R 에 나타나게 된다. 따라서, r 은 s의 1/V(R,Y) 의 같은 Y 값들을 가질수 있게 된다.

이와 유사하게, V(R,Y) < V(S,Y) 라면,  r 의 Y 값들은 S 에 나타나게 되고, 가능성은 1/V(S,Y) 이다.

 

일반적으로 Y가 일치할 확률은, 1/max(V(R,Y),V(S,Y)) 이며, Join Cardinarity 는

 

T(R ⋈ S) = T(R)T(S) / max(V(R,Y),V(S,Y))

 

위의 공식은 T(R ⋈ S) 에서 두 릴레이션간 일치하는 tuples 들의 수를 계산하게 된다.

 

 

위에서와 같이 기본적으로 Join 의 크기를 정확히 측정하는것은 한계가 있다.

위의 가정이 일반적으로 맞는 가정이라고 해서, 경험상 이렇게 추정하는것이 어느정도 맞으리라고 기대하게 되는 경험적인 산출방법이기 때문에, 넓은 Case에 있어서 정확한 조인 크기를 산출하지 못한다.

이를 보완하기 위해서 상용 DBMS 의 Join 크기 산출은 위의 공식과 거의 일치하지만,

히스토그램 같은 통계치를 사용하여 Join 크기 산출의 오차를 수정하는 노력이 이루어지고 있다.  

 

 

 

* 위의 글은 DATABASE SYSTEM The Complete Book Second Edition ( Jeffrey D. Ullman )

   의 내용을 을 참고하였습니다. *