Adaptive dictionary compression/decompression for column-store databases

• US 10,235,377 B2
• Filed: 12/23/2013
• Issued: 03/19/2019
• Est. Priority Date: 12/23/2013
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Mueller, Ingo, Ratsch, Cornelius, Sanders, Peter, Faerber, Franz
• Primary Examiner(s): Raab, Christopher J
• Application Number:
  US14/139,669
• Publication Number:
  US 20150178305A1
• Time in Patent Office: 1,912 Days
• Field of Search: None
• CPC Class Codes: G06F 16/17 Details of further file system functions
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof

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.

Claims

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 compression variant of the multiple available compression variants if the frequency of access of the column is greater than a threshold, and choosing a second compression variant of the multiple available compression variants if the frequency of access of the column is less than the threshold, the first compression variant being faster than the second compression variant but having a lower compression rate than the second compression variant.

20. The one or more computer-readable media of claim 7 wherein the run-time performance also accounts for frequency of construction or updating of the string dictionary.

21. In a computing system that implements a compression manager, a method comprising:

with the computing system, 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 evaluating includes estimating compressed dictionary size of the string dictionary according to a compression model for a given compression variant of the multiple available compression variants without applying the given compression variant to the string dictionary, 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;

with the computing system, 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

with the computing system, 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.

22. The method of claim 21 wherein the estimating the compressed dictionary size of the string dictionary includes sampling the values of the column, and wherein a subset of the values of the column is used to estimate the compressed dictionary size of the string dictionary.

23. The method of claim 21 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.

24. The method of claim 21 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.

25. The method of claim 21 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.

26. The method of claim 21 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.

27. A computing system comprising:

memory configured to store one or more tables for an in-memory column-store database; and

one or more processors configured to execute instructions for a compression manager, wherein at least one of the one or more processors is selected from the group consisting of central processing unit, graphics processing unit, and application-specific integrated circuit, the compression manager being adapted to compress at least some columns of the one or more tables using domain encoding, wherein the compression manager is further adapted to;

evaluate, in terms of compressed dictionary size and run-time performance, multiple available compression variants for a string dictionary for a given column of the at least some columns, wherein the run-time performance accounts for frequency of access of the given column, the compression manager being adapted to use compression models for the respective compression variants, a given compression model of the compression models estimating the 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, and wherein the string dictionary maps distinct values among values of the given column to value identifiers, each of the distinct values being a string of one or more characters;

select one of the multiple available compression variants to apply to the string dictionary for the given column; and

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

28. The computing system of claim 27 wherein, for the domain encoding, the values of the given column are replaced with corresponding value identifiers, the corresponding value identifiers being oriented as a column vector.

29. The computing system of claim 27 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.

30. The computing system of claim 27 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.

31. The computing system of claim 27 wherein a tuning parameter sets a preference between the compressed dictionary size and the run-time performance.

32. The computing system of claim 27 wherein the given compression model estimates the compressed dictionary size of the string dictionary using at least some of the values of the given column.

33. The computing system of claim 27 wherein the compression manager is further adapted to, as part of evaluating the multiple available compression variants, evaluate at least some of the multiple available compression variants using characteristics of the respective compression variants, characteristics of the given column, and characteristics of the computing system.

34. The computing system of claim 33 wherein the characteristics of the given 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 given column, a merge frequency, and the values of the given column.