AlphaSort: A RISC Machine Sort.

@inproceedings{DBLP:conf/sigmod/NybergBCGL94,
  author    = {Chris Nyberg and
               Tom Barclay and
               Zarka Cvetanovic and
               Jim Gray and
               David B. Lomet},
  editor    = {Richard T. Snodgrass and
               Marianne Winslett},
  title     = {AlphaSort: A RISC Machine Sort},
  booktitle = {Proceedings of the 1994 ACM SIGMOD International Conference on
               Management of Data, Minneapolis, Minnesota, May 24-27, 1994},
  publisher = {ACM Press},
  year      = {1994},
  pages     = {233-242},
  ee        = {http://doi.acm.org/10.1145/191839.191884, db/conf/sigmod/NybergBCGL94.html},
  crossref  = {DBLP:conf/sigmod/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A new sort algorithm, called AlphaSort, demonstrates that commodity processors and disks can handle commercial batch workloads. Using Alpha AXP processors, commodity memory, and arrays of SCSI disks, AlphaSort runs the industry-standard sort benchmark in seven seconds. This beats the best published record on a 32-cpu 32-disk Hypercube by 8:1. On another benchmark, AlphaSort sorted more than a gigabyte in a minute.

AlphaSort is a cache-sensitive memory-intensive sort algorithm. It uses file striping to get high disk bandwidth. It uses QuickSort to generate runs and uses replacement-selection to merge the runs. It uses shared memory multiprocessors to break the sort into subsort chores.

Because startup times are becoming a significant part of the total time, we propose two new benchmarks: (1) MinuteSort: how much can you sort in a minute, and (2) DollarSort: how much can you sort for a dollar.

Copyright © 1994 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

• 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/smod9397 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

Online Edition: ACM Digital Library

References

[1]

...

[2]

Jean-Loup Baer, Yi-Bing Lin: Improving Quicksort Performance with a Codewort Data Structure. IEEE Trans. Software Eng. 15(5): 622-631(1989) BibTeX

[3]

Bjørn Arild W. Baugstø, Jarle Fredrik Greipsland: Parallel Sorting Methods for Large Data Volumes on a Hypercube Database Computer. IWDM 1989: 127-141 BibTeX

[4]

...

[5]

...

[6]

...

[7]

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

[8]

...

[9]

David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider: Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting. PDIS 1991: 280-291 BibTeX

[10]

...

[11]

...

[12]

Goetz Graefe, Shreekant S. Thakkar: Tuning a Parallel Database Algorithm on a Shared-memory Multiprocessor. Softw., Pract. Exper. 22(7): 495-517(1992) BibTeX

[13]

Jim Gray (Ed.): The Benchmark Handbook for Database and Transaction Systems (1st Edition). Morgan Kaufmann 1991
Contents BibTeX

[14]

...

[15]

Masaru Kitsuregawa, Weikang Yang, Shinya Fushimi: Evaluation of 18-stage Pipeline Hardware Sorter. IWDM 1989: 142-155 BibTeX

[16]

Michelle Y. Kim: Synchronized Disk Interleaving. IEEE Trans. Computers 35(11): 978-988(1986) BibTeX

[17]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX

[18]

Raymond A. Lorie, Honesty C. Young: A Low Communication Sort Algorithm for a Parallel Database Machine. VLDB 1989: 125-134 BibTeX

[19]

...

[20]

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 BibTeX

[21]

...

[22]

...

[23]

...

Referenced by

1. Richard T. Snodgrass: Reminiscences on Influential Papers. SIGMOD Record 28(3): 43-48(1999)
2. Kenneth A. Ross: Review - AlphaSort: A RISC Machine Sort. ACM SIGMOD Digital Review 1: (1999)
3. Jun Rao, Kenneth A. Ross: Cache Conscious Indexing for Decision-Support in Main Memory. VLDB 1999: 78-89
4. Peter A. Boncz, Stefan Manegold, Martin L. Kersten: Database Architecture Optimized for the New Bottleneck: Memory Access. VLDB 1999: 54-65
5. Anastassia Ailamaki, David J. DeWitt, Mark D. Hill, David A. Wood: DBMSs on a Modern Processor: Where Does Time Go? VLDB 1999: 266-277
6. Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter: Scalable Sweeping-Based Spatial Join. VLDB 1998: 570-581
7. Joseph M. Hellerstein: Online Processing Redux. IEEE Data Eng. Bull. 20(3): 20-29(1997)
8. Weiye Zhang, Per-Åke Larson: Dynamic Memory Adjustment for External Mergesort. VLDB 1997: 376-385
9. Nick Roussopoulos, Yannis Kotidis, Mema Roussopoulos: Cubetree: Organization of and Bulk Updates on the Data Cube. SIGMOD Conference 1997: 89-99
10. Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, David E. Culler, Joseph M. Hellerstein, David A. Patterson: High-Performance Sorting on Networks of Workstations. SIGMOD Conference 1997: 243-254
11. Ramesh C. Agarwal: A Super Scalar Sort Algorithm for RISC Processors. SIGMOD Conference 1996: 240-246
12. Gennady Antoshenkov, David B. Lomet, James Murray: Order Preserving Compression. ICDE 1996: 655-663
13. 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)
14. Manish Mehta, David J. DeWitt: Managing Intra-operator Parallelism in Parallel Database Systems. VLDB 1995: 382-394
15. Mauricio A. Hernández, Salvatore J. Stolfo: The Merge/Purge Problem for Large Databases. SIGMOD Conference 1995: 127-138
16. Ambuj Shatdal, Chander Kant, Jeffrey F. Naughton: Cache Conscious Algorithms for Relational Query Processing. VLDB 1994: 510-521
17. Jim Gray, Prakash Sundaresan, Susanne Englert, Kenneth Baclawski, Peter J. Weinberger: Quickly Generating Billion-Record Synthetic Databases. SIGMOD Conference 1994: 243-252
18. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)