Defining and characterizing an analysis space for precomputed views

• US 6,493,699 B2
• Filed: 03/25/1999
• Issued: 12/10/2002
• Est. Priority Date: 03/27/1998
• Status: Expired due to Term

• Current Assignee: Workday Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Haslam, Edward P, Cole, Richard L., McKenna, William J., Johnson, Galt, Colby, Latha S., Wilhite, David G. Jr., Jazayeri, Nasi
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US09/277,034
• Publication Number:
  US 20010013030A1
• Time in Patent Office: 1,356 Days
• Field of Search: 707/1, 707/2, 707/3, 707/102, 707/200, 345/339
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• 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/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

Methods and apparatus for processing precomputed views for answering user queries on a database are described. In accordance with one aspect, a user database query on precomputation strategy effectiveness is responded to by defining, based upon user database query history, an analysis space consisting of a subset of all possible views for the database, and by characterizing the views in the analysis space. In accordance with a second aspect, a structure is imposed on an analysis space consisting of a subset of all possible views for the database based upon the capabilities of a query rewriting facility, and the views in the analysis space are characterized. In accordance with a third aspect, an analysis space consisting of a subset of all possible views for the database is defined, and a cost formula is applied to the analysis space based upon a user-defined subset of the data contained in the database. In accordance with a fourth aspect, an analysis space that includes a candidate view composed of a combination of two or more constituent views is defined, and the views in the analysis space are characterized.

Claims

1. A method of managing precomputed views for answering queries on a database, comprising:

defining an analysis space that includes any combination of existing and potential precomputed views for the database;

keeping a history of queries on the database;

performing a cost-benefit analysis of the existing and potential precomputed views in the analysis space, the analysis being based at least in part on the history of queries on the database; and

presenting a result of the cost-benefit analysis to determine a set of existing precomputed views to retain and a set of potential precomputed views to create for use in responding to future queries.

2. The method of claim 1, wherein keeping a history of queries on the database includes generating a log record of queries on the database.

3. The method of claim 1, wherein keeping a history of queries on the database includes parsing query blocks of queries on the database.

4. The method of claim 1, wherein keeping a history of queries on the database includes determining whether a query on the database was rewritten to include a precomputed view.

5. The method of claim 4, further comprising:

when a query was rewritten to include a precomputed view, keeping information about the precomputed view included in the rewritten query.

6. The method of claim 1, wherein keeping a history of queries on the database includes determining whether rewritten queries include aggregation.

7. The method of claim 1, wherein keeping a history of queries on the database includes identifying a potential precomputed view which could have been used to rewrite a query on the database.

8. The method of claim 7, further comprising:

keeping information about the potential precomputed view.

9. The method of claim 1, wherein the analysis space is defined based upon capabilities of a query rewriting facility.

10. The method of claim 9, wherein the definition of the analysis space reflects whether or not queries have been rewritten.

11. The method of claim 9, wherein the definition of the analysis space reflects whether or not rewritten queries include aggregation.

12. The method of claim 1, wherein the defined analysis space includes potential and existing precomputed views.

13. The method of claim 1, wherein the defined analysis space includes potential precomputed views generated based upon user query history.

14. The method of claim 1, wherein performing a cost-benefit analysis of the precomputed views in the analysis space comprises generating a measure of precomputed view utilization.

15. The method of claim 1, wherein performing a cost-benefit analysis of the views in the analysis space includes generating a measure of benefit of a precomputed view relative to other precomputed views in the analysis space.

16. The method of claim 15, wherein performing a cost-benefit analysis of the precomputed views in the analysis space includes generating a measure of benefit of one that is a potential precomputed view.

17. The method of claim 1, wherein performing a cost-benefit analysis of the precomputed views in the analysis space comprises generating a report that reflects current precomputation strategy effectiveness.

18. The method of claim 1, wherein performing a cost-benefit analysis of the precomputed views in the analysis space comprises generating a report that includes information about potential precomputed views that could be created.

19. The method of claim 1, wherein performing a cost-benefit analysis of the precomputed views in the analysis space comprises applying a cost formula to the analysis space.

20. The method of claim 1, further comprising:

determining hierarchical relationships between possible views in the analysis space; and

performing the cost-benefit analysis based on the hierarchical relationships.

21. The method of claim 1, wherein defining is based upon user database query history.

22. A method of managing precomputed views for answering queries on a database, comprising:

defining an analysis space that includes one or more precomputed views for the database, the one or more precomputed views including a potential precomputed view;

determining hierarchical relationships of the one or more precomputed views in the analysis space;

performing a cost-benefit analysis of the views in the analysis space based on the hierarchical relationships; and

presenting a result of the cost-benefit analysis to determine a set of existing precomputed views to retain and a set of potential precomputed views to create for use in responding to future queries.

23. The method of claim 22, wherein determining hierarchical relationships is based upon meta data.

24. The method of claim 22, wherein determining hierarchical relationships is based upon capabilities of a query rewriting facility.

25. A method of managing precomputed views for answering queries on a database, comprising:

defining an analysis space that includes a potential precomputed view composed of a combination of two or more constituent views;

