Adaptive database caching and data retrieval mechanism

• US 6,493,718 B1
• Filed: 10/15/1999
• Issued: 12/10/2002
• Est. Priority Date: 10/15/1999
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Pasumansky, Mosha, Petculescu, Cristian, Berger, Alexander, Netz, Amir
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/419,437
• Time in Patent Office: 1,152 Days
• Field of Search: 707/102, 707/1, 707/2, 707/3, 707/100, 707/104.1, 707/205
• US Class Current: 707/600
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Systems, clients, servers, methods, and computer-readable media of varying scope are described in which, a data retrieval module of database client implements an aggressive caching scheme that seeks to predict what data cells will be needed to satisfy future queries. The data retrieval module applies an adaptive algorithm to dynamically determine the granularity of data to retrieve from a database server. The data retrieval module adaptively balances the benefit of satisfying future queries locally with the cost of retrieving larger data set from remote database server.

Claims

1. A computerized method for processing a query directed to a multidimensional database comprising:

for each dimension specified by the query, determining a set of member sub-hierarchies suitable for satisfying the query;

analyzing costs and benefits of retrieving the member sub-hierarchies from the multidimensional database;

selecting one of the member sub-hierarchies for each dimension as a function of the analysis; and

retrieving the selected member sub-hierarchies from the multidimensional database.

2. The computerized method of claim 1, wherein determining a set of member sub-hierarchies includes identifying those member sub-hierarchies that encompass a member specified by the query.

3. The computerized method of claim 1, wherein determining a set of member sub-hierarchies includes identifying those member sub-hierarchies from which the member specified by the query can be calculated.

4. The computerized method of claim 1, wherein determining the set of member sub-hierarchies includes generating combinations of each member of each dimension specified by the query.

5. The computerized method of claim 1, wherein determining the set of member sub-hierarchies includes generating a target table for each dimension of the database specified by the query, wherein the target table has a plurality of cells organized in a rows and columns, and further wherein each cell of the target table corresponds to a member sub-hierarchy within a dimension of the database.

6. The computerized method of claim 5, wherein the columns of the table represent hierarchical relationships of the dimension of the database.

7. The computerized method of claim 1, wherein analyzing the costs and the benefits includes for each identified member sub-hierarchy calculating a total number of data cells (T) including the corresponding member sub-hierarchy and all descendants of the member sub-hierarchy.

8. The computerized method of claim 7, wherein analyzing the costs and the benefits includes calculating for each identified member sub-hierarchy a corresponding number of necessary data cells (N) cells that fall within the total number of data cells (T) and that are required to satisfy the query.

9. The computerized method of claim 1, wherein analyzing the costs and the benefits includes calculating a cost-benefit ratio for each member sub-hierarchy.

10. The computerized method of claim 8, wherein analyzing the costs and the benefits includes calculating a cost-benefit ratio for each member sub-hierarchy, and further wherein the cost-benefit ratio equals N/T.

11. The computerized method of claim 10, wherein selecting one or more of the member sub-hierarchies includes rejecting the member sub-hierarchies having a corresponding ratio less than a predefined threshold.

12. The computerized method of claim 1, wherein selecting one or more of the member sub-hierarchies is a function of cache memory available on a database client.

13. The computerized method of claim 1, wherein selecting one or more of the member sub-hierarchies includes applying a predefined policy.

14. The computerized method of claim 13, wherein applying a predefined policy includes selecting member sub-hierarchies approximating those data cells visibly displayed by a software application.

15. The computerized method of claim 13, wherein applying a predefined policy includes selecting member sub-hierarchies in order to maximize the data cells retrieved.

16. The computerized method of claim 13, wherein applying a predefined policy includes selecting member sub-hierarchies as a function of an allotted cache size.

17. The computerized method of claim 13, wherein applying a predefined policy includes selecting member sub-hierarchies in an isolation mode without limitation of an allotted cache size.

18. The computerized method of claim 1, wherein retrieving data from the database includes retrieving data from an OLAP server via an OLAP client.

19. A computer-readable medium having computer-executable instructions for performing a method for processing a query directed to a multidimensional database, the method comprising:

for each dimension specified by the query, determining a set of member sub-hierarchies suitable for satisfying the query;

analyzing costs and benefits of retrieving the member sub-hierarchies from the multidimensional database;

selecting one of the member sub-hierarchies for each dimension as a function of the analysis; and

retrieving the selected member sub-hierarchies from the multidimensional database.

20. The computer-readable medium of claim 19, wherein determining a set of member sub-hierarchies includes identifying those member sub-hierarchies that encompass a member specified by the query.

21. The computer-readable medium of claim 19, wherein determining a set of member sub-hierarchies includes identifying those member sub-hierarchies from which the member specified by the query can be calculated.

22. The computer-readable medium of claim 19, wherein determining the set of member sub-hierarchies includes generating combinations of each member of each dimension specified by the query.

23. The computer-readable medium of claim 19, wherein determining the set of member sub-hierarchies includes generating a target table for each dimension of the database specified by the query, wherein the target table has a plurality of cells organized in a rows and columns, and further wherein each cell of the target table corresponds to a member sub-hierarchy within a dimension of the database.

24. The computer-readable medium of claim 23, wherein the columns of the table represent hierarchical relationships of the dimension of the database.

