%% Slide 7.19: Impact of blocked I/O on the performance of external sort


(1) Non-blocked I/O

B = 1000 buffer pages with 8KB each.
=> perform a (B - 1) = 999-way merge

File of 8GB: N = 1048576 pages
=> will need ceil(log_{B-1}(ceil(N/B))) = ceil(log_999(1049)) = 2 passes


Pass 0: 1049 runs with approx. 1000 pages each
        => 1049 read seeks + 1049 write seeks
           + approx. 2 * 1048576 pages sequential read/write I/Os
Pass 1: writes 2 runs (one with 999000 pages, one with 49576 pages)
        2 * 1048576 pages random read/write I/O (involves as many seeks)
Pass 2: writes 1 run
        2 * 1048576 pages random read/write I/O (involves as many seeks)

Total:

2 * 1049 + 4 * 1048576 seek time (each 8.5ms)     = 10.5h
6 * 1048576 pages I/O transfer time (each 0.13ms) = 13.6min
                              (58 MB/s => 0.13ms transfer time per page)






(2) With blocked I/O 
    Assume blocking factor b = 32 (perform 32-page read/writes instead
    of single page read/writes to account for the characteristics of
    secondary storage devices)
   
   B/b = 31
=> perform a (B/b - 1) = 30-way merge

File of 8GB: N = 1048576 pages
=> will need ceil(log_{B/b-1}(ceil(N/B))) = ceil(log_30(1049)) = 3 passes

Pass 0: 1049 runs with approx. 1000 pages each
        => 1049 read seeks + 1049 write seeks
           + approx. 2 * 1048576 pages sequential read/write I/Os
Pass 1: writes ceil(1049/30) = 35 runs with approx 30000 pages each
        => 35 * 30 * ceil(1000/b) read seeks (approx. 32800)
            |    |        |
            |    |        # of blocked reads per input run
            |    # of input runs per output run
            # of output runs generated
         + 35 * ceil(30000/b) write seeks (approx. 32800)                   
            |        |
            |        # of blocked writes per output run
            # of output runs generated
Pass 2: writes 2 runs (one with 9000000 pages, one with 148576 pages)
        approx. 2 * 32800 read/write seeks
Pass 3: writes 1 run
        approx. 2 * 32800 read/write seeks

Total:

2 * 1049 + 6 * 32800 seek time (each 8.5ms)     = 28.1min
8 * 1048576 pages transfer time (each 0.13ms)   = 18.1min