Teorey J., Lightstone S., Nadeau T. Database Modeling and Design: Logical Design
Подождите немного. Документ загружается.
We now compare the two approaches:
It is clearly seen that the use of table reduction tech-
niques (early selections and projections) has the potential
of greatly reducing the I/O time cost of executing a query.
Although in this example indexes were not required, in
general they can be very useful to reduce I/O time further.
3.4 Query Execution Plan Development
A query execution plan is a data structure that represents
each database operation (selections, projections, and joins)
as a distinct node. The sequence of operations in a query
execution plan can be represented as top down or bottom
up . We use the bottom-up approach, and Figures 3.1 an
d 3.2
are
classic examples of the use of query execution plans to
denote possible sequences of operations needed to complete
SQL queries. An SQL query may have many possible execu-
tion sequences, depending on the complexity of the query,
and each sequence can be represented by a query execution
plan. Our goal is to find the query execution plan that
finds the correct answer to the query in the least amount of
time. Since the optimal solution to this problem is often too
difficult and time consuming to determine relative to the time
restrictions imposed on database queries by customers,
query optimization is really a process of finding a “good”
solution that is reasonably close to the optimal solution, but
can be quickly computed.
A popular heuristic for many quer
y optim
ization algorithms
in database systems today involves the simple observation
from Section 3.3 that selections
and projections should be
done before joins because joins tend to be b y far the most
time-costlyoperations.Joinsshouldbedonewiththesmallest
segments of tables possible, that is, those segments that have
only the critical data needed to satisfy the query. F or instance
in Example Query 3.1, the supplier recor ds are requested for
Block Accesses
Option 1A 6,240 executing joins first
Option 1B 398 executing joins last
14 Chapter 3 QUERY OPTIMIZATION AND PLAN SELECTION
suppliers in New York, which represents only 10% of the
supplier table. Therefore , it makes sense to find those recor ds
first, store them in a temporary table, and use that table as
the supplier table for the join between supplier and shipment.
Similarly, only the columns of the tables in a join that have
meaning to the join, the subsequent joins, and the final display
of results need to be carried along to the join operations.
All other columns should be projected out of the table before
the join operations are executed.
To facilitate the transformation of a query execution
plan
from a random sequence
of operations to a methodi-
cal sequence that does selections and projections first and
joins last, we briefly review the basic transformation rules
that can be applied to such an algorithm.
3.4.1 Transformation Rules for Query
Execution Plans
The following are self-evident rules for transforming
operations in query execution plans to reverse the sequence
and produce the same result (Silberschatz, 2006). Allow
different quer
y trees to produce the same result.
Rule 1. Commutativity of joins: R1
join R2 ¼ R2 join R1.
Rule 2. Associativity of joins: R1 join (R2 join R3)
¼ (R1 join R2) join R3.
Rule 3. The order of selections on a table does not affect
the result.
Rule 4. Selections and projections on the same table
can be done in any order, so long as a projection does
not eliminate an attribute to be used in a selection.
Rule 5. Selections on a table before a join produce the
same result as the identical selections on that table after
a join.
Rule 6. Projections and joins involving the same
attributes can be done in any order so long as the
attributes eliminated in the projection are not involved
in the join.
Rule 7. Selections (or projections) and union operations
involving the same table can be done in any order.
This flexibility in the order of operations in a query exe-
cution plan makes it easy to restructure the plan to an
optimal or near-optimal structure quickly.
Chapter 3 QUERY OPTIMIZATION AND PLAN SELECTION 15
3.4.2 Query Executio n Plan Restructuring
Algorithm
The following is a simple heuristic to restructure a quer y
execution plan for optimal or near-optimal performance.
1. Separate a selection with several AND clauses into a
sequence of selections (rule 3).
2. Push selections down the query execution plan as far as
possible to be executed earlier (rules 4, 5, 7).
3. Group a sequence of selections as much as possible
(rule 3).
4. Push projections down the plan as far as possible (rules
4, 6, 7).
5. Group projections on the same tables, removing
redundancies.
Figure 3.1 illustrates
a query execution
plan that
emphasizes executing the joins first using a bottom-up
execution sequence. Figure 3.2 is the same plan, trans-
formed to a plan that executes the joins last using this
heuristic.
3.5 Selectivity Factors, Table Size, and
Query Cost Estimation
Once we are given a candidate query execution plan to
analyze, we need to be able to estimate the sizes of the
intermediate tables the query optimizer will create during
query execution. Once we have estimated those table sizes,
we can compute the I/O time to execute the query using
that query execution plan as we did in Section 3.3. The
sizes of the intermediate
tables were given in that
example. Now we will show how to estimate those table
sizes.
Selectivity (S) of a table is defined as the proportion of
records in a
table that satisfies a given condition. Thus,
selectivity takes on a value between zero and one. For
example, in Example Query 3.1, the selectivity of records
in the table supplier that satisfies the condition WHERE
city ‘NY’ is 0.1, because 10% of the records have the value
NY for city.
16 Chapter 3 QUERY OPTIMIZATION AND PLAN SELECTION
To help our discussion of selectivity, let us define the
following measures of data within a table:
• The number (cardinality) of rows in table R: card(R).
• The number (cardinality) of distinct values of attribute
A in table R: card
A
(R)
• Maximum value of attribute A in a table R: max
A
(R)
• Minimum value of attribute A in a table R: min
A
(R)
3.5.1 Estimating Selectivity Factor for a Selection
Operation or Predicate
The following relationships show how to compute
the selectivity of selection operations on an SQL query
(Ozsu, 1991).
The selectivity for an attribute A in table R to have a spe-
cific value a in a selected re
cord applies to two situations.
First, if the attribute A is a primary key, where each value
is unique, then we have an exact selectivity measure
SðA ¼ aÞ¼1=card
A
ðRÞ: 3.1
For example, if the table has 50 records, then the selectivity
is 1/50 or 0.02.
On the other hand, if attribute A is not a primary key and
has multiple occurrences for each value a, then we can also
use Equation 3.1 to estimate the selectivity,
but we must
acknowledge that we are guessing that the distribution
of values is uniform. Sometimes this is a poor estimate, but
generally it is all we can do without actual distribution
data to draw upon. For example, if there are 25 cities out of
200 suppliers in the supplier table in Example Query 3.1,
then the number of records with ‘NY’ is estimated to be
card
city
(supplier) ¼ 200/25 ¼ 8. The selectivity of ‘NY’ is
1/card
city
(supplier) ¼ 1/8 ¼ 0.125. In reality, the number
of records was given in the example to be 10%, so in this
case our estimate is pretty good, but it is not always true.
The selectivity of an attribute A being greater than (or
less than) a specific value a also
depends on a uniform
distribution (random probability) assumption for our
estimation:
SðA > aÞ¼ðmax
A
ðRÞaÞ=ð max
A
ðRÞ min
A
ðRÞÞ: 3.2
SðA < aÞ¼ða min
A
ðRÞÞ=ð max
A
ðRÞ min
A
ðRÞÞ: 3.3
Chapter 3 QUERY OPTIMIZATION AND PLAN SELECTION 17
The selectivity of two intersected selection operations
(predicates) on the same table can be estimated exactly if
the individual selectivities are known:
SðP and QÞ¼SðPÞSðQÞ, 3.4
where P and Q are predicates.
So if we have the query
SELECT city, qty
FROM shipment
WHERE city ¼ ’London’
AND qty ¼ 1000;
where P is the predicate city ¼ ‘London’ and Q is the
predicate qty ¼ 1000, and we know that
Sðcity ¼ ‘London’Þ¼:3, and
Sðqty ¼ 1000Þ¼:6, then the selectivity of the
entire query,
Sðcity ¼ ‘London’ AND qty ¼ 1000Þ¼:3 :6 ¼ :18:
The selectivity of the union of two selection operations
(predicates) on the same table can be estimated using the
well-known formula for randomly selected variables:
SðPorQÞ¼SðPÞþSðQÞSðPÞSðQÞ 3.5
where P and Q are predicates.
So if we take the same query above and replace the inter-
section of predicates with a union of predicates, we have:
SELECT city, qty
FROM shipment
WHERE city ¼ ’London’
OR qty ¼ 1000;
Sðcity ¼ ‘London’Þ¼:3
Sðqty ¼ 1000Þ¼:6
Sðcity ¼ ‘London’ OR qty ¼ 1000Þ¼:3 þ :6 :3 :6 ¼ :72:
3.5.2 Histograms
The use of average values to compute selectivities can
be reasonably accurate for some data, but for other data
it may be off by significantly large amounts. If all databases
only used this approximation, estimates of query time
could be seriously misleading. Fortunately, many database
18 Chapter 3 QUERY OPTIMIZATION AND PLAN SELECTION
management systems now store the actual distribution of
attribute values as a histogram. In a histogram, the values
of an attribute are divided into ranges, and within each
range, a count of the number of rows whose attribute falls
within that range is made.
In the example above we were given the selectivity of
qty ¼ 1000 to be .6. If we know that there are 2,000 differ-
ent quantities in the shipment table out of 100,000 rows,
then the average number of rows for a given quantity
would be 100,000/2,000 ¼ 50. Therefore, the selectivity of
qty ¼ 1000 would be 50/100,000 ¼ .0005. If we have stored
a histogram of quantities in ranges consisting of integer
values: 1, 2, 3, 4, ......, 1,000, 1,001,......2,000, and found
that we had 60,000 rows containing quantity values equal
to 1,000, we would estimate the selectivity of qty ¼ 1000
to be .6. This is a huge difference in accuracy that would
have dramatic effects on query execution plan cost estima-
tion and optimal plan selection.
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
Chapter 3 QUERY OPTIMIZATION AND PLAN SELECTION 19
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.
Case 1: Join Executed First
If the join is executed first we know
that there are 200 suppliers (rows in
the supplier table) and 100,000 ship-
ments (rows in the shipment table),
so the selectivity of supplier number
in the supplier table is 1/200. Now
we apply Equation 3.6 to find the cardi-
nality of the join, that is, the count
of rows (records) in the intermediate
table formed by the join of supplier
and shipment:
cardðsupplier join shipmentÞ
¼ SðsnumÞcardðsupplierÞ
cardðshipmentÞ
¼ð1=200Þ200 100, 000
¼ 100, 000:
This is consistent with the basic
rule of thumb that a join between a
table R1 with a primary key and a
table R2 with the corresponding for-
eign key results in a table with the
same number of rows as the table
with the foreign key (R2). The query
execution plan for this case is shown
in Figure 3.3(a). The result of the two
selections on this joined table is:
(a) Join executed first
(b) Join executed last
RESULT
2
TEMP
100K
SNUM
SUPPLIER
200
SHIPMENT
100K
London
1-Jun-2006
RESULT
2
TEMP01
4
TEMP02
100
SNUM
SUPPLIER
200
SHIPMENT
100K
London 1-Jun-2006
Figure 3.3 Query execution
plan for cases 1 and 2.
20 Chapter 3 QUERY OPTIMIZATION AND PLAN SELECTION
cardðresultÞ¼Sðsupplier:city ¼ ‘London’Þ
Sðshipment:shipdate ¼
‘01-JUN-2006’Þcard
ðsupplier join shipmentÞ
¼ð1=50Þð1=1, 000Þ100, 000
¼ 2 rows:
Case 2: Selections Executed First
If the selections are executed first, before the join, the
computation of estimated selectivity and intermediate
table size is slightly more complicated, but still straight-
forward. We assume there are 50 different cities in the sup-
plier table and 1,000 different ship dates in the shipment
table. See the query execution plan in Figure 3.3(b).
Sðsupplier:city ¼ ‘London’Þ¼1=card
city
ðsupplierÞ¼1=50:
Sðshipment:shipdate ¼ ‘01-JUN-2006’Þ
¼ 1=card
shipment
ðshipmentÞ
¼ 1=1, 000:
We now determine the sizes (cardinalities) of the results
of the two selections on supplier and shipment:
cardðsupplier:city ¼ ‘London’Þ
¼ð1=50Þð200 rows in supplierÞ¼4 rows:
cardðshipment:shipdate ¼ ‘01-JUN-2006’Þ
¼ð1=1; 000Þð100; 000Þ¼100 rows:
These two results are stored as intermediate tables,
reduced versions of supplier and shipment, which we will
now call ‘supplier’ and ‘shipment’:
cardð‘supplier’Þ¼4ðNote: ‘supplier’ has 4 rows with city
¼ ‘London’:Þ
cardð‘shipment’Þ¼100ðNote: ‘shipment’ has 100 rows
with shipdate ¼ ‘01-JUN-2006’:Þ
Now that we have the sizes of the two intermediate
tables we can apply Equation 3.6 to
find the size of
the
final result of the join:
Chapter 3 QUERY OPTIMIZATION AND PLAN SELECTION 21
cardð‘supplier’ join ‘shipment’Þ
¼ SðsnumÞcardð‘supplier’Þcardð‘shipment’Þ
¼ð1=200Þ4 100
¼ 2:
The final result is 2 rows, that is, all the suppliers in
London with the ship date of 01-JUN-2006.
We note that both ways of computing the final result
have the same number of rows in the result, but the
number of block accesses for each is quite different. The
cost of doing the joins first is much higher than the cost
for doing the selections first.
3.5.5 Example Estimations of Query Execution
Plan Table Sizes
We now revisit Figures 3.1 and 3.2 for actual table sizes
within the query execution plan for Example Query 3.1.
Option 1A (Figure 3.1)
For the query execution plan in Figure 3.1 we first join
supplier (S) and shipment (SH) to form TEMPA. The size
of TEMPA is computed from Equation 3.6 as
cardðTEMPAÞ¼S ðcardðsupplierÞcardðshipmentÞÞ
¼ 1=200 200 100,
000 ¼ 100, 000 rows,
where
S ¼ 1/200, the selectivity of the common attribute in
the join, snum.
Next we join TEMPA with the part table, forming
TEMPB.
cardðTEMPBÞ¼S ðcardðTEMPAÞcardðpartÞÞ
¼ 1=100 100, 000 100 ¼ 100, 000 rows,
where S ¼ 1/100, the selectivity of the common attribute in
the join, pnum.
Finally we select the 10% of the rows from the result
that have city ¼ ‘NY’, giving us 10,000 rows in TEMPC
and the final result of the query. We note that the 10% ratio
holds through the joins as long as the joins involve primary
key–foreign key pairs (and do not involve the attribute
city).
22 Chapter 3 QUERY OPTIMIZATION AND PLAN SELECTION
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 ther
efore 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 from the sequential and random block accesses
needed to execute a query. We also looked at the
Chapter 3 QUERY OPTIMIZATION AND PLAN SELECTION 23