Fair scheduling for mixed-query loads

• US 10,817,513 B2
• Filed: 06/27/2017
• Issued: 10/27/2020
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Harris, Michael, Carrino, John, Wong, Eric
• Primary Examiner(s): Hu, Jensen
• Application Number:
  US15/634,422
• Publication Number:
  US 20170293653A1
• Time in Patent Office: 1,218 Days
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24535 of sub-queries or views
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

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.

Claims

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 by 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 by 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 by 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 by 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 by 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 by 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 by 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 by 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 by 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 by 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 by 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 by 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 by 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 by 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 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 by the database management system, re-enqueuing an item for the query onto the tail of the queue.

18. The one or more non-transitory computer-readable media of claim 15, 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 by 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.

19. The one or more non-transitory computer-readable media of claim 15, wherein the first sub-query is configured with a result limiter that limits a number of results the first sub -query returns.

20. The one or more non-transitory computer-readable media of claim 15, 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 by the database management system is based, at least in part, on the de-queueing.

21. The one or more non-transitory computer-readable media of claim 15, 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 by the database management system, not re-enqueuing an item for the query onto the tail of the queue.