performing a cost-benefit analysis of the potential precomputed view in the analysis space; and

presenting a result of the cost-benefit analysis to determine a set of existing precomputed views to retain and a set of potential precomputed views to create for use in responding to future queries.

26. The method of claim 25, wherein at least one of the constituent views of the potential precomputed view is another potential precomputed view.

27. The method of claim 25, wherein at least one of the constituent views of the potential precomputed view is an existing precomputed view.

28. The method of claim 25, wherein the defined analysis space includes the constituent views of the potential precomputed view.

29. The method of claim 25, wherein the defined analysis space does not include the constituent views of the potential precomputed view.

30. An apparatus for processing precomputed views for answering user queries on a database, comprising:

a query processor; and

an advisor configured to describe precomputation strategy effectiveness by defining an analysis space that includes any combination of existing and potential precomputed views for the database, keeping a history of queries processed by the query processor, and performing a cost-benefit analysis of the views in the analysis space, the analysis based at least in part on the history of queries, and presenting a result of the cost- benefit analysis to determine a set of existing precomputed views to retain and a set of potential precomputed views to create for use in responding to future queries.

31. The apparatus of claim 30, wherein keeping a history of queries processed by the query processor includes generating a log record of received queries.

32. The apparatus of claim 31, wherein the log record of received queries includes information about a precomputed view included in a rewritten query.

33. The apparatus of claim 31, wherein the log record of received queries includes information about a potential precomputed view which could have been used to rewrite the query.

34. The apparatus of claim 30, wherein keeping a history of queries processed by the query processor includes parsing query blocks of queries processed by the query processor.

35. The apparatus of claim 30, wherein keeping a history of queries processed by the query processor includes determining whether a query was rewritten to include a precomputed view.

36. The apparatus of claim 30, wherein keeping a history of queries processed by the query processor includes determining whether a rewritten query includes aggregation.

37. The apparatus of claim 30, wherein keeping a history of queries processed by the query processor includes identifying a potential precomputed view which could have been used to rewrite a query processed by the query processor.

38. The apparatus of claim 30, wherein the analysis space is defined based upon capabilities of a query rewriting facility.

39. The apparatus of claim 38, wherein the definition of the analysis space reflects whether or not queries processed by the query processor have been rewritten.

40. The apparatus of claim 38, wherein the definition of the analysis space reflects whether or not rewritten queries include aggregation.

41. The apparatus of claim 30, wherein the analysis space is defined based upon meta data.

42. The apparatus of claim 30, wherein the defined analysis space includes potential precomputed views generated based upon the history of queries processed by the query processor.

43. The apparatus of claim 30, wherein performing a cost-benefit analysis of the precomputed views in the analysis space includes generating a measure of precomputed view utilization.

44. The apparatus of claim 30, wherein performing a cost-benefit analysis of the precomputed views in the analysis space includes generating a measure of benefit of a precomputed view relative to other precomputed views in the analysis space.

45. The apparatus of claim 30, wherein presenting the result of the cost-benefit analysis of the views in the analysis space comprises generating a report that reflects current precomputation strategy effectiveness.

46. The apparatus of claim 30, wherein performing a cost-benefit analysis of the views in the analysis space includes generating a report that includes information about a potential precomputed view which could have been used to rewrite the query.

47. The apparatus of claim 30, wherein performing a cost-benefit analysis of the precomputed views in the analysis space includes applying a cost formula to the analysis space.

48. The apparatus of claim 30, wherein the advisor is further configured to describe precomputation strategy effectiveness by:

determining hierarchical relationships of the one or more precomputed views in the analysis space; and

performing the cost-benefit analysis based at least in part on the hierarchical relationships.

49. An apparatus for processing precomputed views for answering user queries on a database, comprising:

a query processor; and

an advisor configured to define an analysis space that includes one or more precomputed views for the database, the one or more precomputed views including a potential precomputed view, determine hierarchical relationships of the precomputed views in an analysis space, and perform a cost-benefit analysis of the precomputed views in the analysis space based at least in part on the hierarchical relationships, and present a result of the cost-benefit analysis to determine a set of existing precomputed views to retain and a set of potential precomputed views to create for use in responding to future queries.

50. The apparatus of claim 49, wherein the hierarchical relationships are determined based upon meta data.

51. The apparatus of claim 49, wherein the hiearchical relationships are determined based upon capabilities of a query rewriting facility.

52. An apparatus for processing precomputed views for answering user queries on a database, comprising:

a query processor; and

an advisor configured to define an analysis space that includes a potential precomputed view composed of a combination of two or more constituent views, perform a cost-benefit analysis of the views in the analysis space, and present a result of the cost-benefit analysis to determine a set of existing precomputed views to retain and a set of potential precomputed views to create for use in responding to future queries.

53. The apparatus of claim 52, wherein at least one of the constituent views of the potential precomputed view is a potential precomputed view.

54. The apparatus of claim 52, wherein at least one of the constituent views of the potential precomputed view is another potential precomputed view.

55. The apparatus of claim 52, wherein the defined analysis space includes the constituent views of the potential precomputed view.

