External sorting: I/O analysis and parallel processing techniques
Sai Choi Kwan · 1986
This thesis deals with sorting of data that are much too large to fit in main memory, or external sorting. We focus on two aspects of external sorting: I/O analysis and parallel processing techniques. Storage device models are defined and applied to analyze the I/O complexities of multi-way merge sort and tag sort (or key sort). We show that using higher merge orders, though reduces the number of merge passes, causes excessive random I/O accesses and degrades the overall I/O performance of multi-way merge sort. We develop techniques for producing long runs in merge sort and for rearranging the records in tag sort after their ranks have been determined. A lower bound for the I/O access time of rearranging the records in tag sort is derived. We explore two methods for implementing distribution sort on parallel computers. The first method, multi-pass distribution sort, determines the bucket ranges with one read pass over the input file, and uses subsequent passes to distribute the data into buckets and sort them. The distribution and sorting of the buckets are processed in parallel using a two stage pipeline. The second method, one-pass distribution sort, coalesces the bucket partition, bucket distribution and sort bucket phases all together so that the input file needs to be processed only once. We report a primitive distributed merge sort implemented on a local area network. We indicate two parallel external merges for overcoming the serial nature of the network merge in the primitive distributed merge sort. The first method, two stage pipelined merge, overlaps the merges of the processors using pipeline processing. The second distributive parallel merge method combines the merge and distribution paradigms. This technique of partitioning the global (or network) merge processing among the processors is suitable for sorting distributed files that do not change drastically in between of sort invocations.