QUERY PLAN REFORMULATION
First Claim
Patent Images
1. An apparatus, comprising:
- a processing node comprising a data reception module to receive an original query plan comprising query nodes that include one or more database operations; and
an analysis module to couple to the processing node, the analysis module to transform the original query plan into an equivalent executable compact query plan to store on a machine readable device, the compact query plan comprising at least two source nodes including scan operations to source tables, the at least two source nodes coupled to at least one abstract node and at least one singleton node, wherein a child of the at least one abstract node comprises at least one of the source nodes or the at least one singleton node, but not another abstract node, wherein the at least one singleton node comprises a single operation selected from aggregate, union, order by, or null accepting full outer join, wherein the at least one abstract node comprises a set of operations selected from at least one of Cartesian product, evaluation, filter, left outer join, or null rejecting full outer join, and wherein the at least one abstract node is partitioned into multiple intra-partition commutable operations that can be executed in a different order from the original query plan based on upward compatibility or a combination of a single null rejecting left outer join operation and the multiple intra-partition commutable operations.
2 Assignments
0 Petitions
Accused Products
Abstract
Apparatus, systems, and methods may operate to receive an original query plan, to transform the original query plan into an equivalent executable compact query plan, and to store the compact query plan on a machine readable device. Further activities may include computing maximal source sub-queries associated with the compact query plan, and computing semi-join reductions of the maximal source sub-queries to provide an executable derivative query plan, which may also be stored on a machine readable device. Additional apparatus, systems, and methods are disclosed.
-
Citations
23 Claims
-
1. An apparatus, comprising:
-
a processing node comprising a data reception module to receive an original query plan comprising query nodes that include one or more database operations; and an analysis module to couple to the processing node, the analysis module to transform the original query plan into an equivalent executable compact query plan to store on a machine readable device, the compact query plan comprising at least two source nodes including scan operations to source tables, the at least two source nodes coupled to at least one abstract node and at least one singleton node, wherein a child of the at least one abstract node comprises at least one of the source nodes or the at least one singleton node, but not another abstract node, wherein the at least one singleton node comprises a single operation selected from aggregate, union, order by, or null accepting full outer join, wherein the at least one abstract node comprises a set of operations selected from at least one of Cartesian product, evaluation, filter, left outer join, or null rejecting full outer join, and wherein the at least one abstract node is partitioned into multiple intra-partition commutable operations that can be executed in a different order from the original query plan based on upward compatibility or a combination of a single null rejecting left outer join operation and the multiple intra-partition commutable operations. - View Dependent Claims (2, 3, 4)
-
-
5. A system, comprising:
-
a storage node to store at least one of a plurality of databases; a first processing node comprising a data reception module to receive at least a portion of an original query plan comprising query nodes that include one or more database operations to be conducted on the plurality of databases; and a second processing node comprising an analysis module to couple to the first processing node, the analysis module to transform the original query plan into an equivalent executable compact query plan to store on a machine readable device, the compact query plan comprising at least two source nodes including scan operations to source tables, the at least two source nodes coupled to at least one abstract node and at least one singleton node, wherein a child of the at least one abstract node comprises at least one of the source nodes or the at least one singleton node, but not another abstract node, wherein the at least one singleton node comprises a single operation selected from aggregate, union, order by, or null accepting full outer join, wherein the at least one abstract node comprises a set of operations selected from at least one of Cartesian product, evaluation, filter, left outer join, or null rejecting full outer join, and wherein the at least one abstract node is partitioned into multiple intra-partition commutable operations that can be executed in a different order from the original query plan based on upward compatibility or a combination of a single null rejecting left outer join operation and the multiple intra-partition commutable operations. - View Dependent Claims (6, 7)
-
-
8. A processor-implemented method to execute on one or more processors that perform the method, comprising:
-
receiving an original query plan comprising query nodes that include one or more database operations; transforming the original query plan into an equivalent executable compact query plan comprising at least two source nodes including scan operations to source tables, the at least two source nodes coupled to at least one abstract node and at least one singleton node, wherein a child of the at least one abstract node comprises at least one of the source nodes or the at least one singleton node, but not another abstract node, wherein the at least one singleton node comprises a single operation selected from aggregate, union, order by, or null accepting full outer join, wherein the at least one abstract node comprises a set of operations selected from at least one of Cartesian product, evaluation, filter, left outer join, or null rejecting full outer join, and wherein the at least one abstract node is partitioned into multiple intra-partition commutable operations that can be executed in a different order from the original query plan based on upward compatibility or a combination of a single null rejecting left outer join operation and the multiple intra-partition commutable operations; and storing the compact query plan on a machine readable device. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. An article comprising a tangible computer-readable storage medium containing executable instructions stored thereon which, when executed, result in a processor performing:
-
transforming an original query plan into an equivalent executable compact query plan comprising at least two source nodes including scan operations to source tables, the at least two source nodes coupled to at least one abstract node and at least one singleton node, wherein a child of the at least one abstract node comprises at least one of the source nodes or the at least one singleton node, but not another abstract node, wherein the at least one singleton node comprises a single operation selected from aggregate, union, order by, or null accepting full outer join, wherein the at least one abstract node comprises a set of operations selected from at least one of Cartesian product, evaluation, filter, left outer join, or null rejecting full outer join, and wherein the at least one abstract node is partitioned into multiple intra-partition commutable operations that can be executed in a different order from the original query plan based on upward compatibility or a combination of a single null rejecting left outer join operation and the multiple intra-partition commutable operations; computing maximal source sub-queries associated with the compact query plan; computing semi-join reductions of the maximal source sub-queries to provide an executable derivative query plan; and storing the derivative query plan on a machine readable device. - View Dependent Claims (20, 21)
-
-
22. A processor-implemented method to execute on one or more processors that perform the method, comprising:
-
receiving an original query plan comprising query nodes that include one or more database operations; transforming the original query plan into an equivalent executable compact query plan comprising at least two source nodes including scan operations to source tables, the at least two source nodes coupled to at least one abstract node and at least one singleton node, wherein a child of the at least one abstract node comprises at least one of the source nodes, but not another abstract node, wherein the at least one singleton node comprises an aggregate operation, wherein the at least one abstract node comprises a set of operations including left outer join, and wherein the at least one abstract node is partitioned into multiple intra-partition commutable operations that can be executed in a different order from the original query plan based on upward compatibility; and storing the compact query plan on a machine readable device.
-
-
23. A processor-implemented method to execute on one or more processors that perform the method, comprising:
-
receiving an original query plan comprising query nodes that include one or more database operations; transforming the original query plan into an equivalent executable compact query plan comprising at least two source nodes including scan operations to source tables, the at least two source nodes coupled to at least one abstract node and at least one singleton node, wherein a child of the at least one abstract node comprises the at least one singleton node, but not another abstract node, wherein the at least one singleton node comprises a union operation, wherein the at least one abstract node comprises a set of operations including an evaluation operation, and wherein the at least one abstract node is partitioned into multiple intra-partition commutable operations that can be executed in a different order from the original query plan based on a combination of a single null rejecting left outer join operation and the multiple intra-partition commutable operations; and storing the compact query plan on a machine readable device.
-
Specification