Let there be an unclustered hash index on ProfId and assume that, as before, 5 Professor tuples ?t in one page, 10 Teaching tuples ?t in one page, and the cardinality of Teaching is 10,000. Estimate the cost of computing the above join using index-nested loops and block-nested loops with a 51-page bu?er.

Question

Consider the join Professor  Id=ProfId Teaching used in the running example of Section 11.3. Let us change the statistics slightly and assume that the number of distinct values for Teaching.ProfId is 10,000 (which translates into lower weight for
this attribute).

Answer 1

Since in the previous problem we concluded that Professor has 10,000 tuples and there are 5 tuple/page, this relation will have 2,000 pages. For Teaching,the statistics do not change: 10,000 tuples, 1,000 pages.
For index-nested loops join, we scan Professor and use the index on ProfId to fetch the matching tuples in Teaching. Since there are 10,000 tuples in Teaching and 10,000 values of ProfId, there is 1 matching tuple per value. So, the unclustered nature of the index on ProfId does not matter. There is going to be 1.2*10,000 page transfers in order to ?nd all matching tuples in Teaching plus the cost of the scan of Professor is 2,000. The total cost is 14,000 page transfers.
For the block-nested loops join, we scan the smaller relation, Teaching,in the outer loop. Since we have 51 bu?er pages, we use 49 for Teaching,one for Professor, and one for the output bu?er. Thus, we will scan Professor once for every 49-page block of Teaching: 1000/49 = 21 scans. So, the cost is 21*2,000 + 1,000 = 43,000 page transfers.