56. The apparatus of claim 52, wherein the defined analysis space does not include the constituent views of the potential precomputed view.

57. A computer program product, tangibly stored on a computer-readable medium, for processing precomputed views for answering queries on a database, comprising instructions operable to cause a programmable processor to:

define an analysis space that includes any combination of possible views for the database,

perform a cost-benefit analysis of the views in the analysis space; and

present a result of the cost-benefit analysis to determine a set of existing precomputed views to retain and a set of potential precomputed views to create for use in responding to future queries.

58. The computer program product of claim 57, wherein the analysis space is defined based upon capabilities of a query rewriting facility.

59. The computer program product of claim 58, wherein the definition of the analysis space reflects whether or not received queries have been rewritten.

60. The computer program product of claim 58, wherein the definition of the analysis space reflects whether or not rewritten queries include aggregation.

61. The computer program product of claim 57, wherein the analysis space is defined based upon meta data.

62. The computer program product of claim 57, wherein the defined analysis space includes precomputed views.

63. The computer program product of claim 57, wherein the defined analysis space includes potential precomputed views generated based upon query history.

64. The computer program product of claim 57, wherein instructions to perform a cost-benefit analysis comprise instructions operable to cause a programmable processor to generate a measure of precomputed view utilization.

65. The computer program product of claim 57, wherein instructions to perform a cost-benefit analysis comprise instructions operable to cause a programmable processor to generate a measure of benefit of a precomputed view relative to other views in the analysis space.

66. The computer program product of claim 57, wherein instructions to perform a cost-benefit analysis comprise instructions operable to cause a programmable processor to generate a report that reflects current precomputation strategy effectiveness.

67. The computer program product of claim 57, wherein instructions to perform a cost-benefit analysis comprise instructions operable to cause a programmable processor to generate a report that includes information about candidate views that could be created.

68. The computer program product of claim 57, wherein instructions to perform a cost-benefit analysis comprise instructions operable to cause a programmable processor to generate a measure of benefit of a potential precomputed view relative to other views in the analysis space.

69. The computer program product of claim 57, wherein instructions to perform a cost-benefit analysis comprise instructions operable to cause a programmable processor to apply a cost formula to the analysis space.

70. The computer program product of claim 57, further comprising instructions operable to cause a programmable processor to:

determine hierarchical relationships between the possible views in the analysis space; and

perform the cost-benefit analysis based on the hierarchical relationships.

71. The computer program product of claim 57, wherein the analysis space is defined based upon database query history.

72. The computer program product of claim 70, wherein the instructions to define an analysis space comprise instructions operable to cause a programmable processor to generate a log record for received queries.

73. The computer program product of claim 72, wherein the instructions to generate a log record comprise instructions operable to cause a programmable processor to parse query blocks from queries.

74. The computer program product of claim 72, wherein instructions to generate a log record for a user query comprises instructions operable to cause a programmable processor to determine whether the query was rewritten to include a precomputed view.

75. The computer program product of claim 72, wherein instructions to generate a log record comprises instructions operable to cause a programmable processor to determine whether rewritten user queries include aggregation.

76. The computer program product of claim 72, wherein instructions to generate a log record comprises instructions operable to cause a programmable processor to identify a potential precomputed view which could have been used to rewrite the received queries.

77. The computer program product of claim 72, wherein the log record generated for a query comprises information about a precomputed view used to rewrite the query.

78. The computer program product of claim 72, wherein the log record generated for a user query comprises information about a potential precomputed view which could have been used to rewrite the received query.

79. A computer program product, tangibly stored on a computer-readable medium, for processing precomputed views for answering queries on a database, comprising instructions operable to cause a programmable processor to:

determine hierarchical relationships between or among views in an analysis space that includes any combination of potential precomputed of potential precomputed views for the database;

perform a cost-benefit analysis of the views in the analysis space based on the hierarchiacal relationships; and

present a result of the cost-benefit analysis to determine a set of existing precomputed views to retain and to create a set of potential precomputed views for use in responding to future queries.

80. The computer program product of claim 79, wherein the hierarchical relationships are determined based upon meta data.

81. The computer program product of claim 79, wherein the hierarchical relationships are determined based upon capabilities of a query rewriting facility.

82. A computer program product, tangibly stored on a computer-readable medium, for processing precomputed views for answering queries on a database, comprising instructions operable to cause a programmable processor to:

define an analysis space that includes a potential precomputed view composed of a combination of two or more constituent views; and

perform a cost-benefit analysis of the views in the analysis space; and

present a result of the cost-benefit analysis to determine a set of existing precomputed views to retain and a set of potential precomputed views to create for use in responding to future queries.

83. The computer program product of claim 82, wherein at least one of the constituent views of the potential precomputed view is another potential precomputed view.

84. The computer program product of claim 82, wherein at least one of the constituent views of the potential precomputed view is a precomputed view.

85. The computer program product of claim 82, wherein the defined analysis space includes the constituent views of the potential precomputed view.

86. The computer program product of claim 82, wherein the defined analysis space does not include the constituent views of the potential precomputed view.