ADAPTIVE DICTIONARY COMPRESSION/DECOMPRESSION FOR COLUMN-STORE DATABASES

• US 20150178305A1
• Filed: 12/23/2013
• Published: 06/25/2015
• Est. Priority Date: 12/23/2013
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Sanders, Peter, Faerber, Franz, Mueller, Ingo, Ratsch, Cornelius
• Granted Patent: US 10,235,377 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 tangible computer-readable media storing computer-executable instructions for causing a computing system programmed thereby to perform a method comprising:

selecting one of multiple available dictionary compression variants to apply to a dictionary for a column of a table in a column-store database; and

applying the selected dictionary compression variant to the dictionary.

2. The one or more computer-readable media of claim 1 wherein the dictionary maps distinct values among values of the column to value identifiers, wherein, for domain encoding that uses the 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 dictionary is a string dictionary sorted according to the distinct values for the column.

4. The one or more computer-readable media of claim 1 wherein the multiple available dictionary compression variants include one or more of:

a first dictionary compression variant that uses Huffman coding or Hu-Tucker coding;

a second dictionary compression variant that uses front coding;

a third dictionary compression variant that uses bit compression;

a fourth dictionary 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;

a fifth dictionary compression variant that uses Re-Pair compression; and

a sixth dictionary compression variant that uses column-wise bit compression.

5. The one or more computer-readable media of claim 1 wherein the multiple available dictionary compression variants include one or more of:

a first dictionary 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 dictionary compression variant that uses an array of fixed-length blocks;

a third dictionary compression variant that uses one or more data structures for front coding; and

a fourth dictionary 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 dictionary 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 method further comprises:

evaluating at least some of the available dictionary compression variants in terms of compressed dictionary size and run-time performance, wherein the selecting is based at least in part on results of the evaluating.

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 method further comprises:

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 method further comprises:

evaluating at least some of the available dictionary compression variants using compression models for the respective dictionary compression variants, wherein a given compression model of the compression models predicts size of the compressed dictionary using at least some values of the column, wherein the selecting is based at least in part on results of the evaluating.

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

12. The one or more computer-readable media of claim 1 wherein the method further comprises:

evaluating at least some of the available dictionary compression variants using characteristics of the respective dictionary compression variants, characteristics of the column and characteristics of the computing system for the database, wherein the selecting is based at least in part on results of the evaluating.

13. The one or more computer-readable media of claim 12 wherein the characteristics of the dictionary compression variants include, for a given dictionary compression variant of the available dictionary compression variants, a 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 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 based at least in part on user input that indicates the selected dictionary compression variant.

17. The one or more computer-readable media of claim 1 wherein the selecting includes:

determining which of the multiple available dictionary compression variants results in smallest compressed dictionary size;

determining which of the multiple available dictionary compression variants results in shortest delays in run-time performance;

or

determining which of the multiple available dictionary compression variants results in an acceptable trade-off between compressed dictionary size and delays in run-time performance;

wherein the compressed dictionary size accounts for size of the column and/or the run-time performance accounts for frequency of access, and wherein a scaling parameter controls impact of the frequency of access.

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

with the computing system, predicting size of a compressed dictionary for a column of a table in a column-store database according to a compression model for a dictionary compression variant; and

with the computing system, based at least in part on the predicted compressed dictionary size, applying the dictionary compression variant to the dictionary.

19. The method of claim 18 wherein the predicting the size of the compressed dictionary includes sampling values of the column, wherein a subset of the values of the column is used to predict the size of the compressed dictionary.

20. A computing system comprising:

an in-memory column-store database adapted to store one or more tables;

a compression manager 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 multiple available dictionary compression variants for a string dictionary for a given column of the at least some columns;

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

apply the selected dictionary compression variant to the string dictionary.