DEFINING AND CHARACTERIZING AN ANALYSIS SPACE FOR PRECOMPUTED VIEWS

• US 20010013030A1
• Filed: 03/25/1999
• Published: 08/09/2001
• Est. Priority Date: 03/27/1998
• Status: Active Grant

• Current Assignee: Workday Incorporated
• Original Assignee: Informix Software, Inc. (International Business Machines Corporation)
• Inventors: JOHNSON, GALT, COLE, RICHARD L., MCKENNA, WILLIAM J., JAZAYERI, NASI, COLBY, LATHA S., HASLAM, EDWARD P., WILHITE, DAVID G. Jr.
• Granted Patent: US 6,493,699 B2
• Time in Patent Office: Days
• US Class Current: 707/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 processing precomputed views for answering user queries on a database, comprising:

in response to a user database query on precomputation strategy effectiveness, defining, based upon user database query history, an analysis space consisting of a subset of all possible views for the database, and characterizing the views in the analysis space.

2. The method of

claim 1

, wherein defining an analysis space comprises generating a log record for received user queries.

3. The method of

claim 2

, wherein generating a log record comprises parsing query blocks from user queries.

4. The method of

claim 2

, wherein generating a log record for a user query comprises determining whether the query was rewritten to use a precomputed view.

5. The method of

claim 2

, wherein generating a log record comprises determining whether rewritten user queries include aggregation.

6. The method of

claim 2

, wherein generating a log record comprises identifying a candidate view that could be used to rewrite user queries.

7. The method of

claim 2

, wherein the log record generated for a query comprises information about a precomputed view used to rewrite the query.

8. The method of

claim 2

, wherein the log record generated for a user query comprises information about a candidate view that could be used to rewrite the query.

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 user queries have been rewritten.

11. The method of

claim 9

, wherein the definition of the analysis space reflects whether or not rewritten user queries include aggregation.

12. The method of

claim 9

, wherein the query rewrite facility is configured to impose a structure on the analysis space.

13. The method of

claim 12

, wherein the imposed structure includes a graph representative of hierarchical relationships between views in the analysis space.

14. The method of

claim 1

, wherein the analysis space is defined based upon meta data.

15. The method of

claim 14

, wherein the analysis space is defined based upon hierarchical relationships among views.

16. The method of

claim 1

, wherein the defined analysis space includes precomputed views.

17. The method of

claim 1

, wherein the defined analysis space includes candidate views generated based upon user query history.

18. The method of

claim 1

, wherein characterizing the views in the analysis space comprises generating a measure of precomputed view utilization.

19. The method of

claim 1

, wherein characterizing the views in the analysis space comprises generating a measure of the benefit of a precomputed view relative to other views in the analysis space.

20. The method of

claim 1

, wherein characterizing the views in the analysis space comprises generating a report that reflects current precomputation strategy effectiveness.

21. The method of

claim 1

, wherein characterizing the views in the analysis space comprises generating a report that includes information about candidate views that could be created.

22. The method of

claim 1

, wherein characterizing the views in the analysis space comprises generating a measure of the benefit of a candidate view relative to other views in the analysis space.

23. The method of

claim 1

, wherein characterizing the views in the analysis space comprises applying a cost formula to the analysis space.

24. A method of processing precomputed views for answering user queries on a database, comprising:

imposing a structure 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

characterizing the views in the analysis space.

25. The method of

claim 24

, wherein structure is imposed on the analysis space based upon meta data.

26. The method of

claim 24

, wherein structure is imposed on the analysis space based upon hierarchical relationships between views in the analysis space.

27. A method of processing precomputed views for answering user queries on a database, comprising:

defining an analysis space consisting of a subset of all possible views for the database; and

applying a cost formula to the analysis space based upon a user-defined subset of the data contained in the database.

28. A method of processing precomputed views for answering user queries on a database, comprising:

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

characterizing the views in the analysis space.

29. The method of

claim 28

, wherein at least one of the constituent views of the candidate view is a candidate view.

