System and method for database query optimization

• US 5,819,255 A
• Filed: 12/27/1996
• Issued: 10/06/1998
• Est. Priority Date: 08/23/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Tandem Computers Incorporated (HP Inc.)
• Inventors: Zeller, Hansjorg, Celis, Pedro, Vaishnav, Jay
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US08/773,695
• Time in Patent Office: 648 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5, 707/6
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• 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
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A system and method for optimizing a database query with improved performance enhancements is herein disclosed. The database query consists of one or more logical expressions. Through the repeated application of one or more rules, the logical expressions are transformed into physical expressions and in some cases, execution plans that implement the database query. Each expression has associated with it a set of group attributes that specifies its characteristic inputs and outputs and a cost that estimates the computational expense for executing the expression. The group attributes are used to categorize similar expressions into groups that are stored in a search data structure. They are also used to track duplicate expressions. The cost associated with an expression is used to guide the search process to consider those expressions that will produce low cost plans. The cost is estimated in accordance with a six-fold criteria with each criterion weighted to account for the context of the expression and the application'"'"'s particular computing environment. The query optimizer is rule-based including transformation and implementation rules that are used to perform transformations on the logical expressions in a subproblem in order to produce a plan. A OnceGuidance guidance method is used to select a set of rules in certain cases that prevent the regeneration of an existing expression.

Claims

1. A computer-implemented method for generating a plan for executing a database query, comprising:

(a) representing said database query as a query tree including one or more levels of logical expressions, each logical expression including zero or more logical expressions as inputs, a subset of said inputs representing one or more subtrees, each subtree having a top logical expression and zero or more logical expressions as inputs, each level other than a top level having one or more logical expressions that are input to a higher level logical expression at a preceding level, one of said logical expressions representing a root expression, each logical expression including zero or more inputs and zero or more outputs;

(b) for each said logical expression in said query tree, determining group attributes for each said logical expression, said group attributes including a set of characteristic inputs and a set of characteristic outputs, said characteristic inputs representing inputs required for a particular logical expression and zero or more logical expressions at one or more subsequent levels to said particular expression, said characteristic outputs representing outputs generated by a specified logical expression and zero or more logical expressions at one or more preceding levels to said specified logical expression;

(c) storing in a memory a search data structure used to store a plurality of groups, each said group representing equivalent expressions having common group attributes, each said group including at least one logical expression, zero or more equivalent expressions associated therewith, and one or more plans, each of said plans implementing at least one expression associated with each said group;

(d) for each said logical expression in said query tree, storing each said logical expression in a corresponding one of said groups in said search data structure associated with each said logical expression'"'"'s group attributes;

(e) obtaining a plurality of rules for use in generating one or more equivalent expressions or one or more plans;

(f) partitioning said query tree into one or more levels of subproblems, each subproblem including one or more of said logical expressions stored in said search data structure, a first level having one of said subproblems representing said root expression, each subproblem at each subsequent level representing one of said inputs to a corresponding logical expression at a preceding level, each subproblem associated with one of said groups in said search data structure;

(g) determining at least one plan for each of said subproblems, said determining step further comprising the steps of;

(1) selecting a set of one or more rules for application to one or more expressions of a particular one of said subproblems;

(2) generating zero or more equivalent expressions from applying said set of rules to one or more expressions associated with said particular subproblem;

(3) for each said generated equivalent expressions,

(i) providing an associated set of group attributes for each said generated equivalent expression,

(ii) using said group attributes and said generated equivalent expression to determine if a duplicate expression matching said generated equivalent expression is currently stored in said search data structure, and

(iii) storing said generated equivalent expression in a group of said search data structure having equivalent group attributes when no duplicate expression as said generated equivalent expression exists in said search data structure; and

(4) forming one or more plans from one or more expressions associated with said particular subproblem; and

(h) generating a plan for said database query from said plans associated with each of said subproblems.

2. The method of claim 1,

said step (b) further comprising the steps of:

traversing each said level of said query tree from said top level to a bottom level to determine characteristic inputs for each expression at each traversed level;

for each said expression at each said traversed level, determining a corresponding set of characteristic inputs for a particular one of said expressions, said set including characteristic inputs for said particular expression and for expressions in one or more preceding levels; and

traversing each said level of said query tree from said bottom level to said top level to determine characteristic outputs for each expression at each traversed level; and

for each said expression at each said traversed level, determining a corresponding set of characteristic outputs for a particular one of said expressions, said set including characteristic outputs for said particular expression and for expressions in one or more succeeding levels.

3. The method of claim 2,

