Flexible query hints in a relational database

• US 8,190,595 B2
• Filed: 03/28/2009
• Issued: 05/29/2012
• Est. Priority Date: 03/28/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bruno, Nicolas, Ramamurthy, Ravishankar, Chaudhuri, Surajit
• Primary Examiner(s): Channavajjala, Srirama
• Assistant Examiner(s): Park, Grace
• Application Number:
  US12/413,544
• Publication Number:
  US 20100250518A1
• Time in Patent Office: 1,158 Days
• Field of Search: 707/713, 707/718, 707/719, 707/798
• US Class Current: 707/713
• CPC Class Codes: G06F 16/24 Querying

Abstract

A flexible query hints system and method for discovering and expressing query hints in a database management system. Embodiments of the flexible query hints system and method include a power hints (Phints) language that enables the specification of constraints to influence a query optimizer. Phints expressions are defined as tree patterns annotated with constraints. Embodiments of the flexible query hints system and method also include techniques to incorporate the power hints language expressions into an extended query optimizer. Theses techniques include computing a directed acyclic graph for Phints expression, deriving candidate matches using the Phints expression and the graph, computing candidate matches, and extracting a revised execution plan having a lowest cost and satisfying constraints of the Phints expression. Embodiments of the flexible query hints system and method include a flexible query hint user interface that allow users to interactively adjust query hints.

Claims

1. A method implemented on a general-purpose computing device for discovering and expressing query hints in a database management system, comprising:

using the general-purpose computing device to perform the following;

input a query having an initial query execution plan;

computing a direct acyclic graph for the query;

constraining the query using a power hints query language expression that is appended to the query and contains a predicate;

computing candidate matches for each operator in the initial execution plan;

enumerating possible query execution plans in the directed acyclic graph and filtering out any of the possible query execution plans that do not match the power hints language expression to obtain filtered possible query execution plans;

extracting a revised query execution plan that is a revision of the initial query execution plan, the revised query execution plan being one of the filtered possible query execution plans having a lowest cost as determined by a query optimizer cost model that satisfies constraints of the power hints query language expression;

displaying the revised query execution plan in a graphical manner to a user; and

allowing the user to change the revised query execution plan if the user is not satisfied with the revised query execution plan.

2. The method of claim 1, further comprising deriving the candidate matches for subplans of a given execution plan using the power hints query language expression and the direct acyclic graph.

3. The method of claim 2, further comprising:

inputting an operator in an execution plan that is an OP node having arity K;

inputting matches for children of the OP node to obtain fully-matched OP node children; and

promoting each of the fully-matched OP node children into an equivalent form in terms of the OP node to obtain transformed matches.

4. The method of claim 3, further comprising:

determining whether each of the transformed matches partially match the same tree pattern;

if not, then determining that no candidate match can be derived; and

if so, then determining whether the same candidate match is returned by multiple OP node children.

5. The method of claim 4, further comprising:

if the same candidate match is not returned by multiple OP node children, then determining that no unique matching is possible and that no candidate match can be derived; and

if the same candidate match is returned by multiple OP node children, then assembling a result by concatenating candidate matches for each of the OP node children.

6. The method of claim 5, further comprising:

determining whether the OP node satisfies subtree constraints of a tree pattern of the result;

if not, then determining that no unique matching is possible and that no candidate match can be derived; and

if so, then determining that a tree pattern of the result has a constraint on an order.

7. The method of claim 6, further comprising:

determining whether the order is satisfied by the OP node and its subtrees;

if not, then determining that no unique matching is possible and that no candidate match can be derived; and

if so, then determining that the result is a full match.

8. The method of claim 7, further comprising:

determining whether self-constraints of the result tree pattern are satisfied;

if not, then determining that no unique matching is possible and that no candidate match can be derived; and

if so, then outputting a valid candidate match for the OP node.

9. The method of claim 2, further comprising:

inputting an OP node of arity K;

inputting sets of matches for each child of the OP node;

selecting a match from a match set; and

testing the selected match set to determine whether the selected match is a full-candidate match.

10. The method of claim 9, further comprising:

if the selected match is a full-candidate match, then adding the full-candidate match to candidate match results; and

testing each match set in the sets of matches to determine whether each match set match is a full-candidate match.

11. The method of claim 10, further comprising:

selecting a combination of input candidate matches;

using the derived candidate matches to extend partial matches with respect to the OP node; and

