Calculating priority indicators for requests in a queue

• US 8,924,981 B1
• Filed: 11/12/2010
• Issued: 12/30/2014
• Est. Priority Date: 11/12/2010
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradat US Incorporated
• Inventors: Brown, Douglas P., Julien, Thomas P., Burger, Louis M., Richards, Anita
• Primary Examiner(s): Kawsar, Abdullah Al
• Application Number:
  US12/945,064
• Time in Patent Office: 1,509 Days
• Field of Search: None
• US Class Current: 718/103
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

Requests to be executed in the database system are received, where a plurality of the requests are provided in a queue for later execution. Priority indicators are calculated for assignment to corresponding ones of the plurality of requests in the queue, where the priority indicators are calculated based on delay times and predefined priority levels of the requests. The requests in the queue are executed in order according to the calculated priority indicators.

Claims

1. A method for use in a database system, comprising:

receiving, in the database system including at least one processor, requests to be executed in the database system;

providing, in the database system, a plurality of the requests in at least one queue, the plurality of the requests including preemptive requests and timeshare requests;

calculating, in the database system, first priority indicators for assignment to corresponding ones of the preemptive requests in the at least one queue, wherein the first priority indicators are calculated based on delay times, estimated execution times, and predefined priority levels of corresponding ones of the preemptive requests;

calculating, in the database system, second priority indicators for assignment to corresponding ones of the timeshare requests, wherein the second priority indicators are calculated in a different manner from the first priority indicators and are based on delay times and predefined priority levels of corresponding ones of the timeshare requests;

executing the plurality of the requests from the at least one queue in an order according to the calculated first and second priority indicators, wherein executing the timeshare requests comprises;

selecting, based on the calculated second priority indicators, a highest priority one of the timeshare requests for execution; and

selecting another of the timeshare requests to execute with the selected highest priority timeshare request, wherein selecting the another timeshare request is based on a determination that the another timeshare request shares resources by greater than some predefined amount with the selected highest priority timeshare request;

monitoring, in the database system, progress of execution of a particular one of the plurality of the requests;

adjusting, in the database system, resource estimates for the particular request based on the monitored progress, wherein the resource estimates include estimates of usage of at least one resource in the database system; and

based on the adjusted resource estimates, adjusting, in the database system, a priority setting of the particular request to affect the execution of the particular request.

2. The method of claim 1, wherein each of the delay times includes an amount of time waiting in the at least one queue by a corresponding one of the plurality of the requests.

3. The method of claim 1, wherein the first priority indicators are calculated further based on service level goals of respective ones of the preemptive requests.

4. The method of claim 3, wherein the preemptive requests have higher priorities than the timeshare requests.

5. The method of claim 1, wherein the timeshare requests share resources of the database system according to the predefined priority levels assigned to corresponding ones of the timeshare requests.

6. The method of claim 1, further comprising:

providing the preemptive requests in a first queue;

providing the timeshare requests in a second queue.

7. The method of claim 1, wherein executing the timeshare requests and the preemptive requests comprises executing the timeshare requests using resources of the database system not used by the preemptive requests.

8. The method of claim 1, wherein the resource estimates include estimates of usage of one or more of the at least one processor, an input/output resource, a network resource, and a memory resource.

9. The method of claim 1, further comprising:

assigning the received requests to respective workload groups based on matching characteristics of the requests with workload group rules,

wherein the workload groups are associated with respective different ones of the predefined priority levels.

10. A database system comprising:

at least one processor;

at least one delay queue;

a workload management subsystem executable on the at least one processor to;

provide delayed requests in the at least one delay queue, the delayed requests including preemptive requests and timeshare requests;

calculate, based on delay times, execution times, and predefined priority levels of the respective preemptive requests, first priority indicators for corresponding ones of the preemptive requests, wherein the predefined priority levels include service level goals of corresponding ones of the preemptive requests;

calculate, based on delay times and predefined priority levels of the respective timeshare requests, second priority indicators for corresponding ones of the timeshare requests, the second priority indicators calculated in a different manner from the first priority indicators;

schedule, for execution, the delayed requests in the at least one delay queue according to an order defined by the calculated first and second priority indicators, wherein scheduling of the timeshare requests comprises;

selecting, based on the second priority indicators, a highest priority one of the timeshare requests for execution; and

selecting another of the timeshare requests to execute with the selected highest priority timeshare request, wherein selecting the another timeshare request is based on a determination that the another timeshare request shares resources by greater than some predefined amount with the selected highest priority timeshare request

wherein the workload management subsystem includes a regulator to;

monitor progress of execution of a particular one of the delayed requests;

adjust resource estimates for the particular delayed request based on the monitored progress, wherein the resource estimates include estimates of usage of at least one resource in the database system; and

based on the adjusted resource estimates, adjust a priority setting of the particular delayed request to allow the particular delayed request to satisfy the corresponding service level goal.

11. The database system of claim 10, wherein the predefined priority levels for the timeshare requests include values that specify respective amounts of sharing of resources of the database system by corresponding ones of the timeshare requests.

12. The database system of claim 10, wherein the at least one delay queue includes a first delay queue to store the preemptive requests, and a second delay queue to store the timeshare requests.

13. The database system of claim 10, wherein the resource estimates include estimates of usage of one or more of the at least one processor, an input/output resource, a network resource, and a memory resource.

14. An article comprising at least one non-transitory machine-readable storage medium storing instructions that upon execution cause a database system having at least one processor to:

receive requests to be executed in the database system;

provide a plurality of the requests in at least one queue, the plurality of the requests including preemptive requests and timeshare requests;

calculate first priority indicators for assignment to corresponding ones of the preemptive requests in the at least one queue, wherein the first priority indicators are calculated based on delay times, execution times, and predefined priority levels of corresponding ones of the preemptive requests;

calculate second priority indicators for assignment to corresponding ones of the timeshare requests, wherein the second priority indicators are calculated in a different manner from the first priority indicators and are based on delay times and predefined priority levels of corresponding ones of the timeshare requests;

execute the plurality of the requests from the at least one queue in an order according to the calculated first and second priority indicators, wherein executing the timeshare requests comprises;

selecting, based on the calculated second priority indicators, a highest priority one of the timeshare requests for execution; and

selecting another of the timeshare requests to execute with the selected highest priority timeshare request, wherein selecting the another timeshare request is based on a determination that the another timeshare request shares resources by greater than some predefined amount with the selected highest priority timeshare request;

monitor progress of execution of a particular one of the plurality of the requests;

adjust resource estimates for the particular request based on the monitored progress, wherein the resource estimates include estimates of usage of at least one resource in the database system; and

based on the adjusted resource estimates, adjust a priority setting of the particular request to affect the execution of the particular request.

15. The article of claim 14, wherein each of the delay times includes an amount of time waiting in the at least one queue by a corresponding one of the plurality of the requests.

16. The article of claim 15, wherein the predefined priority levels include service level goals or deterministic values specifying corresponding relative sharing of database system resources.

17. The article of claim 14, wherein the resource estimates include estimates of usage of one or more of the at least one processor, an input/output resource, a network resource, and a memory resource.