W4112 Database Systems Implementation, Spring 2022
Homework 2, due 3/4/2022.
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.
Copyright By PowCoder代写 加微信 powcoder
(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-sharing and answer the following:
(a) Explain the concept of scan sharing. What performance advantages does it offer? 1
(b) In a system that uses scan sharing, how would cost estimation for concurrent queries that access a common large table be different from what we’ve discussed in class?
(c) The idea that one might optimize the total cost of a collection of queries at once (rather than each query separately) is called multi-query optimization. Why is multi-query optimization appropriate in a system that uses scan-sharing? Give an example where separate query optimization of a set of queries would lead to different plans compared to joint optimization of all queries in the set.
5. Consider a query
SELECT R.A, S.B, T.C
FROM R, S, T
WHERE R.D=S.E and R.F=T.G AND T.H < 7
(a) Show two different query plans (trees) that could potentially be generated by a dynamic program- ming query optimization algorithm on this query.
(b) For each of the two plans from part (a) above, what properties of the data in the three underlying tables might make that plan optimal? (Exact computation of query costs is not required.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com