Query optimization by predicate move-around

• US 5,659,725 A
• Filed: 06/06/1994
• Issued: 08/19/1997
• Est. Priority Date: 06/06/1994
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Levy, Alon Yitzchak, Mumick, Inderpal Singh
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US08/254,215
• Time in Patent Office: 1,170 Days
• Field of Search: 395/600, 395/700, 395/66
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24537 of operators
• 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

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.

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.

2. The method set forth in claim 1 further comprising the step of:

reducing the number of the predicates in the query graph data structure.

3. The method set forth in claim 2 wherein:

the step of reducing the number of the predicates reduces the predicates such that no predicate is applied more than once.

4. The method set forth in claim 2 wherein the step of reducing comprises the step of:

removing any predicate from a given node'"'"'s label which is applied at a descendant of the given node.

5. The method set forth in either claim 2 or claim 4 wherein the step of reducing comprises the step of:

removing any predicate in a label which is implied by another predicate in the label.

6. The method set forth in either claim 1 or claim 2 wherein:

the step of inferring a first at least one new predicate in the parent node'"'"'s label is repeatedly performed beginning with a child node which is a leaf node and ending when the parent node has no parent; and

the step of inferring a second at least one new predicate in the child node'"'"'s label is repeatedly performed beginning with a parent node which has no parent and ending when the child node is a leaf node.

7. The method set forth in either claim 1 or claim 2 wherein:

each node of the query graph data structure represents a computation in the query;

the predicate used to infer the first at least one new predicate is a predicate on an exported attribute, the exported attribute appearing in the result of the computation represented by the child node; and

the predicate used to infer the second at least one new predicate is a predicate on an exported attribute.

8. The method set forth in claim 7 wherein the step of inferring the first at least one new predicate from the predicate on the exported attribute comprises:

applying the predicate on the exported attribute to a local attribute local to the node which corresponds to the exported attribute.

9. The method set forth in claim 7 wherein the step of inferring the second at least one new predicate from the predicate on the exported attribute comprises:

applying the predicate on the exported attribute to a local attribute local to the node which corresponds to the exported attribute.

10. The method set forth in claim 1 or claim 2 wherein:

in the step of inferring a first at least one new predicate, the predicate on the label belonging to the child node includes an aggregation operation.

11. The method set forth in claim 10 wherein the step of inferring a first at least one new predicate comprises the step of:

inferring the first at least one new predicate such that the first at least one new predicate limits the result of the aggregation operation.

12. The method set forth in claim 1 or claim 2 wherein:

in the step of inferring a second at least one new predicate, the predicate on the label belonging to the parent of the node includes an aggregation operation.

13. The method set forth in claim 10 wherein the step of inferring a second at least one new predicate comprises the step of:

inferring the second at least one new predicate such that the second at least one new predicate limits the result of the aggregation operation.

14. The method set forth in claim 1 or claim 2 further comprising the step performed in the parent node of:

adding a third at least one new predicate which is implied by predicates in the label.

15. The method set forth in either claim 1 or claim 2 wherein the step making a query graph data structure further comprises the step of:

inferring a predicate from a function on an attribute of a base relation.

16. The method set forth in claim 1 or claim 2 further comprising the step performed in the child node of:

adding a fourth at least one new predicate which is implied by predicates in the label.

17. The method set forth in either claim 1 or 2 wherein the step of removing the predicates:

reduces the number of predicates to an equivalent smaller number thereof.