[prev] 4 [next]

Estimating Join Result Size

Analysis relies on semantic knowledge about data/relations.

Consider equijoin on common attr: R ⋈a S

Case 1:   values(R.a) ∩ values(S.a) = {}   ⇒   size(R ⋈a S) = 0

Case 2:   uniq(R.a) and uniq(S.a)   ⇒   size(R ⋈a S)  ≤  min(|R|, |S|)

Case 3:   pkey(R.a) and fkey(S.a)   ⇒   size(R ⋈a S)  ≤  |S|