CS634 – Homework 4

Due Mar. 28 (solution available Mar. 29)

Chaps 14-15

Problem 1

Exercise  14.4 (parts 1-4). Since b is the primary key, it should have an index on b, but the problem says no indexes, so assume that.

Problem 2

Exercise 14.4, but now assume a clustered B-tree index on the PK column b, and estimate the indexed nested loop join cost.

Problem 3

Exercise 15.2 in the textbook (only sub-question 1). Note that, the question in the book is incomplete, because you also need the page size. Assume a page size of 8KB, with 8000 useful bytes after the page header, and dense indexes. Also assume each unclustered index is 2000 pages in size, from the ratio of data entry size (20 bytes) to record size (100 bytes) and the size of the whole table (10,000 pages). The clustered index is mostly the table itself, in its leaves, where there are 8000/100 = 80 records/leaf (a little less, really). The next level up has 10,000 index entries of about 20 bytes each, so 200,000/8000 pages = 25 pages, pretty negligible, but show it in calculations. The next level up is the root.

Sample answer: #rows in table = 80/page*10,000 pages = 800,000

a.       Sal > 100. Only #2 index matches.

Cost = index access + table access = .1*2000 + .1*800000 = 80,200 page i/os

Problem 4

Exercise 15.4 in the textbook (only sub-questions 2-3). Note that, the question in the book is incomplete, because you also need the total number of records. Assume that there are 500,000 records. Assume that the table size can also be used as any clustered index size.

Problem 5

Exercise 15.9 in the textbook (only sub-question 6, parts a,b as below). Change the sal condition from the ridiculous “sal = 50000” to “sal >= 50000 and sal < 50100”, still very selective and very important to the best plan selection. Assume nested-loop joins are to be used, and left-deep plans.

a.       1-relation plans: apply any selections, list RFs, index to use if any, and costs for these plans

2-relation plans: joins of two tables that join (have a join condition) in the query, with appropriate selections and/or index use. Draw all the possibilities.

3-relation plans: left-deep, draw all the possibilities, then argue where to put the sal selection and what indexes, if any, to use.

b.      Cost of the plan you argued for