Reordering of database records for improved compression

• US 9,910,855 B2
• Filed: 03/11/2015
• Issued: 03/06/2018
• Est. Priority Date: 05/27/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dickie, Garth A., Keller, Jeffrey M.
• Primary Examiner(s): Chau, Dung K
• Application Number:
  US14/644,762
• Publication Number:
  US 20150347426A1
• Time in Patent Office: 1,091 Days
• Field of Search: 707693, 707753, 707756, 707758, 707999101, 709204, 709225, 715764
• CPC Class Codes: G06F 16/122 using management policies backup systems G06F11/1446; file migration policies for HSM systems G06F16/185
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 7/36 Combined merging and sorting

Abstract

According to embodiments of the present invention, apparatus, systems, methods and computer program products for sorting and compressing an unordered set of data records from a structured database are provided. Fields of the unordered set of data records are prioritized based on an impact of those fields to a compression scheme for column-oriented compression. The unordered set of data records are sorted based on the prioritized field(s) with a greatest impact on the performance metric. Data of the sorted data records are compressed according to a compression scheme. In some embodiments, prioritizing the fields may be based on an anticipated level of usage of data within those fields and/or a cost function associated with a performance metric as well as optimization of compression. A performance metric may include a faster computational time, reduced I/O computation, faster scan time, etc.

Claims

1. A method of compressing an unordered set of data records from a structured database comprising:

prioritizing a plurality of fields of the unordered set of data records based on an impact of those fields to a performance metric for accessing data stored in a column-oriented compressed database;

selecting one or more of the prioritized fields based on priority of the prioritized fields, wherein the priority is based on a frequency of access of the fields;

sorting the unordered set of data records based on the selected one or more prioritized fields for compression and optimal performance; and

compressing data of the sorted data records according to a compression scheme to increase performance for accessing the data stored in the column-oriented compressed database.

2. The method of claim 1, wherein prioritizing the fields is based on a performance metric as assessed by a cost function, the cost function including minimizing a total amount of time reading and computing on a column as well as the compressed size of data in the column.

3. The method of claim 1, wherein sorting the unordered set of data records further includes:

sorting the unordered set of data records based on a prioritized tuple of sort keys.

4. The method of claim 1, wherein the unordered set of data records is from a columnar database or a hybrid columnar database.

5. The method of claim 1, wherein the performance metric is determined based upon historical data.

6. The method of claim 1, further comprising:

updating, based upon monitored performance metrics, relative priorities of the various fields to each other;

decompressing a set of ordered compressed records to obtain an unordered set of data records;

sorting the unordered set of data records based on the updated field priorities to obtain a second set of sorted data records; and

compressing data of the second set of sorted data records according to a compression scheme.