1 of 8

Cardinality Estimation

See speaker notes for explanations.

2 of 8

Cardinality Estimation (Point Selection)

Assume a uniform distribution.

σ_{color = “orange”}

X ≅ 1 / V(color)

≅ 1/4

3 of 8

Cardinality Estimation (Union)

Assume conditions are disjoint.

σ_{color = “orange” OR color = “green”}

X ≅ 1 / V(color) + 1 / V(color)

≅ 1/4 + 1/4 = 1/2

4 of 8

Cardinality Estimation (Intersection)

Assume independence.

σ_{c1 = “red” AND c2 = “yellow”}

X ≅ 1 / V(c1) · 1 / V(c2)

≅ 1/2 · 1/2 = 1/4

c1

c2

5 of 8

Cardinality Estimation (Ranges)

Schema: Weather(date, pressure)

Assume a uniform distribution.

σ_{pressure < p}

σ_{pressure > p}

σ_{p < pressure < q}

X ≅ (p − min) / (max - min)

X ≅ (max − p) / (max - min)

X ≅ (q − p) / (max - min)

min(pressure)

max(pressure)

p

q

6 of 8

Cardinality Estimation (Equijoin)

Assume uniform distribution and full overlap.

⋈_{c1 = c2}

X ≅ 1 / (V(c1) · V(c2)) · min(V(c1), V(c2))

≅ 1 / max(V(c1), V(c2))

≅ 1/4

c1

c2

Equijoins are tricky. The first guess we might have for the selectivity factor is X = 1/V(c1) * 1/V(c2). This isn’t quite right though, as 1/V(c1) * 1/V(c2) = 1/3 * 1/4 = 1/12. The correct answer we want is X = 3/12 = 1/4. What went wrong?

Let’s think of what 1/V(c1) * 1/V(c2) really means. From the “Point Selection” slide, we know that 1/V(c1) is the selection factor for choosing one specific color from c1. For example, the selectivity factor for σ (c1 = ‘red’) is 1/V(c1) = 1/3. The same goes for 1/V(c2). For example, σ (c2 = ‘red’) has a selectivity factor of 1/V(c2) = 1/4.

From the “Intersection” slide, we know that multiplying selectivity conditions (when they are independent, and in this case they are) is the same as the AND of them. So σ (c1 = ‘red’ AND c2 = ‘red’) has a selectivity factor of 1/3 * 1/4 = 1/12. If we look at the table, that’s exactly right: there is just one circle that is red for c1 and c2.

We don’t just want one circle here, though. The equijoin is like multiple selections at once: σ (c1 = ‘red’ AND c2 = ‘red’) + σ (c1 = ‘orange’ AND c2 = ‘orange’) + σ (c1 = ‘yellow’ AND c2 = ‘yellow’) = 1/12 + 1/12 + 1/12 = 1/12 * 3 = 3/12.

Is that why we multiply by min(V(c1), V(c2))? Yes! Think about this: the selectivity factor for each σ is always the same: 1/V(c1) * 1/V(c2). The only question is how many we need to add together. When the tables are different sizes, the smaller table is the one that constrains the join. You could add 100 new colors to c2 and it would not increase the cardinality of the join as c1 would not have any of those new colors. The cardinality only increases when V(c1) increases to match V(c2).

In conclusion, we get the formula 1/V(c1) * 1/V(c2) * min(V(c1), V(c2)), which we can simplify to 1/max(V(c1), V(c2)). (When we divide the smaller of V(c1) and V(c2) by both V(c1) and V(c2), we’re left with the larger of the two--max(V(c1), V(c2)).)

7 of 8

Cardinality Estimation (Equijoin)

Assume uniform distribution and full overlap.

⋈_{c1 = c2}

X ≅ 1 / (V(c1) · V(c2)) · min(V(c1), V(c2))

≅ 1 / max(V(c1) · V(c2))

≅ 1/4 (didn’t change)

c1

c2

8 of 8

Cardinality Estimation (Equijoin)

Assume uniform distribution and full overlap.

⋈_{c1 = c2}

X ≅ 1 / (V(c1) · V(c2)) · min(V(c1), V(c2))

≅ 1 / max(V(c1) · V(c2))

≅ 1/5 (decreased)

c1

c2