Databases Reference
In-Depth Information
3.5.3 Estimating the Selectivity Factor for a Join
Estimating the selectivity for a join is difficult if it is based on nonkeys; in the worst case
it can be a Cartesian product at one extreme or no matches at all at the other extreme.
We focus here on the estimate based on the usual scenario for joins between a primary
key and a nonkey (a foreign key). Let's take, for example, the join between a table R1,
which has a primary key, and a table R2, which has a foreign key:
×
×
card(R1 join R2) = S
card(R1)
card(R2),
3.6
where S is the selectivity of the common attribute used in the join, when that attribute
is used as a primary key. Let's illustrate this computation of the selectivity and then the
size of the joined table, either the final result of the query or an intermediate table in the
query.
3.5.4 Example Query 3.2
Find all suppliers in London with the shipping date of June 1, 2006.
SELECT supplierName
FROM supplier S, shipment SH
WHERE S.snum = SH.snum
AND S.city = 'London'
AND SH.shipdate = '01-JUN-2006';
Let us assume the following data that describes the three tables: supplier, part, and
shipment:
•
card(supplier) = 200
•
card
city
(supplier) = 50
•
card(shipment) = 100,000
•
card
shipdate
(shipment) = 1,000
•
card(part) = 100
There are two possible situations to evaluate:
1.
The join is executed before the selections.
2.
The selections are executed before the join.
