Optimal Operator Placement for Distributed Query Processing

• US 20150149442A1
• Filed: 08/01/2014
• Published: 05/28/2015
• Est. Priority Date: 11/26/2013
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Kim, Ki Hong, Hwang, Sangyong, Yoon, Joo Young, Cha, Sang Kyun, Wi, Sung Heun, Lee, Jane Jung
• Granted Patent: US 9,892,163 B2
• Time in Patent Office: Days
• US Class Current: 707/719
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination

Abstract

Total global minimum costs can be determined for multiple sub-plans for completing a multi-operation database process to be performed in a distributed database management system that includes a plurality of nodes. The multiple sub-plans can include different distributions of node locations of a plurality of operators among the plurality of nodes. An optimal plan having a lowest total minimum global cost can be selected from the multiple sub-plans.

Claims

1. A computer program product comprising a machine-readable storage medium storing instructions that, when executed by at least one processor, cause the at least one processor to perform operations comprising:

generating, for a multi-operation database process to be performed in a distributed database management system comprising a plurality of nodes, a plurality of sub-plans, each of the plurality of sub-plans comprising a different distribution of node locations of a plurality of operators among the plurality of nodes, the plurality of operators being those necessary to complete the multi-operation database process;

calculating a total minimum global cost for each sub-plan of the plurality of sub-plans; and

selecting an optimal plan from the plurality of sub-plans, the optimal plan having a lowest total minimum global cost.

2. A computer program product as in claim 1, wherein the selecting comprises pruning at least one sub-plan from the plurality of sub-plans, the pruning comprising:

tracking, for each operator of the plurality of operators, a best sub-tree cost for each node location, one or more child locations corresponding to the best sub-tree costs, and one or more child plans corresponding to the best sub-tree costs; and

eliminating at least one sub-plan having a cost greater than the best sub-tree cost for the node location.

3. A computer program product as in claim 1, wherein the selecting comprises pruning at least one sub-plan from the plurality of sub-plans, the pruning comprising eliminating at least one sub-plan having a cost greater than a best sub-plan cost for a second sub-plan that involves action at another node location plus a transfer cost for transferring one or more tables between node locations as part of the second sub-plan.

4. A computer program product as in claim 1, wherein the calculating of the total minimum global cost for each of the plurality of sub-plans further comprises quantifying child table transfer counts associated with at least one operation of the multi-operation database process.

5. A computer program product as in claim 1, wherein the calculating of the total minimum global cost for each of the plurality of sub-plans further comprises quantifying child table transfer counts associated with at least one operation of assuming placement of a physical operator on either of at least tow nodes generates a same amount of output.

6. A computer program product as in claim 1, wherein the calculating of the total minimum global cost for each of the plurality of sub-plans further comprises assuming that each node of the plurality of node has a same and symmetric network configuration.

7. A system comprising:

computer hardware configured to perform operations comprising;

generating, for a multi-operation database process to be performed in a distributed database management system comprising a plurality of nodes, a plurality of sub-plans, each of the plurality of sub-plans comprising a different distribution of node locations of a plurality of operators among the plurality of nodes, the plurality of operators being those necessary to complete the multi-operation database process;

calculating a total minimum global cost for each sub-plan of the plurality of sub-plans; and

selecting an optimal plan from the plurality of sub-plans, the optimal plan having a lowest total minimum global cost.

8. A system as in claim 7, wherein the selecting comprises pruning at least one sub-plan from the plurality of sub-plans, the pruning comprising:

tracking, for each operator of the plurality of operators, a best sub-tree cost for each node location, one or more child locations corresponding to the best sub-tree costs, and one or more child plans corresponding to the best sub-tree costs; and

eliminating at least one sub-plan having a cost greater than the best sub-tree cost for the node location.

9. A system as in claim 7, wherein the selecting comprises pruning at least one sub-plan from the plurality of sub-plans, the pruning comprising:

eliminating at least one sub-plan having a cost greater than a best sub-plan cost for a second sub-plan that involves action at another node location plus a transfer cost for transferring one or more tables between node locations as part of the second sub-plan.

10. A system as in claim 7, wherein the calculating of the total minimum global cost for each of the plurality of sub-plans further comprises quantifying child table transfer counts associated with at least one operation of the multi-operation database process.

11. A system as in claim 7, wherein the calculating of the total minimum global cost for each of the plurality of sub-plans further comprises quantifying child table transfer counts associated with at least one operation of assuming placement of a physical operator on either of at least tow nodes generates a same amount of output.

12. A system as in claim 7, wherein the calculating of the total minimum global cost for each of the plurality of sub-plans further comprises assuming that each node of the plurality of node has a same and symmetric network configuration.

13. A system as in claim 7, wherein the computer hardware comprises:

a programmable processor; and

a machine-readable storage medium storing instructions that, when executed by at least one processor, cause the at least one processor to perform at least some of the operations.

16. A system as in claim 7, wherein the selecting comprises pruning at least one sub-plan from the plurality of sub-plans, the pruning comprising:

eliminating at least one sub-plan having a cost greater than a best sub-plan cost for a second sub-plan that involves action at another node location plus a transfer cost for transferring one or more tables between node locations as part of the second sub-plan.

14. A computer-implemented method comprising:

generating, for a multi-operation database process to be performed in a distributed database management system comprising a plurality of nodes, a plurality of sub-plans, each of the plurality of sub-plans comprising a different distribution of node locations of a plurality of operators among the plurality of nodes, the plurality of operators being those necessary to complete the multi-operation database process;

calculating a total minimum global cost for each sub-plan of the plurality of sub-plans; and

selecting an optimal plan from the plurality of sub-plans, the optimal plan having a lowest total minimum global cost.

15. A computer-implemented method as in claim 14, wherein the selecting comprises pruning at least one sub-plan from the plurality of sub-plans, the pruning comprising:

tracking, for each operator of the plurality of operators, a best sub-tree cost for each node location, one or more child locations corresponding to the best sub-tree costs, and one or more child plans corresponding to the best sub-tree costs; and

eliminating at least one sub-plan having a cost greater than the best sub-tree cost for the node location.

17. A computer-implemented method as in claim 14, wherein the calculating of the total minimum global cost for each of the plurality of sub-plans further comprises quantifying child table transfer counts associated with at least one operation of the multi-operation database process.

18. A computer-implemented method as in claim 14, wherein the calculating of the total minimum global cost for each of the plurality of sub-plans further comprises quantifying child table transfer counts associated with at least one operation of assuming placement of a physical operator on either of at least tow nodes generates a same amount of output.

19. A computer-implemented method as in claim 14, wherein the calculating of the total minimum global cost for each of the plurality of sub-plans further comprises assuming that each node of the plurality of node has a same and symmetric network configuration.

20. A computer-implemented method as in claim 14, wherein at least one of the generating, the calculating, and the selecting is performed by one or more systems comprising computer hardware.