AlphaSort: A RISC Machine Sort

Summary: AlphaSort is a cache-sensitive, memory-intensive sort for commodity hardware that completes the industry-standard sort benchmark in seven seconds, beating a 32-CPU Hypercube by 8:1. It uses file striping for disk bandwidth, QuickSort-based run generation, replacement-selection merges, and shared-memory multiprocessing; and introduces MinuteSort and DollarSort as startup-time benchmarks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2791
Venue: SIGMOD
Year: 1994
Pagerank: 0.00024507963
Overall Rank: 215 | 98.53%
DOI: 10.1145/191839.191884

Incoming Non-self Citations Over Time

Authors

1. Chris Nyberg (Digital Equipment Corporation)
2. Tom Barclay (Digital Equipment Corporation)
3. Zarka Cvetanovic (Digital Equipment Corporation)
4. Jim Gray (Digital Equipment Corporation)
5. Dave Lomet (Digital Equipment Corporation)

BibTeX Citation

@inproceedings{nyberg_sigmod94,
        title = {{AlphaSort: A RISC Machine Sort}},
        author = {Nyberg, Chris and Barclay, Tom and Cvetanovic, Zarka and Gray, Jim and Lomet, Dave},
        series = {{SIGMOD} '94},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/191839.191884},
        url = {https://dl.acm.org/doi/10.1145/191839.191884},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
58	The Merge/Purge Problem for Large Databases	1995	SIGMOD	0.00040116748
74	Cache Conscious Algorithms for Relational Query Processing	1994	VLDB	0.00037330605
109	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.000331207
204	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00025342994
209	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024932174
305	GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management	2006	SIGMOD	0.00021872796
545	Improving Index Performance through Prefetching	2001	SIGMOD	0.00016766463
826	High-Performance Sorting on Networks of Workstations	1997	SIGMOD	0.0001377339
1,291	Managing Intra-operator Parallelism in Parallel Database Systems	1995	VLDB	0.00011307625
1,717	Improving the Performance of List Intersection	2009	VLDB	9.9327227e-05
1,880	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5562066e-05
3,379	Cubetree: Organization of and Bulk Incremental Updates on the Data Cube	1997	SIGMOD	7.4582502e-05
3,396	A Super Scalar Sort Algorithm for RISC Processors	1996	SIGMOD	7.4473906e-05
4,955	Dynamic Memory Adjustment for External Mergesort	1997	VLDB	6.4297637e-05
9,172	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	5.3092396e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,299	A Low Communication Sort Algorithm for a Parallel Database Machine	1989	VLDB	0.00011258763

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,139	CellSort: High Performance Sorting on the Cell Processor	2007	VLDB
2	6,113	Patience is a Virtue: Revisiting Merge and Sort on Modern Processors	2014	SIGMOD
3	3,842	FastSort: A Distributed Single-Input Single-Output External Sort	1990	SIGMOD
4	2,667	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD
5	4,177	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB
6	678	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD
7	7,191	WiscSort: External Sorting For Byte-Addressable Storage	2023	VLDB
8	12,033	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD
9	712	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB
10	3,396	A Super Scalar Sort Algorithm for RISC Processors	1996	SIGMOD