# US 2025/0156414 A1 · Short query prioritization for data processing service

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2025/0156414 A1
- Document ID: US20250156414A1
- Status: Published application
- Kind: A1
- Application number: 18/991,083
- Filed: 2024-12-20
- Published: 2025-05-15
- Earliest claimed: 2023-04-27
- Assignees: Databricks, Inc.
- Applicants: Databricks, Inc.
- Inventors: Venkata Sai Akhil Gudesa; Herman Rudolf Petrus Catharina van Hövell tot Westerflier; Supun Chathuranga Nakandala
- Web page: https://patentgrep.com/patent/US20250156414A1

## CPC

- G06F 16/2453: Query optimisation
- G06F 9/4887: {involving deadlines, e.g. rate based, periodic}
- G06F 11/3419: {by assessing time}
- G06F 16/285: {Clustering or classification}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A cluster computing system maintains a first set of queues for short queries and a set second set for longer queries. The first set is allocated a majority of the cluster's processing resources and processes queries on a first in first out basis. The second set is allocated a minority of the cluster's processing resources which are shared among queries in the second set. Accordingly, the system assigns each query to the first set of queues for a fixed amount of resource time. While a query is processing, the system monitors the query's resource time and reassigns the query to the second set of queues if the query has not completed within the allotted amount of resource time. Thus, short queries receive the necessary resources to complete quickly without getting stuck behind longer queries while ensuring that longer queries continue to make progress.

## Claims

### Claim 1

(canceled)

### Claim 2

A method, comprising:
accessing a cluster including a driver node and one or more executor nodes each including one or more task engines, the cluster configured to schedule queries according to at least a first queue, a second queue, and a third queue, the first queue storing information on queries with a higher priority than queries assigned to the second queue, and the second queue storing information on queries with a higher priority than queries assigned to the third queue;
receiving a query and assigning the query to the first queue, the query divided into a set of tasks;
allocating a number of task engines in a first set of executor nodes to process the set of tasks of the query;
monitoring a resource time for the query while the query is being executed at the first set of executor nodes;
responsive to determining that the resource time for the query is equal to or above a threshold resource time, assigning the query to the second queue;
responsive to assigning the query to the second queue, executing the tasks of the query on a second set of executor nodes;
responsive to determining that a second resource time for the query is equal to or above a second threshold resource time, assigning the query to the third queue; and
responsive to assigning the query to the third queue, executing the tasks of the query on a third set of executor nodes.

### Claim 3 (depends on 2)

The method of claim 2, wherein a number of executor nodes in the third set of executor nodes is smaller than a number of executor nodes in the first set of executor nodes.

### Claim 4 (depends on 2)

The method of claim 2, further comprising:
receiving another query for execution;
responsive to assigning the query to the second queue, assigning task engines to the another query assigned to the first queue; and
reallocating at least a portion of executor nodes from the first set of executor nodes to process the other query assigned to the first queue.

### Claim 5 (depends on 2)

The method of claim 2, wherein monitoring the resource time comprises:
determining, for each task of the query, an execution time to execute the task on a respective task engine; and
summing the execution time of the tasks of the query to determine the resource time.

### Claim 6 (depends on 2)

The method of claim 2, further comprising:
monitoring a number of tasks for queries assigned to the first queue;
determining a number of task engines to be reserved for queries assigned to the first queue based on the monitored number of tasks; and
reserving the number of task engines on the cluster for queries assigned to the first queue for a next time step.

### Claim 7 (depends on 6)

The method of claim 6, wherein the number of tasks for queries assigned to the first queue includes pending and running tasks, and wherein reserving the number of task engines on the cluster for queries assigned to the first queue for the next time step includes:
applying an exponential moving average (EMA) function on a sum of the pending and the running tasks; and
reserving Y task engines for the queries in the first queue, where Y=f(aggressiveness factor, X), where X is the sum of the pending and the running tasks and the aggressiveness factor is a constant.

### Claim 8 (depends on 2)

The method of claim 2, further comprising:
monitoring a number of task engines for processing queries assigned to the third queue;
responsive to determining that the number of task engines is equal to or above a threshold, reducing at least the third set of executor nodes dedicated to processing the query.

### Claim 9

A non-transitory computer-readable storage medium comprising stored instructions that, when executed by one or more computer processors, causes the one or more computer processors to:
access a cluster including a driver node and one or more executor nodes each including one or more task engines, the cluster configured to schedule queries according to at least a first queue, a second queue, and a third queue, the first queue storing information on queries with a higher priority than queries assigned to the second queue, and the second queue storing information on queries with a higher priority than queries assigned to the third queue;
receive a query and assigning the query to the first queue, the query divided into a set of tasks;
allocate a number of task engines in a first set of executor nodes to process the set of tasks of the query;
monitor a resource time for the query while the query is being executed at the first set of executor nodes;
responsive to determining that the resource time for the query is equal to or above a threshold resource time, assign the query to the second queue;
responsive to assigning the query to the second queue, execute the tasks of the query on a second set of executor nodes;
responsive to determining that a second resource time for the query is equal to or above a second threshold resource time, assign the query to the third queue; and
responsive to assigning the query to the third queue, execute the tasks of the query on a third set of executor nodes.

