Data compression of large scale data stored in sparse tables

A computer-implemented method of compressing data in a table data structure, comprising:

• accessing a data set within the table data structure, the data set having associated therewith a range of rows of the table data structure;
• wherein data items in the data set are represented by key-value pairs;
• wherein the key of each key-value pair uniquely corresponds to the value of the key-value pair;
• applying a first compression to the values of the key-value pairs in the data set to produce a first compressed output;
• and
• applying a second compression to the first compressed output and to uncompressed keys of the key-value pairs in the data set to produce a first compressed output block, wherein the second compression is distinct from the first compression and the first compressed output block is stored in a computer readable medium.

A system for storing data, comprising:

• at least one processor;
• storage to store a table data structure, the table data structure including a plurality of rows and columns for storing data, wherein the rows have associated row identifiers, the columns have associated column identifiers, and each of a plurality of data items is stored in the table data structure at a respective cell in the table data structure specified by a respective row identifier and respective column identifier;
• executable instructions, executable by the at least one processor, including:
• instructions to access a data set within the table data structure, the data set having associated therewith a range of rows of the table data structure;
• wherein data items in the data set are represented by key-value pairs;
• wherein the key of each key-value pair uniquely corresponds to the value of the key-value pair;
• instructions to apply a first compression to the values of the key-value pairs in the data set to produce a first compressed output;
• instructions to apply a second compression, distinct from the first compression, to the keys of the key-value pairs in the data set to produce a second compressed output;
• and
• instructions to apply a third compression to the first compressed output and second compressed output to produce a first compressed output block, wherein the third compression is distinct from the first compression and second compression.

A system for storing data, comprising:

• at least one processor;
• storage to store a table data structure, the table data structure including a plurality of rows and columns for storing data, wherein the rows have associated row identifiers, the columns have associated column identifiers, and each of a plurality of data items is stored in the table data structure at a respective cell in the table data structure specified by a respective row identifier and respective column identifier;
• executable instructions, executable by the at least one processor, including:
• instructions to access a data set within the table data structure, the data set having associated therewith a range of rows of the table data structure;
• wherein data items in the data set are represented by key-value pairs;
• wherein the key of each key-value pair uniquely corresponds to the value of the key-value pair;
• instructions to apply a first compression to the values of the key-value pairs in the data set to produce a first compressed output;
• and
• instructions to applying a second compression to the first compressed output and to uncompressed keys of the key-value pairs in the data set to produce a first compressed output block, wherein the second compression is distinct from the first compression.

A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising instructions for:

• accessing a data set within the table data structure, the data set having associated therewith a range of rows of the table data structure;
• wherein data items in the data set are represented by key-value pairs;
• wherein the key of each key-value pair uniquely corresponds to the value of the key-value pair;
• applying a first compression to the values of the key-value pairs in the data set to produce a first compressed output;
• applying a second compression, distinct from the first compression, to the keys of the key-value pairs in the data set to produce a second compressed output;
• and
• applying a third compression to the first compressed output and second compressed output to produce a first compressed output block, wherein the third compression is distinct from the first compression and second compression.