AlphaSort: A Cache-Sensitive Parallel External Sort
- 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.
- The main techniques to optimize its use of the processor cache
- QuickSort input record groups
- Rather than sort records, sort (key-prefix, pointer) pairs
- The runs generated by QuickSort are merged using a replacement-selection tree.
- Record sort wins Key-Prefix/Pointer sort if the size of records is small.