COMPRESSION-AWARE PARTIAL SORT OF STREAMING COLUMNAR DATA

• US 20160154831A1
• Filed: 08/26/2015
• Published: 06/02/2016
• Est. Priority Date: 12/02/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dickie, Garth A.
• Granted Patent: US 10,606,816 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

According to one embodiment of the present invention, a system for sorting data records generates a plurality of data structures associated with corresponding record fields used to sort the data records, and inserts values of the record fields into the corresponding data structures. Each of the data structures comprises one or more ordered parts, and each inserted value is inserted into a part of the corresponding data structure. Each part of a data structure corresponding to a record field having a sort priority immediately below another record field corresponds to a distinct value inserted into a part of the data structure corresponding to the other record field. The system processes the generated data structures to determine sorted data records. Embodiments of the present invention further include a method and computer program product for sorting data records in substantially the same manners described above.

Claims

1. A computer-implemented method of sorting data records comprising:

generating a plurality of data structures associated with corresponding record fields used to sort the data records, and inserting values of the record fields into the corresponding data structures;

wherein

each of the data structures comprises one or more ordered parts;

each inserted value is inserted into a part of the corresponding data structure; and

each part of a data structure corresponding to a record field having a sort priority immediately below another record field corresponds to a distinct value inserted into a part of the data structure corresponding to the other record field; and

processing the generated data structures to determine sorted data records.

2. The computer-implemented method of claim 1, wherein each part comprises a collection of one or more elements comprising an inserted field value and count of insertions of that field value, and the elements of the collection are ordered by field value.

3. The computer-implemented method of claim 2, wherein inserting a value of a record field into the corresponding data structure comprises generating an instruction for inserting a value of another field of the same record into a part of a partitioned data structure corresponding to the other field.

4. The computer-implemented method of claim 3, wherein inserting a value of a record field into the corresponding data structure is an O(log(m)+log(n)) operation, where n is the number of parts of the data structure, and m is the number of elements in the part of the data structure the value is inserted into.

5. The computer-implemented method of claim 1, wherein processing the generated data structures to determine sorted data records comprises determining a predetermined quantity of sorted data records.

6. The computer-implemented method of claim 1, wherein the data records are compressed, and inserting the field values further comprises:

decompressing selected fields of the data records.

7. The computer-implemented method of claim 1, wherein the data records include streaming column data from a database table.

8. The computer-implemented method of claim 5, further including:

compressing the data records indicated by the data structure based on the count of occurrence of the values of the corresponding record fields.