Compression-aware partial sort of streaming columnar data

Patent metadata

Field	Value
Publication number	US-9959299-B2
Application number	US-201414557757-A
Country	US
Kind code	B2
Filing date	Dec 2, 2014
Priority date	Dec 2, 2014
Publication date	May 1, 2018
Grant date	May 1, 2018

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.

First claim

What is claimed is:

1. A system for sorting data records comprising:
at least one processor configured to:
generate a plurality of data structures, each of which is associated with a different corresponding record field used to sort the data records, and insert 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;
insert 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, perform:
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

emit 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 system 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 system 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 system of claim 1 , wherein the at least one processor is configured to determine a predetermined quantity of the sorted data records.

5. The system of claim 4 , wherein the at least one processor is further configured to:
compress 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 system 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 system of claim 1 , wherein the data records include streaming column data from a database table.

8. A computer program product for sorting data records comprising:
a computer readable storage medium having computer readable program code embodied therewith for execution on a processing system, the computer readable program code comprising computer readable program code configured to:
generate a plurality of data structures, each of which is associated with a different corresponding record field used to sort the data records, and insert 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;
insert 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, perform:
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

emit 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.

9. The computer program product of claim 8 , 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.

10. The computer program product of claim 9 , wherein the 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.

Assignees

• IBM

Inventors

• Dickie Garth A

Classifications

• G06F16/24554

  Unary operations; Data partitioning operations · CPC title

• G06F16/221 Primary

  Column-oriented storage; Management thereof · CPC title

• G06F16/24568

  Data stream processing; Continuous queries · CPC title

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title

• G06F16/2272

  Management thereof · CPC title