Compression-aware partial sort of streaming columnar data

Patent metadata

Field	Value
Publication number	US-2016154831-A1
Application number	US-201514836132-A
Country	US
Kind code	A1
Filing date	Aug 26, 2015
Priority date	Dec 2, 2014
Publication date	Jun 2, 2016
Grant date	—

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

Assignees

• IBM

Inventors

• Dickie Garth A

Classifications

• G06F16/24568

  Data stream processing; Continuous queries · CPC title

• G06F16/24554

  Unary operations; Data partitioning operations · CPC title

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title

• G06F16/221 Primary

  Column-oriented storage; Management thereof · CPC title

• G06F16/2272

  Management thereof · CPC title