adding the extended partial matches to the candidate match results.

12. The method of claim 11, further comprising:

determining that K=1;

designating the OP node as a unary OP node; and

determining whether the candidate match of a single child of the unary OP node is valid for the OP node.

13. The method of claim 12, further comprising:

determining that the candidate match of a single child of the unary OP node is valid for the OP node; and

adding the candidate match of the single child to the candidate match results.

14. A computer-implemented method for revising an initial query execution plan for a query in a database management system on the computer, comprising:

using the computer to perform the following;

computing a direct acyclic graph for the query;

defining a power hints language where expressions in the power hints language are tree patterns in the acyclic graph annotated with constraints;

constraining the query using a power hints language expression that is appended to the query and contains a predicate;

enumerating each of the possible query execution plans in the direct acyclic graph;

filtering out the possible query execution plans that do not match the power hints language expression; and

finding a matching query execution plan have a lowest estimated cost to determine a revised query execution plan, which is a revision of the initial query execution plan for the query.

15. The method of claim 14, further comprising:

defining a subplan, P, in the direct acyclic graph; and

determining that the subplan, P, matches a tree pattern, S, of the power hints query language expression if there is a mapping, M, between nodes in the tree pattern, S, and distinct OP nodes in the subplan, P, such that for each leaf node, s, in the tree pattern, S, a mapping of the leaf node, M(s), is a matching leaf node in the subplan, P, and that those are the leaf nodes in the subplan, P.

16. The method of claim 15, further comprising determining that the subplan, P, matches a tree pattern, S, of the power hints query language expression if there is a mapping, M, between nodes in the tree pattern, S, and distinct OP nodes in the subplan, P, such that for each leaf node, s, in the tree pattern, S, with children {s_i, . . . ,s_k}, every mapping of the children, M(s_i), is a descendant of the mapping of the leaf node, M(s), and no mapping of the children, M(s_i), is a descendant of M(s_j) for i≠

j; and

such that for each leaf node, s, in the tree pattern, S, the leaf node mapping, M(s), and its descendants in the subplan, P, must satisfy the constraints defined on the leaf node, s.

17. The method of claim 15, further comprising:

specifying the power hints language expression as follows;

writing the tree pattern, S, in an infix order, where parenthesis are used to denote parent-child relationships and square brackets are used if an order constraint is present in the parent node;

denoted a node with the symbol “

*”

if there are no self constraints;

if there are self constraints, then denoting the node with an “

A”

such that “

force(A)”

is used to denote a self-constraint, “

!A”

is used to denote a disable(A) self-constraint, “

T”

is used to denote a forceTable(T) constraint, and “

L=>

P”

is used to denote a condForce(L,P) constraint; and

subtree constraints are written in curly braces next to the node description.

18. The method of claim 14, further comprising:

presenting the revised query execution plan to a user in a graphical manner on a flexible query hints user interface;

determining whether the user is satisfied with the revised query execution plan;

if the user is not satisfied, then allowing the user to create another power hints language expression to further constrain the query; and

continuing the process of presenting the revised query execution plan to the user, determining whether the user is satisfied, and, if not, creating another power hints language expression until the user is satisfied.

19. A computer-implemented process contained on a computer-readable storage media having stored and encoded thereon computer-executable instructions for execution on a general-purpose computing device for incorporating query hints into a query optimizer of a database management system, comprising:

using the general-purpose computing device to perform the following process actions;

inputting a query;

computing a directed acyclic graph for the query;

creating a power hints language expression using a power hints language;

constraining the query using the power hints language expression that is appended to the query and contains a predicate;

deriving candidate matches for subplans of an execution plan for the query using the power hints language expression and the directed acyclic graph;

inputting OR nodes from the directed acyclic graph;

implementing a first memoization to guarantee that each OR node is computed once;

selecting an OR node to process and a child alternative for the selected OR node;

implementing a second memoization to guarantee that each OP node in the child alternative is processed once;

selecting an OP node to process;

creating an extended OP node from the selected OP node;

setting any children of the extended OP node;

determining cost for the extended OP node;

computing candidate matches for the extended OP node from the derived candidate matches; and

extracting a revised query execution plan having a lowest cost and satisfying constraints given the power hints language expression.

20. The computer-implemented process of claim 19, further comprising:

determining whether the extended OP node is a non-dominated node; and

if so, then adding the extended OP node to a set of extended OP nodes to aid in extracting the revised query execution plan.