QVLDB AlphaSort A Cache-Sensitive Parallel External Sort.pdf

VLDB Journal, 4, 603-627 (1995), Stanley Y.W. Su, Editor 603 QVLDB AlphaSort: A Cache-Sensitive Parallel External Sort Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, and Dave Lomet Received September 8, 1994; revised version received, March 28, 1995; accepted March 28, 1995. Abstract. A new sort algorithm, called AlphaSort, demonstrates that commodity processors and disks can handle commercial batch workloads. Using commod- ity 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 clus- tered data structures to get good cache locality, file striping to get high disk band- width, QuickSort to generate runs, and replacement-selection to merge the runs. It uses shared memory multiprocessors to break the sort into subsort chores. Be- cause 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. Key Words. sort, cache, disk, memory, striping, parallel, Alpha, Dec 7000. 1. Introduction In 1985, an in formal group of 25 da tabase exper ts f rom a dozen compan ie s and univers i t ies def ined th ree basic benchmarks to measu re the t ransac t ion process ing p e r f o r m a n c e of c o m p u t e r systems. 1. DebitCredit: A marke t -ba ske t of da tabase reads and writes, t e rmina l IO, and t ransac t ion commits to measu re on- l ine t ransac t ion process ing p e r f o r m a n c e Chris Nyberg, M.S., is President, Ordinal Technology Corp., 20 Crestview Dr.