Fair scheduling for mixed-query loads

• US 9,715,526 B2
• Filed: 05/29/2015
• Issued: 07/25/2017
• 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:
  US14/726,211
• Publication Number:
  US 20150261817A1
• Time in Patent Office: 788 Days
• Field of Search: 707718
• 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 fairly scheduling queries for execution by a database management system. The system obtains query jobs for execution by the database management system and cost estimates to execute the query jobs. The cost estimate can be a number of results the query is expected to return. Based on the cost estimates, the system causes the database management system to execute the query jobs as separately 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 a large number of results.

Claims

1. A computer-implemented method performed via one or more processors, the method comprising:

obtaining, via at least one of the one or more processors, a query job for execution by a database management system and a cost estimate for the database management system to execute the query job;

based on the cost estimate, dividing, via at least one of the one or more processors, the query job into a plurality of sub-query tasks for execution by the database management system;

causing, via at least one of the one or more processors, the plurality of sub-query tasks to be executed by the database management system;

after the database management system has finished executing a first sub-query task of the plurality of sub-query tasks, determining, via at least one of the one or more processors, a value of a last result returned by the database management system for the first sub-query task; and

causing, via at least one of the one or more processors, the database management system to initiate execution of a next sub-query task of the plurality of sub-query tasks;

wherein the next sub-query task includes the determined value of the last result returned by the database management system for the first sub-query task;

wherein the first sub-query task includes a rate limiter that limits the number of results returned by the first sub-query task when executed by the database management system.

2. The method of claim 1, wherein the cost estimate is a number of results the database management system is expected to return as an answer to the query job.

3. The method of claim 2, wherein each sub-query task of the plurality of sub-query tasks is configured to cause the database management system to return less than the number of results of the cost estimate.

4. The method of claim 1, wherein causing each of the plurality of sub-query tasks to be executed by the database management system comprises:

enqueing, via at least one of the one or more processors, a job item representing the query job onto the end of a job execution queue having a front and an end;

dequeing, via at least one of the one or more processors, the job item after the job item has reached the front of the job execution queue;

after the job item is de-queued, causing, via at least one of the one or more processors, the database management system to execute a sub-query task of the plurality sub-query tasks;

after the sub-query task is completely executed by the database management system, determining, via at least one of the one or more processors, whether there are more sub-query tasks of the plurality of sub-query tasks to be executed by the database management system;

in response to determining, via at least one of the one or more processors, that there are more sub-query tasks of the plurality of sub-query tasks to be executed by the database management system, re-enqueing, via at least one of the one or more processors, the job item onto the end of the job execution queue; and

wherein the job item re-enqueued onto the end of the job execution queue indicates that the sub-query task is completely executed.

5. The method of claim 1, wherein the query job is obtained in a job request.

6. The method of claim 1, wherein the cost estimate is obtained in a job request.

7. The method of claim 1, wherein the query job comprises one or more query parameters.

8. The method of claim 1, further comprising:

in response to receiving, via at least one of the one or more processors, a request to cancel the query job, removing, via at least one of the one or more processors, a job item representing the query job from a job execution queue.

9. The method of claim 1, further comprising:

at a first time, removing, via at least one of the one or more processors, a job item representing a first query job from a job execution queue having a front and an end;

wherein, at the first time, a sub-query task of the first query job is executing on a first computing node of the database management system; and

at a second time that is after the first time;

generating, via at least one of the one or more processors, a second query job based on the first query job,

enqueing, via at least one of the one or more processors, a job item representing the second query job onto the end of the job execution queue, and

causing, via at least one of the one or more processors, the database management system to initiate execution of a first sub-query task of the second query job on a second computing node of the database management system that is not the first computing node.

10. The method of claim 1, further comprising:

determining, via at least one of the one or more processors, if a job execution queue is full with jobs items;

wherein each job item, of the jobs items in the jobs execution queue, represents a query job for which execution of at least a portion of the query job by the database management system is initiated but not complete;

enqueing, via at least one of the one or more processors, a job item representing a new query job onto the end of the job execution queue only if the job execution queue is not full; and

