Fair scheduling for mixed-query loads

• US 9,092,482 B2
• Filed: 03/14/2013
• Issued: 07/28/2015
• 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:
  US13/826,228
• Publication Number:
  US 20140280034A1
• Time in Patent Office: 866 Days
• Field of Search: 707/718
• US Class Current: 1/1
• 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 is disclosed. The techniques involve obtaining computer-executable query jobs and cost estimates to execute the query jobs. For example, the cost estimate can be a number of results the query is expected to return. Based on the cost estimates, the fair scheduling system causes the database management system to execute the query jobs as separately executable sub-query tasks in a round-robin fashion which can decrease latency of low cost queries concurrently executing with high cost queries.

Claims

1. A computer-implemented method, comprising:

obtaining a computer-executable query job and a cost estimate to execute the query job;

based on the cost estimate exceeding a threshold cost, determining to divide the query job into a plurality of computer-executable sub-query tasks;

causing each of the plurality of sub-query tasks to be separately executed by a database management system;

wherein causing each of the plurality of sub-query tasks to be separately executed by the database management system includes;

causing the database management system to initiate execution of a first sub-query task of the plurality sub-query tasks, the first sub-query task including rate limiter that limits the number of results returned by the first sub-query task;

after the database management system has finished executing the first sub-query task, determining a value of a last result returned by the database management system for the first sub-query task;

causing the database management system to initiate execution of a next sub-query task of the plurality of sub-query tasks, the next sub-query task including the determined value of the last result returned by the database management system for the first sub-query task;

wherein the method is performed using one or more processors.

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

enqueing a job item representing the query job onto the end of a job execution queue having a front and an end;

dequeing the job item after the job item has reached the front of the job execution queue;

after dequeing the job item, causing the database management system to initiate execution of a first sub-query task of the plurality sub-query tasks;

after dequeing the job item, determining whether there are more sub-query tasks of the plurality of sub-query tasks to execute;

in response to determining that there are more sub-query tasks of the plurality of sub-query tasks to execute, re-enqueing the job item onto the end of the job execution queue.

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

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

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

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

7. The method of claim 1, further comprising:

in response to receiving a request to cancel the query job, removing a job item representing the query job from a job execution queue.

8. The method of claim 1, further comprising:

at a first time, removing 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 node of the database management system;

at a second time that is after the first time;

generating a second query job based on the first query job,

enqueing a job item representing the second query job onto the end of the job execution queue, and

causing the database management system to initiate execution of a first sub-query task of the second query job on a second node of the database management system that is not the first node.

9. A fair scheduling system, comprising:

one or more computing devices;

one or more non-transitory computer-readable storing instructions which, when executed by the one or more computing devices, cause the one or more computing devices to perform a method comprising;

obtaining a computer-executable query job and a cost estimate to execute the query job;

based on the cost estimate exceeding a threshold cost, determining to divide the query job into a plurality of computer-executable sub-query tasks;

causing each of the plurality of sub-query tasks to be separately executed by a database management system;

wherein causing each of the plurality of computer-executable sub-query tasks to be separately executed by the database management system includes;

causing the database management system to initiate execution of a first sub-query task of the plurality sub-query tasks, the first sub-query task including rate limiter that limits the number of results returned by the first sub-query task;

after the database management system has finished executing the first sub-query task, determining a value of a last result returned by the database management system for the first sub-query task;

causing the database management system to initiate execution of a next sub-query task of the plurality of sub-query tasks, the next sub-query task including the determined value of the last result returned by the database management system for the first sub-query task.

10. The system of claim 9, wherein causing each of the plurality of sub-query tasks to be separately executed by the database management system includes:

enqueing a job item representing the query job onto the end of a job execution queue having a front and an end;

dequeing the job item after the job item has reached the front of the job execution queue;

after dequeing the job item, causing the database management system to initiate execution of a first sub-query task of the plurality sub-query tasks;

after dequeing the job item, determining whether there are more sub-query tasks of the plurality of sub-query tasks to execute;

in response to determining that there are more sub-query tasks of the plurality of sub-query tasks to execute, re-enqueing the job item onto the end of the job execution queue.

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

12. The system of claim 9, wherein the query job is obtained in a job request.

13. The system of claim 9, wherein the cost estimate is obtained in a job request.

14. The system of claim 9, wherein the query job comprises one or more query parameters.

15. The system of claim 9, the method further comprising:

in response to receiving a request to cancel the query job, removing a job item representing the query job from a job execution queue.

16. The system of claim 9, the method further comprising:

at a first time, removing 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 node of the database management system;

at a second time that is after the first time;

generating a second query job based on the first query job,

enqueing a job item representing the second query job onto the end of the job execution queue, and

causing the database management system to initiate execution of a first sub-query task of the second query job on a second node of the database management system that is not the first node.