Database index validation mechanism

• US 7,272,589 B1
• Filed: 11/01/2000
• Issued: 09/18/2007
• Est. Priority Date: 11/01/2000
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Smith, Gregory S., Mozes, Ari W., Guay, Todd P., Royal, Gaylen D.
• Primary Examiner(s): Pham; Khanh B.
• Application Number:
  US09/703,909
• Time in Patent Office: 2,512 Days
• Field of Search: 707 2- 5
• US Class Current: 707/716
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: Y10S 707/954 Relational
• 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/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method evaluates a plurality of candidate index sets for a workload of database statements in a database system by first generating baseline statistics for each statement in the workload. An index superset is formed by combining an existing or current index set and a proposed index set. A candidate index set is derived from the index superset, the candidate index being one of the plurality of candidate index sets. Statistics for a statement are generated by first creating an execution plan which represents an efficient series of steps for executing the statement given the candidate index set. The execution plan is evaluated, and statistics based on the evaluation of the execution plan are generated and recorded. The cost of the execution plan is then determined and statistics are generated. Statistics for each candidate index set are rolled up and presented to a user or an index tuning mechanism.

Claims

1. A method for evaluating a plurality of candidate index sets for a workload of database statements in a database system, the method comprising:

forming an index superset from a union of a current index set and a proposed index set;

deriving a candidate index set from the index superset, the derived candidate index set being incorporated into the plurality of candidate index sets;

analyzing collected database statistics based on the derived candidate index set;

repeatedly deriving a candidate index set and analyzing collected statistics based on the proposed index set;

terminating the repeated execution when at least one candidate index solution is found that adheres to user-imposed constraints and no further indexes can be removed from said candidate index solution without degrading performance of the workload and without disabling an integrity constraint, wherein the integrity constraint describes a condition about the database that must always be true or must always be false; and

presenting the analyzed collected statistics.

2. The method of claim 1, further comprising:

deriving current index statistics for the workload responsive to the current index set, the presented collected statistics comprising the derived current index statistics.

3. The method of claim 1, wherein analyzing statistics for a statement comprises generating at least one statistic based on an execution plan created by an optimizer.

4. The method of claim 3, wherein the execution plan is based on available access paths.

5. The method of claim 3, wherein the execution plan is based on statistics for at least one schema object accessed by the statement.

6. The method of claim 5 wherein the at least one schema object is a table.

7. The method of claim 5 wherein the at least one schema object is an index.

8. The method of claim 3, further comprising:

for a table accessed by a statement under evaluation, using the execution plan to identify at least one index that would be used to retrieve data from the table upon an execution of the statement.

9. The method of claim 3, wherein the optimizer generates a cost of the execution plan.

10. The method of claim 9, wherein the cost of the execution plan is derived from a resource use needed to execute the statement according to the execution plan.

11. The method of claim 10, wherein the resource use includes CPU execution time.

12. The method of claim 10, wherein the resource use includes input/output access.

13. The method of claim 3, wherein the collected database statistics comprise the number of executions of the statement.

14. The method of claim 3, wherein the collected database statistics comprise a user-defined importance of the statement.

15. The method of claim 3, wherein the collected database statistics comprise an index usage.

16. The method of claim 1, wherein the statements are SQL statements.

17. The method of claim 1, wherein the workload is reduced into unique statements.

18. The method of claim 1, wherein deriving a candidate index set is responsive to a predetermined maximum number of allowed indexes.

19. The method of claim 1, wherein deriving a candidate index set is responsive to available storage space.

20. The method of claim 1, wherein the proposed index set is provided by a user.

21. The method of claim 1, wherein the proposed index set is provided by an expert system.

22. The method of claim 1, wherein an execution plan is created without creating indexes which are not in the current index set.

23. The method of claim 1, wherein the statistics include index volatility.

24. The method of claim 1, further comprising:

generating baseline statistics for each statement in the workload, wherein generating statistics is additionally based on the baseline statistics.

25. The method of claim 24, wherein analyzing the collected baseline statistics comprises disabling current indexes.

26. The method of claim 1 wherein terminating comprises:

terminating the repeated execution when at least one candidate index solution is found that adheres to user-imposed constraints and no further indexes can be removed from said candidate index solution without degrading performance of the workload and without disabling an integrity constraint, wherein the integrity constraint describes a condition about the database that must always be true or must always be false, and wherein any removed index that does not enforce an integrity constraint is disabled.

27. A system for evaluating a plurality of candidate index sets for a workload in a database system, the workload derived from a plurality of statements, the system comprising:

a workload evaluator, including a processor, wherein the workload evaluator evaluates each statement within the workload using collected database statistics;

an index solution evaluator which, responsive to the workload evaluator, evaluates each index in a candidate index set with respect to the workload, the candidate index solution being one of the plurality of candidate index sets, each candidate index set derived from an index superset formed by the union of a current index set and a proposed index set;

a solution/rollup evaluator which, responsive to the index solution evaluator, evaluates the candidate index solution; and

