APPARATUS AND METHOD FOR SORTING DATA

• US 20110320451A1
• Filed: 05/17/2011
• Published: 12/29/2011
• Est. Priority Date: 06/23/2010
• Status: Active Grant

• Current Assignee: Kyndryl Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Boh, Ritsuko, Kohno, Noriaki
• Granted Patent: US 8,725,734 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951
• CPC Class Codes: G06F 7/08 Sorting, i.e. grouping record carriers in numerical or other ordered sequence according to the classification of at least some of the information they carry by merging two or more sets of carriers in ordered sequence G06F7/16

Abstract

A method and system for sorting data of an input file containing multiple records associated with multiple tables of a database. The multiple records include key values. The key values are segmented into ranges of key values for each table. Each range of key values for each table is a segment having a segment value. Multiple key values are selected for the multiple records. A block number, which contains a unique permutation of the segment values of the segments, is generated. The segment values denote the ranges of key values encompassing the multiple key values in each record. A sort key value for each record is ascertained, based on the generated block number for each record, and added to each record. The multiple records are sorted according to the sort key values in the multiple records. The sorted multiple records are stored in an output file.

Claims

1. A method for sorting data of an input file stored on a first tangible storage device, said input file comprising multiple records associated with multiple tables of a database, each record of the multiple records comprising a plurality of key values, said method comprising:

segmenting the plurality of key values in the multiple records associated with each table into ranges of key values for each table, each range of key values for each table denoted as a segment having an associated segment value;

selecting multiple key values for each record of the multiple records, said multiple key values being selected in association with the tables of the multiple tables;

generating, for each record of the multiple records, a block number comprising a unique permutation of the segment values of the segments, said segment values respectively denoting the ranges of key values encompassing the multiple key values;

ascertaining, for each record of the multiple records, a sort key value based on the generated block number for each record of the multiple records;

adding, to each record of the multiple records, the sort key value ascertained for each record of the multiple records; and

after said adding the sort key value to all records of the multiple records, sorting the multiple records according to the sort key values added to the multiple records; and

storing the sorted multiple records in an output file on a second tangible storage device.

2. The method of claim 1, wherein the generated block numbers collectively constitute multiple block numbers, wherein the method further comprises sequencing the block numbers of the multiple block numbers in a block sequence such that the segment value differs in only one position within the unique permutation of the segment values in each pair of successive blocks in the block sequence, and wherein said ascertaining the sort key value for each record of the multiple records comprises:

converting the generated block number for each record of the multiple records to an ordinal value denoting a sequential position of the generated block number within the block sequence;

determining an intra-block key position, within the unique permutation of the segment values of the generated block for each record of the multiple records, as being said only one position at which the segment value differs from the segment value in the block immediately preceding the generated block in the block sequence;

determining an intra-block key value as being the key value of the multiple key values of each record of the multiple records at the segment associated with the intra-block key position; and

generating the sort key value for each record of the multiple records from a combination of the ordinal value and the intra-block key value.

3. The method of claim 1, wherein said segmenting comprises:

providing a dedicated buffer pool for each table of the multiple tables;

computing a number of storable records for each table as equal to a size of the dedicated buffer pool for each table divided by a record length of each record of each table;

computing a total number of segments for each table as equal to a total number of records of each table divided by the computed number of storable records for each table;

after said computing the total number of segments for each table, selecting the range of key values for the segments of each table in a manner that uniformly distributes the plurality of key values among the segments of each table; and

computing a segment value for each segment for each table as being equal to a product divided by a divisor, said computed segment value rounded down to a next lower integer if the computed segment value is not an integer, said product being a product of the calculated number of segments for each table and a difference between a highest key value in each segment and a lowest key value from the ranges of key values, said divisor being an increment between successive key values plus a difference between a highest key value from the ranges of key values and the lowest key value from the ranges of key values.

4. The method of claim 1, wherein said selecting multiple key values selects all key values that satisfy a condition for determining that the data in the multiple tables are readable sequentially.

5. The method of claim 4,

wherein the condition is:

a total number of records in the input file/(number of segments 1×

number of segments 2×

. . . ×

number of segments n)>

max(number of records in table i/number of segments i)/coefficient;

wherein n is a total number of tables of the multiple tables;

wherein the multiple tables are denoted as table 1, table 2, . . . , table n;

