Adaptive dictionary compression/decompression for column-store databases

Patent metadata

Field	Value
Publication number	US-10235377-B2
Application number	US-201314139669-A
Country	US
Kind code	B2
Filing date	Dec 23, 2013
Priority date	Dec 23, 2013
Publication date	Mar 19, 2019
Grant date	Mar 19, 2019

Abstract

Innovations for adaptive compression and decompression for dictionaries of a column-store database can reduce the amount of memory used for columns of the database, allowing a system to keep column data in memory for more columns, while delays for access operations remain acceptable. For example, dictionary compression variants use different compression techniques and implementation options. Some dictionary compression variants provide more aggressive compression (reduced memory consumption) but result in slower run-time performance. Other dictionary compression variants provide less aggressive compression (higher memory consumption) but support faster run-time performance. As another example, a compression manager can automatically select a dictionary compression variant for a given column in a column-store database. For different dictionary compression variants, the compression manager predicts run-time performance and compressed dictionary size, given the values of the column, and selects one of the dictionary compression variants.

First claim

We claim:

1. One or more non-transitory computer-readable media storing computer-executable instructions for causing a computing system, when programmed thereby, to perform operations comprising:
evaluating at least some of multiple available compression variants to apply to a string dictionary for a column of a table in a column-store database, wherein the string dictionary maps distinct values among values of the column to value identifiers, each of the distinct values being a string of one or more characters, and wherein the evaluating uses compression models for the respective at least some of the multiple available compression variants, a given compression model of the compression models estimating compressed dictionary size of the string dictionary for a given compression variant of the multiple available compression variants without applying the given compression variant to the string dictionary;
selecting, based at least in part on results of the evaluating, one of the multiple available compression variants to apply to the string dictionary; and
applying the selected compression variant to the string dictionary, thereby reducing the compressed dictionary size of the string dictionary, including, for each of at least one of the distinct values of the string dictionary, replacing at least one character of the string for the distinct value with one or more codes that represent the replaced at least one character, the one or more codes being shorter than the replaced at least one character.

2. The one or more computer-readable media of claim 1 wherein, for domain encoding that uses the string dictionary, the values of the column are replaced with corresponding value identifiers, the corresponding value identifiers being oriented as a column vector, and wherein the column-store database is an in-memory column-store database.

3. The one or more computer-readable media of claim 2 wherein the string dictionary is sorted according to the distinct values for the column.

4. The one or more computer-readable media of claim 1 wherein the multiple available compression variants include:
a first compression variant that uses Huffman coding or Hu-Tucker coding in which the one or more codes include one or more Huffman codes;
a second compression variant that uses front coding in which the one or more codes include one or more prefix lengths;
a third compression variant that uses bit compression in which the one or more codes include one or more x-bit codes each representing a single character;
a fourth compression variant that uses N-gram compression according to which N-tuples are replaced with x-bit codes, for N greater than or equal to 2, as the one or more codes, each of the one or more codes representing N characters;
a fifth compression variant that uses Re-Pair compression in which the one or more codes include one or more x-bit codes each representing a combination of characters; and/or
a sixth compression variant that uses column-wise bit compression in which the one or more codes include one or more x-bit codes each representing a single character of a column.

5. The one or more computer-readable media of claim 1 wherein the multiple available compression variants include:
a first compression variant that uses an array of string data and an array of pointers to locations in the array of string data, wherein the string data is compressed using one of Hu-Tucker coding, bit compression, N-gram compression or Re-Pair compression;
a second compression variant that uses an array of fixed-length blocks;
a third compression variant that uses one or more data structures for front coding; and/or
a fourth compression variant that uses one or more data structures for bit-wise column compression.

6. The one or more computer-readable media of claim 5 wherein, for the third compression variant:
if inline front coding is used, prefix lengths are interleaved with suffix lengths and string suffixes; and
if block header-based front coding is used, a block header includes the prefix lengths and the suffix lengths, and a block includes the string suffixes.

7. The one or more computer-readable media of claim 1 wherein the evaluating at least some of the multiple available compression variants accounts for the compressed dictionary size and run-time performance, the run-time performance accounting for frequency of access of the column.

8. The one or more computer-readable media of claim 7 wherein the selecting is also based at least in part on a tuning parameter that sets a preference between the compressed dictionary size and the run-time performance.

9. The one or more computer-readable media of claim 8 wherein the operations further comprise:
adjusting the tuning parameter based at least in part on amount of free memory.

10. The one or more computer-readable media of claim 1 wherein the given compression model estimates the compressed dictionary size using at least some of the values of the column.

11. The one or more computer-readable media of claim 10 wherein a sampling of the values of the column is used to estimate the compressed dictionary size for the given compression model.

12. The one or more computer-readable media of claim 1 wherein the evaluating at least some of the multiple available compression variants uses characteristics of the respective compression variants, characteristics of the column, and characteristics of the computing system for the database.

13. The one or more computer-readable media of claim 12 wherein the characteristics of the compression variants include, for the given compression variant, the given compression model and one or more run time values.

14. The one or more computer-readable media of claim 12 wherein the characteristics of the column include an expected number of extract operations until a next merge operation, an expected number of locate operations until the next merge operation, a size of a column vector for the column, a merge frequency, and the values of the column.

15. The one or more computer-readable media of claim 12 wherein the characteristics of the computing system for the database include an amount of free physical memory and an amount of physical memory currently consumed by the database.

16. The one or more computer-readable media of claim 1 wherein the selecting is also based at least in part on user input that indicates the selected compression variant.

17. The one or more computer-readable media of claim 1 wherein the evaluating includes:
determining which of the multiple available compression variants results in smallest values for the compressed dictionary size;
determining which of the multiple available compression variants results in shortest delays in run-time performance; or
determining which of the multiple available compression variants results in an acceptable trade-off between the compressed dictionary size and delays in run-time performance;
wherein weighting of the compressed dictionary size accounts for size of the column and/or the run-time performance accounts for frequency of access of the column, and wherein a scaling parameter controls impact of the frequency of access of the column.

18. The one or more computer-readable media of claim 7 wherein the frequency of access of the column quantifies an expected number of extract operations from the string dictionary and/or an expected number of locate operations from the string dictionary.

19. The one or more computer-readable media of claim 7 wherein the selecting includes choosing a first co

Assignees

• Mueller Ingo
• Ratsch Cornelius
• Sanders Peter
• Faerber Franz
• Sap Se

Inventors

• Mueller Ingo
• Ratsch Cornelius
• Sanders Peter
• Faerber Franz

Classifications

• G06F17/30315

  Physics · mapped topic

• G06F17/30129 Primary

  Physics · mapped topic

• G06F16/221 Primary

  Column-oriented storage; Management thereof · CPC title

• G06F16/17 Primary

  Details of further file system functions · CPC title