Transformation rule profiling for a query optimizer

• US 8,332,388 B2
• Filed: 06/18/2010
• Issued: 12/11/2012
• Est. Priority Date: 06/18/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Giakoumakis, Leo, Narasayya, Vivek, Ramamurthy, Ravi
• Primary Examiner(s): Ehichioya, Fred I
• Assistant Examiner(s): OBISESAN, AUGUSTINE KUNLE
• Application Number:
  US12/818,237
• Publication Number:
  US 20110314000A1
• Time in Patent Office: 907 Days
• Field of Search: None
• US Class Current: 707/718
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

Technology is described for transformation rule profiling for a query optimizer. The method can include obtaining a database query configured to be optimized by the query optimizer of a database system. An optimized query plan for the database query can be found using a host set of transformation rules. One transformation rule can be removed and checked at a time. Each transformation rule can be checked to determine whether the transformation rule affects an optimal query plan output. A test query plan can be generated after each transformation rule has been removed. The query optimizer can determine whether the test query plan is different than the optimized query plan in the absence of the removed transformation rule. An equivalent set of transformation rules can be created that includes transformation rules where the test query plan generated from the equivalent set of transformation rules is equivalent to the optimized plan.

Claims

1. A method for transformation rule profiling for a query optimizer, comprising:

obtaining a database query configured to be optimized by the query optimizer of a database system;

finding an optimized query plan for the database query using a host set of transformation rules;

removing individual transformation rules from a query plan generation, wherein one transformation rule is removed and checked at a time;

generating a test query plan after one transformation rule has been removed;

determining whether the test query plan is different than the optimized query plan in the absence of the removed transformation rule;

defining a relevance ratio for a transformation rule as a fraction of the total generated test query plans for which the transformation rule is relevant;

creating an equivalent set of transformation rules that includes transformation rules whose relevance ratio exceeds a relevance threshold where the test query plan generated from the equivalent set of transformation rules is equivalent to the optimized plan.

2. The method as in claim 1, further comprising disabling individual transformation rules in the host rule set for each transformation rule that does not cause the test query plan to change as compared to the optimized query plan is removed from the optimization rule set.

3. The method as in claim 1, further comprising using the optimization rule set to determine a lower bound for a time taken for optimizing the search query.

4. The method as in claim 3, wherein a first optimization time for the search query using the host set of transformation rules can be compared with a second optimization time using an equivalent set of transformation rules so as to determine whether a query optimizer can be further tuned to optimize search queries faster.

5. The method as in claim 1, further comprising using the optimized rule set as rule hints for optimizing a search query.

6. The method as in claim 1, further comprising optimizing the query plan using the equivalent set of transformation rules.

7. The method as in claim 6, further comprising:

obtaining search results from the database system for the optimized query plan; and

displaying the search results to an end user.

8. The method as in claim 1, wherein the database system is located on a database server having a processor and memory.

9. A method for transformation rule profiling for a query optimizer of a database system, comprising:

identifying a workload of queries including a plurality of database queries configured to be optimized by the query optimizer of the database system;

finding an optimized query plan for a database query using a host set of transformation rules;

removing individual transformation rules from a query plan generation, wherein one transformation rule is removed and checked at a time;

generating a test query plan after the transformation rule has been removed from the host set of transformation rules;

determining whether the test query plan is identical to the optimized query plan in the absence of the removed transformation rule;

marking a transformation rule as relevant to a database query based on a changed test plan when the transformation rule has been removed;

defining a relevance ratio of a selected rule for a workload of queries as a fraction of queries in the workload of queries where the selected rule is relevant to a query because removal of the transformation rule affects the optimized query plan; and

selecting transformation rules with a relevance ratio that exceed a relevance threshold to be applied to queries using the query optimizer.

10. The method as in claim 9, further comprising determining which transformation rules are useful for at least one database query.

11. The method as in claim 9, further comprising turning off the rules in the query optimizer except the transformation rules with the relevance ratio exceeding the relevance threshold.

12. The method as in claim 9, wherein the relevance threshold is set to select transformation rules relevant to greater than a pre-defined percentage of queries.

13. The method as in claim 9, wherein the transformation rule can be defined as relevant when optimizing the database query with the transformation rule turned off does not significantly change a plan cost identified by the query optimizer.

14. The method as in claim 9, further comprising:

obtaining search results from the database system for the optimized query plan; and

displaying the search results to an end user.

15. The method as in claim 9, wherein the relevance threshold is set to select 10 to 50 transformation rules.

16. The method as in claim 9, wherein the database system is located on a database server having a processor and memory.

17. A system for profiling transformation rules for search queries, comprising:

a database server having a database system, a memory storing a plurality of database queries, and a processor;

a host set of transformation rules comprising a plurality of transformation rules;

a query optimizer configured to use the plurality of transformation rules to optimize the database queries; and

a relevance rule module configured to;

create an equivalent set of transformation rules that includes transformation rules where the transformation rules are used to find an optimized plan for a data query;

find an optimized query plan for a database query using the host set of transformation rules;

remove individual transformation rules in a query plan generation process, wherein one transformation rule is removed and checked at a time;

generate a test query plan after one transformation rule has been removed;

determine whether the test query plan was changed as compared to the optimized query plan in the absence of individual transformation rules;

determine a relevance ratio for the plurality of transformation rules in the host set of transformation rules, the relevance ratio indicative of a ratio for which the selected transformation rule was relevant to a plurality of test query plans; and

create an equivalent set of transformation rules that includes selected transformation rules where a test query plan generated without the selected transformation rule is different than an optimized plan, and wherein the selected transformation rules comprises transformation rules having a relevance ratio that exceeds a relevance threshold.

18. The system as in claim 17, further comprising a relevant rules module to determine which transformation rules are useful for at least one database query.

19. The system as in claim 17, wherein the relevant rules module can be used to find transformation rules that are not used for optimization because the transformation rules have errors.