Efficient column based data encoding for large-scale data storage

• US 8,452,737 B2
• Filed: 01/10/2012
• Issued: 05/28/2013
• Est. Priority Date: 07/31/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Netz, Amir, Petculescu, Cristian, Crivat, Ioan Bogdan
• Primary Examiner(s): THAI, HANH B
• Application Number:
  US13/347,367
• Publication Number:
  US 20120109910A1
• Time in Patent Office: 504 Days
• Field of Search: 707/687, 707/693, 380/28
• US Class Current: 707/687
• 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 computer-implemented method for encoding data to simultaneously compact and organize the data in a manner that facilitates efficient data access operations, including:

an act of a computer system, which includes at least one processing unit, organizing the data according to a set of column based sequences of values corresponding to different data fields of the data;

an act of the computer system 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

an act of the computer system compressing the set of column based integer sequences according to an iterative hybrid compression algorithm, wherein the iterative hybrid compression algorithm includes performing the following, in at least one iterative encoding step;

an act of analyzing the set of column based integer sequences to determine which encoding technique from a plurality of encoding techniques to apply to compress the set of column based integer sequences by at least comparing a first computed bit savings of applying a first encoding technique against a second computed bit savings of applying a second encoding technique; and

an act of applying the first or second encoding technique on at least a portion of the set of column based integer sequences based on the analysis.

2. The method of claim 1, wherein the method further includes, subsequent to the analyzing, an act of selecting and applying the first encoding technique, the first encoding technique comprising a run length encoding (RLE) technique that replaces one or more sequences of a same data value with a single data value and a count of the number of times the data value appears in each sequence.

3. The method of claim 1, wherein the method further includes, subsequent to the analyzing, an act of selecting and applying the first encoding technique, the first encoding technique comprising a bit packing encoding technique that minimizes a number of bits used to represent each value in a set values, by determining a numeric range over which the set of values span and applying one or more optimizations.

4. The method of claim 3, wherein the one or more optimizations include eliminating any bits not needed to represent numbers within the numeric range.

5. The method of claim 3, wherein the one or more optimizations include removing common powers.

6. The method of claim 3, wherein the one or more optimizations include shifting the set of values.

7. The method of claim 1, wherein the method further includes, subsequent to the analyzing, an act of selecting and applying the first encoding technique, the first encoding technique comprising a greedy run length encoding (RLE) technique that, at each iterative encoding step, applies to a portion of the set of column based integer sequences where the maximum bit savings are achieved and wherein the compressing includes generating a histogram to assist in determining where the maximum bit savings are achieved.

8. The method of claim 1, wherein the iterative hybrid compression algorithm compresses at least a first portion of one of the column based integer sequences using a run length encoding (RLE) technique and wherein the iterative hybrid compression algorithm also compresses at least a second portion of the one of the column based integer sequences using a bit packing encoding technique.

9. The method of claim 8, wherein the iterative hybrid compression algorithm rearranges the integer sequences of the one of the column based integer sequences to facilitate compressing the first portion using the RLE technique and compressing the second portion using the bit packing encoding technique.

10. The method of claim 9, wherein rearranging the integer sequences comprises rearranging the integer sequences of the one of the column based integer sequences only.

11. The method of claim 9, wherein rearranging the integer sequences comprises rearranging integer sequences of each sequence in the set of the column based integer sequences to keep the data in lock step across the set of the column based integer sequences.

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

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

14. A computer system, comprising:

at least one processing unit; and

one or more storage media having stored thereon executable instructions that, when executed by the at least one processing unit, carry out a method for encoding data to simultaneously compact and organize the data in a manner that facilitates efficient data access operations, including the following;

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

an act of the computer system 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

an act of the computer system compressing the set of column based integer sequences according to an iterative hybrid compression algorithm, wherein the iterative hybrid compression algorithm includes performing the following, in at least one iterative encoding step;

an act of analyzing the set of column based integer sequences to determine which encoding technique from a plurality of encoding techniques to apply to compress the set of column based integer sequences by at least comparing a first computed bit savings of applying a first encoding technique against a second computed bit savings of applying a second encoding technique; and

an act of applying the first or second encoding technique on at least a portion of the set of column based integer sequences based on the analysis.

15. The computer system of claim 14, wherein the method further includes, subsequent to the analyzing, an act of selecting and applying the first encoding technique, the first encoding technique comprising a run length encoding (RLE) technique that replaces one or more sequences of a same data value with a single data value and a count of the number of times the data value appears in each sequence.

16. The computer system of claim 14, wherein the method further includes, subsequent to the analyzing, an act of selecting and applying the first encoding technique, the first encoding technique comprising a bit packing encoding technique that minimizes a number of bits used to represent each value in a set values, by determining a numeric range over which the set of values span and applying one or more optimizations.

17. The computer system of claim 14, wherein the iterative hybrid compression algorithm compresses at least a first portion of one of the column based integer sequences using a run length encoding (RLE) technique and wherein the iterative hybrid compression algorithm also compresses at least a second portion of the one of the column based integer sequences using a bit packing encoding technique.

18. One or more physical storage medium storing computer-executable instructions that, when executed by at least one processing unit of a computer system, carry out a method for encoding data to simultaneously compact and organize the data in a manner that facilitates efficient data access operations, including the following:

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

an act of the computer system 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

an act of the computer system compressing the set of column based integer sequences according to an iterative hybrid compression algorithm, wherein the iterative hybrid compression algorithm includes performing the following, in at least one iterative encoding step;

an act of analyzing the set of column based integer sequences to determine which one or more encoding technique from a plurality of encoding techniques to apply to compress the set of column based integer sequences by at least comparing a first computed bit savings of applying a first encoding technique against a second computed bit savings of applying a second encoding technique; and

an act of applying the one or more encoding technique on at least a portion of the set of column based integer sequences based on the analysis.

19. The one or more physical storage medium of claim 18, wherein the one or more encoding technique includes either (1) a run length encoding (RLE) technique that replaces one or more sequences of a same data value with a single data value and a count of the number of times the data value appears in each sequence, or (2) a bit packing encoding technique that minimizes a number of bits used to represent each value in a set values, by determining a numeric range over which the set of values span and applying one or more optimizations.

20. The one or more physical storage medium of claim 18, wherein the one or more encoding technique includes both (1) a run length encoding (RLE) technique that replaces one or more sequences of a same data value with a single data value and a count of the number of times the data value appears in each sequence, and (2) a bit packing encoding technique that minimizes a number of bits used to represent each value in a set values, by determining a numeric range over which the set of values span and applying one or more optimizations, and such that the iterative hybrid compression algorithm compresses at least a first portion of one of the column based integer sequences using the RLE technique and at least a second portion of the one of the column based integer sequences using the bit packing encoding technique.