Database Systems Questions:

Double Buffering with IO

This problem explores an optimization often referred to as double buffering, which we'll use to speed up the external merge sort algorithm.

Consider a modification of the external merge sort algorithm where reads are always read in 4-page chunks (i.e. 4 pages sequentially at a time) so as to take advantage of sequential reads. Calculate the cost of performing the external merge sort for a setup having B + 1 = 20 buffer pages and an unsorted input file with 160 pages.

Show the steps of your work and make sure to explain your reasoning by writing them as python comments above the final answers.

a) Give the exact IO cost of spliting and sorting the files? As is standard we want runs of size B + 1

b) How many passes of merging are required?

c) What is the IO cost of the first pass of merging? Note: the highest arity merge should always be used.

d) What is the total IO cost of running this external merge sort algorithm? Do not forget to add in the remaining passes (if any) of merging.