Chapter 19: Query Optimization
CHAPTER 19: QUERY OPTIMIZATION
Answers to Selected Questions
19.15 – Develop cost functions for the PROJECT, UNION, INTERSECTION,
SET DIFFERENCE, and CARTESIAN PRODUCT algorithms discussed in section
19.4.
Answer:
Assume relations R and S are stored in b R and b S disk blocks, respectively. Also, assume
that the file resulting from the operation is stored in b RESULT disk blocks (if the size
cannot be otherwise determined).
PROJECT operation: if <attribute list> includes a key of R, then the cost is 2*b R since the
read–in and write–out files have the same size, which is the size of R itself; if <attribute
list> does not include a key of R, then we must sort the intermediate result file before
19.16 – No solution provided.
19.18 – Calculate the cost functions for different options of executing the JOIN operation
OP7 discussed in section 19.3.2.
Answer:
The operation is
OP7: DEPARTMENT |x| MGRSSN=SSN EMPLOYEE.
As in section 18.2.3 we assume the secondary index on MGRSSN of DEPARTMENT, with
selection cardinality s=1 and level x=1; also the join selectivity of OP7 is js = 1/125 =
Copyright © 2016 Pearson Education, Inc., Hoboken NJ
19.19 – 19.20: No solution provided.
19.21 – Compare the cost of two different query plans for the following query:
salary > 40000 select (EMPLOYEE |X| DNO=DNUMBER DEPARTMENT)
Use the database statistics in Figure 15.8
Answer:
One plan might be for the following query tree
So the the number of data blocks to be accessed would be
(1/5) * (NUM_ROWS) = (1/5) * 10,000 = 2000
Since 10,000 rows are stored in 2000 blocks, we have that
2000 rows can be stored in 400 blocks. So the TEMPORARY table (i.e., the result of the selection
operator) would contain 400 blocks.
Copyright © 2016 Pearson Education, Inc., Hoboken NJ
18.22 (continued)
Therefore, the total cost would be
11 + 2000 + 400 + 2005 = 4416 block accesses
NOTE: If we have 5 main memory buffer pages available during the join, then we could store all 5
blocks of the DEPARTMENT table there. This would reduce the cost of the join to 5 + 400 = 405 and
the total cost would be reduced to 11 + 2000 + 400 + 405 = 2816. A second plan might be for the
following query tree
Again, we could use a nested loop for the join but instead of creating a temporary table for the result
we can use a pipelining approach and pass the joining rows to the select
operator as they are computed. Using a nested loop join algorithm would yield the following
50 + (50 * 2000) = 100,050 blocks We would pipeline the result to the selection operator