Parallel merge and sort process method and system thereof

• US 5,640,554 A
• Filed: 10/12/1994
• Issued: 06/17/1997
• Est. Priority Date: 10/12/1993
• Status: Expired due to Term

• Current Assignee: Google Inc. (Alphabet Inc.)
• Original Assignee: Fujitsu Limited
• Inventors: Take, Riichiro
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Lintz, Paul R.
• Application Number:
  US08/321,772
• Time in Patent Office: 979 Days
• Field of Search: 395/600, 395/800, 395/650
• US Class Current: 1/1
• CPC Class Codes: G06F 7/36 Combined merging and sorting

Abstract

When a list to be sorted is divided into L sorted merge objective lists, each of the merge objective lists is formed of a plurality of blocks (where L is any natural number larger than or equal to 2). For each block, a block information record having a block identifier and a key value of a representative record of the block is generated. With the block information records, a first auxiliary information list is generated. The first auxiliary information list is sorted in a predetermined order of key values so as to generate a second auxiliary information list. The second auxiliary information list is almost equally divided into P portions (where P is any natural number larger than or equal to 2). For each of the P sub-auxiliary information lists, a forward boundary value and a backward boundary value are set corresponding to a predetermined rule. The P sub-auxiliary information lists are allocated to P process units. Each of the P process units retrieves a portion (segment) corresponding to the sub-auxiliary information list from the L sorted merge objective lists and merges blocks of the segment.

Claims

1. A merge and sort process method for dividing a data sequence to be sorted into a plurality of sorted data sequences and merging the sorted data sequences, comprising the steps of:

(1) dividing the data sequence to be sorted into L sorted data sequences, each of which is formed of a plurality of blocks where L is any natural number larger than or equal to 2;

(2) generating a block information record for each block in the sorted data sequences, the block information record having identification information of the block and representative data thereof and arranging the block information records so as to generate a first auxiliary information record group;

(3) arranging the block information records of the first auxiliary information record group in a predetermined order corresponding to values of the representative data so as to generate a second auxiliary record group;

(4) dividing the second auxiliary record group into P sub-auxiliary information record groups, each of which has nearly the same number of the block information records where P is any natural number larger than or equal to 2; and

(5) allocating the P sub-auxiliary information record groups to a plurality of process units adapted for merging blocks corresponding to the block information records of the sub-auxiliary information record groups of the L sorted data sequences allocated to the process units in parallel and for merging the P sorted data sequences so as to sort the data sequence to be merged in a predetermined order.

2. The parallel merge and sort process method as set forth in claim 1,

wherein the step (1) is performed by storing the L sorted data sequences that are an arrangement of blocks in a secondary memory unit, and

wherein the step (2) is performed by setting information necessary for accessing a block of the secondary memory unit as block identification information of the block information record and selecting the first data of the block.

3. The parallel merge and sort process method as set forth in claim 2,

wherein the block has a fixed length, and

wherein the step (2) is performed by setting an identifier as the identification information of the block.

4. The parallel merge and sort process method as set forth in claim 3,

wherein the block is a data input/output unit of the secondary memory unit.

5. The parallel merge and sort process method as set forth in claim 2,

wherein the block has a variable length,

wherein the step (2) is performed by setting information for specifying a storage address of the secondary memory unit for the block as the identification information of the block.

6. The parallel merge and sort process method as set forth in claim 1,

wherein the step (5) is performed by allocating the P sub-auxiliary record groups to the P process units adapted for merging the L sorted data sequences corresponding to the sub-auxiliary information record groups allocated thereto in parallel.

7. The parallel merge and sort process method as set forth in claim 1,

wherein the data sequence to be sorted is a list of a plurality of records linked,

wherein the step (1) is performed by dividing the list to be sorted into L sorted merge objective lists, each of which is formed of a plurality of blocks,

wherein the step (2) is performed by generating a block information record for each block of the divided merge objective lists, the block information record having identification information of the block and a representative record of the block so as to generate the first auxiliary information record group formed of the block information records,

