QUERY PLAN REFORMULATION

• US 20110131199A1
• Filed: 11/30/2009
• Published: 06/02/2011
• Est. Priority Date: 11/30/2009
• Status: Active Grant

• Current Assignee: Business Objects Incorporated (SAP SE)
• Original Assignee: Business Objects Incorporated (SAP SE)
• Inventors: Llirbat, Francois, Fabret, Francoise, Dragusanu, Adrian, Dieu, Nicolas, Simon, Eric
• Granted Patent: US 8,688,683 B2
• Time in Patent Office: Days
• US Class Current: 707/714
• CPC Class Codes: G06F 16/24542 Plan optimisation

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.

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.

2. The apparatus of claim 1, further comprising:

a display to display a search result provided by executing the compact query plan or a derivative query plan derived from the compact query plan.

3. The apparatus of claim 1, further comprising:

multiple processors, wherein the processing node comprises a first one of the multiple processors, and wherein the analysis module comprises a software module to be executed by a second one of the multiple processors.

4. The apparatus of claim 1, wherein the processing node comprises one of a server or a client.

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.

6. The system of claim 5, wherein the plurality of databases are stored on a plurality of storage nodes, including the storage node.

7. The system of claim 5, further comprising:

a display coupled to a third processing node to display at least a portion of a database query that is processed to provide the original query plan.

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.

9. The method of claim 8, further comprising:

grouping the database operations within the at least one abstract node into sets of operations; and

determining a set of precedence links between the sets that define exactly all ordering dependencies between the sets.

10. The method of claim 8, further comprising:

traversing the query nodes in the original query plan; and

forming one of the source nodes in the compact query plan when a data source scan operator is encountered in the original query plan.

11. The method of claim 8, wherein the transforming further comprises:

traversing the query nodes in the original query plan; and

forming additional singleton nodes in the compact query plan when an Aggregate Group by (A) operator, null-accepting Full Outer Join (FOJ) operator, Order by (O) operator, or Union (U) operator is encountered in the original query plan.

12. The method of claim 8, further comprising:

traversing the query nodes of the original query plan; and

forming additional abstract nodes in the compact query plan when a Cartesian product (C) operator, Filter (F) operator, Evaluation (E) operator, a Left Outer Join (LOJ) operator, or null-rejecting Full Outer Join (FOJ_rej) operator is encountered in the original query plan.

13. The method of claim 12, further comprising:

computing maximal source sub-queries associated with the compact query plan.

14. The method of claim 13, wherein computing the maximal source sub-queries further comprises:

searching for some of the maximal source sub-queries that can be extracted from the additional abstract nodes; and

when a single one of the maximal source sub-queries that is equivalent to a first one of the additional abstract nodes is found, moving a tree rooted at the first one of the additional abstract nodes to a new source node,

otherwise, if an equivalent maximal source sub-query is not found, creating new source nodes for multiple ones of the maximal source sub-queries, removing the new source nodes from a second one of the additional abstract nodes, and merging the new source nodes with the maximal source sub-queries associated with the source nodes corresponding to an input of the second one of the additional abstract nodes.

15. The method of claim 12, wherein computing the maximal source sub-queries further comprises:

determining that all input nodes to the at least one singleton node in the compact query plan are associated with a single data source; and

moving a tree rooted at the at least one singleton node to a source node associated with the single data source to increase a profit function.

16. The method of claim 8, further comprising:

computing semi-join reductions of maximal source sub-queries associated with the compact query plan to provide a derivative query plan.

17. The method of claim 16, wherein computing the semi-join reductions further comprises:

determining a reducer set of variables for each output variable of the compact query plan that can be transitively reduced by each one of the reducer set of variables.

18. The method of claim 16, wherein computing the semi-join reductions further comprises:

integrating the semi-join reductions into the at least one abstract node.

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.

20. The article of claim 19, containing executable instructions stored thereon which, when executed, result in the processor performing:

reducing some of the source nodes by determining existence of reducible vectors associated with input nodes of the source nodes.

21. The article of claim 19, containing executable instructions stored thereon which, when executed, result in the processor performing:

revising one of the source nodes to include a bind join between a cache node and another node along a reduction path.

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.