SYSTEM-WIDE QUERY OPTIMIZATION

• US 20140156632A1
• Filed: 11/30/2012
• Published: 06/05/2014
• 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
• Granted Patent: US 9,229,983 B2
• Time in Patent Office: Days
• US Class Current: 707/713
• 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 configured to operate a first execution engine, the first execution engine comprising a first partition of a partitioned data set;

the first computing node configured to operate a first query optimizer operable to determine a first plan of executing a query on the first execution engine, the query directed to the partitioned data set;

a second computing node configured to operate a second execution engine, the second execution engine comprising a second partition of the partitioned data set;

the second computing node configured to operate a second query optimizer operable to determine a second plan of executing the query on the second execution engine; and

an optimizer configured to determine whether the first plan of executing the query or the second plan of executing the query should be used to execute the query on the first and second execution engine.

2. The system of claim 1, wherein the execution engine is a database.

3. The system of claim 1, wherein the optimizer is configured to determine whether the first or second plan of executing a query should be used by comparing a first cost of executing the first plan of executing the query and a second cost of using the second plan of executing the query.

4. The system of claim 3, wherein the optimizer is configured to determine whether the first or second plan of executing a query should be used by adjusting the first and second costs based on characteristics of the first and second computing nodes.

5. The system of claim 1, wherein the second computing node is configured to receive information indicative of the first plan of executing the query.

6. The system of claim 1, wherein the second computing node is configured to execute the query using the first plan of executing the query based on the determination of the optimizer.

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

8. The system of claim 1, wherein the optimizer is configured to determine whether the first plan of execution or the second plan of execution should be used to execute the query based on one or more of statistics determined from prior executions of the query and collected performance metrics.

9. 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; and

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.

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

11. The method of claim 10, 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.

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

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

14. The method of claim 9, 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.

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

16. The method of claim 9, 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.

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

18. The method of claim 9 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.

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

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

21. 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 the 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 the 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.

22. The non-transitory computer-readable storage medium of claim 21, 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.

23. The non-transitory computer-readable storage medium of claim 21, 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.

24. 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 query optimizer, a first plan for executing a query on a first computing node;

obtain, from a query optimizer, a second plan for executing the query on a second computing node;

compare the predicted costs of executing the first and second plans for executing the query;

based on the comparison, determine which of the first or second plans for executing the query is preferred; and

send information indicative of the preferred first or second plan for executing a query.

25. The non-transitory computer-readable storage medium of claim 24, wherein the information is transmitted to a client application.

26. The non-transitory computer-readable storage medium of claim 24, wherein the information is transmitted to a user, the transmission comprising one or more of a storage device, queue, or messaging system.

27. The non-transitory computer-readable storage medium of claim 24, wherein the information comprises suggestions for modifying the query to cause a query optimizer to produce a plan for executing the query consistent with the preferred first or second plan for executing the query.

28. The non-transitory computer-readable storage medium of claim 24, wherein the information comprises suggestions to route the query to a specific computing device.