# US 9,436,739 B2 · Dynamic priority-based query scheduling

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,436,739 B2
- Document ID: US9436739B2
- Status: Granted
- Kind: B2
- Application number: 14/106,313
- Filed: 2013-12-13
- Published: 2015-06-18
- Granted: 2016-09-06
- Earliest claimed: 2013-12-13
- Assignees: VMware, Inc.
- Applicants: VMware, Inc.
- Inventors: Zhenmin Li; Chengdu Huang; Jay A. Patel
- Web page: https://patentgrep.com/patent/US9436739B2

## CPC

- G06F 16/2471: {Distributed queries}
- G06F 16/24557: {Efficient disk access during query execution}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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

### Claim 4 (depends on 1)

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

### Claim 5 (depends on 2)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 6)

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.

### Claim 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.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 8)

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

### Claim 11 (depends on 8)

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

### Claim 12 (depends on 9)

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.

### Claim 13 (depends on 8)

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.

### Claim 14 (depends on 13)

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.

### Claim 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.

### Claim 16 (depends on 15)

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.

### Claim 17 (depends on 15)

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

### Claim 18 (depends on 15)

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

### Claim 19 (depends on 16)

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.

### Claim 20 (depends on 15)

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.

### Claim 21 (depends on 20)

The computer system of claim 20 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.

### Claim 22 (depends on 3)

The method of claim 3 wherein the resource consumption metric shrinks in size as the query gets older.

### Claim 23 (depends on 10)

The non-transitory computer readable storage medium of claim 10 wherein the resource consumption metric shrinks in size as the query gets older.

### Claim 24 (depends on 17)

The computer system of claim 17 wherein the resource consumption metric shrinks in size as the query gets older.