30. The method of

claim 28

, wherein at least one of the constituent views of the candidate view is a precomputed view.

31. The method of

claim 28

, wherein the defined analysis space includes the constituent views of the candidate view.

32. The method of

claim 28

, wherein the defined analysis space does not include the constituent views of the candidate view.

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

a query processor; and

an advisor configured to respond to a user database query on precomputation strategy effectiveness 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.

34. The apparatus of

claim 33

, wherein defining an analysis space comprises generating a log record for received user queries.

35. The apparatus of

claim 34

, wherein generating a log record comprises parsing query blocks from user queries.

36. The apparatus of

claim 34

, wherein generating a log record for a user query comprises determining whether the query was rewritten to use a precomputed view.

37. The apparatus of

claim 34

, wherein generating a log record comprises determining whether rewritten user queries include aggregation.

38. The apparatus of

claim 34

, wherein generating a log record comprises identifying a candidate view that could be used to rewrite user queries.

39. The apparatus of claim 34, wherein the log record generated for a query comprises information about a precomputed view used to rewrite the query.

40. The apparatus of

claim 34

, wherein the log record generated for a user query comprises information about a candidate view that could be used to rewrite the query.

41. The apparatus of

claim 33

, wherein the analysis space is defined based upon capabilities of a query rewriting facility.

42. The apparatus of

claim 41

, wherein the definition of the analysis space reflects whether or not user queries have been rewritten.

43. The apparatus of

claim 41

, wherein the definition of the analysis space reflects whether or not rewritten user queries include aggregation.

44. The apparatus of

claim 41

, wherein the query rewrite facility is configured to impose a structure on the analysis space.

45. The apparatus of

claim 44

, wherein the imposed structure includes a graph representative of hierarchical relationships between views in the analysis space.

46. The apparatus of

claim 33

, wherein the analysis space is defined based upon meta data.

47. The apparatus of

claim 46

, wherein the analysis space is defined based upon hierarchical relationships among views.

48. The apparatus of

claim 33

, wherein the defined analysis space includes precomputed views.

49. The apparatus of

claim 33

, wherein the defined analysis space includes candidate views generated based upon user query history.

50. The apparatus of

claim 33

, wherein characterizing the views in the analysis space comprises generating a measure of precomputed view utilization.

51. The apparatus of

claim 33

, wherein characterizing the views in the analysis space comprises generating a measure of the benefit of a precomputed view relative to other views in the analysis space.

52. The apparatus of

claim 33

, wherein characterizing the views in the analysis space comprises generating a report that reflects current precomputation strategy effectiveness.

53. The apparatus of

claim 33

, wherein characterizing the views in the analysis space comprises generating a report that includes information about candidate views that could be created.

54. The apparatus of

claim 33

, wherein characterizing the views in the analysis space comprises generating a measure of the benefit of a candidate view relative to other views in the analysis space.

55. The apparatus of

claim 33

, wherein characterizing the views in the analysis space comprises applying a cost formula to the analysis space.

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

a query processor; and

an advisor configured to impose a structure 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 to characterize the views in the analysis space.

57. The apparatus of

claim 56

, wherein structure is imposed on the analysis space based upon meta data.

58. The apparatus of

claim 56

, wherein structure is imposed on the analysis space based upon hierarchical relationships between views in the analysis space.

59. 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 consisting of a subset of all possible views for the database, and to apply a cost formula to the analysis space based upon a user-defined subset of the data contained in the database.

60. 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 candidate view composed of a combination of two or more constituent views, and to characterize the views in the analysis space.

61. The apparatus of

claim 60

, wherein at least one of the constituent views of the candidate view is a candidate view.

62. The apparatus of

claim 60

, wherein at least one of the constituent views of the candidate view is a precomputed view.

63. The apparatus of

claim 60

, wherein the defined analysis space includes the constituent views of the candidate view.

64. The apparatus of

claim 60

, wherein the defined analysis space does not include the constituent views of the candidate view.