### Claim 10 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein a number of executor nodes in the third set of executor nodes is smaller than a number of executor nodes in the first set of executor nodes.

### Claim 11 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein the instructions further cause the one or more computer processors to:
receive another query for execution;
responsive to assigning the query to the second queue, assign task engines to the another query assigned to the first queue; and
reallocate at least a portion of executor nodes from the first set of executor nodes to process the other query assigned to the first queue.

### Claim 12 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein the instructions further cause the one or more computer processors to:
determine, for each task of the query, an execution time to execute the task on a respective task engine; and
sum the execution time of the tasks of the query to determine the resource time.

### Claim 13 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein the instructions further cause the one or more computer processors to:
monitor a number of tasks for queries assigned to the first queue;
determine a number of task engines to be reserved for queries assigned to the first queue based on the monitored number of tasks; and
reserve the number of task engines on the cluster for queries assigned to the first queue for a next time step.

### Claim 14 (depends on 13)

The non-transitory computer-readable storage medium of claim 13, wherein the number of tasks for queries assigned to the first queue includes pending and running tasks, and wherein the instructions further cause the one or more computer processors to:
apply an exponential moving average (EMA) function on a sum of the pending and the running tasks; and
reserve Y task engines for the queries in the first queue, where Y=f(aggressiveness factor, X), where X is the sum of the pending and the running tasks and the aggressiveness factor is a constant.

### Claim 15 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein the instructions further cause the one or more computer processors to:
monitor a number of task engines for processing queries assigned to the third queue;
responsive to determining that the number of task engines is equal to or above a threshold, reduce at least the third set of executor nodes dedicated to processing the query.

### Claim 16

A computer system comprising:
one or more computer processors; and
one or more non-transitory computer readable storage mediums comprising stored instructions that, when executed by one or more computer processors, causes the one or more computer processors to:
access a cluster including a driver node and one or more executor nodes each including one or more task engines, the cluster configured to schedule queries according to at least a first queue, a second queue, and a third queue, the first queue storing information on queries with a higher priority than queries assigned to the second queue, and the second queue storing information on queries with a higher priority than queries assigned to the third queue;
receive a query and assigning the query to the first queue, the query divided into a set of tasks;
allocate a number of task engines in a first set of executor nodes to process the set of tasks of the query;
monitor a resource time for the query while the query is being executed at the first set of executor nodes;
responsive to determining that the resource time for the query is equal to or above a threshold resource time, assign the query to the second queue;
responsive to assigning the query to the second queue, execute the tasks of the query on a second set of executor nodes;
responsive to determining that a second resource time for the query is equal to or above a second threshold resource time, assign the query to the third queue; and
responsive to assigning the query to the third queue, execute the tasks of the query on a third set of executor nodes.

### Claim 17 (depends on 16)

The computer system of claim 16, wherein a number of executor nodes in the third set of executor nodes is smaller than a number of executor nodes in the first set of executor nodes.

### Claim 18 (depends on 16)

The computer system of claim 16, wherein the instructions further cause the one or more computer processors to:
receive another query for execution;
responsive to assigning the query to the second queue, assign task engines to the another query assigned to the first queue; and
reallocate at least a portion of executor nodes from the first set of executor nodes to process the other query assigned to the first queue.

### Claim 19 (depends on 16)

The computer system of claim 16, wherein the instructions further cause the one or more computer processors to:
determine, for each task of the query, an execution time to execute the task on a respective task engine; and
sum the execution time of the tasks of the query to determine the resource time.

### Claim 20 (depends on 16)

The computer system of claim 16, wherein the instructions further cause the one or more computer processors to:
monitor a number of tasks for queries assigned to the first queue;
determine a number of task engines to be reserved for queries assigned to the first queue based on the monitored number of tasks; and
reserve the number of task engines on the cluster for queries assigned to the first queue for a next time step.

### Claim 21 (depends on 20)

The computer system of claim 20, wherein the number of tasks for queries assigned to the first queue includes pending and running tasks, and wherein the instructions further cause the one or more computer processors to:
apply an exponential moving average (EMA) function on a sum of the pending and the running tasks; and
reserve Y task engines for the queries in the first queue, where Y=f(aggressiveness factor, X), where X is the sum of the pending and the running tasks and the aggressiveness factor is a constant.
