Hierarchical database compression and query processing

• US 9,928,267 B2
• Filed: 06/13/2014
• Issued: 03/27/2018
• Est. Priority Date: 06/13/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Raman, Vijayshankar, Sidle, Richard S.
• Primary Examiner(s): Andersen, Kristopher
• Application Number:
  US14/304,211
• Publication Number:
  US 20150363456A1
• Time in Patent Office: 1,383 Days
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/185 Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof details of archiving G06F16/11
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes

Abstract

Embodiments relate to hierarchical database compression. An aspect includes applying a first level of a first type of compression to a first partition of a column of a database. Another aspect includes applying a second level of the first type of compression to a subset of the first partition, wherein the first level of the first type of compression comprises a first first-level dictionary and the second level of the first type of compression comprises a first second-level dictionary, and wherein a code size of the first first-level dictionary is larger than a code size of the first second-level dictionary.

Claims

1. A method for hierarchical database compression, comprising:

applying, by a database management unit, a first level of a first type of compression to a first partition of a column of a database and storing data generated from applying the first level of the first type of compression to the first partition in a memory buffer external to the database; and

applying, by the database management unit, a second level of the first type of compression to a subset of the data, wherein the first level of the first type of compression comprises a first first-level dictionary and the second level of the first type of compression comprises a first second-level dictionary, and wherein a code size of the first first-level dictionary is larger than a code size of the first second-level dictionary, wherein applying the second level of the first type of compression further comprises;

adding a first data entry to a set of data corresponding to a page of the database;

determining an amount of space saved by applying the second level of the first type of compression to the set of data;

determining a size of the first second-level dictionary corresponding to the first type of compression;

based on determining that the amount of space is larger than the size of the first second-level dictionary, adding a second data entry to the set of data corresponding to the page;

determining, based on the adding of the second data entry to the set of data, that there is a change to at least one of size of the first second-level dictionary and the code size of the first second-level dictionary;

calculating a size of the page based on the determined change;

determining that the page is full based on the calculated size of the page;

removing the second data entry from the set of data corresponding to the page;

applying the second level of the first type of compression without the determined change to the set of data corresponding to the page;

performing predicate evaluation on the subset of the first partition by converting a predicate value into a compressed predicate value using the first first-level dictionary and the first second-level dictionary, and comparing the predicate value directly to compressed data in the subset of the first partition, wherein the compressed data is compressed using the first level and the second level of the first type of compression;

performing join/groupby processing on the subset of the first partition by converting of second-level codes to first-level codes using the first second-level dictionary, and performing the join/groupby processing on the first-level codes; and

performing expression evaluation on the subset of the first partition by converting second-level codes to uncompressed data using the first first-level dictionary and the first second-level dictionary.

2. The method of claim 1, further comprising:

applying a first level of a second type of compression to a second partition of the column of the database;

applying a second level of the second type of compression to a subset of the second partition, wherein the first level of the second type of compression comprises a second first-level dictionary and the second level of the second type of compression comprises a second second-level dictionary, and wherein a code size of the second first-level dictionary is larger than a code size of the second second-level dictionary.

3. The method of claim 1, wherein the first type of compression comprises dictionary coding, wherein the first second-level dictionary comprises bidirectional mappings between first-level codes and second-level codes, and wherein:

compressing data in the subset of the first partition comprises converting the data into first-level codes using the first first-level dictionary, and converting the first-level codes into second-level codes using the first second-level dictionary; and

wherein decoding data in the subset of the first partition comprises converting second-level codes into first level-codes using the first second-level dictionary, and converting first-level codes into the data using the first first-level dictionary.

4. The method of claim 1, wherein the first type of compression comprises minus coding, and wherein the first first-level dictionary comprises a first base value, and the first second-level dictionary comprises a second base value, wherein the first base value is different from the second base value.

5. The method of claim 1, further comprising a third partition of the column of the database, wherein the third partition is uncoded;

and

applying a third type of compression to a subset of a third partition of the column of the database, wherein third type of compression comprises one of dictionary coding and minus coding.

6. A computer program product for hierarchical database compression, the computer program product comprising:

a non-transitory computer readable storage medium having program code embodied therewith, the program code executable by a processor to;

apply a first level of a first type of compression to a first partition of a column of a database and store data generated from an application of the first level of the first type of compression to the first partition in a memory buffer external to the database; and

apply a second level of the first type of compression to a subset of the data, wherein the first level of the first type of compression comprises a first first-level dictionary and the second level of the first type of compression comprises a first second-level dictionary, and wherein a code size of the first first-level dictionary is larger than a code size of the first second-level dictionary, wherein to apply the second level of the first type of compression further comprises;

adding a first data entry to a set of data corresponding to a page of the database;

determining an amount of space saved by applying the second level of the first type of compression to the set of data;

determining a size of the first second-level dictionary corresponding to the first type of compression;

based on determining that the amount of space is larger than the size of the first second-level dictionary, adding a second data entry to the set of data corresponding to the page;

determining, based on the adding of the second data entry to the set of data, that there is a change to at least one of size of the first second-level dictionary and the code size of the first second-level dictionary;

calculating a size of the page based on the determined change;

determining that the page is full based on the calculated size of the page;

removing the second data entry from the set of data corresponding to the page;

