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.