Query optimization by predicate move-around
DCFirst Claim
1. A method of operation of a data base system for optimizing a query having predicates applicable to attributes involved in the query, the method comprising the steps of:
- making a query graph data structure for the query by creating a label with at least one predicate applicable to the attributes mentioned in at least one node;
in a parent node of the query graph data structure, inferring a first at least one new predicate in the parent node'"'"'s label from a predicate in a label belonging to any child node of the parent, and propagating the inferred first at least one new predicate to the parent node;
in a child node of the query graph data structure, inferring a second at least one new predicate in the child node'"'"'s label from a predicate in a label belonging to any parent of the node and propagating the inferred second at least one new predicate to children of the parent node; and
generating an optimized query from the query graph data structure by removing from the query graph data structure any redundant predicates.
5 Assignments
Litigations
0 Petitions
Accused Products
Abstract
Query optimization which is done by making a graph of the query and moving predicates around in the graph so that they will be applied early in the optimized query generated from the graph. Predicates are first propagated up from child nodes of the graph to parent nodes and then down into different child nodes. After the predicates have been moved, redundant predicates are detected and removed. Predicates are moved through aggregation operations and new predicates are deduced from aggregation operations and from functional dependencies. The optimization is not dependent on join order and works where nodes of the graph cannot be merged.
220 Citations
17 Claims
-
1. A method of operation of a data base system for optimizing a query having predicates applicable to attributes involved in the query, the method comprising the steps of:
-
making a query graph data structure for the query by creating a label with at least one predicate applicable to the attributes mentioned in at least one node; in a parent node of the query graph data structure, inferring a first at least one new predicate in the parent node'"'"'s label from a predicate in a label belonging to any child node of the parent, and propagating the inferred first at least one new predicate to the parent node; in a child node of the query graph data structure, inferring a second at least one new predicate in the child node'"'"'s label from a predicate in a label belonging to any parent of the node and propagating the inferred second at least one new predicate to children of the parent node; and generating an optimized query from the query graph data structure by removing from the query graph data structure any redundant predicates. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
Specification