a solution refiner which, responsive to the solution/rollup evaluator, generates at least one new candidate index solution, the at least one new candidate index solution being incorporated into the plurality of candidate index sets, wherein the solution refiner further generates at least one new candidate index solution by eliminating at least one index on a small table under evaluation, wherein the at least one index does not enforce an integrity constraint, wherein the integrity constraint describes a condition about the database that must always be true or must always be false.

28. The system of claim 27, wherein the solution refiner generates at least one new candidate index solution by eliminating at least one index within the candidate index solution that does not adhere to user-imposed constraints.

29. The system of claim 28, wherein the constraint is a user-defined constraint.

30. The system of claim 28, wherein the constraint is a memory-usage constraint.

31. The system of claim 27, wherein the workload evaluator evaluates an execution plan created by an optimizer, the execution plan comprising, for each statement of the workload, an execution plan which represents a series of steps for executing the statement, the workload evaluator further generating and recording statistics based on the evaluation of the execution plan.

32. The system of claim 31, wherein each execution plan is created based on available access paths.

33. The system of claim 31, wherein each execution plan is created based on statistics for at least one schema object accessed by the statement.

34. The system of claim 33 wherein the at least one schema object is a table.

35. The system of claim 33 wherein the at least one schema object is an index.

36. The system of claim 31, wherein the workload evaluator, for a table accessed by a statement under evaluation, identifies at least one index which would be used to retrieve data from the table upon an execution of the statement.

37. The system of claim 31, wherein the workload evaluator determines a cost of the execution plan.

38. The system of claim 37, wherein the cost of the execution plan is derived from a resource use needed to execute the statement according to the execution plan.

39. The system of claim 38, wherein the resource use includes CPU execution time.

40. The system of claim 38, wherein the resource use includes input/output access.

41. The system of claim 31, wherein the statistics include the number of executions of the statement.

42. The system of claim 31, wherein the statistics include a user-defined importance of the statement.

43. The system of claim 31, wherein the statistics include an index usage.

44. The system of claim 31, wherein the statistics include a cost of the execution plan.

45. The system of claim 31, wherein the statistics include index volatility.

46. The system of claim 27, wherein the statements are SQL statements.

47. The system of claim 27, wherein the workload is reduced into unique statements.

48. The system of claim 27, wherein the solution refiner is responsive to a predetermined maximum number of allowed indexes.

49. The system of claim 27, wherein the solution refiner is responsive to available storage space.

50. The system of claim 27, wherein the proposed index set is provided by a user.

51. The system of claim 27, wherein the proposed index set is provided by an expert system.

52. The system of claim 27, wherein an execution plan is created without creating indexes which are not in the current index set.

53. The system of claim 27 wherein a solution refiner comprises:

a solution refiner which, responsive to the solution/rollup evaluator, generates at least one new candidate index solution, the at least one new candidate index solution being incorporated into the plurality of candidate index sets, wherein the solution refiner further generates at least one new candidate index solution by eliminating at least one index on a small table under evaluation, wherein the at least one index does not enforce an integrity constraint, wherein the integrity constraint describes a condition about the database that must always be true or must always be false, and wherein any eliminated index that does not enforce an integrity constraint is disabled.

54. A computer program product for evaluating a plurality of candidate index sets for a workload of database statements in a database system, the computer program product comprising a computer usable medium having computer readable code thereon, including program code which:

forms an index superset from a union of a current index set and a proposed index set;

repeatedly derives a candidate index set from the index superset, the derived candidate index set being incorporated into the plurality of candidate index sets, generates statistics based on the proposed index set, and analyzes collected database statistics based on the derived candidate index set;

terminates the repeated execution when at least one candidate index solution is found that adheres to user-imposed constraints and no further indexes can be removed from said candidate index solution without degrading performance of the workload and without disabling an integrity constraint, wherein the integrity constraint describes a condition about the database that must always be true or must always be false; and

presents the analyzed statistics.

55. The computer program product of claim 54, further comprising code which:

derives current index statistics for the workload responsive to the current index set, the presented analyzed statistics comprising the derived current index statistics.

56. The computer program product of claim 54, wherein the statistics include index volatility.

57. The computer program product of claim 54, further comprising code which:

derives baseline statistics for each statement in the workload, wherein deriving statistics is additionally based on the baseline statistics.

58. The computer program product of claim 57, wherein deriving the baseline statistics comprises disabling current indexes.

59. The computer program product of claim 54, wherein statistics for a statement are derived by generating at least one statistic based on an execution plan created by an optimizer.

60. The computer program product of claim 59, wherein the execution plan is based on available access paths.

61. The computer program product of claim 59, wherein the execution plan is based on statistics for at least one schema object accessed by the statement.

62. The computer program product of claim 61 wherein the at least one schema object is a table.

63. The computer program product of claim 61 wherein the at least one schema object is an index.

64. The computer program product of claim 59, further comprising code which:

