This lecture on "Result size estimation" defines a formula of equi-joins based on Selinger paper.
result cardinality
= max number of tuples possible
* product of all selectivities
1 - max number of tuples possible
. This is the product of the cardinalities of both relations.
2 - product of all selectivities
. Which means that we have to compute the selectivity of each term and multiply them. This is defined in an equi-join by 1/MAX(#keys_left, #keys_right).
ex:
100 bunnies
with 2 distinct left ear colors {C1, C2}
with 10 distinct right ear colors {C1...C10}.
What is the probability of matching ears?
P(L = R) =
E_i P(C_i, C_i) =
P(C_1, C_1) + P(C_2, C_2) + P(C_3, C_3) + ... =
(1/2 * 1/10) + (1/2 * 1/10) + (0 * 1/10) + ... =
1/10 =
1/MAX(2,10)
Ok. Now I suppose I am able to estimate the size of the result or how much storage I will use to compute this equi-join.
scenario 1 - Relation L I have 10 tuples and the key cardinality is 10.
Relation R I have 2 tuples and the key cardinality is 2.
The result estimation cardinality is:
10*2*1/MAX(2,10) = 20*(1/10) = 2 tuples
2 - Relation L I have 100 tuples and the key cardinality is 10.
Relation R I have 20 tuples and the key cardinality is 2.
The result estimation cardinality is:
100*20*1/MAX(2,10) = 2000*(1/10) = 200 tuples
3 - Relation L I have 1000 tuples and the key cardinality is 10.
Relation R I have 200 tuples and the key cardinality is 2.
The result estimation cardinality is:
1000*200*1/MAX(2,10) = 200000*(1/10) = 20000 tuples
Is that right? If the professor is teaching about estimation and my answer is 20,000 tuples on the scenario 3, I suppose this is the estimation of the tuples. But I guess this is actually the exact number of tuples that my equi-join will produce. Is this an estimation or exactly answers? Or maybe the estimation comes if my cardinality is estimation the result will be also an estimation?
I am not sure if I have to open another question to the following subject. And what if I am working with data stream? I mean with unbounded data coming to execute a join?
Thanks