1. In class we saw that hash partitioning of a table T larger than RAM could be useful for various relational algebra operations.  Suppose our RAM is M blocks big.  Suppose also that (unlike what we covered in class) we separately count the number s of sequential I/O requests and the number r of random I/O requests. The overall cost would then be s * Cs + r * Cr  where Cs  is the cost of a sequential I/O and Cr  is the cost of a random I/O. For some devices, Cr  is much bigger than Cs .

In this question, we’ll try to convert some of the random I/Os into sequential I/Os.  In particular, instead of bringing in one block from the input, we’ll bring in k contiguous blocks at a time. Similarly, for each hash partition, we’ll buffer k blocks and only write out data to the disk in units of k contiguous blocks.

(a)  Calculate r and s for a single partitioning pass through the input, in terms of k and  |T | (the number of blocks in T).

(b) Write an inequality that represents the conditions on k and |T | that ensure the partitions will each fit in RAM after one partitioning pass.  For this question you may assume that the hash function perfectly partitions the data into equal-sized pieces.

(c)  How would your answer to the previous question change if you also implemented double buffering to overlap CPU and I/O latencies?

(d)  Given your answers above, how would you choose k in practice?

2.  Table R has 500,000,000 records, a clustering B-tree index on R.A, a secondary hash index on R.B, and a secondary B-tree index on (R.C, R.D).  A disk page holds 100 records from R on average, and tree nodes hold 500 records on average in a disk page.  According to the catalog, A is a key for the table, there are 1,000,000 distinct B values, 15,000 distinct C values, and 100 distinct D values.  For each of the SQL or relational algebra queries below, give the best access plan for the query and estimate its cost.  You can use Figure 15.3 for cost formulas, and assume tS   = 5 milliseconds and tT   = 0.1 milliseconds.

(a)  σA=5(R).

(b)  σB=5 (R).

(c)  σC=5(R).

(d)  σB=5  and C=5(R). (e)  σC=5  and D=5 (R). (f)  σB=5 or C=5(R).   (g)  σC=5 or D=5 (R).

(h)  Select C, sum(D) From R Group by C

(i)  Select D, sum(C) From R Group by D

3. We  saw  in  class  that  multidimensional  histograms  can  help  determine  selectivities  for  correlated columns. There are several ways to choose the bucket boundaries for such histograms. Take a look at http://www.vldb.org/conf/1997/P486.PDF and answer the following:

(a)  Based on Section 5 of that paper, explain how the MHIST-2 method chooses bucket boundaries for 2-dimensional histograms.  (Two paragraphs is about right.)

(b)  Based on  Section  7,  outline how the  authors determine that MHIST-2 performs well.   (Two paragraphs is plenty.)

4.  Take a look at https://www.ibm.com/docs/en/db2/11.1?topic=methods-scan-sharingand answer the following:

(a)  Explain the concept of scan sharing. What performance advantages does it offer?