25. The computer-readable medium of claim 19, wherein analyzing the costs and the benefits includes for each identified member sub-hierarchy calculating a total number of data cells (T) including the corresponding member sub-hierarchy and all descendants of the member sub-hierarchy.

26. The computer-readable medium of claim 25, wherein analyzing the costs and the benefits includes calculating for each identified member sub-hierarchy a corresponding number of necessary data cells (N) cells that fall within the total number of data cells (T) and that are required to satisfy the query.

27. The computer-readable medium of claim 19, wherein analyzing the costs and the benefits includes calculating a cost-benefit ratio for each member sub-hierarchy.

28. The computer-readable medium of claim 26, wherein analyzing the costs and the benefits includes calculating a cost-benefit ratio for each member sub-hierarchy, and further wherein the cost-benefit ratio equals N/T.

29. The computer-readable medium of claim 19, wherein selecting one or more of the member sub-hierarchies includes rejecting the member sub-hierarchies having a corresponding ratio less than a predefined threshold.

30. The computer-readable medium of claim 19, wherein selecting one or more of the member sub-hierarchies is a function of cache memory available on a database client.

31. The computer-readable medium of claim 19, wherein selecting one or more of the member sub-hierarchies includes applying a predefined policy.

32. The computer-readable medium of claim 31, wherein applying a predefined policy includes selecting member sub-hierarchies approximating those data cells visibly displayed by a software application.

33. The computer-readable medium of claim 31, wherein applying a predefined policy includes selecting member sub-hierarchies in order to maximize the data cells retrieved.

34. The computer-readable medium of claim 31, wherein applying a predefined policy includes selecting member sub-hierarchies as a function of an allotted cache size.

35. The computer-readable medium of claim 31, wherein applying a predefined policy includes selecting member sub-hierarchies in an isolation mode without limitation of an allotted cache size.

36. The computer-readable medium of claim 19, wherein retrieving data from the database includes retrieving data from an OLAP server via an OLAP client.

37. A computerized system comprising:

a processor and a computer-readable medium;

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

a database client executing within the operating environment for interfacing with a database server having a multidimensional database, wherein an OLAP client processes a database query by;

determining a set of member sub-hierarchies for each dimension specified by the query that are suitable for satisfying the query;

analyzing costs and benefits of retrieving the member sub-hierarchies from the multidimensional database of the database server;

selecting one of the member sub-hierarchies for each dimension as a function of the analysis; and

retrieving the selected member sub-hierarchies from the multidimensional database.

38. The computerized system of claim 37, wherein determining a set of member sub-hierarchies includes identifying those member sub-hierarchies that encompass a member specified by the query.

39. The computerized system of claim 37, wherein determining a set of member sub-hierarchies includes identifying those member sub-hierarchies from which the member specified by the query can be calculated.

40. The computerized system of claim 37, wherein determining the set of member sub-hierarchies includes generating combinations of each member of each dimension specified by the query.

41. The computerized system of claim 37, wherein determining the set of member sub-hierarchies includes generating a target table for each dimension of the database specified by the query, wherein the target table has a plurality of cells organized in a rows and columns, and further wherein each cell of the target table corresponds to a member sub-hierarchy within a dimension of the database.

42. The computerized system of claim 41, wherein the columns of the table represent hierarchical relationships of the dimension of the database.

43. The computerized system of claim 37, wherein analyzing the costs and the benefits includes for each identified member sub-hierarchy calculating a total number of data cells (T) including the corresponding member sub-hierarchy and all descendants of the member sub-hierarchy.

44. The computerized system of claim 43, wherein analyzing the costs and the benefits includes calculating for each identified member sub-hierarchy a corresponding number of necessary data cells (N) cells that fall within the total number of data cells (T) and that are required to satisfy the query.

45. The computerized system of claim 37, wherein analyzing the costs and the benefits includes calculating a cost-benefit ratio for each member sub-hierarchy.

46. The computerized system of claim 44, wherein analyzing the costs and the benefits includes calculating a cost-benefit ratio for each member sub-hierarchy, and further wherein the cost-benefit ratio equals N/T.

47. The computerized system of claim 46, wherein selecting one or more of the member sub-hierarchies includes rejecting the member sub-hierarchies having a corresponding ratio less than a predefined threshold.

48. The computerized system of claim 37, wherein selecting one or more of the member sub-hierarchies is a function of cache memory available on a database client.

49. The computerized system of claim 37, wherein selecting one or more of the member sub-hierarchies includes applying a predefined policy.

50. The computerized system of claim 49, wherein applying a predefined policy includes selecting member sub-hierarchies approximating those data cells visibly displayed by a software application.

51. The computerized system of claim 49, wherein applying a predefined policy includes selecting member sub-hierarchies in order to maximize the data cells retrieved.

52. The computerized system of claim 49, wherein applying a predefined policy includes selecting member sub-hierarchies as a function of an allotted cache size.

53. The computerized system of claim 49, wherein applying a predefined policy includes selecting member sub-hierarchies in an isolation mode without limitation of an allotted cache size.

54. The computerized system of claim 37, wherein the database is a relational database system.

55. The computerized system of claim 37, wherein the database server is an OLAP server.

56. The computerized system of claim 37, wherein the database client is an OLAP client.