ACM SIGMOD Anthology VLDB dblp.uni-trier.de

AlphaSort: A Cache-Sensitive Parallel External Sort.

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)
@article{DBLP:journals/vldb/NybergBCGL95,
  author    = {Chris Nyberg and
               Tom Barclay and
               Zarka Cvetanovic and
               Jim Gray and
               David B. Lomet},
  title     = {AlphaSort: A Cache-Sensitive Parallel External Sort},
  journal   = {VLDB J.},
  volume    = {4},
  number    = {4},
  year      = {1995},
  pages     = {603-627},
  ee        = {db/journals/vldb/NybergBCGL95.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A new sort algorithm, called AlphaSort, demonstrates that commodity processors and disks can handle commercial batch workloads. Using commodity processors, 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 one minute. AlphaSort is a cache-sensitive, memory-intensive sort algorithm. We argue that modern architectures require algorithm designers to re-examine their use of the memory hierarchy. AlphaSort uses clustered data structures to get good cache locality, file striping to get high disk bandwidth, QuickSort to generate runs, and 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 one minute, and (2) PennySort: how much can you sort for one penny.

Copyright © 1995 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.

Key Words

Sort, cache, disk, memory, striping, parallel, Alpha, Dec 7000.

Preliminary Version: SIGMOD 1994: 233-242

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[Anon et al. 1989]
...
[Baer & Lin 1989]
Jean-Loup Baer, Yi-Bing Lin: Improving Quicksort Performance with a Codewort Data Structure. IEEE Trans. Software Eng. 15(5): 622-631(1989) BibTeX
[Baugsto & Greipsland 1989]
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
[Baugsto et al. 1990]
...
[Beck et al. 1988]
Micah Beck, Dina Bitton, W. Kevin Wilkinson: Sorting Large Files on a Backend Multiprocessor. IEEE Trans. Computers 37(7): 769-778(1988) BibTeX
[Bitton 1981]
...
[Connor 1977]
...
[Cvetanovic & Bhandarkar 1994]
Zarka Cvetanovic, Dileep Bhandarkar: Characterization of Alpha AXP Performance Using TP and SPEC Workloads. ISCA 1994: 60-70 BibTeX
[DeWitt et al. 1992]
David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider: Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting. PDIS 1991: 280-291 BibTeX
[Graefe 1990]
...
[Graefe & Thakkar 1992]
Goetz Graefe, Shreekant S. Thakkar: Tuning a Parallel Database Algorithm on a Shared-memory Multiprocessor. Softw., Pract. Exper. 22(7): 495-517(1992) BibTeX
[Gray 1991]
Jim Gray (Ed.): The Benchmark Handbook for Database and Transaction Systems (1st Edition). Morgan Kaufmann 1991
Contents BibTeX
[Kaivalya 1993]
...
[Kim 1986]
Michelle Y. Kim: Synchronized Disk Interleaving. IEEE Trans. Computers 35(11): 978-988(1986) BibTeX
[Kitsuregawa et al. 1989]
Masaru Kitsuregawa, Weikang Yang, Shinya Fushimi: Evaluation of 18-stage Pipeline Hardware Sorter. IWDM 1989: 142-155 BibTeX
[Knuth 1973]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[Lorie & Young 1989]
Raymond A. Lorie, Honesty C. Young: A Low Communication Sort Algorithm for a Parallel Database Machine. VLDB 1989: 125-134 BibTeX
[Lorin 1974]
...
[Nyberg et al. 1994]
Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, David B. Lomet: AlphaSort: A RISC Machine Sort. SIGMOD Conference 1994: 233-242 BibTeX
[Salzberg et al. 1990]
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
[Tsukerman 1986]
...
[Weinberger 1986]
...
[Yamane & Take 1988]
Yasuo Yamane, R. Take: Parallel Partition Sort for Database Machines. IWDM 1987: 117-130 BibTeX

Referenced by

  1. Richard T. Snodgrass, Serge Abiteboul, Sophie Cluet, Michael J. Franklin, Guy M. Lohman, David B. Lomet, Gultekin Özsoyoglu, Raghu Ramakrishnan, Kenneth A. Ross, Timos K. Sellis, Patrick Valduriez: Reminiscences on Influential Papers. SIGMOD Record 28(1): 110-114(1999)
  2. Ramesh C. Agarwal: A Super Scalar Sort Algorithm for RISC Processors. SIGMOD Conference 1996: 240-246
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:31:25 2009