JOIN ORDER OPTIMIZATION IN A QUERY OPTIMIZER FOR QUERIES WITH OUTER AND/OR SEMI JOINS
First Claim
1. A method for join order optimization in a query optimizer, comprising:
- receiving a query tree having a plurality of join operators including at least one multi-way join forming a join back bone between relational operators in the query tree, wherein the join operators include at least one of an outer-join, a semi-join, and an anti-semi join;
transforming the multi-way-join to a multi-join operator with a plurality of join back bone children representing the relational operators;
tracking dependencies that occur between the join back bone children;
evaluating join order validity based on the tracked dependencies; and
applying one or more multi-join rules to the at least one multi-join operator sufficient to generate at least one join subtree representing a potential join order when the at least one join subtree is determined to have a valid join order.
2 Assignments
0 Petitions
Accused Products
Abstract
A system and method for join order optimization in a query optimizer is disclosed. The method includes receiving a query having a plurality of join operators, including at least one multi-way join between relational operators in the query tree. The join operators include at least one outer-join and/or semi-join. The multi-way-join is transformed to a multi-join operator with a plurality of join back bone children representing the relational operators. The dependencies that occur between the join back bone children are tracked. Join order validity is evaluated based on the tracked dependencies. One or more multi-join rules are applied to the multi-join operator sufficient to generate at least one join subtree when at least one join subtree is determined to have a valid join order.
36 Citations
20 Claims
-
1. A method for join order optimization in a query optimizer, comprising:
-
receiving a query tree having a plurality of join operators including at least one multi-way join forming a join back bone between relational operators in the query tree, wherein the join operators include at least one of an outer-join, a semi-join, and an anti-semi join; transforming the multi-way-join to a multi-join operator with a plurality of join back bone children representing the relational operators; tracking dependencies that occur between the join back bone children; evaluating join order validity based on the tracked dependencies; and applying one or more multi-join rules to the at least one multi-join operator sufficient to generate at least one join subtree representing a potential join order when the at least one join subtree is determined to have a valid join order. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A computer-implemented method, comprising:
-
receiving a query tree for a query, the query tree having at least one multi-way join forming a join back bone between relational operators, wherein the join operators include at least one asymmetric join; transforming the multi-way-join to a multi-join operator with a plurality of join back bone children representing the relational operators; tracking dependencies that occur between the join back bone children; and applying one or more multi-join rules to the multi-join operator, when the at least one join subtree is determined to have a valid join order based on the tracked dependencies, sufficient to generate at least one join subtree representing a potential join order. - View Dependent Claims (11, 12, 13, 14)
-
-
15. 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 for join order optimization in a query optimizer comprising; receiving a query tree having a plurality of join operators including at least one multi-way join between relational operators in the query tree, wherein the join operators include at least one of an outer-join, a semi-join, and an anti-semi join; transforming the multi-way-join to a multi-join operator with a plurality of join back bone children representing the relational operators; tracking dependencies that occur between the join back bone children; evaluating join order validity based on the tracked dependencies; and applying one or more multi-join rules to the multi-join operator sufficient to generate at least one join subtree representing a potential join order when the at least one join subtree is determined to have a valid join order. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification