I/O Characteristics and Performance of External Sorting

Database Characteristics

Database page size: KiB
Available working space in database buffer (B): pages (that's MiB)
I/O blocking factor (b): pages

Disk Characteristics

Disk seek time: ms
Disk read/write speed: MiB/s
Resulting transfer time for a KiB block: ms

Size of Sort Problem

Size of input file to be sorted: GiB (this makes for N = pages of input)

---

Resulting External Sort Behavior

Pass 0 will produce runs, each of size pages but the last run (which only has pages).
We will need merge passes, with a fan-in of . (This is a two-way merge sort.)

Resulting I/O and Disk Seek Effort

The sort process will initiate I/O operations (reads and writes) and disk head seeks.

Resulting Overall Time for Sort Process

Disk seeking will need minutes, while minutes is spent on I/O itself.
Overall, we end up waiting minutes hours for the sort result.