EFFICIENT DATABASE COMPRESSION

• US 20120150877A1
• Filed: 12/09/2010
• Published: 06/14/2012
• Est. Priority Date: 12/09/2010
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ramamurthy, Ravishankar, Mohapatra, Abhijeet
• Application Number:
  US12/964,549
• Publication Number:
  US 20120150877A1
• Time in Patent Office: Days
• US Class Current: 707/752
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data

Abstract

A method for compressing data. The method includes accessing, within an electronic system, a database relation comprising a plurality of attributes and determining a sort order of the plurality of attributes of the database relation. The method further includes determining an order of a plurality of compression operators operable to compress the database relation and compressing the database relation to produce a compressed database based on the sort order and the order of the plurality compression operators.

Claims

1. A method for compressing data comprising:

accessing, within an electronic system, a database relation comprising a plurality of attributes;

determining a sort order of said plurality of attributes of said database relation;

determining an order of a plurality of compression operators operable to compress said database relation; and

compressing said database relation to produce a compressed database data based on said sort order and said order of said plurality compression operators.

2. The method as recited in claim 1 further comprising:

compressing said compressed database data with a general purpose compressor.

3. The method as recited in claim 1 wherein said plurality of compression operators comprises run-length encoding.

4. The method as recited in claim 3 wherein said plurality of compression operators further comprises delta coding.

5. The method as recited in claim 4 wherein said plurality of compression operators further comprises dictionary coding.

6. The method as recited in claim 1 further comprising:

restructuring said database relation based on one or more restructuring operators.

7. The method as recited in claim 6 wherein said restructuring operators comprises a first operator for vertically partitioning said database relation and a second operator for horizontally partitioning said database relation.

8. The method as recited in claim 1 wherein said compressed database data comprises a plurality of files, wherein each file of said plurality of files corresponds a respective attribute or a group of attributes of said plurality of attributes.

9. The method as recited in claim 1 wherein said order of said plurality of compression operators is determined based on the field size of each of said plurality of attributes.

10. The method as recited in claim 9 wherein said order of said plurality of compression operators is determined based on the number of distinct values for each of said plurality of attributes.

11. An apparatus for compressing database data comprising:

a restructuring module for restructuring a database relation;

a compression operator order module for determining an order of a plurality of compression operators; and

a compression module operator for compressing said database relation to produce a compressed database relation based on said order of compression operators and said structuring of said database relation.

12. The apparatus as recited in claim 11 further comprising:

a general purpose compressor operable to compress said compressed database relation.

13. The apparatus as recited in claim 11 further comprising:

a decompression module for decompressing said compressed database relation based on said restructuring of said database relation and said order of said plurality of compression operators.

14. The apparatus as recited in claim 11 wherein said plurality of compression operators is selected from the group consisting of run-length encoding, delta coding, and dictionary coding.

15. The apparatus as recited in claim 11 wherein said restructuring module is operable to horizontally partitioning said database relation.

16. The apparatus as recited in claim 11 wherein said order of said plurality of compression operators comprises a tree of compression operators.

17. The apparatus as recited in claim 16 wherein said order of said plurality of compression operators is based on a predetermined depth of said tree or based on a random sample of said database.

18. A method for compression a database comprising:

accessing a database relation, wherein said database relation comprises an attribute;

determining a sort order for a plurality of tuples corresponding to said attribute of said database relation;

determining a compression operator order for compressing said attribute of said database relation; and

compressing said attribute based on said compression operator order.

19. The method of claim 18 wherein said compression operator order is determined based on a number of runs for said attribute being greater than a number of distinct values of said attribute.

20. The method of claim 18 wherein said sort order is based on a minimum number of runs of said attribute.