Data compression for records of multidimensional database

• US 6,493,728 B1
• Filed: 06/22/2000
• Issued: 12/10/2002
• Est. Priority Date: 06/22/1999
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Berger, Alexander
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/602,615
• Time in Patent Office: 901 Days
• Field of Search: 707/202, 707/203, 707/101, 341/87
• US Class Current: 1/1
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• 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: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Compressing measure data in cell data records in a database is disclosed. The systems and methods of the invention define an efficient mechanism to compress measure data in a multidimensional database. The measure data stored in integer format within the cell record is compressed. If the measure data is constant within a measure data field then no space is used to store the measure data other than the value of the measure data stored within a header. The format used lends itself well to random access, and also to creating aggregations of the cell data.

Claims

1. A method for compressing a measure data of a cell record for a database, the method comprising:

accessing the measure data;

determining if the measure data may be compressed, and if so;

determining a size of a space to store the measure data in a compressed format;

storing a value in a header according to the determined size of the space;

compressing the measure data in accordance with the stored value to create a compressed measure data; and

storing the compressed measure data in a data store.

2. The method of claim 1, wherein accessing the measure data, comprises accessing the measure data in segments.

3. The method of claim 2, wherein determining the size of the space to store the measure data;

comprises;

determining a minimum value and a maximum value for the measure data; and

determining the size of the space based on the minimum and maximum value.

4. The method of claim 3, wherein determining the size of the space based on the minimum and maximum value, comprises:

setting the size of the space to zero if the minimum value equals the maximum value; and

setting the size of the space based on the maximum value if the minimum value is not equal to the maximum value.

5. The method of claim 4, wherein setting the size of the space based on the maximum value if the minimum value is not equal to the maximum value, comprises;

setting the size of the space to the number of bits used to represent the maximum value in binary format.

6. The method of claim 5, wherein compressing the measure data in accordance with the determined size to create a compressed measure data, comprises converting the measure data to binary format.

7. A system comprising:

a processor and a computer-readable medium;

an operating environment executing on the processor from the computer-readable medium;

a data store; and

an OLAP server executing under the control of the operating environment and operative to perform actions, including;

loading a plurality of cell records from a data store, the cell records having at least one measure data field;

calculating if each measure data field may be compressed, and if so;

calculating a compressed size of a space to store each measure data field in a compressed format;

storing each compressed size of each space in a header;

compressing each measure data in accordance with each compressed size to create at least one compressed measure data; and

storing each measure data in a data store.

8. The system of claim 7, wherein calculating the size of the space to store each measure data field;

comprises;

calculating a minimum value and a maximum value for each measure data field; and

calculating the compressed size of the space based on the minimum and maximum value.

9. The system of claim 8, wherein calculating the compressed size of the space based on the minimum and maximum value, comprises:

setting the compressed size of the space to zero if the minimum value equals the maximum value; and

setting the compressed size of the space based on the maximum value if the minimum value is not equal to the maximum value.

10. The system of claim 9, wherein setting the size of the space based on the maximum value if the minimum value is not equal to the maximum value, comprises;

setting the compressed size of the space to the number of bits used to represent the maximum value in binary format.

11. The system of claim 10, wherein compressing each measure data in accordance with the calculated size to create a compressed measure data, comprises converting each measure data to binary format.

12. A computer-readable medium readable by a computing system and having computer instructions for executing a computer process for compressing a set of measure data, the computer process comprising:

accessing a segmented set of measure data of a cell record for a database;

determining if the segmented set of measure data may be compressed;

determining a size of a space to store the set of measure data in a compressed format;

storing the size of the space in a header;

compressing the set of measure data in accordance with each determined size to create a set of compressed measure data; and

storing the set of measure data in a data store.

13. The computer-readable medium of claim 12, wherein the act of determining the size of the space to store the measure data;

comprises;

determining a minimum value and a maximum value for the set of measure data; and

determining the size of the space based on the minimum and maximum value.

14. The computer-readable medium of claim 13, wherein the act of determining the size of the space based on the minimum and maximum value, comprises:

setting the size of the space to zero if the minimum value equals the maximum value; and

calculating a difference between the minimum value and the maximum value; and

setting the size of the space based on the difference if the minimum value is not equal to the maximum value.

15. The computer-readable medium of claim 14, wherein the act of setting the size of the space based on the difference if the minimum value is not equal to the maximum value, comprises:

setting the size of the space to the number of bits used to represent the difference in binary format.

16. The computer-readable medium of claim 15, wherein the act of compressing the set of measure data converts the set of measure data to binary format.

17. Apparatus for compressing a measure data of a cell record in a database, said apparatus comprising:

a load module loading a plurality of cell records from a data store, the cell records having at least one measure data field;

a detector calculating if each measure data field may be compressed, and if so;

size module calculating a calculated size of a space to store each measure data field in a compressed format;

storage module storing each calculated size of each space in a header;

compression module compressing each measure data in accordance with each calculated size to create at least one compressed measure data; and

a data store storing each measure data.

18. The apparatus of claim 17, wherein said size module comprises:

a min/max module determining a minimum value and a maximum value for each measure data field and calculating the size of the space based on the minimum and maximum value.

19. The system of claim 18, wherein the min/max module, comprises:

a set module setting the size of the space to zero if the minimum value equals the maximum value and setting the size of the space based on the maximum value if the minimum value is not equal to the maximum value.

20. The system of claim 19, wherein said set module setting the size of the space based on the maximum value, if the minimum value is not equal to the maximum value, sets the size of the space to the number of bits used to represent the maximum value in binary format.

21. The system of claim 20, wherein said compression module converts each measure data to binary format.