|
|
|
@inproceedings{DBLP:conf/vldb/LorieY89,
author = {Raymond A. Lorie and
Honesty C. Young},
editor = {Peter M. G. Apers and
Gio Wiederhold},
title = {A Low Communication Sort Algorithm for a Parallel Database Machine},
booktitle = {Proceedings of the Fifteenth International Conference on Very
Large Data Bases, August 22-25, 1989, Amsterdam, The Netherlands},
publisher = {Morgan Kaufmann},
year = {1989},
isbn = {1-55860-101-5},
pages = {125-134},
ee = {db/conf/vldb/LorieY89.html},
crossref = {DBLP:conf/vldb/89},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
The paper considers the prcblem of sorting a file in a distributed system. The file is originally distributed on many sites, and the result of the sort isneeded 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.
Copyright © 1989 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.