wherein said number of segments i denotes the total number of segments associated with each table i (i=1, 2, . . . , n);

wherein max(number of records in table i/number of segments i) denotes a maximum value of (number of records in table i/number of segments i) over i=1, 2, . . . , n;

wherein coefficient is a number of pages from a page read immediately before a currently read page is handled as page-sequential; and

wherein page denotes a unit of storing data on the first tangible storage device.

6. The method of claim 1, wherein the method comprises deleting the sort key value for each record of the multiple records during or after said sorting, which results in the sort key value for each record of the multiple records not being included in the sorted multiple records in the output file.

7. The method of claim 1, wherein each key value of the multiple key values of each record of the multiple records is associated with a different table of the multiple tables.

8. A computer program product, comprising a computer readable tangible storage medium having a computer readable program code stored therein, said program code configured to be executed by a processor of a computer system to implement a method for sorting data of an input file stored on a first tangible storage device, said input file comprising multiple records associated with multiple tables of a database, each record of the multiple records comprising a plurality of key values, said method comprising:

segmenting the plurality of key values in the multiple records associated with each table into ranges of key values for each table, each range of key values for each table denoted as a segment having an associated segment value;

selecting multiple key values for each record of the multiple records, said multiple key values being selected in association with the tables of the multiple tables;

generating, for each record of the multiple records, a block number comprising a unique permutation of the segment values of the segments, said segment values respectively denoting the ranges of key values encompassing the multiple key values;

ascertaining, for each record of the multiple records, a sort key value based on the generated block number for each record of the multiple records;

adding, to each record of the multiple records, the sort key value ascertained for each record of the multiple records; and

after said adding the sort key value to all records of the multiple records, sorting the multiple records according to the sort key values added to the multiple records; and

storing the sorted multiple records in an output file on a second tangible storage device.

9. The computer program product of claim 8, wherein the generated block numbers collectively constitute multiple block numbers, wherein the method further comprises sequencing the block numbers of the multiple block numbers in a block sequence such that the segment value differs in only one position within the unique permutation of the segment values in each pair of successive blocks in the block sequence, and wherein said ascertaining the sort key value for each record of the multiple records comprises:

converting the generated block number for each record of the multiple records to an ordinal value denoting a sequential position of the generated block number within the block sequence;

determining an intra-block key position, within the unique permutation of the segment values of the generated block for each record of the multiple records, as being said only one position at which the segment value differs from the segment value in the block immediately preceding the generated block in the block sequence;

determining an intra-block key value as being the key value of the multiple key values of each record of the multiple records at the segment associated with the intra-block key position; and

generating the sort key value for each record of the multiple records from a combination of the ordinal value and the intra-block key value.

10. The computer program product of claim 8, wherein said segmenting comprises:

providing a dedicated buffer pool for each table of the multiple tables;

computing a number of storable records for each table as equal to a size of the dedicated buffer pool for each table divided by a record length of each record of each table;

computing a total number of segments for each table as equal to a total number of records of each table divided by the computed number of storable records for each table;

after said computing the total number of segments for each table, selecting the range of key values for the segments of each table in a manner that uniformly distributes the plurality of key values among the segments of each table; and

computing a segment value for each segment for each table as being equal to a product divided by a divisor, said computed segment value rounded down to a next lower integer if the computed segment value is not an integer, said product being a product of the calculated number of segments for each table and a difference between a highest key value in each segment and a lowest key value from the ranges of key values, said divisor being an increment between successive key values plus a difference between a highest key value from the ranges of key values and the lowest key value from the ranges of key values.

11. The computer program product of claim 8, wherein said selecting multiple key values selects all key values that satisfy a condition for determining that the data in the multiple tables are readable sequentially.

12. The computer program product of claim 11,

wherein the condition is:

a total number of records in the input file/(number of segments 1×

number of segments 2×

. . . ×

number of segments n)>

max(number of records in table i/number of segments i)/coefficient;

wherein n is a total number of tables of the multiple tables;

wherein the multiple tables are denoted as table 1, table 2, . . . , table n;

wherein said number of segments i denotes the total number of segments associated with each table i (i=1, 2, . . . , n);

wherein max(number of records in table i/number of segments i) denotes a maximum value of (number of records in table i/number of segments i) over i=1, 2, . . . , n;

wherein coefficient is a number of pages from a page read immediately before a currently read page is handled as page-sequential; and

