Use of multi-join operator and rules as framework for join tree processing in database systems

• US 7,512,600 B2
• Filed: 06/10/2005
• Issued: 03/31/2009
• 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: Perfilov, Sergei, Al-Omari, Awny K., Siddiqui, Kashif A.
• Primary Examiner(s): Chace; Christian P.
• Assistant Examiner(s): BUCKINGHAM, KELLYE DEE
• Application Number:
  US11/150,803
• Publication Number:
  US 20060282423A1
• Time in Patent Office: 1,390 Days
• Field of Search: 707 3- 5, 707/101
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24544 Join order optimisation
• 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
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

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, at a computer, a query tree for a query, the query tree having one or more multi-way joins between relational operators;

representing at least one individual multi-way join with a multi-join operator;

applying one or more rules to the multi-join operator sufficient to generate one or more subtrees, wherein said applying one or more rules includes applying a multi-join prime table rule for reducing a selected number of rows in a prime table that is a largest table after application of local predicates;

selecting a join order based on application of said one or more rules; and

producing and executing, by the computer, an execution plan that searches only parts of a search space for the query.

2. The method of claim 1, wherein said act of representing comprises processing each multi-way join to compact it into a single multi-join node.

3. The method of claim 2, wherein said act of processing creates the single multi-join node to have a same number of children as a number of joined expressions in the multi-way join.

4. The method of claim 1, wherein application of one rule to the multi-join operator generates a fully or partially specified join order/shape.

5. The method of claim 4, wherein fully specified join order/shapes are characterized as having all leaves as join backbone children expressions.

6. The method of claim 4, wherein partially specified join order/shapes are characterized as having one or more multi-join operator leaves that join a subset of original multi-join children.

7. The method of claim 1, wherein said act of applying comprises applying at least a multi-join enumeration rule for enumerating different join orders of a join backbone.

8. The method of claim 7, wherein said act of applying comprises applying a multi-join enumeration rule that performs a search of the search space without applying pruning mechanisms.

9. The method of claim 8, wherein the search space comprises a search space selected from a group of search spaces comprising:

left linear search space, zigzag search space or bushy tree search space.

10. The method of claim 7, wherein said act of applying comprises applying a multi-join enumeration rule that performs a search of the search space and applies pruning mechanisms.

11. The method of claim 1, wherein the act of applying at least a multi-join prune table rule comprises:

sorting all join backbone children by their after local predicate cardinality, wherein the join backbone child with a largest cardinality is the prime table;

creating an available node set that includes all join backbone children except the prime table;

computing fringes of the prime table by iterating over the join backbone children connected to the prime table in order of descending cardinality of the connected join backbone children;

identifying fringes as reducing fringes or non-reducing fringes;

sorting reducing fringes in ascending order based on the dataflow generated when the reducing fringe is joined to the prime table;

determining a best position for the prime table in the sorted reducing fringes; and

breaking up the join backbone children in the available node set in accordance with a pre-defined sort metric.

12. The method of claim 1, wherein said act of applying comprises applying one or more of the following types of rules:

pattern specific rules, decomposition rules, sampling rules and dynamic programming rules.

13. The method of claim 1, wherein said act of applying comprises:

after applying said multi-join prime table rule, applying a multi-join enumeration rule for enumerating different join orders of a join backbone.

14. The method of claim 13 further comprising prior to applying said multi-join enumeration rule, scheduling a join commutivity rule on substitutes generated by the multi-join prime table rule.

15. A computer-implemented method comprising:

receiving a query tree for a query, the query tree having one or more multi-way joins between relational operators;

representing at least one individual multi-way join with a multi-join operator, wherein said act of representing comprises processing each multi-way join to compact it into a single multi-join node;

applying one or more rules to the multi-join operator sufficient to generate one or more subtrees, wherein said act of applying comprises;

applying at least a multi-join enumeration rule for enumerating different join orders of a join backbone; and

applying at least a multi-join prime table rule for reducing a number of selected rows in a prime table, the prime table being a largest table after application of local predicates;

selecting a join order based, at least in part, on application of said one or more rules; and

producing and executing an execution plan that searches only parts of a search space for the query.

16. The method of claim 15, wherein said act of applying one or more rules comprises applying the multi-join prime table rule and applying the multi-join enumeration rule after application of the multi-join prime table rule.

17. The method of claim 16 further comprising prior to applying said multi-join enumeration rule, scheduling a join commutivity rule on substitutes generated by the multi-join prime table rule.

18. 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;

receiving a query tree for a query, the query tree having one or more multi-way joins between relational operators;

representing at least one individual multi-way join with a multi-join operator, wherein said act of representing comprises processing each multi-way join to compact it into a single multi-join node;

applying one or more rules to the multi-join operator sufficient to generate one or more subtrees, wherein said act of applying comprises;

applying at least a multi-join enumeration rule for enumerating different join orders of a join backbone;

applying at least a multi-join prime table rule for reducing a selected number of rows in a prime table, the prime table being a largest table after application of local predicates;

selecting a join order based, at least in part, on application of said one or more rules; and

producing and executing an execution plan that searches only part of a search space for the query.

19. The system of claim 18, wherein said act of applying one or more rules comprises applying the multi-join prime table rule and applying the multi-join enumeration rule after application of the multi-join prime table rule.