Patent US5819255A successfully refreshed from Google Patents.
US5819255A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for database query optimization
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1996-12-27
•
Granted: 1998-10-06
•
Expires: 2016-12-27
Abstract
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.
Inventors
- 👤 Pedro Celis
- 👤 Jay Vaishnav
- 👤 Hansjorg Zeller
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 16:56
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24542; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99935; Y10S707/99936
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
575 words
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.
Claim 2
Dependent Claim
575 words
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.
Claim 3
Dependent Claim
151 words
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.
Claim 4
Dependent Claim
32 words
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.
Claim 5
Dependent Claim
82 words
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.
Claim 6
Dependent Claim
58 words
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.
Claim 7
Dependent Claim
96 words
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.
Claim 8
Dependent Claim
39 words
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.
Claim 9
Dependent Claim
73 words
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.
Claim 10
Dependent Claim
508 words
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.
Claim 11
Dependent Claim
508 words
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.
Claim 12
Dependent Claim
53 words
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.
Claim 13
Dependent Claim
17 words
The system of claim 9, a database implementor that utilizes heuristics in determining each subproblem's optimization goal.
Claim 14
Dependent Claim
34 words
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.
Claim 15
Dependent Claim
83 words
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.
Claim 16
Dependent Claim
61 words
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.
Claim 17
Dependent Claim
82 words
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.
Claim 18
Dependent Claim
519 words
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.
Claim 19
Dependent Claim
519 words
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.
Claim 20
Dependent Claim
53 words
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.
Claim 21
Dependent Claim
17 words
The medium of claim 16, a database implementor that utilizes heuristics in determining each subproblem's optimization goal.
Claim 22
Dependent Claim
34 words
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.
Claim 23
Dependent Claim
83 words
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.
Claim 24
Dependent Claim
55 words
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.
Claim 25
Dependent Claim
81 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-10-05 | 2002-04-06 | 2002-10-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-10-05 | 2006-04-06 | 2006-10-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-10-05 | 2010-04-06 | 2010-10-06 | $7700.00 | Window Closed / Lapsed |