1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.