Method for determining the computability of data for an active multi-dimensional cache in a relational database management system

• US 6,763,357 B1
• Filed: 06/27/2000
• Issued: 07/13/2004
• Est. Priority Date: 06/27/2000
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation
• Inventors: Deshpande, Prasad Manikarao, Shukla, Amit, Ramasamy, Karthikeyan, Naughton, Jeffrey F.
• Primary Examiner(s): Pardo, Thuy N.
• Application Number:
  US09/605,202
• Time in Patent Office: 1,477 Days
• Field of Search: 707/2, 707/100, 707/101, 707/102, 707/104, 707/103, 707/3, 707/10, 709/217
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

An “active cache”, for use by On-Line Anaytic Processing (OLAP) systems, that can not only answer queries that match data stored in the cache, but can also answer queries that require aggregation or other computation of the data stored in the cache.

Claims

1. A method for caching multi-dimensional data sets for an on-line analytical processing (OLAP) system, comprising:

(a) accessing multi-dimensional data from a relational database management system (RDBMS) in order to answer at least a portion of a first query;

(b) storing the multi-dimensional data in an active cache;

(c) determining when it is possible to answer at least a portion of a second query by aggregating the multi-dimensional data stored in the cache; and

(d) selecting from among a plurality of aggregation paths and answering the portion of the second query by aggregating the multi-dimensional data stored in the cache using the selected aggregation path, after it has been determined that it is possible to answer the portion of the second query by aggregating the multi-dimensional data stored in the cache.

2. The method of claim 1, wherein the selecting step further comprises selecting a fastest aggregation path to answer the portion of the second query.

3. The method of claim 2, wherein the selecting step further comprises maintaining cost-based information using a virtual count method to determine the fastest aggregation path.

4. The method of claim 3, wherein the aggregated data stored in the cache includes a plurality of aggregation levels.

5. The method of claim 4, wherein each of the aggregation levels corresponds to a different GROUP-BY operation performed on the multi-dimensional data.

6. The method of claim 5, wherein the multi-dimensional data is stored in the cache using chunk-based caching.

7. The method of claim 6, further comprising determining whether a chunk resulting from a particular GROUP-BY operation can be computed from the multi-dimensional data stored in the cache by exploring all of the paths in the lattice from a node representing the particular GROUP-BY operation to a node representing a base GROUP-BY operation.

8. The method of claim 7, wherein a virtual count method maintains a virtual count for each chunk at each aggregation level, and a chunk is either directly present in the cache or a chunk is computed through a path in the lattice.

9. The method of claim 8, wherein the virtual count indicates a number of parents of a node through which there is a successful path, wherein the virtual count is incremented by one if the chunk is directly present in the cache.

10. The method of claim 9, wherein the virtual count is indicative of whether a chunk can be computed.

11. The method of claim 10, wherein if a node has k parents in the lattice, a chunk represented by the node cannot have a virtual count greater than k+1.

12. The method of claim 11, wherein the virtual count of a chunk is non-zero if it can be computed from the cache.

13. The method of claim 12, wherein the virtual count method maintains information about the chunks found on the successful path, so that they can be aggregated.

14. The method of claim 13, wherein if a chunk cannot be computed from the cache, then the virtual count method completes in constant time.

15. The method of claim 14, wherein if a chunk can be computed from the cache, then the virtual count method explores exactly one successful path in the lattice.

16. The method of claim 15, wherein unsuccessful paths in the lattice are rejected immediately without being explored completely.

17. The method of claim 16, further comprising maintaining the virtual counts when chunks are inserted or deleted from the cache.

18. The method of claim 17, wherein a cost based version of the virtual count method finds a best path in the lattice for computing a chunk by maintaining cost information in addition to the virtual count.

19. The method of claim 18, wherein the cost based version of the virtual count method further comprises, for each computable chunk, storing a least cost path to compute the chunk and the parent through which the least cost path passes.

20. The method of claim 19, further comprises updating the cost:

(1) when a chunk becomes newly computable, and (2) when the least cost of computing a chunk changes.

21. The method of claim 20, further comprising determining the least cost of computing a chunk in order to decide whether to aggregate the multi-dimensional data in the cache or access the multi-dimensional data from the relational database management system.

22. The method of claim 21, further comprising re-computing a benefit of a chunk whenever the chunk is used to compute another chunk in order to account for an aggregation benefit.

23. The method of claim 22, wherein the benefit of the chunk depends on how it has been computed:

(1) if the chunk has been computed by aggregating other chunks, then its benefit is equal to the cost of the aggregation;