said set of characteristic inputs including a minimum number of said characteristic inputs and said set of characteristic outputs including a minimum number of said characteristic outputs.

4. The method of claim 1,

said step (g)(3) further comprising the step of associating a cost with each said generated equivalent expression, said cost based on a prescribed criteria that considers said computing environment executing said method and a context associated with each said generated equivalent expression;

and

said step (g)(4) further comprising the step of selecting one or more expressions associated with said particular subproblem having an associated cost that is lower than a threshold cost associated with said particular subproblem.

5. The method of claim 1,

said step (g)(1) further comprising the step of providing one or more search heuristics for selecting said set of rules, one of said search heuristics selecting ones of said rules that can be applied to a particular one of said expressions and to a substitute expression that is generated from said particular expression.

6. The method of claim 1,

said step (g) further comprising the step of merging two groups in accordance with an application of a specified one of said rules, said merging step further comprising the steps of:

selecting a first one of said merged groups to store contents of both merged groups and selecting a second one of said merged groups to merge with said first merged group;

adjusting references in said search data structure to said second group as said first group;

detecting duplicate expressions in said search data structure; and

deleting said detected duplicate expressions.

7. The method of claim 1,

said step (g)(3)(i) further comprising the step of:

for a particular one of said generated equivalent expressions corresponding to a top level expression, assigning said top level expression'"'"'s group attributes to said particular expression.

8. The method of claim 7,

said step (g)(3)(i) further comprising the step of:

for a particular one of said generated equivalent expressions corresponding to a logical expression having inputs, performing a dataflow analysis to determine group attributes for said particular generated equivalent expression; and

said step (g)(3)(iii) further comprising the step of;

for said particular generated equivalent expression, storing said particular generated equivalent expression in a new group in said search data structure.

9. A database query optimization system, comprising:

a memory for storing

a query tree representing a database query, said query tree including one or more levels of logical expressions, each logical expression including zero or more logical expressions as inputs, a subset of said inputs representing one or more subtrees, each level other than a top level having one or more logical expressions that are input to a higher level logical expression at a preceding level, one of said logical expressions representing a root expression,

a search data structure including a plurality of groups, each said group representing equivalent expressions having common group attributes, each said group including at least one logical expression from said query tree, zero or more equivalent expressions associated therewith, one or more plans, and one or more contexts, each of said plans implementing at least one expression associated with said group and having an optimization goal and a cost, each of said contexts having an associated optimization goal and representing ones of said plans that are compatible with said context'"'"'s associated optimization goal, and

a plurality of rules for use in generating one or more equivalent expressions or one or more plans;

a search engine for generating one or more plans that execute said database query, said search engine including instructions that

determine group attributes for each said logical expression in said query tree, said group attributes including a set of characteristic inputs and a set of characteristic outputs, said characteristic inputs representing inputs required for a particular logical expression and zero or more logical expressions at one or more subsequent levels to said particular expression, said characteristic outputs representing outputs generated by a specified logical expression and zero or more logical expressions at one or more preceding levels to said specified logical expression,

store each said logical expression of said query tree in a corresponding one of said groups in said search data structure associated with said logical expression'"'"'s group attributes,

partition said database query into one or more subproblems, each subproblem including one or more of said logical expressions and an optimization goal, a first level having one of said subproblems representing said root expression, each subproblem at each subsequent level representing one of said inputs to a corresponding top logical expression at a preceding level, each of said subproblems associated with one of said groups corresponding to said top logical expression in said subproblem,

formulate at least one plan for each of said subproblems from one or more expressions associated with each said subproblems, each said plan formulated by generating zero or more equivalent expressions from applying a set of rules to one or more expressions associated with a particular subproblem, each said generated expression having a set of group attributes associated therewith, said group attributes used to determine if said generated expression exists in said search data structure and to store said generated expression into an appropriate group in said search data structure, and

generate a plan for said database query as a combination of each of said subproblem'"'"'s plans.

10. The system of claim 9 further comprising:

a plurality of tasks, each task including a subset of said search engine'"'"'s instructions;

a task scheduler that manages scheduling one or more tasks on one or more processors associated with said system; and

a task data structure for storing one or more tasks awaiting execution.

11. The system of claim 9,

a database implementor that utilizes heuristics in determining each subproblem'"'"'s optimization goal.

12. The system of claim 11,

said database implementor including a OnceGuidance heuristic for use in selecting ones of said rules that can be applied to a specified expression and to said specified expression'"'"'s substitute.

13. The system of claim 9,

said search engine further including instructions that

associate a cost with each said generated expression, said cost based on a prescribed criteria that considers performance characteristics associated with said system and a context associated with each said generated expression,