wherein the step (3) is performed by sorting the information records of all the blocks of the first auxiliary information record group in a predetermined order of values of sort keys so as to generate the second auxiliary information record group,

wherein the step (4) is performed by dividing the second auxiliary record group into P sub-auxiliary record groups, each of which has the same number of the block information records, and

wherein the step (5) is performed by allocating the P sub-auxiliary record groups to the process units adapted for merging blocks corresponding to the block information records of the sub-auxiliary information record groups of the L sorted merge objective list allocated to the process units in parallel and for merging the P sorted lists so as to sort the data sequence to be merged in a predetermined order.

8. The parallel merge and sort process method as set forth in claim 7,

wherein the L sorted lists are divided into blocks and stored in the secondary memory unit, and

wherein the block identification information of the block information records of the second auxiliary information record group is information necessary for the secondary memory unit to access a corresponding block, and

wherein the sort key value is the value of a key of the first record of the block.

9. The parallel merge and sort process method as set forth in claim 8,

wherein all the records of the L sorted lists are sorted in the ascending order of the key values,

wherein the step (4) includes

(a) dividing the second auxiliary information record group into P sub-auxiliary information record groups, each of which has nearly the same number of the block information records,

(b) setting a key value of the first block information record to a forward boundary value of each of the P sub-auxiliary information record groups,

(c) setting a key value of the first block information record of the sub-auxiliary information record group to a backward boundary value when the sub-auxiliary information record group is followed by another sub-auxiliary information record group and setting a value larger than the maximum key value of the records of the sort objective list to the backward boundary value when the sub-auxiliary information record group is not followed by another sub-auxiliary information record group, and

(d) extracting block information records corresponding to all blocks that may contain records with key values larger than or equal to the forward boundary value of a first sub-auxiliary information record group from a second sub-auxiliary information record group and adding the extracted block information records to the beginning of the first sub-auxiliary information record group when the first sub-auxiliary information record group is preceded by the second sub-auxiliary information record group, and

wherein the step (5) is performed by causing each of the process units to merge records of blocks corresponding to the block information records of the sub-auxiliary information record group allocated to the process unit when key values of the records are larger than or equal to the forward boundary value of the sub-auxiliary information record group and less than the backward boundary value thereof.

10. The parallel merge and sort process method as set forth in claim 7,

wherein the L sorted lists are divided into blocks and stored in the secondary memory unit, and

wherein the block identification information of the block information records of the second auxiliary information record group is information necessary for the secondary memory unit to access a corresponding block, and

wherein the sort key value is the value of a key of the last record of the block.

11. The parallel merge and sort process method as set forth in claim 10,

wherein the step (4) includes

(a) dividing the second auxiliary information record group into P sub-auxiliary information record groups, each of which has nearly the same number of the block information records,

(b) setting a key value of the last block information record of the sub-auxiliary information record group to a forward boundary value when the sub-auxiliary information record group is preceded by another sub-auxiliary information record group and setting a value smaller than the minimum key value of the records of the sort objective list to the forward boundary value when the sub-auxiliary information record group is not preceded by another sub-auxiliary information record group,

(c) setting a key value of the last block information record to a backward boundary value of each of the P sub-auxiliary information record groups, and

(d) extracting block information records corresponding to all blocks that may contain records with key values larger than the forward boundary value and smaller than or equal to the backward boundary value of a first sub-auxiliary information record group from a second sub-auxiliary information record group and adding the extracted block information records to the last of the first sub-auxiliary information record group when the first sub-auxiliary information record group is followed by the second sub-auxiliary information record group, and

wherein the step (5) is performed by causing each of the process units to merge records of blocks corresponding to the block information records of the sub-auxiliary information record group allocated to the process unit when key values of the records are larger than the forward boundary value of the sub-auxiliary information record group and less than or equal to the backward boundary value thereof.

12. The parallel merge and sort process method as set forth in claim 7,

wherein the step (4) is performed by dividing the second auxiliary information record group into P sub-auxiliary information record groups, each of which has nearly the same number of the block information records, and

wherein the step (5) is performed by allocating the P sub-auxiliary information record groups to the P process units adapted for merging segments formed of blocks corresponding to the block information records of the sub-auxiliary information record groups allocated to the process units.

13. The parallel merge and sort process method as set forth in claim 7,

wherein the block has a fixed length, and

wherein the step (2) is performed by setting an identifier as the identification information of the block.

14. The parallel merge and sort process method as set forth in claim 13,

wherein the block is data input/output from the secondary memory unit.

15. A merge and sort process system for dividing a data sequence to be sorted into a plurality of sorted data sequences and merging the sorted data sequences, comprising:

a plurality of process units;

first dividing means for dividing the data sequence to be sorted into L sorted data sequences, each of which is formed of a plurality of blocks where L is any natural number larger than or equal to 2;

first generating means for generating a block information record for each block in the sorted data sequences, the block information record having identification information of the block and representative data thereof and arranging the block information records so as to generate a first auxiliary information record group;

second generating means for arranging the block information records of the first auxiliary information record group in a predetermined order corresponding to values of the representative data so as to generate a second auxiliary record group;

second dividing means for dividing the second auxiliary record group in P sub-auxiliary information record groups, each of which has nearly the same number of the block information records where P is any natural number larger than or equal to 2;

allocating means for allocating the P sub-auxiliary information record groups to said process units; and

sorting means for causing said process units to merge blocks corresponding to the block information records of the sub-auxiliary information record groups of the L sorted data sequences allocated to said process units in parallel and for merging the P sorted data sequences so as to sort the merged data sequence in a predetermined order.

16. The parallel merge and sort process system as set forth in claim 15,

wherein said dividing means is adapted for storing the L sorted data sequences that are an arrangement of blocks in a secondary memory unit, and

wherein said first generating means is adapted for setting information necessary for accessing a block of the secondary memory unit as block identification information of the block information record and selecting the first data of the block.

17. The parallel merge and sort process system as set forth in claim 16,

wherein the block has a fixed length, and

wherein said first dividing means is adapted for setting an identifier as the identification information of the block.

18. The parallel merge and sort process system as set forth in claim 17,

wherein the block is a data input/output unit of the secondary memory unit.

19. The parallel merge and sort process system as set forth in claim 16,

wherein the block has a variable length, and

wherein said first generating means is adapted for setting information for specifying a storage address of the secondary memory unit for the block as the identification information of the block.

20. The parallel merge and sort process system as set forth in claim 19,

wherein said allocating means is adapted for allocating the P sub-auxiliary record groups to the P process units adapted, and

wherein said merging means is adapted for causing said process units to merge the L sorted data sequences corresponding to the sub-auxiliary information record groups allocated thereto in parallel.

21. The parallel merge and sort process system as set forth in claim 15,

wherein the data sequence to be sorted is a list of a plurality of records linked,

wherein said first dividing means is adapted for dividing the list to be sorted into L sorted merge objective lists, each of which is formed of a plurality of blocks,

wherein said first generating means is adapted for generating a block information record for each block of the divided merge objective lists, the block information record having identification information of the block and a representative record of the block so as to generate the first auxiliary information record group formed of the block information records,

wherein said second generating means is adapted for sorting the information records of all the blocks of the first auxiliary information record group in a predetermined order of values of sort keys so as to generate the second auxiliary information record group,

wherein said second dividing means is adapted for dividing the second auxiliary record group into P sub-auxiliary record groups, each of which has the same number of the block information records,

wherein said allocating means is adapted for allocating the P sub-auxiliary record groups to said process units, and

wherein said merging means is adapted for causing said process units to merge blocks corresponding to the block information records of the sub-auxiliary information record groups of the L sorted merge objective list allocated to said process units in parallel and for merging the P sorted lists so as to sort the data sequence to be merged in a predetermined order.

22. The parallel merge and sort process system as set forth in claim 21,

