Method for sorting using approximate key distribution in a distributed

Abstract

A fast method for sorting data in a distributed data processing system is disclosed. Each processor P.sub.1 12i locally sorts its data into a local sorted file S.sub.i 34i, simultaneously producing an index to the sorted data and a file of key data records R' 32 each comprising a key value paired with the processor's identifier. Each processor produces a distribution table DT.sub.i 28i of its key values using the index, and sends the table to acoordinator processor 18 which merges the processors' tables into a global distribution table GST 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 V.sub.i 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 S.sub.i to the host, which reads records from them in the order specified by the global output stream V.