System-wide query optimization

• US 9,229,983 B2
• Filed: 11/30/2012
• Issued: 01/05/2016
• Est. Priority Date: 11/30/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Yu, Liang Gang, Smiley, John Robert
• Primary Examiner(s): Lee, Wilson
• Application Number:
  US13/691,213
• Publication Number:
  US 20140156632A1
• Time in Patent Office: 1,131 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24524 Access plan code generation and invalidation; Reuse of access plans
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/2471 Distributed queries

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

1. A system comprising:

a first computing node operable to execute a database query on a first partition of a partitioned data set;

a second computing node operable to execute the database query on a second partition of the partitioned data set; and

one or more memories having stored thereon computer-readable instructions that, upon execution by a processor of the one or more computing nodes, cause the system at least to;

receive information indicative of a first estimated cost of executing a first set of instructions for executing the database query on the first computing node, the first set of instructions performing the database query in a manner determined by the first computing node;

receive information indicative of a second estimated cost of executing a second set of instructions for executing the database query on the second computing node, the second set of instructions performing the database query in a manner determined by the second computing node;

determine to use one of the first or second set of instructions for performing the database query on at least one of the first and second computing nodes by comparing the first and second estimated costs; and

execute the database query on the second computing node using the first set of instructions for performing the database query based at least in part on the comparing the first and second estimated costs.

2. The system of claim 1, further comprising one or more memories having stored thereon computer-readable instructions that, upon execution by the processor of the one or more computing nodes, cause the system at least to:

determine whether to use the first or second set of instructions based at least in part on adjusting the first estimated cost based on characteristics of the first computing node.

3. The system of claim 1, wherein the second computing node is configured to receive information indicative of the first set of instructions for performing the database query.

4. The system of claim 1, wherein the database query is a parameterized query.

5. The system of claim 1, further comprising one or more memories having stored thereon computer-readable instructions that, upon execution by the processor of the one or more computing nodes, cause the system at least to:

determine whether the first set of instructions or the second set of instructions should be used to execute the query based at least in part on one or more of statistics determined from prior executions of the query.

6. The system of claim 1, further comprising one or more memories having stored thereon computer-readable instructions that, upon execution by the processor of the one or more computing nodes, cause the system at least to:

determine whether the first set of instructions should be used to execute the query based at least in part on comparing a first statistic collected during prior execution of the database query on the first computing node to a second statistic collected during prior execution of the database query on a second computing node.

7. A non-transitory computer-readable storage medium having stored thereon computer instructions that, upon execution by a computing device, cause the computing device to at least:

receive an estimate of a first cost of performing a query, the first cost comprising a determination of an estimated cost of performing a first set of instructions in a first computing node;

estimate a second cost of performing the query, the second estimated cost comprising a determination of the estimated cost of performing a second set of instructions on a second computing node;

compare the first cost with the second cost after adjusting for relative characteristics of the first and second computing nodes and determine that the first set of instructions is preferable for performing the query on the first and second computing nodes; and

execute the query on the second computing node using the first set of instructions.

8. The non-transitory computer-readable storage medium of claim 7, having stored thereon instructions that, upon execution by a computing device, cause the computing device to at least:

associate the first set of instructions with the query, so that the query, when executed on the second computing node, is performed using the first set of instructions.

9. The non-transitory computer-readable storage medium of claim 7, having stored thereon instructions that, when executed by a computing device, cause the device to at least:

associate the first set of instructions with the query, so that the query, when executed on a third computing node, is performed using the first set of instructions.

10. A method for executing a database query comprising:

receiving information indicative of a first estimated cost of executing a first set of instructions for executing the database query on a first computing node, the first set of instructions performing the database query in a manner determined by the first computing node;

receiving information indicative of a second estimated cost of executing a second set of instructions for executing the database query on a second computing node, the second set of instructions performing the database query in a manner determined by the second computing node;

determining whether to use the first or second set of instructions for performing the database query on at least one of the first and second computing node by comparing the first and second estimated costs; and

executing the database query on the second computing node using the first set of instructions, based at least in part on the determining.

11. The method of claim 10, wherein comparing the first and second estimated costs further comprises adjusting for performance characteristics of the first and second computing nodes.

12. The method of claim 11, wherein the performance characteristics include one or more of processor speed, storage device speed, available memory, working set, CPU utilization, average disk queue depth, cache coherence measurements, average number of user sessions, and event log entries.

13. The method of claim 10, wherein comparing the first and second estimated costs comprises adjusting for characteristics of data managed by the first and second computing nodes.

14. The method of claim 13, wherein the characteristics of data comprises one or more of a number of rows of data and a frequency of data repetition.

15. The method of claim 10, wherein comparing the first and second estimated costs comprises adjusting an estimated cost of at least one instruction in the first or second set of instructions based on characteristics of the first or second computing nodes relative to the estimated cost of the at least one instruction.

16. The method of claim 10, wherein the first computing node transmits to the second computing node information indicative of an estimated cost of executing the first set of instructions.

17. The method of claim 10, wherein determining whether to use the first or second set of instructions is performed by at least one of the first or the second computing nodes.

18. The method of claim 10, wherein the database query is directed to a partitioned table and a query optimizer determines the first set of instructions.

19. The method of claim 10, wherein the cost is a function of at least one of computing power, CPU speed, memory capacity, cache capacity, storage device read performance, storage device write performance, storage device write performance, storage device seek time, row count, and duplication of data.

20. The method of claim 10, wherein determining whether to use the first or second set of instructions is performed subsequent to a triggering event.

21. The method of claim 20, wherein the triggering event comprises one or more of a periodic event, a change of hardware components, a change to configuration of hardware, and a change in data stored on a database.