Efficient search space analysis for join factorization
First Claim
Patent Images
1. A computer implemented method, comprisingtransforming a base query that includes a plurality of base branches of a union operator in a base query;
- andwherein transforming the base query includes;
generating a plurality of units that each correspond to a set of base branches of the plurality of base branches;
wherein each unit of said plurality of units represents a factorization of a common table set involving a common table joined in each branch of the respective set of base branches;
generating a certain plurality of states that conform to one or more criteria, wherein each state of said certain plurality of states corresponds to a combination of one or more units of said plurality of units, and a query transformation according to the one or more factorizations represented by the combination of one or more units;
generating costs for at least a subset of states of said certain plurality of states;
making a comparison of the costs of the subset of states to select a certain state of said certain plurality of states; and
wherein said computer implemented method is performed by one or more computing devices.
1 Assignment
0 Petitions
Accused Products
Abstract
Under a type of query transformation referred to herein as join factorization, the branches of an UNION/UNION ALL query that join a common table are combined to reduce accesses to the common table. The transformation can be expressed as (T1 join T2) union all (T1 join T3)=T1 join (T2 union all T3), where T1, T2 and T3 are three tables. A given query may be rewritten in many alternate ways using join factorization. Evaluating each alternative can be expensive. Therefore, the alternatives are generated and evaluated in a way that minimizes the cost of evaluating the alternatives.
-
Citations
22 Claims
-
1. A computer implemented method, comprising
transforming a base query that includes a plurality of base branches of a union operator in a base query; - and
wherein transforming the base query includes; generating a plurality of units that each correspond to a set of base branches of the plurality of base branches; wherein each unit of said plurality of units represents a factorization of a common table set involving a common table joined in each branch of the respective set of base branches; generating a certain plurality of states that conform to one or more criteria, wherein each state of said certain plurality of states corresponds to a combination of one or more units of said plurality of units, and a query transformation according to the one or more factorizations represented by the combination of one or more units; generating costs for at least a subset of states of said certain plurality of states; making a comparison of the costs of the subset of states to select a certain state of said certain plurality of states; and wherein said computer implemented method is performed by one or more computing devices. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
- and
-
11. A computer implemented method, comprising
generating a plurality of units that each correspond to a set of base branches of a plurality of base branches of a union operator in a base query; -
wherein each unit of said plurality of units represents a factorization of a common table set comprising a common table joined by each of the respective set of base branches; generating costs for combinations of the one or more units of said plurality of units; determining how to transform the base query based on a comparison of the costs; and wherein said computer implemented method is performed by one or more computing devices.
-
-
12. One or more storage media storing instructions which, when executed by one or more computing devices, cause performance of the method comprising:
-
transforming a base query that includes a plurality of base branches of a union operator in a base query; and wherein transforming the base query includes; generating a plurality of units that each correspond to a set of base branches of the plurality of base branches; wherein each unit of said plurality of units represents a factorization of a common table set involving a common table joined in each branch of the respective set of base branches; generating a certain plurality of states that conform to one or more criteria, wherein each state of said certain plurality of states corresponds to a combination of one or more units of said plurality of units, and a query transformation according to the one or more factorizations represented by the combination of one or more units; generating costs for at least a subset of states of said certain plurality of states; making a comparison of the costs of the subset of states to select a certain state of said certain plurality of states; and wherein said computer implemented method is performed by one or more computing devices. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
22. One or more storage media storing instructions which, when executed by one or more computing devices, cause performance of the method comprising:
-
generating a plurality of units that each correspond to a set of base branches of a plurality of base branches of a union operator in a base query; wherein each unit of said plurality of units represents a factorization of a common table set comprising a common table joined by each of the respective set of base branches; generating costs for combinations of the one or more units of said plurality of units; determining how to transform the base query based on a comparison of the costs; and wherein said computer implemented method is performed by one or more computing devices.
-
Specification