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 We can use the salary index on EMPLOYEE for the select operation: The table in Figure 18.8(a) indicates that there are 500 unique salary values, with a low value of 1 and a high value of 500. (It might be in reality that salary is in units of 1000 dollars, so 1 represents $1000 and 500 represents $500,000.) The selectivity for (Salary > 400) can be estimated as (500 - 400)/500 = 1/5 This assumes that salaries are spread evenly across employees. So the cost (in block accesses) of accessing the index would be Blevel + (1/5) * (LEAF BLOCKS) = 1 + (1/5)* 50 = 11 Since the index is nonunique, the employees can be stored on any of the data blocks. 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. The cost of writing the TEMPORARY table to disk would be 400 blocks. Now, we can do a nested loop join of the temporary table and the DEPARTMENT table. The cost of this would be b + (b * b ) DEPARTMENT DEPARTMENT TEMPORARY We can ignore the cost of writing the result for this comparision, since the cost would be the same for both plans, we will consider. We have 5 + (5 * 400) = 2005 block accesses 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 and it would choose only those rows whose salary value was greater than 400. NOTE: If we have 50 main memory buffer pages available during the join, then we could store the entire DEPARTMENT table there. This would reduce the cost of the join and the pipelined select to 50 + 2000 = 2050. �PAGE � Copyright © 2007 Pearson Education, Inc. Publishing as Pearson Addison-Wesley.