or

(2) if the chunk has been computed at the relational database management system, then its benefit incorporates the cost of connecting to the relational database management system, issuing a query, and accessing results from the query.

24. The method of claim 23, further comprising forming groups of useful chunks in the cache to create higher benefits for all chunks in the group.

25. The method of claim 23, wherein the groups of useful chunks are generated by pre-computing GROUP-BY operations.

26. An on-line analytical processing (OLAP) system that caches multi-dimensional data sets, comprising:

(a) a computer system;

(b) logic, performed by the computer system, for;

(1) accessing multi-dimensional data from a relational database management system (RDBMS) in order to answer at least a portion of a first query;

(2) storing the multi-dimensional data in an active cache;

(3) determining when it is possible to answer at least a portion of a second query by aggregating the multi-dimensional data stored in the cache; and

(4) selecting from among a plurality of aggregation paths and answering the portion of the second query by aggregating the multi-dimensional data stored in the cache using the selected aggregation path, after it has been determined that it is possible to answer the portion of the second query by aggregating the multi-dimensional data stored in the cache.

27. The system of claim 26, wherein the logic for selecting further comprises logic for selecting a fastest aggregation path to answer the portion of the second query.

52. The article of manufacture of claim 27, wherein the selecting step further comprises selecting a fastest aggregation path to answer the portion of the second query.

53. The article of manufacture of claim 52, wherein the selecting step further comprises maintaining cost-based information using a virtual count method to determine the fastest aggregation path.

54. The article of manufacture of claim 53, wherein the aggregated data stored in the cache includes a plurality of aggregation levels.

55. The article of manufacture of claim 54, wherein each of the aggregation levels corresponds to a different GROUP-BY operation performed on the multi-dimensional data.

56. The article of manufacture of claim 55, wherein the multidimensional data is stored in the cache using chunk-based caching.

57. The article of manufacture of claim 56, further comprising determining whether a chunk resulting from a particular GROUP-BY operation can be computed from the multi-dimensional data stored in the cache by exploring all of the paths in the lattice from a node representing the particular GROUP-BY operation to a node representing a base GROUP-BY operation.

58. The article of manufacture of claim 57, wherein a virtual count method maintains a virtual count for each chunk at each aggregation level, and a chunk is either directly present in the cache or a chunk is computed through a path in the lattice.

59. The article of manufacture of claim 58, wherein the virtual count indicates a number of parents of a node through which there is a successful path, wherein the virtual count is incremented by one if the chunk is directly present in the cache.

60. The article of manufacture of claim 59, wherein the virtual count is indicative of whether a chunk can be computed.

61. The article of manufacture of claim 60, wherein if a node has k parents in the lattice, a chunk represented by the node cannot have a virtual count greater than k+1.

62. The article of manufacture of claim 61, wherein the virtual count of a chunk is non-zero if it can be computed from the cache.

63. The article of manufacture of claim 62, wherein the virtual count method maintains information about the chunks found on the successful path, so that they can be aggregated.

64. The article of manufacture of claim 63, wherein if a chunk cannot be computed from the cache, then the virtual count method completes in constant time.

65. The article of manufacture of claim 64, wherein if a chunk can be computed from the cache, then the virtual count method explores exactly one successful path in the lattice.

66. The article of manufacture of claim 65, wherein unsuccessfuil paths in the lattice are rejected immediately without being explored completely.

67. The article of manufacture of claim 66, further comprising maintaining the virtual counts when chunks are inserted or deleted from the cache.

68. The article of manufacture of claim 67, wherein a cost based version of the virtual count method finds a best path in the lattice for computing a chunk by maintaining cost information in addition to the virtual count.

69. The article of manufacture of claim 68, wherein the cost based version of the virtual count method further comprises, for each computable chunk, storing a least cost path to compute the chunk and the parent through which the least cost path passes.

70. The article of manufacture of claim 69, further comprises updating the cost:

(1) when, a chunk becomes newly computable, and (2) when the least cost of computing a chunk changes.

71. The article of manufacture of claim 70, further comprising determining the least cost of computing a chunk in order to decide whether to aggregate the multidimensional data in the cache or access the multi-dimensional data from the relational database management system.

72. The article of manufacture of claim 71, further comprising re-computing a benefit of a chunk whenever the chunk is used to compute another chunk in order to account for an aggregation benefit.

73. The article of manufacture of claim 72, wherein the benefit of the chunk depends on how it has been computed:

