System and method for compression in a distributed column chunk data store

• US 20070061544A1
• Filed: 09/13/2005
• Published: 03/15/2007
• Est. Priority Date: 09/13/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Mahat Technologies, LLC
• Inventors: Uppala, Radha
• Granted Patent: US 7,447,865 B2
• Time in Patent Office: Days
• US Class Current: 711/173
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof

Abstract

An improved system and method for compression in a distributed column chunk data store is provided. A distributed column chunk data store may be provided by multiple storage servers operably coupled to a network. A storage server provided may include a database engine for partitioning a data table into the column chunks for distributing across multiple storage servers, a storage shared memory for storing the column chunks during processing of semantic operations performed on the column chunks, and a storage services manager for striping column chunks of a partitioned data table across multiple storage servers. Any data table may be flexibly partitioned into column chunks using one or more columns with various partitioning methods. Domain specific compression may be applied to a column chunk to reduce storage requirements of column chunks and increase transmission speeds for sending column chunks between storage servers.

Claims

1. A computer-implemented method for compressing a partitioned data table in a computer system, comprising:

partitioning a data table into column chunks for storing on one or more storage servers;

applying data domain compression to one or more column chunks of the partitioned data table for compressing the one or more column chunks; and

storing the one or more compressed column chunks of the partitioned data table on the one or more storage servers.

2. The method of claim 1 wherein applying data domain compression to one or more column chunks of the partitioned data table comprises determining whether the data domain of values in a column chunk represents random numeric values.

3. The method of claim 1 wherein applying data domain compression to one or more column chunks of the partitioned data table comprises determining whether the data domain of values in a column chunk represents a range of numeric values.

4. The method of claim 3 further comprising compressing the representation of each numeric value in the range.

5. The method of claim 1 wherein applying data domain compression to one or more column chunks of the partitioned data table comprises determining whether the data domain of values in a column chunk represents a string of characters.

6. The method of claim 5 further comprising compressing the representation of the string of characters.

7. The method of claim 1 wherein applying data domain compression to one or more column chunks of the partitioned data table comprises determining whether the data domain of values in a column chunk includes sub-fields.

8. The method of claim 7 further comprising decomposing the sub-fields in the column chunk into separate column chunks.

9. The method of claim 8 further comprising compressing the values in the separate column chunks.

10. The method of claim 1 wherein applying data domain compression to one or more column chunks of the partitioned data table comprises determining whether the data domain of values in a column chunk represent key-value pairs.

11. The method of claim 10 further comprising decomposing the key-value pairs in the column chunk into one or more arrays of values.

12. The method of claim 11 further comprising compressing the key-value pairs in the one or more arrays of values.

13. A computer-readable medium having computer-executable instructions for performing the method of claim 1.

14. A computer-implemented method for compressing a partitioned data table in a computer system, comprising:

determining whether the data domain of values in a column chunk of a partitioned data table represents a range of numeric values;

determining the number of bits needed to represent the range of numeric values;

normalizing the numeric values of the column chunk to the bit representation of the range of numeric values;

packing each normalized numeric value into a bit vector to represent the column chunk;

compressing the bit vector to create a compressed column chunk; and

storing the compressed column chunk of the partitioned data table on one or more storage servers.

15. The method of claim 14 further comprising determining that the numeric values may be represented as several bytes.

16. The method of claim 15 further comprising decomposing the representation of the numeric values into bytes and assigning each byte of the numeric value to a separate array associated with that byte position (separate array;

creating an array of values for each byte position representing the numeric values).

17. A computer-readable medium having computer-executable instructions for performing the method of claim 14.

19. The method of claim 16 further comprising:

calculating a storage size of an entire column of values;

calculating a storage size of a column of values for each occurrence of a key;

calculating a storage size of a table of values for multiple keys; and

determining the smallest storage size for creating compressed column chunks.

18. A computer-implemented method for compressing a partitioned data table in a computer system, comprising:

determining whether the data domain of values in a column chunk of a partitioned data table represents key-value pairs;

decomposing the key-value pairs in the column chunk into one or more arrays of values;

compressing the key-value pairs in the one or more arrays of values to create a compressed column chunk; and

storing the compressed column chunk of the partitioned data table on one or more storage servers.

20. A computer-readable medium having computer-executable instructions for performing the method of claim 18.