for a table accessed by a statement under evaluation, uses the execution plan to identify at least one index that would be used to retrieve data from the table upon an execution of the statement.

65. The computer program product of claim 59, wherein the optimizer generates a cost of the execution plan.

66. The computer program product of claim 65, wherein the cost of the execution plan is derived from a resource use needed to execute the statement according to the execution plan.

67. The computer program product of claim 66, wherein the resource use comprises CPU execution time.

68. The computer program product of claim 66, wherein the resource use comprises input/output access.

69. The computer program product of claim 59, wherein the statistics comprise the number of executions of the statement.

70. The computer program product of claim 59, wherein the statistics comprise a user-defined importance of the statement.

71. The computer program product of claim 59, wherein the statistics comprise an index usage.

72. The computer program product of claim 54, wherein the statements are SQL statements.

73. The computer program product of claim 54, wherein the workload is reduced into unique statements.

74. The computer program product of claim 54, wherein a candidate index set is derived responsive to a predetermined maximum number of allowed indexes.

75. The computer program product of claim 54, wherein deriving a candidate index set is responsive to available storage space.

76. The computer program product of claim 54, wherein the proposed index set is provided by a user.

77. The computer program product of claim 54, wherein the proposed index set is provided by an expert system.

78. The computer program product of claim 54, wherein an execution plan is created without creating indexes which are not in the current index set.

79. The computer program product of claim 54 wherein program code which terminates comprises:

terminates the repeated execution when at least one candidate index solution is found that adheres to user-imposed constraints and no further indexes can be removed from said candidate index solution without degrading performance of the workload and without disabling an integrity constraint, wherein the integrity constraint describes a condition about the database that must always be true or must always be false, and wherein any removed index that does not enforce an integrity constraint is disabled.

80. A system for evaluating a plurality of candidate index sets for a workload of database statements in a database system, comprising:

means for forming an index superset from a union of a current index set and a proposed index set, wherein the means include a processor;

means for deriving a candidate index set from the index superset, the derived candidate index set being incorporated into the plurality of candidate index sets;

means for analyzing collected database statistics based on the derived candidate index set;

means for repeatedly deriving a candidate index set and generating statistics based on the proposed index set;

means for terminating the repeated execution when at least one candidate index solution is found that adheres to user-imposed constraints and no further indexes can be removed from said candidate index solution without degrading performance of the workload and without disabling an integrity constraint, wherein the integrity constraint describes a condition about the database that must always be true or must always be false; and

means for presenting the analyzed statistics.

81. The system of claim 80, further comprising:

means for generating current index statistics for the workload responsive to the current index set, the presented generated statistics comprising the generated current index statistics.

82. The system of claim 80, wherein the statistics include index volatility.

83. The system of claim 80, further comprising:

means for generating baseline statistics for each statement in the workload, wherein statistics are generated based additionally on the baseline statistics.

84. The system of claim 83, wherein analyzing the baseline statistics comprises disabling current indexes.

85. The system of claim 80, wherein analyzing statistics for a statement comprises generating at least one statistic based on an execution plan created by an optimizer.

86. The system of claim 85, wherein the execution plan is based on available access paths.

87. The system of claim 85, wherein the execution plan is based on statistics for at least one schema object accessed by the statement.

88. The system of claim 87 wherein the at least one schema object is a table.

89. The system of claim 87 wherein the at least one schema object is an index.

90. The system of claim 85, further comprising:

means for using, for a table accessed by a statement under evaluation, the execution plan to identify at least one index that would be used to retrieve data from the table upon an execution of the statement.

91. The system of claim 85, wherein the optimizer generates a cost of the execution plan.

92. The system of claim 91, wherein the cost of the execution plan is derived from a resource use needed to execute the statement according to the execution plan.

93. The system of claim 92, wherein the resource use comprises CPU execution time.

94. The system of claim 92, wherein the resource use comprises input/output access.

95. The system of claim 85, wherein the statistics comprise the number of executions of the statement.

96. The system of claim 85, wherein the statistics comprise a user-defined importance of the statement.

97. The system of claim 85, wherein the statistics comprise an index usage.

98. The system of claim 80, wherein the statements are SQL statements.

99. The system of claim 80, wherein the workload is reduced into unique statements.

100. The system of claim 80, wherein deriving a candidate index set is responsive to a predetermined maximum number of allowed indexes.

101. The system of claim 80, wherein deriving a candidate index set is responsive to available storage space.

102. The system of claim 80, wherein the proposed index set is provided by a user.

103. The system of claim 80, wherein the proposed index set is provided by an expert system.

104. The system of claim 80, wherein an execution plan is created without creating indexes which are not in the current index set.

105. The system of claim 80 wherein means for terminating comprises:

means for terminating the repeated execution when at least one candidate index solution is found that adheres to user-imposed constraints and no further indexes can be removed from said candidate index solution without degrading performance of the workload and without disabling an integrity constraint, wherein the integrity constraint describes a condition about the database that must always be true or must always be false, and wherein any removed index that does not enforce an integrity constraint is disabled.