A Low Communication Sort Algorithm for a Parallel Database Machine.

@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}
}

Abstract

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.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb8997 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[1]

Micah Beck, Dina Bitton, W. Kevin Wilkinson: Sorting Large Files on a Backend Multiprocessor. IEEE Trans. Computers 37(7): 769-778(1988) BibTeX

[2]

Dina Bitton, David J. DeWitt, David K. Hsiao, Jai Menon: A Taxonomy of Parallel Sorting. ACM Comput. Surv. 16(3): 287-318(1984) BibTeX

[3]

...

[4]

Shimon Even: Parallelism in Tape-Sorting. Commun. ACM 17(4): 202-204(1974) BibTeX

[5]

...

[6]

...

[7]

Philip J. Janus, Edmund A. Lamagna: An Adaptive Method for Unknown Distributions in Distributive Partitioned Sorting. IEEE Trans. Computers 34(4): 367-372(1985) BibTeX

[8]

S. Lakshmivarahan, Sudarshan K. Dhall, Leslie L. Miller: Parallel Sorting Algorithms. Advances in Computers 23: 295-354(1984) BibTeX

[9]

Raymond A. Lorie, Jean-Jacques Daudenarde, Gary Hallmark, James W. Stamos, Honesty C. Young: Adding Intra-transaction Parallelism to an Existing DBMS: Early Experience. IEEE Data Eng. Bull. 12(1): 2-8(1989) BibTeX

[10]

...

[11]

...

Referenced by

1. Sven Helmer, Till Westmann, Guido Moerkotte: Diag-Join: An Opportunistic Join Algorithm for 1:N Relationships. VLDB 1998: 98-109
2. Sven Helmer, Guido Moerkotte: Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates. VLDB 1997: 386-395
3. Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, David B. Lomet: AlphaSort: A Cache-Sensitive Parallel External Sort. VLDB J. 4(4): 603-627(1995)
4. Goetz Graefe, Ann Linville, Leonard D. Shapiro: Sort versus Hash Revisited. IEEE Trans. Knowl. Data Eng. 6(6): 934-944(1994)
5. Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, David B. Lomet: AlphaSort: A RISC Machine Sort. SIGMOD Conference 1994: 233-242
6. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
7. Betty Salzberg, Alex Tsukerman, Jim Gray, Michael Stewart, Susan Uren, Bonnie Vaughan: FastSort: A Distributed Single-Input Single-Output External Sort. SIGMOD Conference 1990: 94-101
8. C. Mohan, Donald J. Haderle, Yun Wang, Josephine M. Cheng: Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques. EDBT 1990: 29-43
9. Balakrishna R. Iyer, Gary R. Ricard, Peter J. Varman: Percentile Finding Algorithm for Multiple Sorted Runs. VLDB 1989: 135-144