Use of connectivity analysis to assist rule-based optimizers

• US 8,145,627 B2
• Filed: 06/10/2005
• Issued: 03/27/2012
• Est. Priority Date: 06/10/2005
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Al-omari, Awny K.
• Primary Examiner(s): NGUYEN, PHONG H
• Application Number:
  US11/150,388
• Publication Number:
  US 20060282422A1
• Time in Patent Office: 2,482 Days
• Field of Search: 707/713, 707/718, 707/797
• US Class Current: 707/718
• CPC Class Codes: G06F 16/24544 Join order optimisation

Abstract

Methods and systems receive a normalized query tree and analyze the tree to collect information about join operators and their children, and tables in an associated query. This information is then made available to a rule based optimizer that is configured to produce, from the normalized query tree, an execution plan. In addition, in at least some embodiments, an extensible framework is provided for join order optimization via the use of a multi-join operator and multi-join rules as part of the general framework of a query optimizer.

Claims

1. A computer-implemented method comprising:

receiving a normalized query tree;

dividing the normalized query tree into regions of multiple join backbones that refer to multi-way joins between two or more relational expressions;

analyzing the regions of the normalized query tree to collect information about;

join operators and their children, and

tables in an associated query; and

making said information available to a rule based optimizer that produces, from the normalized query tree, an execution plan that visits only parts of a search space rather than using a pruning technique to reduce the search space.

2. The method of claim 1, wherein the act of analyzing is performed by:

conducting join backbone analysis, wherein a join backbone comprises a multi-way join between two or more relational expressions; and

conducting table connectivity analysis which collects predicate relationship information.

3. The method of claim 2, wherein the act of analyzing comprises defining a node analysis data structure that holds collected information, said node analysis data structure being associated with one or more group analysis data structures;

wherein at least some individual operator nodes are assigned a node analysis structure, the node analysis structure being associated with a join backbone child analysis data structure that captures relationship information between a particular join backbone child and its sibling join backbone children within a join backbone and a table analysis data structure that captures predicate connectivity relations between a table and other tables in a query.

4. The method of claim 3, wherein the join backbone child analysis data structure captures relationship information comprising joined join backbone children, joining predicates with each join backbone child, and join types.

5. The method of claim 3, wherein the table analysis data structure is structured to enable lookup for available access paths, natural sort orders and partitioning.

6. The method of claim 3, wherein said data structures are accessible from within the rule base optimizer.

7. A computer-implemented method comprising:

receiving a normalized query tree;

recursively traversing the normalized query tree and assigning analysis constructs as follows;

(a) creating a node analysis object with table analysis object for each scan expression and assigning the node analysis object to a group analysis object of a group attributes object of the associated scan node; and

(b) assigning a node analysis object with join backbone child object to individual expressions that are children of a join expression, the node analysis object being assigned to a group analysis object of a group attributes object of the join expression;

invoking a join backbone analysis task that associates join backbone children with their associated join backbone parents and computing relationships between sibling join backbone children;

invoking a table connectivity analysis task that captures connectivity relationships between different base columns and base tables in a query; and

using the join backbone analysis task and the table connectivity analysis task to produce an execution plan that visits only parts of a search space rather than using a pruning technique to reduce the search space.

8. The method of claim 7, wherein the act of computing relationships is performed by computing join predicates, join types and join data flow reductions.

9. The method of claim 7, wherein the table connectivity analysis task captures said connectivity relationships as a hyper-graph in which nodes in the hyper-graph represent base columns and connections represent predicates in the normalized query tree.

10. The method of claim 9, wherein connection predicates are selected from a group of connection predicates comprising:

a reference connection which considers two or more nodes to be connected if they are both referenced by a predicate, or

an equivalence connection which considers two or more nodes connected if they have an equality predicate.

11. The method of claim 10, wherein said act of invoking a table connectivity analysis task comprises:

recursively traversing the normalized query tree;

for each expression in the normalized query tree, analyzing the selection predicate including, for join expressions, analyzing the join predicate by traversing the scalar expression tree of each predicate looking for base column references, wherein if a predicate is an equality predicate, gathering information about base column members of the equality relationship;

setting predicate-column associations and resulting column-column associations; and

setting consequent table-table and table-column connectivity associations.

12. The method of claim 7, wherein said acts of recursively traversing the normalized query tree, invoking a join backbone analysis task and invoking a table connectivity analysis task develops information;

and

further comprising making said information available to a rule based optimizer that is configured to produce, from the normalized query tree, an execution plan.

13. A system comprising:

one or more processors;

one or more computer-readable media;

computer-readable instructions on the one or more computer-readable media which, when executed by the one or more processors, cause the one or more processors to implement a method comprising;

dividing the normalized query tree into regions of multiple join backbones that refer to multi-way joins between two or more relational expressions;

receiving a normalized query tree;

analyzing the regions of the normalized query tree to collect information about;

join operators and their children, and

tables in an associated query; and

making said information available to a rule based optimizer that produces, from the normalized query tree, an execution plan that visits only parts of a search space rather than using a pruning technique to reduce the search space.

14. The system of claim 13, wherein the act of analyzing is performed by:

conducting join backbone analysis, wherein a join backbone comprises a multi-way join between two or more relational expressions; and

conducting table connectivity analysis which collects predicate relationship information.

15. The system of claim 14, wherein the act of analyzing comprises defining a node analysis data structure that holds collected information, said node analysis data structure being associated with one or more group analysis data structures;

wherein at least some individual operator nodes are assigned a node analysis structure, the node analysis structure being associated with a join backbone child analysis data structure that captures relationship information between a particular join backbone child and its sibling join backbone children within a join backbone and a table analysis data structure that captures predicate connectivity relations between a table and other tables in a query.

16. The method of claim 15, wherein the join backbone child analysis data structure captures relationship information comprising joined join backbone children, joining predicates with each join backbone child, and join types.

17. The method of claim 15, wherein the table analysis data structure is structured to enable lookup for available access paths, natural sort orders and partitioning.

18. The method of claim 15, wherein said data structures are accessible from within the rule base optimizer.