System-wide query optimization

Patent metadata

Field	Value
Publication number	US-11249997-B1
Application number	US-201815933140-A
Country	US
Kind code	B1
Filing date	Mar 22, 2018
Priority date	Nov 30, 2012
Publication date	Feb 15, 2022
Grant date	Feb 15, 2022

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.

First claim

What is claimed:

1. A system, comprising:
a first computing device, comprising a hardware processor and at least one memory, that, in response to receiving information indicative of a query of a data set, determines a first plan for executing the query on a first partition of the data set, based at least in part on a first set of statistics, the first set of statistics based on performance of the first computing device;
a second computing device that, in response to receiving information indicative of the query, determines a second plan for executing the query on a second partition of the data set, based at least in part on a second set of statistics different than the first set of statistics, the second set of statistics based on performance of the second computing device; and
a third computing device that determines, by comparing a first cost of executing the first plan to a second cost of executing the second plan, that the first plan should be used for executing the query on both the first partition and the second partition and causes the second computing device to execute the query using the first plan.

2. The system of claim 1 , wherein the first computing device comprises a first database that accesses the first partition and the second computing device comprises a second database that accesses the second partition.

3. The system of claim 1 , wherein the third computing device determines that the first plan should be used by comparing a first cost of executing the first plan to a second cost of executing the second plan.

4. The system of claim 3 , wherein the comparing comprises calculating an adjusted first cost of executing based at least in part on a characteristic of the first computing device.

5. The system of claim 1 , wherein the second computing device receives information indicative of the first plan and executes the query on the second partition using the first plan.

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

7. The system of claim 1 , wherein the third computing device is configured to determine whether the first plan or the second plan should be used to execute the query based on a metric collected during a prior execution of the query.

8. A non-transitory computer-readable storage medium comprising processor-executable instructions that, in response to execution by at least one processor of a computing device, cause the computing device to at least:
obtain a first plan for executing a query on a first partition of a data set on a first computing node, the first plan based at least in part on a first set of statistics associated with performance of the first computing node;
obtain a second plan for executing the query on a second partition of the data set on a second computing node, the second plan based at least in part on a second set of statistics associated with performance of the second computing node;
determine, based on comparison of a predicted cost of executing the first plan with a predicted cost of executing the second plan, that the first plan is preferred for executing the query; and
send the first plan for executing a query to the second computing node.

9. The non-transitory computer-readable storage medium of claim 8 , wherein the processor-executable instructions that cause the computing device to send the first plan for executing the query to the second computing node further cause the computing device to transmit the first plan to a client application.

10. The non-transitory computer-readable storage medium of claim 8 , wherein the processor-executable instructions that cause the computing device to send the first plan for executing the query to the second computing node further cause the computing device to transmit the first plan and metadata to a user, the metadata comprising one or more of a storage device, queue, or messaging system.

11. The non-transitory computer-readable storage medium of claim 8 , wherein the processor-executable instructions that cause the computing device to send the first plan for executing the query to the second computing node further cause the computing device to send suggestions for modifying the query to cause a query optimizer to produce a third plan for executing the query consistent with the first plan.

12. The non-transitory computer-readable storage medium of claim 8 , wherein the processor-executable instructions that cause the computing device to send the first plan for executing the query to the second computing node further cause the computing device to send suggestions to route the query to a specific computing device.

13. A computer-implemented method comprising:
determining, based at least in part on statistics associated with performance of a first computing device, a first plan for executing a query on a first partition of a data set;
determining, based at least in part on statistics associated with performance of a second computing device, a second plan for executing the query on a second partition of the data set;
determining, based at least in part on a comparison of a first predicted cost of executing the first plan with a second predicted cost of executing the second plan, that the first plan is preferred for executing the query; and
causing the second computing device to execute the query on the second partition using the first plan.

14. The computer-implemented method of claim 13 , wherein the first computing device comprises a first database that accesses the first partition and the second computing device comprises a second database that accesses the second partition.

15. The computer-implemented method of claim 13 , wherein the first predicted cost is adjusted based on the statistics associated with the first computing device and on performance characteristics of the first computing device.

16. The computer-implemented method of claim 13 , wherein the comparison is based on weighing characteristics of the first computing device and of the second computing device.

17. The computer-implemented method of claim 15 , wherein the comparison is executed by a third computing device and in response to the third computing device being idle.

18. The computer-implemented method of claim 13 , wherein determining the first plan is further based on a received hint, the hint indicating a type of scan as preferable for a specified query.

19. The computer-implemented method of claim 13 , wherein determining the first plan is based on a hardware configuration changing at the first computing device.

20. The computer-implemented method of claim 19 , wherein determining the second plan is based on at least one of:
the hardware configuration changing at the first computing device; and
receiving a notification that the first plan indicated a change in cost relative to a previous plan utilized by the first computing device.

Assignees

• Amazon Tech Inc

Inventors

• Yu liang gang
• Smiley John Robert

Classifications

• G06F16/2471

  Distributed queries · CPC title

• G06F16/24554

  Unary operations; Data partitioning operations · CPC title

• G06F16/24542 Primary

  Plan optimisation · CPC title

• G06F16/24545 Primary

  Selectivity estimation or determination · CPC title

• G06F16/24524

  Access plan code generation and invalidation; Reuse of access plans · CPC title