Optimization of database queries for database systems and environments

Abstract

As an abstract representation, a set of equivalent logical structures representative of multiple execution plans for execution of a database query can be used to optimize a database query. A logical structure can include one or more logical operators each representing multiple physical operators for executing the database query. Group and Operator Rules can be applied as rules to the set of equivalent logical structures to obtain additional equivalent logical structures and logical operator until no additional logical operators can be obtained. A set of possible implementation plans for the total number of the obtained logical operators can be obtained, for example, based on physical and/or implementation context. An optimization request can be effectively propagated through an implantation plan in a top-down manner, for example, recursively for each child of physical operators, where only new contexts are optimized, in order to generate an optimized structure, for example, in consideration of, implementation details, costs, physical properties, etc. One of the optimized structures can be selected as an optimal plan.

1 . A method for optimizing execution of one or more database queries of a database configured to store data, wherein the method is implemented at least partly by a device, and wherein the method comprises:
 obtaining at least one set of equivalent logical structures in an optimization task structure arranged as a tree optimization task structure for optimization of execution of one or more database queries of a database, wherein the set of equivalent logical structures include one or more logical operators each representative of multiple logical execution plans for the one or more database queries of the database, wherein each one of the logical structures in the set of equivalent logical structures in the tree optimization task structure represents a distinct one of the logical execution plans for execution of at least a portion of the one or more database queries of the database and includes one or more logical operators each representative of multiple physical operators for the execution of the one or more database queries;   applying one or more rules to the set of equivalent logical structures in the tree optimization task structure to obtain another set of equivalent logical structures and at least one new logical operator in the tree optimization task structure;   propagating an optimization request of the one or more database queries through the tree optimization task structure in a top-down manner, to generate multiple optimized structures; and   selecting one of the optimized structures as an optimal physical plan for executing the one or more database queries of the database.   
     
     
         2 . The method of  claim 1 , wherein the method further comprises:
 repeating the applying of the one or more rules to the set of equivalent logical structures in the tree optimization task structure to the other obtained set of equivalent logical structures in the tree optimization task structure until no additional new logical operators can be obtained in the tree optimization task structure, thereby obtaining a total number of logical operators.   
     
     
         3 . The method of  claim 2 , wherein the method further comprises:
 determining a set of possible implementation plans for the obtained total number of the logical operators in the tree optimization task structure; and   eliminating a number of possible implementation plans in the tree optimization task structure to obtain one or more plausible implementation plans in the tree optimization task structure respectively represented as one or more plausible structures in the tree optimization task structure.   
     
     
         4 . The method of  claim 3 , wherein the method further comprises:
 for each one of the plausible implementation plans in the tree optimization task structure, propagating an optimization request of the one or more database queries through its plausible structure in the tree optimization task structure in a top-down manner, recursively for each child of physical operators, wherein only new contexts are optimized in order to generate an optimized structure, to generate an optimized structure that includes one or more physical operates for executing the one or more database queries.   
     
     
         5 . The method of  claim 4 , wherein the method further comprises: assigning a priority and/or a status to one or more of the logical structures. 
     
     
         6 . The method of  claim 5 , wherein the status includes one of more of the following: completed, waiting on child, scheduled to run, and running. 
     
     
         7 . The method of  claim 4 , wherein the plurality of optimizer tasks are maintained in the tree optimization task structure for the scheduling such that at least one task schedules two or more other tasks as it children, recursively. 
     
     
         8 . The method of  claim 7 , wherein the propagation of the optimization request of the one or more database queries starts with a Optimize Group Task (OGT) as a root of the tree structure of the tree optimization task structure and the single Optimize Group Task (OGT) has two or more children, and wherein the single Optimize Group Task (OGT) schedules at least two or more of its children in the tree structure of the tree optimization task structure in a recursive manner to generate for optimization tree task structure, one or more Apply Rule Tasks (ART) nodes, one or more Generate implementation tasks (GIT) nodes and one or more Generate Plan Tasks nodes. 
     
     
         9 . The method of  claim 8 , wherein during the propagating of the optimization request of the one or more database queries an instance of each one of the plurality of optimizer tasks optimizer tasks, maintained in the optimization task structure for the scheduling, has one of the following states: (i) Scheduled to run, (ii) running, (iii) waiting on a child, (iv) completed, and (v) pruned. 
     
     
         10 . The method of  claim 3 , wherein the eliminating of the number of possible implementation plans is performed based on at least one of: heuristics, and an optimization cost limit. 
     
     
         11 . The method of  claim 3 , wherein the determining of the set of possible implementation plans for the total number of the obtained logical operators is performed at least based on a context and/or a physical context. 
     
     
         12 . The method of  claim 1 , wherein the one or more rules include at least one of one or more group rules and one or more operator rules. 
     
     
         13 . A device, comprising:
 memory; and   one or more processors configured to access the memory, wherein the one or more processors are further configured to:
 obtain at least one set of equivalent logical structures in an optimization task structure arranged as a tree optimization task structure for optimization of execution of one or more database queries of a database, wherein the set of equivalent logical structures include one or more logical operators each representative of multiple logical execution plans for the one or more database queries of the database, wherein each one of the logical structures in the set of equivalent logical structures in the tree optimization task structure represents a distinct one of the logical execution plans for execution of at least a portion of the one or more database queries of the database and includes one or more logical operators each representative of multiple physical operators for the execution of the one or more database queries; 
   apply one or more rules to the set of equivalent logical structures in the tree optimization task structure to obtain another set of equivalent logical structures and at least one new logical operator in the tree optimization task structure;   propagate an optimization request of the one or more database queries through the tree optimization task structure in a top-down manner, to generate multiple optimized structures; and   select one of the optimized structures as an optimal physical plan for executing the one or more database queries of the database.   
     
     
         14 . The device of  claim 13 , wherein the one or more processors are further configured to:
 repeat the applying of the one or more rules to the set of equivalent logical structures in the tree optimization task structure to the other obtained set of equivalent logical structures in the tree optimization task structure until no additional new logical operators can be obtained in the tree optimization task structure, thereby obtaining a total number of logical operators.   
     
     
         15 . The device of  claim 13 , wherein the one or more processors are further configured to:
 determine a set of possible implementation plans for the obtained total number of the logical operators in the tree optimization task structure; and   eliminate a number of possible implementation plans in the tree optimization task structure to obtain one or more plausible implementation plans in the tree optimization task structure respectively represented as one or more plausible structures in the tree optimization task structure.   
     
     
         16 . The device of  claim 13 , wherein the one or more processors are further configured to:
 for each one of the plausible implementation plans in the tree optimization task structure, propagate an optimization request of the one or more database queries through its plausible structure in the tree optimization task structure in a top-down manner, recursively for each child of physical operators, wherein only new contexts are optimized in order to generate an optimized structure, to generate an optimized structure that includes one or more physical operates for executing the one or more database queries.   
     
     
         17 . The device of  claim 13 , wherein the one or more processors are further configured to:
 assign a priority and/or a status to one or more of the logical structures.   
     
     
         18 . A non-transitory computer readable storage medium storing at least executable computer code that when executed performs at least the following:
 obtaining at least one set of equivalent logical structures in an optimization task structure arranged as a tree optimization task structure for optimization of execution of one or more database queries of a database, wherein the set of equivalent logical structures include one or more logical operators each representative of multiple logical execution plans for the one or more database queries of the database, wherein each one of the logical structures in the set of equivalent logical structures in the tree optimization task structure represents a distinct one of the logical execution plans for execution of at least a portion of the one or more database queries of the database and includes one or more logical operators each representative of multiple physical operators for the execution of the one or more database queries;   applying one or more rules to the set of equivalent logical structures in the tree optimization task structure to obtain another set of equivalent logical structures and at least one new logical operator in the tree optimization task structure;   propagating an optimization request of the one or more database queries through the tree optimization task structure in a top-down manner, to generate multiple optimized structures; and   selecting one of the optimized structures as an optimal physical plan for executing the one or more database queries of the database.   
     
     
         19 . The non-transitory computer readable storage medium of  claim 18 , wherein when the executable computer code is executed it further performs at least the following:
 repeating the applying of the one or more rules to the set of equivalent logical structures in the tree optimization task structure to the other obtained set of equivalent logical structures in the tree optimization task structure until no additional new logical operators can be obtained in the tree optimization task structure, thereby obtaining a total number of logical operators.   
     
     
         20 . The non-transitory computer readable storage medium of  claim 19 , wherein when the executable computer code is executed it further performs at least the following:
 determining a set of possible implementation plans for the obtained total number of the logical operators in the tree optimization task structure; and   eliminating a number of possible implementation plans in the tree optimization task structure to obtain one or more plausible implementation plans in the tree optimization task structure respectively represented as one or more plausible structures in the tree optimization task structure.