Use of multi-join operator and rules as framework for join tree processing in database systems
First Claim
Patent Images
1. A computer-implemented method comprising:
- receiving a 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; and
selecting a join order based, at least in part, on application of said one or more rules.
4 Assignments
0 Petitions
Accused Products
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.
38 Citations
20 Claims
-
1. A computer-implemented method comprising:
-
receiving a 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; and
selecting a join order based, at least in part, on application of said one or more rules. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A computer-implemented method comprising:
-
receiving a 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 the number of selected rows in a prime table, the prime table being the largest table after application of local predicates; and
selecting a join order based, at least in part, on application of said one or more rules. - View Dependent Claims (17, 18)
-
-
19. 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 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 the selected number of rows in a prime table, the prime table being the largest table after application of local predicates; and
selecting a join order based, at least in part, on application of said one or more rules. - View Dependent Claims (20)
-
Specification