# US 2015/0149501 A1 · Scheduling Database Queries Based on Elapsed Time of Queries

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

- Number: US 2015/0149501 A1
- Document ID: US20150149501A1
- Status: Published application
- Kind: A1
- Application number: 14/463,992
- Filed: 2014-08-20
- Published: 2015-05-28
- Earliest claimed: 2013-11-27
- Assignees: ParAccel LLC
- Applicants: ParAccel LLC
- Inventors: Ravindra Prakash; David Benedict Galimberti; Richard Dennis Glick
- Web page: https://patentgrep.com/patent/US20150149501A1

## CPC

- G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals}
- G06F 2209/506: Constraint
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system, for example, an online system or a database system schedules requests received for execution. The system maintains consumer groups and receives a measure of amount of resources allocated for each consumer group. The system maintains a measure of accumulated elapsed time of execution of requests received from each consumer group. If the system determines that resources are available for executing a request, the system selects a request for execution from a consumer group based on the measure of accumulated elapsed time for processing queries for the consumer group and the measure of amount of resources allocated for the consumer group. The system maintains relative cumulative elapsed times of queries across consumer groups in the same ratio as the allocated share for the consumer groups. Accordingly, the system schedules requests such that each consumer group approaches its allocation of resources compared to other groups smoothly over time.

## Claims

### Claim 1

A computer-implemented method for scheduling queries for execution in a database system, the method comprising:
maintaining a set of consumer groups, each consumer group associated with one or more sources of database queries;
receiving a measure of amount of resource allocated for each consumer group;
maintaining a measure of accumulated elapsed time of execution of database queries received from each consumer group;
determining whether resources are available for processing a database query; and
selecting a database query for execution from a consumer group based on the measure of accumulated elapsed time for processing queries for the consumer group and the measure of amount of resources allocated for the consumer group, if resources are available for executing the database query.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein selecting the database query is based on a comparison of the measure of accumulated elapsed time for processing queries for the consumer group and the measure of amount of resources allocated for the consumer group.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, wherein selecting the database query is based on a ratio of the measure of accumulated elapsed time for processing queries for the consumer group and the measure of amount of resources allocated for the consumer group.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1, wherein selecting a database query for execution comprises:
reducing the rate at which queries from a particular consumer group are processed if the measure of accumulated elapsed time for processing queries exceeds the measure of amount of resources allocated for that particular consumer group.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1, wherein selecting a database query for execution comprises:
increasing the rate at which queries from a particular consumer group are processed if the measure of accumulated elapsed time for processing queries is below the measure of amount of resources allocated for that particular consumer group.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1, wherein selecting a database query for execution comprises:
maintaining the current rate at which queries from a particular consumer group are processed if the measure of accumulated elapsed time for processing queries is within a threshold value of the measure of amount of resources allocated for a particular consumer group.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1, further comprising:
determining a measure of difference between accumulated elapsed time for processing queries and the measure of amount of resources allocated for a particular consumer group; and
determining an amount by which the rate at which queries from that particular consumer group are processed is changed.

### Claim 8 (depends on 7)

The computer-implemented method of claim 7, wherein the amount by which the rate at which queries from that particular consumer group are processed is changed further depends on a configurable speedup factor.

### Claim 9 (depends on 8)

The computer-implemented method of claim 8, further comprising:
increasing a value of the speedup factor for achieving faster convergence of the amount of resources used by consumer groups towards a ratio of the amount of resources allocated to each consumer group.

### Claim 10 (depends on 8)

The computer-implemented method of claim 8, further comprising:
decreasing a value of the speedup factor for achieving slower convergence of the amount of resources used by consumer groups towards a ratio of the amount of resources allocated to each consumer group.

### Claim 11 (depends on 1)

The computer-implemented method of claim 1, further comprising:
classifying the database queries based on a consumer group classification to determine the consumer group for each query, the consumer group classification specifying a set of classification rules mapping query attributes to consumer groups.

### Claim 12 (depends on 11)

The computer-implemented method of claim 11, wherein a classification rule maps a database query to a consumer group based on one or more of:
database user name, client user name, application name, client IP address, authentication type, or a type of the database query.

### Claim 13 (depends on 1)

The computer-implemented method of claim 1, further comprising:
classifying the database queries based on a service class specifying runtime attributes of resources used for executing each database query.

### Claim 14 (depends on 1)

The computer-implemented method of claim 1, wherein a source of database queries is one of a user or an application.

### Claim 15 (depends on 1)

The computer-implemented method of claim 1, further comprising:
maintaining indication of which requestor groups are actively using resources of the database system, and marking them as active requestor groups;
wherein each resource group is associated with a measure of share of resources for all active requestor groups; and
wherein selecting a query for execution is further based on the share of resources of the requestor group.

### Claim 16 (depends on 15)

The computer-implemented method of claim 15, further comprising:
marking a requestor group inactive responsive to absence of queries received from the requestor group for more than a threshold time.

### Claim 17 (depends on 15)

The computer-implemented method of claim 15, further comprising:
marking an inactive requestor group as active responsive to receiving a database query for processing from the requestor group.

### Claim 18 (depends on 1)

The computer-implemented method of claim 1, wherein the accumulated elapsed time is measured for queries processed within a moving time window.

### Claim 19

A computer readable non-transitory storage medium storing instructions thereon, the instructions when executed by a processor cause the processor to:
maintain a set of consumer groups, each consumer group associated with one or more sources of database queries;
receive a measure of amount of resource allocated for each consumer group;
maintain a measure of accumulated elapsed time of execution of database queries received from each consumer group;
determine whether resources are available for processing a database query; and
select a database query for execution from a consumer group based on the measure of accumulated elapsed time for processing queries and the measure of amount of resources allocated for the consumer group, if resources are available for executing the database query.

### Claim 20

A computer-implemented system for scheduling queries for execution in a database system, the system comprising:
a computer processor; and
a computer-readable storage medium storing instructions thereon, the instructions when executed by a processor cause the processor to:
maintain a set of consumer groups, each consumer group associated with one or more sources of database queries;
receive a measure of amount of resource allocated for each consumer group;
maintain a measure of accumulated elapsed time of execution of database queries received from each consumer group;
determine whether resources are available for processing a database query; and
select a database query for execution from a consumer group based on the measure of accumulated elapsed time for processing queries and the measure of amount of resources allocated for the consumer group, if resources are available for executing the database query.
