SORTING SYSTEM AND METHOD EXECUTED BY PLURAL COMPUTERS FOR SORTING AND DISTRIBUTING DATA TO SELECTED OUTPUT NODES

• US 20020065793A1
• Filed: 08/02/1999
• Published: 05/30/2002
• Est. Priority Date: 08/03/1998
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Hitachi, Ltd.
• Inventors: YAMAMOTO, AKIRA, ARAKAWA, HIROSHI, OHATA, HIDEO, HONMA, SHIGEO
• Granted Patent: US 6,424,970 B1
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 7/36 Combined merging and sorting
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A sorting system includes a plurality of input nodes, each of which sorts sorting target data distributed and stored in input local disks. An internally sorted result is stored as a plurality of sorted strings in a shared disk connected between the input node and output node. Upon reception of a merge instruction from all input nodes, the output node reads the sorted string from the shared disk and merges it and outputs a whole sorted result of all input data to an output local disk. In a process of obtaining a whole sorted result of all input data through parallel processing by a computer system constituted of a plurality of computers (nodes), a time to sorting input data can be shortened.

Claims

1. A sorting system comprising:

a plurality of input nodes;

one output node; and

a shared external storage unit connected between each of said input units and said output unit, wherein;

each of said input units comprises;

a first buffer;

means for storing sorting target data in said first buffer;

means for internally sorting data in said first buffer in accordance with a predetermined sorting rule; and

means for storing as a sorted string an internally sorted result in said shared external storage unit; and

said output node comprises;

a second buffer;

means for storing in said second buffer the sorted string stored in said shared external storage unit;

means for merging a plurality of sorted strings stored in said second buffer, in accordance with the predetermined sorting rule; and

means for outputting a merged result as a sorted result.

2. A sorting system comprising:

a plurality of input nodes;

a plurality of output nodes; and

a shared external storage unit connected between each of said input units and each of said output units, wherein;

each of said input units comprises;

a first buffer;

means for storing sorting target data in said first buffer;

means for internally sorting data in said first buffer in accordance with a predetermined sorting rule;

means for classifying data in said first buffer in accordance with a predetermined classification rule; and

means for storing as a sorted string an internally sorted result in said shared external storage unit, in accordance with the predetermined classification rule; and

said output node comprises;

a second buffer;

means for storing in said second buffer the sorted string stored in said shared external storage unit;

means for merging a plurality of sorted strings stored in said second buffer, in accordance with the predetermined sorting rule; and

means for outputting a merged result as a sorted result.

3. A sorting system comprising:

a plurality of nodes;

a dedicated external storage unit provided for each of said plurality of nodes; and

a shared external storage unit provided between each pair of nodes of said plurality of nodes, wherein;

at least one node among said plurality of nodes comprises;

a first buffer;

means for storing sorting target data in said first buffer;

means for internally sorting data in said first buffer in accordance with a predetermined sorting rule;

means for sorting as a sorted string an internally sorted result in said dedicated external storage unit;

a second buffer;

means for storing in said second buffer the sorted string stored in said shared external storage unit and said dedicated external storage unit;

means for merging a plurality of sorted strings stored in said second buffer, in accordance with the predetermined sorting rule; and

means for outputting a merged result as a sorted result.

4. A sorting system comprising:

a plurality of nodes;

a dedicated external storage unit provided for each of said plurality of nodes; and

a shared external storage unit provided between each pair of nodes of said plurality of nodes, wherein;

at least one node among said plurality of nodes comprises;

a first buffer;

means for storing sorting target data in said first buffer;

means for internally sorting data in said first buffer in accordance with a predetermined sorting rule;

means for classifying data in said first buffer in accordance with a predetermined classification rule;

means for sorting as a sorted string an internally sorted result in said dedicated external storage unit, in accordance with the predetermined classification rule;

a second buffer;

means for storing in said second buffer the sorted string stored in said shared external storage unit and said dedicated external storage unit;

means for merging a plurality of sorted strings stored in said second buffer, in accordance with the predetermined sorting rule; and

means for outputting a merged result as a sorted result.

5. A sorting system according to claim 4, wherein said first and second buffers are a same buffer.

6. A sorting method for a sorting system having a plurality of input nodes, one output node, and a shared external storage unit connected between each of the input units and the output unit, the method comprising the steps of:

storing sorting target data in the input node and internally sorting the sorting target data in accordance with a predetermined sorting rule;

storing as a sorted string an internally sorted result in the shared external storage unit; and

reading the sorted string from the shared external storage unit, storing the sorted string in the output node, and merging the sorted string in accordance with the predetermined sorting rule.

7. A sorting method for a sorting system having a plurality of input nodes, a plurality of output nodes, and a shared external storage unit connected between each of the input units and each of the output units, the method comprising the steps of:

storing sorting target data in each of the input nodes;

classifying and internally sorting the read sorting target data in accordance with a predetermined classification rule and a predetermined sorting rule;

distributing and storing a classified and sorted result in the shared external storage units shared with the output nodes, in accordance with the predetermined classification rule;

performing a process from said storing step to said distributing and storing step for all sorting target data; and

thereafter reading the sorted string from the shared external storage units shared with the input nodes, storing the sorted string in each output node, and merging the sorted string in accordance with the predetermined sorting rule.

8. A sorting method for a sorting system having a plurality of nodes, a dedicated external storage unit provided for each of the plurality of nodes, and a shared external storage unit provided between each pair of nodes of the plurality of nodes, the method comprising the steps of:

storing sorting target data in each of the input nodes and internally sorting the sorting target data in accordance with a predetermined sorting rule;

storing as a sorted string an internally sorted result in the dedicated or shared external storage unit;

performing said internal sorting step and said sorted string storing step for all sorting target data; and

thereafter reading each sorted string from the dedicated and shared external storage units at one of the plurality of nodes and merging each sorted string in accordance with the predetermined sorting rule.

9. A sorting method for a sorting system having a plurality of nodes, a dedicated external storage unit provided for each of the plurality of nodes, and a shared external storage unit provided between each pair of nodes of the plurality of nodes, the method comprising the steps of:

storing sorting target data in at least one of the plurality of nodes;

classifying and internally sorting the read sorting target data in accordance with a predetermined classification rule and a predetermined sorting rule;

distributing and storing as a sorted string a classified and internally stored result in the dedicated or shared external storage unit, in accordance with the classification rule;

performing a process from said storing step to said distributing and storing step for all sorting target data; and

thereafter reading each sorted string from the dedicated and shared external storage units at one of the plurality of nodes and merging each sorted string in accordance with the predetermined sorting rule.

10. A sorting method according to claim 9, wherein at least one node has a same buffer to be used for storing the sorting storage data and storing the sorted string.