consider a subset of said generated expressions for formulation into a plan, said subset including ones of said generated expressions having an associated cost that is lower than a threshold cost associated with a particular one of said subproblems.

14. The system of claim 9,

said search engine including instructions that

merge two groups of said search data structure when a predefined condition occurs,

adjust references in said search data structure to a first one of said merged groups to a second one of said merged groups,

detect duplicate expressions in said search data structure, and

delete said detected duplicate expressions.

15. The system of claim 9,

said search engine further including instructions that

for a particular one of said generated expressions corresponding to a top level expression, assigns said top level expression'"'"'s group attributes to said particular generated expression,

for a select one of said generated expressions corresponding to a logical expression having inputs,

performs a dataflow analysis to determine new group attributes for said select generated expression, and

stores said select generated expression in a new group in said search data structure.

16. A computer readable storage medium for storing data for access by programs being executed on a data processing system, said medium comprising:

a query tree representing a database query, said query tree including one or more levels of logical expressions, each logical expression including zero or more logical expressions as inputs, a subset of said inputs representing one or more subtrees, each level other than a top level having one or more logical expressions that are input to a higher level logical expression at a preceding level, one of said logical expressions representing a root expression;

a search data structure including a plurality of groups, each said group representing equivalent expressions having common group attributes, each said group including at least one logical expression from said query tree, zero or more equivalent expressions associated therewith, one or more plans, and one or more contexts, each of said plans implementing at least one expression associated with said group and having an optimization goal and a cost, each of said contexts having an associated optimization goal and representing ones of said plans that are compatible with said context'"'"'s associated optimization goal;

a plurality of rules for use in generating one or more equivalent expressions or one or more plans;

a search engine for generating one or more plans that execute said database query, said search engine including instructions that

determine group attributes for each said logical expression in said query tree, said group attributes including a set of characteristic inputs and a set of characteristic outputs, said characteristic inputs representing inputs required for a particular logical expression and zero or more logical expressions at one or more subsequent levels to said particular expression, said characteristic outputs representing outputs generated by a specified logical expression and zero or more logical expressions at one or more preceding levels to said specified logical expression,

store each said logical expression of said query tree in a corresponding one of said groups in said search data structure associated with said logical expression'"'"'s group attributes,

partition said database query into one or more subproblems, each subproblem including one or more of said logical expressions and an optimization goal, a first level having one of said subproblems representing said root expression, each subproblem at each subsequent level representing one of said inputs to a corresponding top logical expression at a preceding level, each of said subproblems associated with one of said groups corresponding to said top logical expression in said subproblem,

formulate at least one plan for each of said subproblems from one or more expressions associated with each said subproblems, each said plan formulated by generating zero or more equivalent expressions from applying a set of rules to one or more expressions associated with a particular subproblem, each said generated expression having a set of group attributes associated therewith, said group attributes used to determine if said generated expression exists in said search data structure and to store said generated expression into an appropriate group in said search data structure, and

generate a plan for said database query as a combination of each of said subproblem'"'"'s plans.

17. The medium of claim 16 further comprising:

a plurality of tasks, each task including a subset of said search engine'"'"'s instructions;

a task scheduler that manages scheduling one or more tasks on one or more processors associated with said system; and

a task data structure for storing one or more tasks awaiting execution.

18. The medium of claim 16,

a database implementor that utilizes heuristics in determining each subproblem'"'"'s optimization goal.

19. The medium of claim 18,

said database implementor including a OnceGuidance heuristic for use in selecting ones of said rules that can be applied to a specified expression and to said specified expression'"'"'s substitute.

20. The medium of claim 16,

said search engine further including instructions that

associate a cost with each said generated expression, said cost based on a prescribed criteria that considers performance characteristics associated with said system and a context associated with each said generated expression,

consider a subset of said generated expressions for formulation into a plan, said subset including ones of said generated expressions having an associated cost that is lower than a threshold cost associated with a particular one of said subproblems.

21. The medium of claim 16,

said search engine including instructions that

merge two groups of said search data structure when a predefined condition occurs,

adjust references in said search data structure to a first one of said merged groups to a second one of said merged groups, and

delete duplicate expressions in said merged group.

22. The medium of claim 16,

said search engine further including instructions that

for a particular one of said generated expressions corresponding to a top level expression, assigns said top level expression'"'"'s group attributes to said particular generated expression,

for a select one of said generated expressions corresponding to a logical expression having inputs,

performs a dataflow analysis to determine group attributes for said select generated expression, and

stores said select generated expression in a new group in said search data structure.