# US 2015/0149442 A1 · Optimal Operator Placement for Distributed Query Processing

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0149442 A1
- Document ID: US20150149442A1
- Status: Published application
- Kind: A1
- Application number: 14/450,114
- Filed: 2014-08-01
- Published: 2015-05-28
- Earliest claimed: 2013-11-26
- Assignees: Sap SE
- Inventors: Ki Hong Kim; Sangyong Hwang; Sung Heun Wi; Jane Jung Lee; Joo Young Yoon; Sang Kyun Cha
- Web page: https://patentgrep.com/patent/US20150149442A1

## CPC

- G06F 16/24545: {Selectivity estimation or determination}
- G06F 16/24544: {Join order optimisation}
- G06F 16/24542: {Plan optimisation}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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.

### Claim 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.

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 7)

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.

### Claim 10 (depends on 7)

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.

### Claim 11 (depends on 7)

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.

### Claim 12 (depends on 7)

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.

### Claim 13 (depends on 7)

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.

### Claim 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.

### Claim 15 (depends on 14)

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.

### Claim 16 (depends on 7)

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.

### Claim 17 (depends on 14)

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.

### Claim 18 (depends on 14)

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.

### Claim 19 (depends on 14)

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.

### Claim 20 (depends on 14)

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.