applying the second level of the first type of compression without the determined change to the set of data corresponding to the page;

performing predicate evaluation on the subset of the first partition by converting a predicate value into a compressed predicate value using the first first-level dictionary and the first second-level dictionary, and comparing the predicate value directly to compressed data in the subset of the first partition, wherein the compressed data is compressed using the first level and the second level of the first type of compression;

performing join/groupby processing on the subset of the first partition by converting of second-level codes to first-level codes using the first second-level dictionary, and performing the join/groupby processing on the first-level codes; and

performing expression evaluation on the subset of the first partition by converting second-level codes to uncompressed data using the first first-level dictionary and the first second-level dictionary.

7. The computer program product of claim 6, further comprising:

applying a first level of a second type of compression to a second partition of the column of the database;

applying a second level of the second type of compression to a subset of the second partition, wherein the first level of the second type of compression comprises a second first-level dictionary and the second level of the second type of compression comprises a second second-level dictionary, and wherein a code size of the second first-level dictionary is larger than a code size of the second second-level dictionary.

8. The computer program product of claim 6, wherein the first type of compression comprises dictionary coding, and wherein the first second-level dictionary comprises bidirectional mappings between first-level codes and second-level codes, and wherein:

compressing data in the subset of the first partition comprises converting the data into first-level codes using the first first-level dictionary, and converting the first-level codes into second-level codes using the first second-level dictionary; and

wherein decoding data in the subset of the first partition comprises converting second-level codes into first level-codes using the first second-level dictionary, and converting first-level codes into the data using the first first-level dictionary.

9. The computer program product of claim 6, wherein the first type of compression comprises minus coding, and wherein the first first-level dictionary comprises a first base value, and the first second-level dictionary comprises a second base value, wherein the first base value is different from the second base value.

10. The computer program product of claim 6, further comprising a third partition of the column of the database, wherein the third partition is uncoded;

and

applying a third type of compression to a subset of a third partition of the column of the database, wherein third type of compression comprises one of dictionary coding and minus coding.

11. A system for hierarchical database compression comprising:

a database stored in a memory,

the memory having computer readable computer instructions; and

a processor for executing the computer readable instructions, the instructions including;

applying a first level of a first type of compression to a first partition of a column of the database and storing data generated from an application of the first level of the first type of compression to the first partition in a memory buffer external to the database; and

applying a second level of the first type of compression to a subset of the data, wherein the first level of the first type of compression comprises a first first-level dictionary and the second level of the first type of compression comprises a first second-level dictionary, and wherein a code size of the first first-level dictionary is larger than a code size of the first second-level dictionary, wherein applying the second level of the first type of compression further comprises;

adding a first data entry to a set of data corresponding to a page of the database;

determining an amount of space saved by applying the second level of the first type of compression to the set of data;

determining a size of the first second-level dictionary corresponding to the first type of compression;

based on determining that the amount of space is larger than the size of the first second-level dictionary, adding a second data entry to the set of data corresponding to the page;

determining, based on the adding of the second data entry to the set of data, that there is a change to at least one of size of the first second-level dictionary and the code size of the first second-level dictionary;

calculating a size of the page based on the determined change;

determining that the page is full based on the calculated size of the page;

removing the second data entry from the set of data corresponding to the page;

applying the second level of the first type of compression without the determined change to the set of data corresponding to the page;

performing predicate evaluation on the subset of the first partition by converting a predicate value into a compressed predicate value using the first first-level dictionary and the first second-level dictionary, and comparing the predicate value directly to compressed data in the subset of the first partition, wherein the compressed data is compressed using the first level and the second level of the first type of compression;

performing join/groupby processing on the subset of the first partition by converting of second-level codes to first-level codes using the first second-level dictionary, and performing the join/groupby processing on the first-level codes; and

performing expression evaluation on the subset of the first partition by converting second-level codes to uncompressed data using the first first-level dictionary and the first second-level dictionary.

12. The system of claim 11, further comprising:

applying a first level of a second type of compression to a second partition of the column of the database;

applying a second level of the second type of compression to a subset of the second partition, wherein the first level of the second type of compression comprises a second first-level dictionary and the second level of the second type of compression comprises a second second-level dictionary, and wherein a code size of the second first-level dictionary is larger than a code size of the second second-level dictionary.

13. The system of claim 11, wherein the first type of compression comprises dictionary coding, and wherein the first second-level dictionary comprises bidirectional mappings between first-level codes and second-level codes, and wherein:

compressing data in the subset of the first partition comprises converting the data into first-level codes using the first first-level dictionary, and converting the first-level codes into second-level codes using the first second-level dictionary; and

wherein decoding data in the subset of the first partition comprises converting second-level codes into first level-codes using the first second-level dictionary, and converting first-level codes into the data using the first first-level dictionary.

14. The system of claim 11, wherein the first type of compression comprises minus coding, and wherein the first first-level dictionary comprises a first base value, and the first second-level dictionary comprises a second base value, wherein the first base value is different from the second base value.

15. The system of claim 11, further comprising a third partition of the column of the database, wherein the third partition is uncoded;

and

applying a third type of compression to a subset of a third partition of the column of the database, wherein third type of compression comprises one of dictionary coding and minus coding.