Compression-aware partial sort of streaming columnar data

• US 10,606,816 B2
• Filed: 08/26/2015
• Issued: 03/31/2020
• 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.
• Primary Examiner(s): Corrielus, Jean M
• Application Number:
  US14/836,132
• Publication Number:
  US 20160154831A1
• Time in Patent Office: 1,679 Days
• Field of Search: 707693, 707752
• 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, each of which is associated with a different corresponding record field used to sort the data records, and inserting values of the record fields into the corresponding data structures, the values of the record fields being received in a plurality of streams, each of the plurality of streams corresponding to a different respective record field and including a sequence of chunks, each of the chunks including values of a record field corresponding to the stream including the chunk;

inserting values of the record fields into corresponding data structures, the values being inserted such that the values are in an order in the corresponding data structures, the inserting comprising;

for each respective value of each chunk of each stream of the plurality of streams, performing;

receiving a respective value and an instruction for a respective entry of a respective stream,

updating the data structure for the respective stream according to the respective value and the instruction, and

generating an instruction for a corresponding entry of a next stream; and

emitting a top predetermined number of the sorted data records, the emitting including reading out the inserted values stored in the plurality of data structures, wherein;

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

each inserted value is inserted into a corresponding ordered part of the corresponding data structure, the corresponding ordered part further including a count of occurrences of the value; and

each ordered 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 an ordered part of the data structure corresponding to the another record field.

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

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

4. The computer-implemented method of claim 1, further comprising determining a predetermined quantity of the sorted data records.

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

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

6. The computer-implemented method of claim 1, wherein the data records are compressed, and inserting the values of the record fields 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.