Databases Reference
In-Depth Information
Option 1B (Figure 3.2)
In Figure 3.2 we look at the improved query execution plan for option 1B.
TEMP1 is the result of selecting city = 'NY' rows from supplier, with selectivity .1
using Equation 3.1, giving us 200 rows (supplier)
.1 = 20 rows in TEMP1.
TEMP2 is the result of projecting columns snum and pnum from shipment, and
therefore has the same number of rows as shipment, 100,000. Similarly, TEMP3 is the
result of a projection of pnum and pname from the part table, and has the same number
of rows as part, 100.
TEMP4 is shown as the semi-join of TEMP1 and TEMP2 over the common
attribute, snum. We note that a semi-join can be represented by a join followed by a
projection of pnum and snum from the result. Applying Equation 3.6 to this join:
×
card(TEMP4) = S
×
card(TEMP1)
×
card(TEMP2)
×
×
= 1/200
20
100,000
= 10,000 rows,
where S = 1/200, the selectivity of the common attribute of the join, snum.
TEMP5 is shown as the semi-join of TEMP4 and TEMP3 over the common
attribute, pnum. Again we apply Equation 3.6 to this join:
Card(TEMP5) = S
×
card(TEMP4)
×
card(TEMP3)
×
×
= 1/100
10,000
100
= 10,000 rows,
where S = 1/100, the selectivity of the common attribute of the join, pnum.
The final result, taking a projection over TEMP5, results in 10,000 rows.
3.6
Summary
This chapter focused on the basic elements of query optimization: query execution
plan analysis and selection. We took the point of view of how the query time can be
estimated using the tools developed in Chapter 2, where the I/O time can be esti-
mated from the sequential and random block accesses needed to execute a query. We
also looked at the estimation of intermediate table size in a query made up of a series
of selections, projections, and joins. Table size is a critical measure of how long merge
joins take, whereas index definitions help determine how long indexed or hash joins
take to execute.
