Dynamic priority-based query scheduling

Patent metadata

Field	Value
Publication number	US-9436739-B2
Application number	US-201314106313-A
Country	US
Kind code	B2
Filing date	Dec 13, 2013
Priority date	Dec 13, 2013
Publication date	Sep 6, 2016
Grant date	Sep 6, 2016

Abstract

Techniques for scheduling query execution are provided. In one embodiment, a computer system can receive a query to be executed and can assign a priority to the query. The computer system can further divide the query into a plurality of sub-queries and can assign a sub-priority to each sub-query, where the sub-priority is based on a resource consumption metric of the query. The computer system can then select, from a plurality of sub-query pools, a sub-query pool that includes sub-queries of queries that have the same priority as the query, and can add the plurality of sub-queries to the selected sub-query pool.

First claim

What is claimed is:

1. A method for scheduling query execution, the method comprising:
receiving, by a computer system, a query to be executed;
assigning, by the computer system, a priority to the query, the priority being identical to priorities assigned to one or more previously received queries;
dividing, by the computer system, the query into a plurality of sub-queries;
assigning, by the computer system, a sub-priority to each sub-query in the plurality of sub-queries, wherein the sub-priority for each sub-query of the query is identical to each other, and wherein the sub-priority is based on a resource consumption metric of the query that reflects an amount of computing resources consumed due to execution of the query;
selecting, by the computer system from a plurality of sub-query pools, a sub-query pool that is associated with the priority of the query, the selected sub-query pool including sub-queries of the one or more previously received queries; and
adding, by the computer system, the plurality of sub-queries to the selected sub-query pool.

2. The method of claim 1 further comprising, when a CPU is available for executing a sub-query:
identifying a sub-query pool from the plurality of sub-query pools that includes one or more unexecuted sub-queries and is associated with the highest priority;
updating the sub-priority for each sub-query in the identified sub-query pool;
selecting a sub-query from the identified sub-query pool having the highest sub-priority; and
scheduling the selected sub-query for execution on the CPU.

3. The method of claim 1 wherein the resource consumption metric is a relative metric.

4. The method of claim 1 wherein the priority is based on time sensitivity of the query.

5. The method of claim 2 wherein the computer system is configured to keep track of a total number of in-process queries, and wherein if the total number reaches a preconfigured threshold, the computer system is configured to avoid selection of sub-queries from the identified sub-query pool that do not belong to an in-process query.

6. The method of claim 1 wherein data against which the query is to be executed is organized into a plurality of buckets, each bucket including a subset of the data that corresponds to a range within a data dimension.

7. The method of claim 6 wherein each sub-query in the plurality of sub-queries is an instance of the query that is constrained to data within a single bucket.

8. A non-transitory computer readable storage medium having stored thereon software executable by a computer system, the software embodying a method that comprises:
receiving a query to be executed;
assigning a priority to the query, the priority being identical to priorities assigned to one or more previously received queries;
dividing the query into a plurality of sub-queries;
assigning a sub-priority to each sub-query in the plurality of sub-queries, wherein the sub-priority for each sub-query of the query is identical to each other, and wherein the sub-priority is based on a resource consumption metric of the query that reflects an amount of computing resources consumed due to execution of the query;
selecting, from a plurality of sub-query pools, a sub-query pool that is associated with the priority of the query, the selected sub-query pool including sub-queries of the one or more previously received queries; and
adding the plurality of sub-queries to the selected sub-query pool.

9. The non-transitory computer readable storage medium of claim 8 wherein the method further comprises, when a CPU is available for executing a sub-query:
identifying a sub-query pool from the plurality of sub-query pools that includes one or more unexecuted sub-queries and is associated with the highest priority;
updating the sub-priority for each sub-query in the identified sub-query pool;
selecting a sub-query from the identified sub-query pool having the highest sub-priority; and
scheduling the selected sub-query for execution on the CPU.

10. The non-transitory computer readable storage medium of claim 8 wherein the resource consumption metric is a relative metric.

11. The non-transitory computer readable storage medium of claim 8 wherein the priority is based on time sensitivity of the query.

12. The non-transitory computer readable storage medium of claim 9 wherein the software is configured to keep track of a total number of in-process queries, and wherein if the total number reaches a preconfigured threshold, the software is configured to avoid selection of sub-queries from the identified sub-query pool that do not belong to an in-process query.

13. The non-transitory computer readable storage medium of claim 8 wherein data against which the query is to be executed is organized into a plurality of buckets, each bucket including a subset of the data that corresponds to a range within a data dimension.

14. The non-transitory computer readable storage medium of claim 13 wherein each sub-query in the plurality of sub-queries is an instance of the query that is constrained to data within a single bucket.

15. A computer system comprising:
a processor; and
a non-transitory computer readable medium having stored thereon program code that causes the processor to, upon being executed:
receive a query to be executed;
assign a priority to the query, the priority being identical to priorities assigned to one or more previously received queries;
divide the query into a plurality of sub-queries;
assign a sub-priority to each sub-query in the plurality of sub-queries, wherein the sub-priority for each sub-query of the query is identical to each other, and wherein the sub-priority is based on a resource consumption metric of the query that reflects an amount of computing resources consumed due to execution of the query;
select, from a plurality of sub-query pools, a sub-query pool that is associated with the priority of the query, the selected sub-query pool including sub-queries of the one or more previously received queries; and
add the plurality of sub-queries to the selected sub-query pool.

16. The computer system of claim 15 wherein the program code further causes the processor to, when a CPU is available for executing a sub-query:
identify a sub-query pool from the plurality of sub-query pools that includes one or more unexecuted sub-queries and is associated with the highest priority;
update the sub-priority for each sub-query in the identified sub-query pool;
select a sub-query from the identified sub-query pool having the highest sub-priority; and
schedule the selected sub-query for execution on the CPU.

17. The computer system of claim 15 wherein the resource consumption metric is a relative metric.

18. The computer system of claim 15 wherein the priority is based on time sensitivity of the query.

19. The computer system of claim 16 wherein the processor is configured to keep track of a total number of in-process queries, and wherein if the total number reaches a preconfigured threshold, the processor is configured to avoid selection of sub-queries from the identified sub-query pool that do not belong to an in-process query.

20. The computer system of claim 15 wherein data against which the query is to be executed is organized into a plurality of buckets, each bucket including a subset of the data that corresponds to a range within a data dimension.

21. The computer system of claim 20 wherein each sub-query in the plurality of sub-queries is an instance of

Assignees

• Vmware Inc

Inventors

• Li Zhenmin
• Huang Chengdu
• Patel Jay A

Classifications

• G06F16/2471 Primary

  Distributed queries · CPC title

• G06F16/24557

  Efficient disk access during query execution · CPC title

• G06F17/30545 Primary

  Physics · mapped topic

• G06F17/30492

  Physics · mapped topic