Consider a relation r that takes up 100 blocks on disk If yo

Consider a relation r that takes up 100 blocks on disk. If you have exactly 8 blocks of memory available:

a) How many passes would be required to perform an external sort-merge? Recall that sortmerge requires 1 initial sorting phase + some number of merging passes. Please be clear if you are including the sorting phase in your answer or just number of merging steps.

b) What is the estimated block transfer cost of performing external sort-merge given these numbers? (100 blocks of data and 8 blocks of memory) Please do not count the final write of the sorted output.

c) How many memory blocks would you need to sort relation r in exactly 2 passes total (1 sorting phase + 1 merging phase)?

Solution

a)100/8 passes so 16 passes are required.

b) Estimated cost is for first 50 disks = (50*8)+100=500

c) for two passes (100/8)*2=32 blocks are required