EFFICIENT COLUMN BASED DATA ENCODING FOR LARGE-SCALE DATA STORAGE

• US 20100030796A1
• Filed: 11/14/2008
• Published: 02/04/2010
• Est. Priority Date: 07/31/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Crivat, Ioan Bogdan, Petculescu, Cristian, Netz, Amir
• Granted Patent: US 8,108,361 B2
• Time in Patent Office: Days
• US Class Current: N/A
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/48 alternating with other codes during the code conversion process, e.g. run-length coding being performed only as long as sufficientlylong runs of digits of the same kind are present

Abstract

The subject disclosure relates to column based data encoding where raw data to be compressed is organized by columns, and then, as first and second layers of reduction of the data size, dictionary encoding and/or value encoding are applied to the data as organized by columns, to create integer sequences that correspond to the columns. Next, a hybrid greedy run length encoding and bit packing compression algorithm further compacts the data according to an analysis of bit savings. Synergy of the hybrid data reduction techniques in concert with the column-based organization, coupled with gains in scanning and querying efficiency owing to the representation of the compact data, results in substantially improved data compression at a fraction of the cost of conventional systems.

Claims

1. A method for encoding data, including:

organizing the data according to a set of column based sequences of values corresponding to different data fields of the data;

transforming the set of column based sequences of values to a set of column based integer sequences of values according to at least one encoding algorithm; and

compressing the set of column based integer sequences according to at least one compression algorithm.

2. The method of claim 1, wherein the transforming includes encoding the set of column based sequences via a dictionary encoding that maps data fields to integer values.

3. The method of claim 2, wherein the transforming includes encoding the set of column based sequences via a value encoding that applies an invertible mathematical function to the data fields to use fewer bits to represent the data fields.

4. The method of claim 1, wherein the compressing includes compressing with a greedy run length encoding algorithm that at each encoding step applies where the maximum bit savings are achieved.

5. The method of claim 4, wherein the compressing includes generating a histogram to assist in determining where the maximum bit savings are achieved.

6. The method of claim 1, wherein the compressing includes compressing the set of column based integer sequences according to at least one greedy compression algorithm that seeks to maximize bit savings at each step of the compression.

7. A method for encoding data, including:

transforming the data to integer sequences of values, each integer sequence serially representing values of a different column of the data; and

analyzing the integer sequences to determine whether to apply run length encoding (RLE) compression or bit packing compression including analyzing bit savings of RLE compression relative to bit packing compression to determine where the maximum bit savings is achieved.

8. The method of claim 7, further comprising:

compressing the data where the maximum bit savings are achieved according to the analyzing.

9. The method of claim 8, further comprising:

iteratively performing said analyzing and compressing to perform compression at each step where the maximum bit savings are achieved.

10. The method of claim 7, wherein the analyzing includes determining whether threshold savings can be obtained from run length encoding compression of any portion of the integer sequences.

11. The method of claim 10, wherein, if the threshold savings cannot be obtained from run length encoding compression of any portion of the integer sequences, applying bit packing compression.

12. A method for encoding data, including:

transforming the data to integer sequences of values, each integer sequence serially representing values of a different field of the data;

analyzing the integer sequences to determine whether to apply a run length encoding (RLE) compression or a bit packing compression including analyzing bit savings of RLE compression relative to bit packing compression for groups defined over the columns including generating a histogram for the values of the integer sequences to prioritize maximum bit savings.

13. An encoder, including:

an organization component for organizing raw data received as a set of serialized values corresponding to different fields or columns of the raw data to form columnized sequences of data;

a data encoding component that performs at least one of dictionary encoding or value encoding to uniformly represent the columnized sequences of data as integer sequences; and

a compression component that determines on which portion of which of the integer sequences to perform compression next, and whether to perform the compression with run length encoding (RLE) that represents a repeated value as a run or a bit packing algorithm that seeks to minimize number of bits used to represent a portion including, for each portion defined for the integer sequences, analyzing a performance metric of RLE relative to bit packing.

14. The encoder of claim 13, wherein the compression component re-orders the columns when performing RLE.

15. The encoder of claim 13, wherein the data encoding component that performs value encoding at least one of reduces the integer sequences by eliminating repeated numbers in each data field or reduces the integer sequences by transforming float values to integer values via a mathematical function.

16. A method for encoding data, comprising:

receiving at least one portion of an integer sequence of values representing a column of data;

reducing a number of bits used to represent each integer based on determining a minimum number of bits to use for the at least one portion of the integer sequence;

removing any shared numerical powers across the values of the at least one portion of the integer sequence; and

offsetting the values of the at least one portion of the integer sequence spanning a range, further reducing the number of bits.

17. The method of claim 16, further comprising:

alternatively performing run length encoding where total bit savings from applying run length encoding exceed total bit savings from applying bit packing.

18. The method of claim 16, further comprising:

alternatively performing run length encoding where total bit savings from applying run length encoding exceed a threshold total bit savings.

19. A computer readable medium comprising computer executable instructions for carrying out the method of claim 16.

20. Encoding apparatus comprising means for performing the method of claim 16.