# US 11,113,280 B1 · System-wide query optimization > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,113,280 B1 - Document ID: US11113280B1 - Status: Granted - Kind: B1 - Application number: 14/973,571 - Filed: 2015-12-17 - Granted: 2021-09-07 - Earliest claimed: 2012-11-30 - Assignees: Amazon Technologies, Inc. - Applicants: Amazon Technologies, Inc. - Inventors: Liang Gang Yu; John Robert Smiley - Web page: https://patentgrep.com/patent/US11113280B1 ## CPC - G06F 16/24545: {Selectivity estimation or determination} - G06F 16/24524: {Access plan code generation and invalidation; Reuse of access plans} - G06F 16/24542: {Plan optimisation} - G06F 16/24554: {Unary operations; Data partitioning operations} - G06F 16/2471: {Distributed queries} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A locally optimized plan for executing a command using a sequence of steps can be determined for a single computing node. However, the locally optimized sequence of steps may not be optimized for a combined system comprising multiple computing nodes, any one of which may be tasked with executing the command. A plan that is optimized for the combined system may be determined by comparing the predicted cost of locally optimized plans for computing nodes in the combined system. ## Claims ### Claim 1 A non-transitory computer-readable storage medium having stored thereon instructions that, when executed by a computing device, cause the computing device to at least: obtain, from a first query optimizer of a first computing node, a first plan for executing a query on the first computing node; obtain, from a second query optimizer of a second computing node, a second plan for executing the query on the second computing node; obtain a first number of votes cast by the first computing node, wherein the first number of votes is based on a first characteristic of the first computing node; obtain a second number of votes cast by the second computing node for the second plan, wherein the second number of votes is based on a second characteristic of the second computing node; determine, based on comparing the first number of votes associated with a first predicted execution cost of executing the first plan with the second number of votes associated with a second predicted execution cost of executing the second plan, that the first plan for executing the query on the first computing node is preferred for executing the query on the second computing node, wherein the first predicted execution cost is based at least in part on a first performance characteristic of the first computing node and the second predicted execution cost is based at least in part on a second performance characteristic of the second computing node; and cause, based on the comparison, the second computing node to execute the query using the first plan. ### Claim 2 (depends on 1) The non-transitory computer-readable storage medium of claim 1, wherein the computer-readable storage medium has stored thereon further instructions that, when executed by the computing device, cause the computing device to at least: receive, from a third computing device, information indicative of a vote for using the second plan. ### Claim 3 (depends on 2) The non-transitory computer-readable storage medium of claim 2, wherein the third computing device is allocated votes based at least in part on an amount of data stored on the third computing device. ### Claim 4 (depends on 1) The non-transitory computer-readable storage medium of claim 1, wherein the computer-readable storage medium has stored thereon further instructions that, when executed by the computing device, cause the computing device to at least: receive information indicative of overriding the determination that the first plan is preferred for executing the query. ### Claim 5 (depends on 1) The non-transitory computer-readable storage medium of claim 1, wherein the computer-readable storage medium has stored thereon further instructions that, when executed by the computing device, cause the computing device to at least: transmit a hint to a client, the hint indicative of conforming the first plan for executing a query to a globally optimized execution plan. ### Claim 6 (depends on 1) The non-transitory computer-readable storage medium of claim 1, wherein the comparing comprises adjusting the first execution cost of executing based at least in part on the first performance characteristic of the first computing node. ### Claim 7 A method of executing a query in a distributed database, the method comprising: receiving, from a first query optimizer, a first plan for executing a query on a first partition of the distributed database; receiving, from a second query optimizer, a second plan for executing the query on a second partition of the distributed database; determining a first predicted execution cost of executing the first plan and a second predicted execution cost of executing the second plan, wherein the first predicted execution cost is based at least on one or more first characteristics of computing resources associated with executing queries on the first partition; and causing the second computing device to execute the query using the first plan, based at least in part on comparing a first number of votes cast in favor of using the first plan and a second number of votes cast in favor of using the second plan. ### Claim 8 (depends on 7) The method of claim 7, wherein the first predicted execution cost of executing the first plan corresponds to executing the first plan on both the first partition and the second partition. ### Claim 9 (depends on 7) The method of claim 7, further comprising: receiving, from a third partition of the distributed database, information indicative of a vote for using the second plan. ### Claim 10 (depends on 7) The method of claim 7, further comprising: determining a number of votes for selecting a query plan to allocate to the first partition, the determining based at least in part on an amount of data stored on the first partition. ### Claim 11 (depends on 7) The method of claim 7, wherein the first partition is a first horizontal partition of a table and the second partition is a second horizontal partition of the table. ### Claim 12 A system, comprising: at least one processor; and at least one memory comprising instructions that, in response to being executed by the at least one processor, cause the system at least to: obtain, from a first query optimizer, a first plan for executing a query on a first computing node, the first plan generated on the first computing node; obtain, from a second query optimizer, a second plan for executing the query on a second computing node, the second plan generated on the second computing node; obtain a vote for the first plan, the vote cast for the first plan based on comparing a first predicted execution cost of executing the first plan on the first computing node and the second computing node with a second predicted execution cost of executing the second plan on the first computing node and the second computing node, that the first plan is preferred for executing the query on the second computing node; and cause, based on determining that the first plan is preferred based at least in part on the vote, the second computing node to execute the query using the first plan. ### Claim 13 (depends on 12) The system of claim 12, wherein the first plan is determined based on query statistics of the first computing node. ### Claim 14 (depends on 12) The system of claim 12, wherein the at least one memory comprises further instructions that, in response to being executed by the at least one processor, further cause the system to: adjust a first predicted execution cost of executing the first plan on the first computing node by a first execution cost factor; and adjust a second predicted execution cost of executing the second plan on the second computing node by a second execution cost factor. ### Claim 15 (depends on 14) The system of claim 14, wherein the first plan is determined to be preferred based at least in part on one or more of performance characteristics of the first computing node, data stored on the first computing node, and frequency of executing the query on the first computing node. ### Claim 16 (depends on 12) The system of claim 12, further comprising: adjusting the first predicted execution cost by an execution cost factor and comparing the adjusted execution cost with the second predicted execution cost of the second plan. ### Claim 17 (depends on 16) The system of claim 16, wherein the execution cost factor is based at least in part on relative performance characteristics of the first and second computing nodes. ### Claim 18 (depends on 1) The non-transitory computer-readable storage medium of claim 1, wherein the computer-readable storage medium has stored thereon further instructions that, when executed by the computing device, cause the computing device to at least: obtain the first number of votes from the first query optimizer; and obtain the second number of votes from the second query optimizer. ### Claim 19 (depends on 7) The method of claim 7, wherein the second predicted execution cost is based on at least one or more second characteristics of the second computing node. ### Claim 20 (depends on 12) The system of claim 12, wherein the at least one memory comprises further instructions that, in response to being executed by the at least one processor, further cause the system to: adjust a first predicted execution cost of executing the first plan on the first computing node by a first execution cost factor.