if the job execution queue is full, waiting, via at least one of the one or more processors, until the job execution queue is no longer full before enqueing the job item representing the new query job onto the end of the job execution queue.

11. One or more non-transitory computer-readable media storing one or more computer programs which, when executed via one or more processors, causes performance of the steps of:

obtaining, via at least one of the one or more processors, a query job for execution by a database management system and a cost estimate for the database management system to execute the query job;

based on the cost estimate, dividing, via at least one of the one or more processors, the query job into a plurality of sub-query tasks for execution by the database management system;

causing, via at least one of the one or more processors, the plurality of sub-query tasks to be executed by the database management system;

after the database management system has finished executing a first sub-query task of the plurality of sub-query tasks, determining, via at least one of the one or more processors, a value of a last result returned by the database management system for the first sub-query task; and

causing, via at least one of the one or more processors, the database management system to initiate execution of a next sub-query task of the plurality of sub-query tasks;

wherein the next sub-query task includes the determined value of the last result returned by the database management system for the first sub-query task;

wherein the first sub-query task includes a rate limiter that limits the number of results returned by the first sub-query task when executed by the database management system.

12. The one or more non-transitory computer-readable media of claim 11, wherein the cost estimate is a number of results the database management system is expected to return as an answer to the query job.

13. The one or more non-transitory computer-readable media of claim 12, wherein each sub-query task of the plurality of sub-query tasks is configured to cause the database management system to return less than the number of results of the cost estimate.

14. The one or more non-transitory computer-readable media of claim 11, wherein the step of causing each of the plurality of sub-query tasks to be executed by the database management system comprises the steps of:

enqueing, via at least one of the one or more processors, a job item representing the query job onto the end of a job execution queue having a front and an end;

dequeing, via at least one of the one or more processors, the job item after the job item has reached the front of the job execution queue;

after the job item is de-queued, causing, via at least one of the one or more processors, the database management system to execute a sub-query task of the plurality sub-query tasks;

after the sub-query task is completely executed by the database management system, determining, via at least one of the one or more processors, whether there are more sub-query tasks of the plurality of sub-query tasks to be executed by the database management system;

in response to determining, via at least one of the one or more processors, that there are more sub-query tasks of the plurality of sub-query tasks to be executed by the database management system, re-enqueing, via at least one of the one or more processors, the job item onto the end of the job execution queue; and

wherein the job item re-enqueued onto the end of the job execution queue indicates that the sub-query task is completely executed.

15. The one or more non-transitory computer-readable media of claim 11, wherein the query job comprises one or more query parameters.

16. The one or more non-transitory computer-readable media of claim 11, wherein the one or more computer programs, when executed via the one or more processors, further causes performance of the steps of:

in response to receiving, via at least one of the one or more processors, a request to cancel the query job, removing, via at least one of the one or more processors, a job item representing the query job from a job execution queue.

17. The one or more non-transitory computer-readable media of claim 11, wherein the one or more computer programs, when executed via the one or more processors, further causes performance of the steps of:

at a first time, removing, via at least one of the one or more processors, a job item representing a first query job from a job execution queue having a front and an end;

wherein, at the first time, a sub-query task of the first query job is executing on a first computing node of the database management system; and

at a second time that is after the first time;

generating, via at least one of the one or more processors, a second query job based on the first query job,

enqueing, via at least one of the one or more processors, a job item representing the second query job onto the end of the job execution queue, and

causing, via at least one of the one or more processors, the database management system to initiate execution of a first sub-query task of the second query job on a second computing node of the database management system that is not the first computing node.

18. The one or more non-transitory computer-readable media of claim 11, wherein the one or more computer programs, when executed via the one or more processors, further causes performance of the steps of:

determining, via at least one of the one or more processors, if a job execution queue is full with jobs items;

wherein each job item, of the jobs items in the jobs execution queue, represents a query job for which execution of at least a portion of the query job by the database management system is initiated but not complete;

enqueing, via at least one of the one or more processors, a job item representing a new query job onto the end of the job execution queue only if the job execution queue is not full; and

if the job execution queue is full, waiting, via at least one of the one or more processors, until the job execution queue is no longer full before enqueing the job item representing the new query job onto the end of the job execution queue.