Method and apparatus for accessing multidimensional data

• US 7,734,661 B2
• Filed: 08/11/2004
• Issued: 06/08/2010
• Est. Priority Date: 08/11/2003
• Status: Expired due to Fees

• Current Assignee: Descisys Limited
• Original Assignee: Descisys Limited
• Inventors: Stewart, Jerry, Ng, Keith Steffen, Sanders, Michael John, Jordan, Philip Martin
• Primary Examiner(s): Pham; Hung Q
• Application Number:
  US10/915,570
• Publication Number:
  US 20050071349A1
• Time in Patent Office: 2,127 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/999.001, 707/999.002, 707/999.1, 707/999.101, 707/999.2
• US Class Current: 707/803
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

A method of indexing data in a multidimensional database includes creating a multidimensional logical access model, creating a multidimensional data storage model in which data is located in cells that are stored and retrieved in blocks, gathering data access information derived from one or more user queries of the database, and reorganizing one or more selected cells in the multidimensional data storage model based on the data access information to reduce the time taken to access the one or more selected cells in response to a user query of the database. A computerized apparatus in communication with a multidimensional database includes a program to perform the method. A computer readable medium contains instructions to cause a computer to perform the method.

Claims

1. A method of reorganizing existing data in a multidimensional database, the method comprising:

providing a multidimensional data storage model in which data is located in cells that are stored and retrieved in blocks, each block comprising one or more cells;

providing a multidimensional logical access model independent of the multidimensional data storage model, the multidimensional logical access model comprising a tree index having one or more leaf nodes each corresponding with a cell and pointing to a block in the multidimensional data storage model containing the cell;

gathering, by a computer system, historical data access information derived from a plurality of user queries of the multidimensional database, the gathered historical data access information comprising identifications of all existing cells that have been accessed and the number of times that each cell has been accessed;

determining, by the computer system, for a first frequently-accessed cell, a second cell which is most frequently accessed along with the first frequently-accessed cell, using the gathered historical data access information; and

reorganizing, by the computer system, one or more selected existing cells in the multidimensional data storage model by moving one or both of the first frequently-accessed and second cells into the same block irrespective of the data located therein to minimize the number of blocks retrieved to access cells required in response to a typical user query of the multidimensional database whereby the multidimensional data access model is optimized to respond to queries that are incongruent with the structure of the multidimensional logical access model.

2. The method as claimed in claim 1 wherein the reorganizing of one or more selected cells into one or more blocks further comprises reorganizing cells such that cells that are unlikely to be accessed together are not provided in the same block.

3. A computerized apparatus in communication with a multidimensional database and including a program to perform the method of claim 2.

4. The method as claimed in claim 1 wherein the reorganizing includes performing a first calculation of the cost of access to the one or more selected cells prior to reorganization and a second calculation of the expected cost of access to the one or more selected cells after reorganization, and reorganizing the one or more selected cells if the second calculation returns a lower cost than the first calculation.

5. The method as claimed in claim 1 wherein the tree index is a dimensionally hierarchical index tree.

6. The method as claimed in claim 5 including determining from the historical data access information one or more selected sub-trees of the multidimensional logical access model that index selected cells that are likely to be accessed together, and

re-ordering the structure of the one or more of selected sub-trees by either merging the selected one or more sub-trees, or re-ordering the dimensional hierarchy of the one or more selected sub-trees so that fewer branches of the dimensionally hierarchical index tree are required to be accessed to access the selected cells.

7. The method as claimed in claim 6 wherein merging the one or more selected sub-trees includes merging related leaf level nodes of the one or more sub-trees.

8. The method as claimed in claim 6 including merging the lowest two or three dimensions.

9. The method as claimed in claim 6 including merging two to fifty members in a dimension.

10. The method as claimed in claim 6 wherein re-ordering the dimensional hierarchy includes performing a member frequency analysis for the selected cells non-fixed dimensions, sorting the results of the analysis to provide a list of non-fixed dimensions sorted by the number of members in each from the non-fixed dimension with the least number of members to the non-fixed dimension with the largest number of members, and re-ordering the one or more sub-trees in accordance with the list.

11. The method as claimed in claim 10 including providing a re-ordering threshold, and changing the order of any two dimensions if the proportional difference between the members for each dimension is greater than the re-ordering threshold.

12. The method as claimed in claim 10 including re-organizing cells within blocks following any change in dimension order.

13. The method as claimed in claim 12 including defining a path limit, analysing the index path distance between each cell in the one or more sub-trees and the block to which the cell belongs, and re-organising the cell into another block if the index path for the cell exceeds the path limit.

14. The method as claimed in claim 1 wherein reorganization of the one or more selected existing cells in the multidimensional data storage model does not necessitate any change to the multidimensional access model.

15. The method as claimed in claim 1 wherein the historical data access information includes statistical information identifying cells that are likely to be accessed in future user queries.

16. The method as claimed in claim 1 wherein the time required to access a cell in a previously retrieved block is less than the time required to access a cell in a non-retrieved block.

17. A computer readable medium containing instructions to cause a computer to perform the method of claim 1.