Sorting distributed data.

摘要

A fast method for sorting data in a distributed data processing system is disclosed. Each processor Pi 12i locally sorts its data into a local sorted file Si 34i, simultaneously producing an index to the sorted data and a file of key data records R min 32 each comprising a key value paired with the processor's identifier. Each processor produces a distribution table DTi 28i of its key values using the index, and sends the table to a coordinator processor 18 which merges the processors' tables into a global distribution table GDT 30. The global distribution table assigns subranges of key values to the processors, and is broadcast back to them. Each processor then sends each paired key value and processor identifier to the processor assigned by the global distribution table to handle the subrange containing that key value. The processors receive and merge the incoming key data records simultaneously as they send such pairs to other processors. An output stream Vi 36i consisting only of processor identifiers is created by each processor from the merged key value and processor identifier pairs, and is sent to the host H 16, which merges it into a global output stream of processor identifiers. The processors simultaneously send their local sorted files Si to the host, which reads records from them in the order specified by the global output stream V.