wherein page denotes a unit of storing data on the first tangible storage device.

13. The computer program product of claim 8, wherein the method comprises deleting the sort key value for each record of the multiple records during or after said sorting, which results in the sort key value for each record of the multiple records not being included in the sorted multiple records in the output file.

14. The computer program product of claim 8, wherein each key value of the multiple key values of each record of the multiple records is associated with a different table of the multiple tables.

15. A computer system comprising a processor, a memory unit, and a computer readable tangible storage medium, said storage medium containing program code configured to be executed by the processor via the memory unit to implement a method for sorting data of an input file stored on a first tangible storage device, said input file comprising multiple records associated with multiple tables of a database, each record of the multiple records comprising a plurality of key values, said method comprising:

segmenting the plurality of key values in the multiple records associated with each table into ranges of key values for each table, each range of key values for each table denoted as a segment having an associated segment value;

selecting multiple key values for each record of the multiple records, said multiple key values being selected in association with the tables of the multiple tables;

generating, for each record of the multiple records, a block number comprising a unique permutation of the segment values of the segments, said segment values respectively denoting the ranges of key values encompassing the multiple key values;

ascertaining, for each record of the multiple records, a sort key value based on the generated block number for each record of the multiple records;

adding, to each record of the multiple records, the sort key value ascertained for each record of the multiple records; and

after said adding the sort key value to all records of the multiple records, sorting the multiple records according to the sort key values added to the multiple records; and

storing the sorted multiple records in an output file on a second tangible storage device.

16. The computer system claim 15, wherein the generated block numbers collectively constitute multiple block numbers, wherein the method further comprises sequencing the block numbers of the multiple block numbers in a block sequence such that the segment value differs in only one position within the unique permutation of the segment values in each pair of successive blocks in the block sequence, and wherein said ascertaining the sort key value for each record of the multiple records comprises:

converting the generated block number for each record of the multiple records to an ordinal value denoting a sequential position of the generated block number within the block sequence;

determining an intra-block key position, within the unique permutation of the segment values of the generated block for each record of the multiple records, as being said only one position at which the segment value differs from the segment value in the block immediately preceding the generated block in the block sequence;

determining an intra-block key value as being the key value of the multiple key values of each record of the multiple records at the segment associated with the intra-block key position; and

generating the sort key value for each record of the multiple records from a combination of the ordinal value and the intra-block key value.

17. The computer system claim 15, wherein said segmenting comprises:

providing a dedicated buffer pool for each table of the multiple tables;

computing a number of storable records for each table as equal to a size of the dedicated buffer pool for each table divided by a record length of each record of each table;

computing a total number of segments for each table as equal to a total number of records of each table divided by the computed number of storable records for each table;

after said computing the total number of segments for each table, selecting the range of key values for the segments of each table in a manner that uniformly distributes the plurality of key values among the segments of each table; and

computing a segment value for each segment for each table as being equal to a product divided by a divisor, said computed segment value rounded down to a next lower integer if the computed segment value is not an integer, said product being a product of the calculated number of segments for each table and a difference between a highest key value in each segment and a lowest key value from the ranges of key values, said divisor being an increment between successive key values plus a difference between a highest key value from the ranges of key values and the lowest key value from the ranges of key values.

18. The computer system claim 15, wherein said selecting multiple key values selects all key values that satisfy a condition for determining that the data in the multiple tables are readable sequentially.

19. The computer system claim 18,

wherein the condition is:

a total number of records in the input file/(number of segments 1×

number of segments 2×

. . . ×

number of segments n)>

max(number of records in table i/number of segments i)/coefficient;

wherein n is a total number of tables of the multiple tables;

wherein the multiple tables are denoted as table 1, table 2, . . . , table n;

wherein said number of segments i denotes the total number of segments associated with each table i (i=1, 2, . . . , n);

wherein max(number of records in table i/number of segments i) denotes a maximum value of (number of records in table i/number of segments i) over i=1, 2, . . . , n;

wherein coefficient is a number of pages from a page read immediately before a currently read page is handled as page-sequential; and

wherein page denotes a unit of storing data on the first tangible storage device.

20. The computer system claim 15, wherein the method comprises deleting the sort key value for each record of the multiple records during or after said sorting, which results in the sort key value for each record of the multiple records not being included in the sorted multiple records in the output file.