Fair scheduling for mixed-query loads

Patent metadata

Field	Value
Publication number	US-2017293653-A1
Application number	US-201715634422-A
Country	US
Kind code	A1
Filing date	Jun 27, 2017
Priority date	Mar 14, 2013
Publication date	Oct 12, 2017
Grant date	—

Abstract

A fair scheduling system with methodology for scheduling queries for execution by a database management system in a fair manner. The system obtains query jobs for execution by the database management system and cost estimates to execute the query jobs. Based on the cost estimates, the system causes the database management system to execute the query jobs as separate sub-query tasks in a round-robin fashion. By doing so, the execution latency of low cost query jobs that return few results is reduced when the query jobs are concurrently executed with high cost query jobs that return many results.

First claim

1 . A computing system, comprising:
one or more processors; storage media; one or more programs stored in the storage media and configured for execution by the one or more processors, the one or more programs comprising instructions configured for:
obtaining a query for execution by a database management system and a cost estimate for the database management system to execute the query;
enqueuing an item for the query onto a queue, the queue having a head, a tail, and a maximum number of allowed items;
based, at least in part, on the cost estimate, dividing the query into a plurality of sub-queries;
based, at least in part, on an item for the query reaching the head of the queue, causing a first sub-query of the plurality of sub-queries to be executed against the database management system; and
based, at least in part, on determining there are more sub-queries of the plurality of sub-queries to be executed against the database management system:
re-enqueuing an item for the query onto the tail of the queue if a current number of items in the queue is less than the maximum number of allowed items, or
waiting until a current number of items in the queue is less than the maximum number of allowed items before re-enqueuing an item for the query onto the tail of the queue if a current number of items in the queue is not less than the maximum number of allowed items.

2 . The computing system of claim 1 , wherein the cost estimate is a number of query results the query is expected to return.

3 . The computing system of claim 1 , the one or more programs comprising instructions configured for:
based, at least in part, on the determining there are more sub-queries of the plurality of sub-queries to be executed against the database management system, re-enqueuing an item for the query onto the tail of the queue.

4 . The computing system of claim 1 , the one or more programs comprising instructions configured for:
based, at least in part, on the determining there are more sub-queries of the plurality of sub-queries to be executed against the database management system, waiting until a current number of items in the queue is less than the maximum number of allowed items before re-enqueuing an item for the query onto the tail of the queue.

5 . The computing system of claim 1 , wherein the first sub-query is configured with a result limiter that limits a number of results the first sub-query returns.

6 . The computing system of claim 1 , the one or more programs further comprising instructions configured for:
de-queueing an item for the query from the head of the queue; and wherein the causing the first sub-query to be executed against the database management system is based, at least in part, on the de-queueing.

7 . The computing system of claim 1 , the one or more programs further comprising instructions configured for:
based, at least in part, on determining there are no more sub-queries of the plurality of sub-queries to be executed against the database management system, not re-enqueuing an item for the query onto the tail of the queue.

8 . A method performed by a computing system comprising one or more processors, storage media, and one or more programs stored in the storage media and executed by the one or more processors to perform the method, the method comprising:
obtaining a query for execution by a database management system and a cost estimate for the database management system to execute the query; enqueuing an item for the query onto a queue, the queue having a head, a tail, and a maximum number of allowed items; based, at least in part, on the cost estimate, dividing the query into a plurality of sub-queries; based, at least in part, on an item for the query reaching the head of the queue, causing a first sub-query of the plurality of sub-queries to be executed against the database management system; and based, at least in part, on determining there are more sub-queries of the plurality of sub-queries to be executed against the database management system:
re-enqueuing an item for the query onto the tail of the queue if a current number of items in the queue is less than the maximum number of allowed items, or
waiting until a current number of items in the queue is less than the maximum number of allowed items before re-enqueuing an item for the query onto the tail of the queue if a current number of items in the queue is not less than the maximum number of allowed items.

9 . The method of claim 8 , wherein the cost estimate is a number of query results the query is expected to return.

10 . The method of claim 8 , further comprising:
based, at least in part, on the determining there are more sub-queries of the plurality of sub-queries to be executed against the database management system, re-enqueuing an item for the query onto the tail of the queue.

11 . The method of claim 8 , further comprising:
based, at least in part, on the determining there are more sub-queries of the plurality of sub-queries to be executed against the database management system, waiting until a current number of items in the queue is less than the maximum number of allowed items before re-enqueuing an item for the query onto the tail of the queue.

12 . The method of claim 8 , wherein the first sub-query is configured with a result limiter that limits a number of results the first sub-query returns.

13 . The method of claim 8 , further comprising:
de-queueing an item for the query from the head of the queue; and wherein the causing the first sub-query to be executed against the database management system is based, at least in part, on the de-queueing.

14 . The method of claim 8 , further comprising:
based, at least in part, on determining there are no more sub-queries of the plurality of sub-queries to be executed against the database management system, not re-enqueuing an item for the query onto the tail of the queue.

15 . One or more non-transitory computer-readable media storing one or more one or more programs for execution by a computing system comprising one or more processors and storage media, the one or more programs comprising instructions configured for:
obtaining a query for execution by a database management system and a cost estimate for the database management system to execute the query; enqueuing an item for the query onto a queue, the queue having a head, a tail, and a maximum number of allowed items; based, at least in part, on the cost estimate, dividing the query into a plurality of sub-queries; based, at least in part, on an item for the query reaching the head of the queue, causing a first sub-query of the plurality of sub-queries to be executed against the database management system; and based, at least in part, on determining there are more sub-queries of the plurality of sub-queries to be executed against the database management system:
re-enqueuing an item for the query onto the tail of the queue if a current number of items in the queue is less than the maximum number of allowed items, or
waiting until a current number of items in the queue is less than the maximum number of allowed items before re-enqueuing an item for the query onto the tail of the queue if a current number of items in the queue is not less than the maximum number of allowed items.

16 . The one or more non-transitory computer-readable media of claim 15 , wherein the cost estimate is a number of query results the query is expected to return.

17 . The one or more non-transitory computer-readable media of claim 15 , the one or more programs

Assignees

• Palantir Technologies Inc

Inventors

• Harris Michael
• Carrino John
• Wong Eric

Classifications

• G06F17/30451 Primary

  Physics · mapped topic

• G06F17/30463

  Physics · mapped topic

• G06F17/30864

  Physics · mapped topic

• G06F17/30477

  Physics · mapped topic

• G06F16/2453 Primary

  Query optimisation · CPC title