(1) if the chunk has been computed by aggregating other chunks, then its benefit is equal to the cost of the aggregation;

or

(2) if the chunk has been computed at the relational database management system, then its benefit incorporates the cost of connecting to the relational database management system, issuing a query, and accessing results from the query.

74. The article of manufacture of claim 73, further comprising forming groups of useful chunks in the cache to create higher benefits for all chunks in the group.

75. The article of manufacture of claim 73, wherein the groups of useful chunks are generated by pre-computing GROUP-BY operations.

28. An article of manufacture embodying logic for caching multi-dimensional data sets for an on-line analytical processing (OLAP) system, comprising:

(a) accessing multi-dimensional data from a relational database management system (RDBMS) in order to answer at least a portion of a first query;

(b) storing the multi-dimensional data in an active cache;

(c) determining when it is possible to answer at least a portion of a second query by aggregating the multi-dimensional data stored in the cache; and

(d) selecting from among a plurality of aggregation paths and answering the portion of the second query by aggregating the multi-dimensional data stored in the cache using the selected aggregation path, after it has been determined that it is possible to answer the portion of the second query by aggregating the multi-dimensional data stored in the cache.

29. The system of claim 28, wherein the logic for selecting further comprises logic for maintaining cost-based information using a virtual count method to determine the fastest aggregation path.

30. The system of claim 29, wherein the aggregated data stored in the cache includes a plurality of aggregation levels.

31. The system of claim 30, wherein each of the aggregation levels corresponds to a different GROUP-BY operation performed on the multi-dimensional data.

32. The system of claim 31, wherein the multi-dimensional data is stored in the cache using chunk-based caching.

33. The system of claim 32, further comprising logic for determining whether a chunk resulting from a particular GROUP-BY operation can be computed from the multi-dimensional data stored in the cache by exploring all of the paths in the lattice from a node representing the particular GROUP-BY operation to a node representing a base GROUP-BY operation.

34. The system of claim 33, wherein a virtual count method maintains a virtual count for each chunk at each aggregation level, and a chunk is either directly present in the cache or a chunk is computed through a path in the lattice.

35. The system of claim 34, wherein the virtual count indicates a number of parents of a node through which there is a successful path, wherein the virtual count is incremented by one if the chunk is directly present in the cache.

36. The system of claim 35, wherein the virtual count is indicative of whether a chunk can be computed.

37. The system of claim 36, wherein if a node has k parents in the lattice, a chunk represented by the node cannot have a virtual count greater than k+1.

38. The system of claim 37, wherein the virtual count of a chunk is non-zero if it can be computed from the cache.

39. The system of claim 38, wherein the virtual count method maintains information about the chunks found on the successful path, so that they can be aggregated.

40. The system of claim 39, wherein if a chunk cannot be computed from the cache, then the virtual count method completes in constant time.

41. The system of claim 40, wherein if a chunk can be computed from the cache, then the virtual count method explores exactly one successful path in the lattice.

42. The system of claim 41, wherein unsuccessful paths in the lattice are rejected immediately without being explored completely.

43. The system of claim 42, further comprising logic for maintaining the virtual counts when chunks are inserted or deleted from the cache.

44. The system of claim 43, wherein a cost based version of the virtual count method finds a best path in the lattice for computing a chunk by maintaining cost information in addition to the virtual count.

45. The system of claim 44, wherein the cost based version of the virtual count method further comprises, for each computable chunk, logic for storing a least cost path to compute the chunk and the parent through which the least cost path passes.

46. The system of claim 45, further comprises logic for updating the cost:

(1) when a chunk becomes newly computable, and (2) when the least cost of computing a chunk changes.

47. The system of claim 46, further comprising logic for determining the least cost of computing a chunk in order to decide whether to aggregate the multidimensional data in the cache or access the multi-dimensional data from the relational database management system.

48. The system of claim 47, further comprising logic for re-computing a benefit of a chunk whenever the chunk is used to compute another chunk in order to account for an aggregation benefit.

49. The system of claim 48, wherein the benefit of the chunk depends on how it has been computed:

(1) if the chunk has been computed by aggregating other chunks, then its benefit is equal to the cost of the aggregation;

or

(2) if the chunk has been computed at the relational database management system, then its benefit incorporates the cost of connecting to the relational database management system, issuing a query, and accessing results from the query.

50. The system of claim 49, further comprising logic for forming groups of useful chunks in the cache to create higher benefits for all chunks in the group.

51. The system of claim 49, wherein the groups of useful chunks are generated by pre-computing GROUP-BY operations.