EP0377993A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Sorting distributed data
Assignee: International Business Machines Corp
•
Filing: 1989-12-20
•
Granted: —
•
Expires: 2009-12-20
Abstract
Abstract A fast method for sorting data in a distributed data processing system is disclosed. Each processor P i 12i locally sorts its data into a local sorted file S 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 i 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 V 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 i to the host, which reads records from them in the order specified by the global output stream V.
Inventors
- 👤 Raymond Amand Lorie
- 👤 Honesty Cheng Young
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-02 23:25
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/22; G06F7/24
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
127 words
A method for sorting data in a distributed system having at least two processors each storing data, and communications means for communicating between the processors, the method comprising the steps of: (a) for each processor, sorting its stored data by key value; (b) determining a global key value distribution of at least two subranges; (c) assigning each subrange to a target processor; (d) for each processor, communicating means for identifying the processor together with the processor's key values to the values' respective assigned target processors; (e) for each target processor, creating sort sequence data representing a sorted merger of the key values received from the processors; and (f) receiving by a user each processor s sorted data according to the order specified by the sort sequence data.
Claim 2
Independent Claim
127 words
A method for sorting data in a distributed system having at least two processors each storing data, and communications means for communicating between the processors, the method comprising the steps of: (a) for each processor, sorting its stored data by key value; (b) determining a global key value distribution of at least two subranges; (c) assigning each subrange to a target processor; (d) for each processor, communicating means for identifying the processor together with the processor's key values to the values' respective assigned target processors; (e) for each target processor, creating sort sequence data representing a sorted merger of the key values received from the processors; and (f) receiving by a user each processor s sorted data according to the order specified by the sort sequence data.
Claim 3
Dependent Claim
27 words
A method as claimed in claim 1, wherein step (a) creates a local sorted file; and wherein step (f) sends the local sorted files to the user.
Claim 4
Dependent Claim
21 words
A method as claimed in claim 1, wherein the global key value distribution is based on the processors' key value distributions.
Claim 5
Dependent Claim
20 words
A method as claimed in claim 3, wherein a key value distribution for each processor is created during step (a).
Claim 6
Dependent Claim
24 words
A method as claimed in claim 3, wherein the global distribution is created by a coordinator processor by merging the processors' key value distributions.
Claim 7
Dependent Claim
16 words
A method as claimed in claim 5, wherein the coordinator processor is one of the processors.
Claim 8
Dependent Claim
25 words
A method as claimed in claim 1, wherein step (d) communicates key data records, each consisting of a key value and the local processor's identifier.
Claim 9
Dependent Claim
17 words
A method as claimed in claim 1, wherein the sort sequence data consists of only processor identifiers.
Claim 10
Dependent Claim
15 words
A method as claimed in claim 1, wherein steps (d) and (e) are performed concurrently..
Claim 11
Independent Claim
245 words
A method for sorting data in a distributed data processing system having at least two processors, storage means attached to each processor for storing data, communications means for communicating between each of the processors, and requestor means for requesting sorting of the processors' data, the method comprising the steps of: (a) communicating a sort request from the requestor means to the processors; (b) for each processor, sorting data stored in the processor's storage means into local sorted files, and determining a distribution of key values of that data; (c) producing a global key value distribution from the processors' key value distributions, the global distribution dividing the range of key values into at least two subranges; (d) assigning each subrange of key values to target ones of the processors; (e) for each processor, communicating that processor's key values to their respective assigned target processors, together with means for identifying the sending processor; (f) for each target processor, merging the key values received from the processors to produce a sorted subrange of the range of key values, such that data taken from the processors' local sorted files in the order specified by the representations of the sorted subrange are in sorted order; (g) for each target processor, communicating at least a representation of the sorted subrange to the requestor; and (h) processing by the requestor records received from the processors local sorted files in the order specified by the representations of the sorted subrange of key values.
Claim 12
Independent Claim
245 words
A method for sorting data in a distributed data processing system having at least two processors, storage means attached to each processor for storing data, communications means for communicating between each of the processors, and requestor means for requesting sorting of the processors' data, the method comprising the steps of: (a) communicating a sort request from the requestor means to the processors; (b) for each processor, sorting data stored in the processor's storage means into local sorted files, and determining a distribution of key values of that data; (c) producing a global key value distribution from the processors' key value distributions, the global distribution dividing the range of key values into at least two subranges; (d) assigning each subrange of key values to target ones of the processors; (e) for each processor, communicating that processor's key values to their respective assigned target processors, together with means for identifying the sending processor; (f) for each target processor, merging the key values received from the processors to produce a sorted subrange of the range of key values, such that data taken from the processors' local sorted files in the order specified by the representations of the sorted subrange are in sorted order; (g) for each target processor, communicating at least a representation of the sorted subrange to the requestor; and (h) processing by the requestor records received from the processors local sorted files in the order specified by the representations of the sorted subrange of key values.
Claim 13
Dependent Claim
38 words
A method as claimed in claim 10, wherein the distribution of key values for each processor comprises a distribution table of key values, and wherein the global key value distribution comprises a global distribution table of key values.
Claim 14
Dependent Claim
56 words
A method as claimed in claim 11, wherein step (b) comprises for each processor the steps of: (b1) sorting the data by key value to produce a local sorted file, (b2) producing a local index of the key values of the local sorted file, and (b3) producing the processor's key value distribution using the local index.
Claim 15
Dependent Claim
21 words
A method as claimed in claim 11, wherein step (c) produces the global distribution table by merging the processors' distribution tables.
Claim 16
Dependent Claim
45 words
A method as claimed in claim 13, wherein step (c) comprises the steps of: (c1) selecting a coordinator processor; (c2) communicating the local key value distributions from the processors to the coordinator; and (c3) merging the local distribution tables to produce the global distribution table.
Claim 17
Independent Claim
66 words
A method as claimed in any of claims 11 to 14, wherein step (d) comprises broadcasting the global key value distribution to the processors over the communication means and wherein step (e) comprises for each processor the step of communicating key data records each consisting of a key value and the local processor's identifier to the target processors according to the assignments of the global distribution.
Claim 18
Independent Claim
34 words
A method as claimed in any of claims 10 to 15, wherein the key data records are produced during step (b) and wherein the processors' local sorted files are communicated concurrently to the requestor.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.