wherein the L sorted lists are divided into blocks and stored in the secondary memory unit, and

wherein said first generating means is adapted for setting the block identification information of the block information records of the second auxiliary information record group as information necessary for the secondary memory unit to access a corresponding block and setting the sort key value as the value of a key of the first record of the block.

23. The parallel merge and sort process system as set forth in claim 22,

wherein all the records of the L sorted lists are sorted in the ascending order of the key values,

wherein said allocating means includes:

means for dividing the second auxiliary information record group into P sub-auxiliary information record groups, each of which has nearly the same number of the block information records,

means for setting a key value of the first block information record to a forward boundary value of each of the P sub-auxiliary information record groups,

means for setting a key value of the first block information record of the sub-auxiliary information record group to a backward boundary value when the sub-auxiliary information record group is followed by another sub-auxiliary information record group and setting a value larger than the maximum key value of the records of the sort objective list to the backward boundary value when the sub-auxiliary information record group is not followed by another sub-auxiliary information record group, and

means for extracting block information records corresponding to all blocks that may contain records with key values larger than or equal to the forward boundary value of a first sub-auxiliary information record group from a second sub-auxiliary information record group and adding the extracted block information records to the beginning of the first sub-auxiliary information record group when the first sub-auxiliary information record group is preceded by the second sub-auxiliary information record group, and

wherein said merging means is adapted for causing each of said process units to merge records of blocks corresponding to the block information records of the sub-auxiliary information record group allocated to said process unit when key values of the records are larger than or equal to the forward boundary value of the sub-auxiliary information record group and less than the backward boundary value thereof.

24. The parallel merge and sort processing system as set forth in claim 21,

wherein the L sorted lists are divided into blocks and stored in the secondary memory unit, and

wherein said first generating means is adapted for setting the block identification information of the block information records of the second auxiliary information record group as information necessary for the secondary memory unit to access a corresponding block and setting the sort key value as the value of a key of the last record of the block.

25. The parallel merge and sort process system as set forth in claim 24,

wherein said allocating means includes:

means for dividing the second auxiliary information record group into P sub-auxiliary information record groups, each of which has nearly the same number of the block information records,

means for setting a key value of the last block information record of the sub-auxiliary information record group to a forward boundary value when the sub-auxiliary information record group is preceded by another sub-auxiliary information record group and setting a value smaller than the minimum key value of the records of the sort objective list to the forward boundary value when the sub-auxiliary information record group is not preceded by another sub-auxiliary information record group,

means for setting a key value of the last block information record to a backward boundary value of each of the P sub-auxiliary information record groups, and

means for extracting block information records corresponding to all blocks that may contain records with key values larger than the forward boundary value and smaller than or equal to the backward boundary value of a first sub-auxiliary information record group from a second sub-auxiliary information record group and adding the extracted block information records to the end of the first sub-auxiliary information record group when the first sub-auxiliary information record group is followed by the second sub-auxiliary information record group, and

wherein said merging means is adapted for causing each of said process units to merge records of blocks corresponding to the block information records of the sub-auxiliary information record group allocated to said process unit when key values of the records are larger than the forward boundary value of the sub-auxiliary information record group and less than or equal to the backward boundary value thereof.

26. The parallel merge and sort process system as set forth in claim 21,

wherein said second dividing means is adapted for dividing the second auxiliary information record group into P sub-auxiliary information record groups, each of which has nearly the same number of the block information records,

wherein said allocating means is adapted for allocating the P sub-auxiliary information record groups to P process units, and

wherein said merging means is adapted for causing the process units to merge segments formed of blocks corresponding to the block information records of the sub-auxiliary information record groups allocated to the process units.

27. The parallel merge and sort process system as set forth in claim 21,

wherein the block has a fixed length, and

wherein said first generating means is adapted for setting an identifier as the identification information of the block.

28. The parallel merge and sort process system as set forth in claim 27,

wherein the block is data input/output unit of the secondary memory unit.