System and method for optimizing database queries with improved performance enhancements

• US 6,021,405 A
• Filed: 12/11/1996
• Issued: 02/01/2000
• 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: Vaishnav, Jay, Shak, Diana, Zeller, Hansjorg, Celis, Pedro
• Primary Examiner(s): Choules, Jack M.
• Application Number:
  US08/763,407
• Time in Patent Office: 1,147 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

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 execution plans. The query optimizer partitions the database query into one or more subproblems with each subproblem consisting of one or more logical expressions. A plan is obtained for each subproblem with the plan for the database query including the plans for each subproblem. The query optimizer is cost-based and uses rules including transformation and implementation rules that are used to perform transformations on the logical expressions in a subproblem in order to produce a plan. The rules are classified into context-free and context-sensitive in order to avoid generating duplicate expressions. Context-free rules are applied once for each logical expression and context-sensitive rules are applied once for each logical expression for a particular optimization goal. In a preferred embodiment, the query optimizer performs several optimization passes over the database query in order to obtain an optimal plan. For each pass, if no optimal plan exists for the requested optimization goal, existing plans having the same optimization goal are utilized with each input reoptimized for a more cost effective plan.

Claims

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

(a) providing said database query with an optimization goal;

(b) 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 one 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;

(c) storing in a memory a search data structure for storing a plurality of groups, each 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, 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;

(d) obtaining a plurality of rules for use in generating one or more equivalent expressions or one or more plans, a first subset of said rules including context-free rules for application once to a particular logical expression, a second subset of said rules including context-sensitive rules for application once to a particular logical expression for a particular optimization goal;

(e) partitioning said query tree into one or more levels of subproblems, each subproblem including one or more of said logical expressions, 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 and including a specified optimization goal;

(f) optimizing each of said subproblems so that at least one plan is obtained for each of said subproblems, said optimizing step further comprising the steps of;

(1) searching each of said contexts of a specified subproblem'"'"'s group for at least one plan having an optimization goal that is suitable for said specified subproblem'"'"'s optimization goal;

(2) when no plan is found, determining a set of rules for use in generating zero or more plans that satisfy said specified subproblem'"'"'s optimization goal, said set including zero or more context-free rules and zero or more context-sensitive rules;

(3) applying each of said context-free rules in the determined set to one or more specified logical expressions in said specified subproblem if not applied previously and applying each of said context-sensitive rules in said determined set to one or more specified logical expressions for a particular optimization goal if not applied previously; and

(4) storing zero or more equivalent expressions or plans generated from said application in said specified subproblem'"'"'s group in said search data structure; and

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

2. The method of claim 1,

each logical expression in said search data structure further including data indicating which of said context-free rules have been applied to said logical expression and which of said context-sensitive rules have been applied to said logical expression for an associated optimization goal.

3. The method of claim 1,

said step (f)(1) further comprising the step of bypassing ones of said contexts whose associated optimization goal is incompatible with said subproblem'"'"'s optimization goal.

4. The method of claim 1 further comprising the steps of:

repeating steps (e) through (f) for a number of passes to generate one or more additional plans representing said database query; and

selecting a best one of said plans representing said database query in accordance with a prescribed criteria.

5. The method of claim 1,

wherein each said optimization goal includes one or more required physical properties.

6. The method of claim 1,

said step (e) further comprising the steps of

for each of said subproblems having at least one input, generating a set of subproblems for each input, each generated input subproblem having a different optimization goal that satisfies an associated parent subproblem'"'"'s optimization goal, said set including less than all possible input subproblems that could be generated for the corresponding input.

7. The method of claim 1,

said database query including one or more levels of join expressions, each join expression including one or more input expressions at a subsequent level, each input expression including zero or more join expressions and one or more table expressions, each of said table expressions having an associated table size;

said step (b) further including restructuring each of said join expressions such that each table expression at each level has an associated table size that is larger than or equal to the table size associated with a table expression at an immediately succeeding level.

