Low communication sort algorithm for a parallel database machine

Abstract

The paper considers the problem of sorting a file in a distributed system. The file is originally distributed on many sites, and the result of the sort is needed at another site called the 'host'. The particular environment that we assume is a backend parallel database machine, but the work is applicable to distributed database systems as well. After discussing the drawbacks of several existing algorithms, we propose a novel algorithm that exhibits complete parallelism during the sort, merge, and return-to-host phases. In addition, this algorithm decreases the amount of inter-processor communication compared to existing parallel sort algorithms. We describe an implementation of the algorithm, present performance measurements, and use a validated model to demonstrate its scalability. We also discuss the effect of an uneven distribution of data among the various processors.