Consider a join RR.A-S.B S. We ignore the cost of output the result and measure the...

Transcribed Image Text:

Consider a join RR.A-S.B S. We ignore the cost of output the result and measure the cost with the number of I/O the number of data blocks that need to be transferred. Given the information about relations to be joined below: (1) Relation S contains 20K tuples and has 10 tuples per block; (2) Relation R contains 100K tuples and has 10 tuples per block. (3) Attribute B of S is the primary key of S. In total 52 pages (blocks) are available in memory. a. (10) Assume neither relation has any index. Describe a block nested join algorithm to evaluate the query. Give the cost of joining R and S with a block nested loops join. b. (20) Assume R contains 1000 blocks, 10,000 tuples; S contains 10,000 blocks, 50,000 tuples. There are clustering B+ tree index on R.A and S.B. Both indexes contain two levels with the root note in the first level and all leaf nodes in the second level. The indexes on R.A has 25 leaf nodes; the index on S.B contain 250 leaf nodes. Describe *two* algorithms that can correctly compute GR.ARRA-S.B S and give the corresponding cost measured by the number of block transfers. (There are multiple solutions; describing any two correct algorithms with cost analysis suffice). Consider a join RR.A-S.B S. We ignore the cost of output the result and measure the cost with the number of I/O the number of data blocks that need to be transferred. Given the information about relations to be joined below: (1) Relation S contains 20K tuples and has 10 tuples per block; (2) Relation R contains 100K tuples and has 10 tuples per block. (3) Attribute B of S is the primary key of S. In total 52 pages (blocks) are available in memory. a. (10) Assume neither relation has any index. Describe a block nested join algorithm to evaluate the query. Give the cost of joining R and S with a block nested loops join. b. (20) Assume R contains 1000 blocks, 10,000 tuples; S contains 10,000 blocks, 50,000 tuples. There are clustering B+ tree index on R.A and S.B. Both indexes contain two levels with the root note in the first level and all leaf nodes in the second level. The indexes on R.A has 25 leaf nodes; the index on S.B contain 250 leaf nodes. Describe *two* algorithms that can correctly compute GR.ARRA-S.B S and give the corresponding cost measured by the number of block transfers. (There are multiple solutions; describing any two correct algorithms with cost analysis suffice).