8. 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 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 first subset of said rules including context-free rules for application once to a particular logical expression, a second subset of said rules including context-sensitive rules for application once to a particular logical expression and for a particular optimization goal;

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

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,

obtain a plan for each of said subproblems, said plan generated by first searching each of said contexts associated with a particular subproblem'"'"'s group for at least one plan having an optimization goal that is suitable for said subproblem'"'"'s optimization goal, and when no suitable plan is found, determine a set of rules for use in generating zero or more plans that satisfy said specified subproblem'"'"'s optimization goal, said set including zero or more context-free rules and zero or more context-sensitive rules, apply one or more rules in the determined set to each logical expression in said particular subproblem, each of said context-free rules in the determined set applied to a particular logical expression if not applied previously, each of said context-sensitive rules in the determined set applied to a particular logical expression for a particular optimization goal if not applied previously, and

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

9. The system of claim 8 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.

10. The system of claim 8,

said search engine further including instructions to bypass a context whose associated optimization goal is incompatible with said particular subproblem'"'"'s optimization goal when searching for a suitable plan for a particular subproblem.

11. The system of claim 8,

each of said plans in said search data structure further including references to zero or more levels of input plans, each input plan having zero or more inputs plans, each input plan associated with a different group than an associated parent plan and including a cost;

and

said search engine further including instructions to

repeatedly execute said search engine'"'"'s instructions for a number of passes, each pass generating zero or more additional plans for said database query, each pass utilizing a different set of rules to generate said additional plans,

locate one or more plans generated in a previous pass that match a specified subproblem'"'"'s optimization goal,

generate at least one replacement input plan for one of said input plans associated with at least one of said matching plans, said replacement input plan having a lower cost than said input plan.

12. The system of claim 8,

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

13. The system of claim 8,

each said optimization goal including one or more required physical properties.

14. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

instructions for generating 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;

instructions for generating a search data structure including a plurality of groups, each 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;

instructions for implementing a plurality of rules for use in generating one or more equivalent expressions or one or more plans, a first subset of said rules including context-free rules for application once to a particular logical expression, a second subset of said rules including context-sensitive rules for application once to a particular logical expression and for a particular optimization goal;

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

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,

obtain a plan for each of said subproblems, said plan generated by first searching each of said contexts associated with a particular subproblem'"'"'s group for at least one plan having an optimization goal that is suitable for said subproblem'"'"'s optimization goal, and when no suitable plan is found, determine a set of rules for use in generating zero or more plans that satisfy said specified subproblem'"'"'s optimization goal, said set including zero or more context-free rules and zero or more context-sensitive rules, apply one or more rules in said determined set to each logical expression in said particular subproblem, each of said context-free rules in said determined set applied to a particular logical expression if not applied previously, each of said context-sensitive rules in said determined set applied to a particular logical expression for a particular optimization goal if not applied previously, and

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

15. The computer program product of claim 14 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.

16. The computer program product of claim 14,

said search engine further including instructions to bypass a context whose associated optimization goal is incompatible with said particular subproblem'"'"'s optimization goal when searching for a suitable plan for a particular subproblem.

17. The computer program product of claim 14,

each of said plans in said search data structure further including references to zero or more levels of input plans, each input plan having zero or more inputs plans, each input plan associated with a different group than an associated parent plan and including a cost;

and

said search engine further including instructions to

repeatedly execute said search engine'"'"'s instructions for a number of passes, each pass generating zero or more additional plans for said database query, each pass utilizing a different set of rules to generate said additional plans,

locate one or more plans generated in a previous pass that match a specified subproblem'"'"'s optimization goal,

generate at least one replacement input plan for one of said input plans associated with at least one of said matching plans, said replacement input plan having a lower cost than said input plan.

18. The computer program product of claim 14,

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

19. The computer program product of claim 14,

each said optimization goal including one or more required physical properties.