Framework for Testing Query Transformation Rules

• US 20110295833A1
• Filed: 05/28/2010
• Published: 12/01/2011
• Est. Priority Date: 05/28/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Elmongui, Hicham G., Ramamurthy, Ravishankar, Narasayya, Vivek R.
• Granted Patent: US 8,630,998 B2
• Time in Patent Office: Days
• US Class Current: 707/713
• CPC Class Codes: G06F 11/3664 Environments for testing or debugging software
• CPC Class Codes: G06F 11/3676 for coverage analysis
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation

Abstract

Described is a test framework for testing transformation rules of query optimizers. Rule patterns obtained as tree structures from a query optimizer are used to generate queries that are used to test the rule optimizer'"'"'s transformation rules. The test framework tracks which rules are exercised for each query, and also determines the correctness of the transformation rule by comparing the results of the query processing with the rule and without the rule (by turning off the rule). The test framework creates a composite pattern corresponding to two or more rules, such as to test rules in a set (e.g., as pairs). Also described is the efficient execution of a test suite for correctness testing, in which queries of the test suite are selected based upon cost information.

Claims

1. In a computing environment, a method performed on at least one processor comprising:

obtaining a rule pattern corresponding to a transformation rule of a transformation rule-based query optimizer of a database management system;

generating a query based upon the rule pattern;

providing the query to the transformation rule-based query optimizer for query processing; and

receiving information from the database management system that indicates which rules are exercised during the query processing.

2. The method of claim 1 further comprising, receiving results of the query processing, instructing the optimizer to turn off the transformation rule that corresponds to the rule pattern, providing the query to the rule optimizer for query processing with the transformation rule turned off, receiving results of the query processing with the transformation rule turned off, and determining the correctness of the transformation rule by comparing the results of the query processing against the results of the query processing with the transformation rule turned off.

3. The method of claim 1 wherein the rule pattern corresponds to a tree structure including a generic operator, and wherein generating the query based upon the rule pattern comprises instantiating a generic operator with an argument to provide another tree based structure, and generating a query language query from the other tree structure.

4. The method of claim 1 wherein obtaining the rule pattern comprises receiving the rule pattern from the database management system.

5. The method of claim 1 wherein generating the query based upon the rule pattern includes creating a composite pattern that is based upon the rule pattern and another rule pattern corresponding to another transformation rule.

6. The method of claim 5 wherein creating the composite pattern comprises combining the rule and the other rule with a UNION operator.

7. The method of claim 5 wherein the rule pattern corresponds to a tree structure including a generic operator, and wherein creating the composite pattern comprises combining the rule pattern and the other rule pattern by substituting the other rule pattern into the generic operator of the rule pattern.

8. The method of claim 5 wherein the rule pattern corresponds to a first tree structure and the other rule pattern corresponds to a second tree structure, in which each tree structure includes a generic operator, and wherein creating the composite pattern comprises combining the rule pattern and the other rule pattern into a first composite rule pattern by substituting the other rule pattern into the generic operator of the rule pattern, combining the other rule pattern and the rule pattern into a second composite rule pattern by substituting the rule pattern into the generic operator of the other rule pattern, generating first and second queries from the first and second composite rule patterns, respectively, and selecting the query for providing to the rule optimizer based upon a least number of operators.

9. The method of claim 1 further comprising, determining a test suite of queries for testing one or more transformation rules, and compressing the test suite into a subset of queries, including processing data corresponding to a graph comprising a plurality of rule nodes each representing one or more rules and a plurality of query nodes representing queries, to select the transformation rule based upon cost information associated with the query nodes and one or more criteria including that each rule is exercised a specified number of one or more times by the subset.

10. The method of claim 1 further comprising, determining a test suite of queries for testing one or more transformation rules, and compressing the test suite into a subset of queries, including processing data corresponding to a graph comprising a plurality of rule nodes each representing one or more rules and a plurality of query nodes representing queries, to select the transformation rule based upon cost information associated with edges between the rule nodes and the query nodes and one or more criteria including that each rule is exercised a specified number of one or more times by the subset.

11. The method of claim 10 further comprising sorting the queries based upon query node cost, and maintaining a priority queue of edges and actual costs computed by invoking the optimizer.

12. In a computing environment, a system comprising, a test framework including a query generation component that generates queries based upon rule patterns received from a database management system that includes a query optimizer, the query optimizer configured to use transformation rules to optimize queries to be processed by the database management system, including queries received from the test framework, the test framework further including a correctness validation component that provides the queries to the query optimizer and validates whether results obtained from processing a query with a transformation rule that is exercised in query optimization match results obtained from processing the query without the transformation rule being exercised in query optimization.

13. The system of claim 12 wherein the rule pattern corresponds to a tree structure with at least one generic operator, and wherein the query generation component includes a first module that processes the tree structure into a tree structure without a generic operator, and a second module that generates a query language query from the tree structure without the generic operator.

14. The system of claim 13 wherein the first module creates a composite pattern that is based upon the rule pattern and another rule pattern corresponding to another transformation rule, including by substituting one rule pattern into the generic operator of the other rule pattern.

15. The method of claim 13 wherein the first module creates two composite patterns that are based upon the rule pattern and another rule pattern corresponding to another transformation rule, including by substituting the rule pattern into the generic operator of the other rule pattern and substituting the other rule pattern into the generic operator of the rule pattern, and wherein the framework generates first and second queries from the two composite rule patterns and selects the query for providing to the rule optimizer based upon a number of operators in the first query and a number of operators in the second query.

16. The system of claim 12 further comprising, a test suite generation module that provides a test suite of queries based upon a set of rules to be tested.

17. The system of claim 16 further comprising, a test suite compression module that determines which queries comprise the test suite. Including by processing data corresponding to a graph comprising a plurality of rule nodes each representing one or more rules in the set of rules to be tested and a plurality of query nodes representing queries, to select the queries corresponding to a subgraph that is determined from cost information associated with the query nodes.

18. The system of claim 16 further comprising, a test suite compression module that determines which queries comprise the test suite. Including by processing data corresponding to a graph comprising a plurality of rule nodes each representing one or more rules in the set of rules to be tested and a plurality of query nodes representing queries, to select the queries corresponding to a subgraph that is determined from cost information associated with edges between the rule nodes and the query nodes.

19. One or more computer-readable media having computer-executable instructions, which when executed perform steps, comprising:

using rule patterns corresponding to transformation rules of a rule optimizer of a database management system to generate available queries;

generating a test suite to test a set of transformation rules of a query optimizer, including selecting a subset of the available queries as the test suite to test the set of transformation rules based upon cost information; and

for each query in the test suite;

(a) providing the query to the rule optimizer for query processing;

(b) receiving information from the database management system that indicates which rule or rules was exercised during the query processing;

(c) receiving results from the query processing;

(d) turning off one or more rules that were exercised;

(e) providing the query to the rule optimizer for query processing with the one or more rules turned off;

(f) receiving information from the database management system that indicates which rule or rules was exercised during the query processing with the one or more rules turned off;

(g) receiving results from the query processing with the one or more rules turned off; and

(h) determining whether the results obtained from processing the query with the one or more rules turned off match the results obtained from processing the query without the one or more rules turned off.

20. The computer-readable media of claim 19 wherein using the rule patterns comprises combining two or more rule patterns into a composite rule pattern and using the composite rule pattern to generate the available queries.