Patent Description:
The paper "<NPL>et al. discloses a method of serverless query processing which allocates resources for recurring and non-recurring queries, monitors the queries and dynamically reallocates resources based on the monitoring. The query execution graph is not taken into account for the dynamic reallocation.

Embodiments provide methods, apparatuses, and computer-readable mediums for serverless query processing optimization.

In an aspect, a method of serverless query processing is provided, in a serverless query processing system comprising at least one processor and at least one memory, the at least one memory comprising instructions executed by the at least one processor to process queries. The method includes receiving a query. The method further includes determining whether the query is a recurring query or a non-recurring query. The method further includes predicting, in response to determining that the query is the recurring query, a peak resource requirement during an execution of the query. The method further includes computing, in response to determining that the query is the non-recurring query, a tight resource requirement corresponding to an amount of resources that satisfy a performance requirement over the execution of the query, wherein the tight resource requirement is less than the peak resource requirement. The method further includes allocating resources to the query based on an applicable one of the peak resource requirement or the tight resource requirement. The method further includes starting the execution of the query using the resources.

In another aspect, a device in a serverless query processing system includes at least one processor; and at least one memory in communication with the at least one processor. The at least one memory comprises instructions executed by the at least one processor to process queries including receiving a query; determining whether the query is a recurring query or a non-recurring query; predicting, in response to determining that the query is the recurring query, a peak resource requirement during an execution of the query; computing, in response to determining that the query is the non-recurring query, a tight resource requirement corresponding to an amount of resources that satisfy a performance requirement over the execution of the query, wherein the tight resource requirement is less than the peak resource requirement; allocating resources to the query based on an applicable one of the peak resource requirement or the tight resource requirement; and starting the execution of the query using the resources.

In a further aspect, a serverless query processing apparatus includes a memory and at least one processor coupled to the memory. The at least one processor is configured to process queries including receiving a query; determining whether the query is a recurring query or a non-recurring query; predicting, in response to determining that the query is the recurring query, a peak resource requirement during an execution of the query; computing, in response to determining that the query is the non-recurring query, a tight resource requirement corresponding to an amount of resources that satisfy a performance requirement over the execution of the query, wherein the tight resource requirement is less than the peak resource requirement; allocating resources to the query based on an applicable one of the peak resource requirement or the tight resource requirement; and starting the execution of the query using the resources.

In yet another aspect, a computer-readable medium stores instructions that, when executed by at least one processor of a serverless query processing system, cause the serverless query processing system to process queries including receiving a query; determining whether the query is a recurring query or a non-recurring query; predicting, in response to determining that the query is the recurring query, a peak resource requirement during an execution of the query; computing, in response to determining that the query is the non-recurring query, a tight resource requirement corresponding to an amount of resources that satisfy a performance requirement over the execution of the query, wherein the tight resource requirement is less than the peak resource requirement; allocating resources to the query based on an applicable one of the peak resource requirement or the tight resource requirement; and starting the execution of the query using the resources.

In a further aspect, a query method is provided in a query system comprising at least one processor and at least one memory, the at least one memory comprising instructions executed by the at least one processor to run queries. The query method includes transmitting a query to a serverless query processing system. The query method further includes skipping transmission, to the serverless query processing system, of an amount of resources required for an execution of the query, wherein the skipping is configured to cause the serverless query processing system to determine and allocate the amount of resources required for the execution of the query. The query method further includes receiving results of the execution of the query from the serverless query processing system.

In another aspect, a query device includes at least one processor and at least one memory in communication with the at least one processor. The at least one memory comprises instructions executed by the at least one processor to run queries including transmitting a query to a serverless query processing system; skipping transmission, to the serverless query processing system, of an amount of resources required for an execution of the query, wherein the skipping is configured to cause the serverless query processing system to determine and allocate the amount of resources required for the execution of the query; and receiving results of the execution of the query from the serverless query processing system.

In a further aspect, a query apparatus includes a memory and at least one processor coupled to the memory. The at least one processor is configured to run queries including transmitting a query to a serverless query processing system; skipping transmission, to the serverless query processing system, of an amount of resources required for an execution of the query, wherein the skipping is configured to cause the serverless query processing system to determine and allocate the amount of resources required for the execution of the query; and receiving results of the execution of the query from the serverless query processing system.

In yet another aspect, a computer-readable medium stores instructions that, when executed by at least one processor of a query system, cause the query system to run queries including transmitting a query to a serverless query processing system; skipping transmission, to the serverless query processing system, of an amount of resources required for an execution of the query, wherein the skipping is configured to cause the serverless query processing system to determine and allocate the amount of resources required for the execution of the query; and receiving results of the execution of the query from the serverless query processing system.

The detailed description set forth below in connection with the appended drawings is intended as a description of various configurations and is not intended to re-present the only configurations in which the concepts described herein may be practiced.

The present aspects provide a serverless query processing system that uses machine learning models for predicting peak resource requirements in recurring queries using features from a query plan and input data. Some aspects further provide a tuning algorithm for computing tight allocations (the minimum possible allocation that does not cause any noticeable degradation in performance) in ad-hoc queries by simulating the scheduling behavior of a query plan at compile time. Further, in some aspects, an adaptive algorithm is used to re-compute a peak (or tight) allocation as the query execution progresses and to release any redundant resources. Accordingly, in the present aspects, an end-to-end resource optimization system provides offline training and extensions to compiler, optimizer, scheduler, and job manager, for automatic resource optimization.

A serverless query processing system automatically provisions a set of resources for a query, without having users manage the resources for their computation tasks. In an aspect, a resource may refer to a computing resource, such as a virtual machine (VM), memory, etc. In an aspect, for example, a resource may refer to a "container" which is a collection of processing cores and RAM. In an aspect, for example, a container may provide the functionality of a "light" VM, which is a VM that can be started and stopped cheaply/quickly. A serverless query processing system may provide, for example, an exabyte-scale big data analytics platform where the users specify declarative queries and the system runs the queries in a massively distributed environment. A serverless query processing system may include an engine that decides the number of containers (also known as tokens) to use for each job. A serverless query processing system may process, for example, hundreds of thousands of jobs per day using hundreds of thousands of virtual machines. In an aspect, for example, a job may be an analytical job such as building an index of information downloaded from the Internet, computing a statistical function (e.g., average) of numerical data, etc..

Turning now to the figures, examples are depicted with reference to one or more components and one or more methods that may perform the actions or operations described herein, where components and/or actions/operations in dashed line may be optional. Although the operations described below in one or more of the methods are presented in a particular order and/or as being performed by an example component, the ordering of the actions and the components performing the actions may be varied, in some examples, depending on the implementation. Moreover, in some examples, one or more of the described actions, functions, and/or components may be performed by a specially-programmed processor, a processor executing specially-programmed software or computer-readable media, or by any other combination of a hardware component and/or a software component capable of performing the described actions or functions.

<FIG> is an example end-to-end resource optimization and query processing system <NUM> including a resource predictor <NUM> that predicts the maximum required resources for recurring jobs, a resource shaper <NUM> that dynamically shapes the resource allocation during the execution of a job based on the query execution graph, and a resource tuner <NUM> that finds a tight resource allocation (corresponding to an amount of resources that satisfy a performance requirement over the execution of the query) for non-recurring jobs, according to some present aspects. The system <NUM> first identifies recurring and non-recurring workloads from a workload repository <NUM> that includes query plans, stage graphs, and associated telemetry from previous job executions. Using this data, the system <NUM> learns the models for the resource predictor <NUM> for each recurring job at Step <NUM>. Also, the system <NUM> uses the non-recurring jobs to trigger the resource tuner <NUM> at Step <NUM>. The models for the resource predictor <NUM> are serialized and stored into a workload insight service <NUM> at Step <NUM>. For each job (e.g., analytical job) that gets submitted by a user <NUM> at Step <NUM> (e.g., by a person or an application), a query compiler <NUM> looks up the insight service <NUM> at Step <NUM>, and loads the resource predictor model for that job at Step <NUM>. The query compiler <NUM> passes the compiled abstract syntax tree (AST) along with the predictor model to a query optimizer <NUM> at Step <NUM>, which infers the peak resource requirement using the predictor model at Step <NUM>. For non-recurring jobs, the query optimizer <NUM> invokes the resource tuner <NUM> at Step <NUM>. The query optimizer <NUM> passes the peak resource requirement hints, obtained either from the resource predictor <NUM> or the resource tuner <NUM>, to a job scheduler <NUM> at Step <NUM>, which schedules the job with the peak resource requirement. Once the job starts executing, a job manager <NUM> invokes the resource shaper <NUM> at Step <NUM>, and in case of excess resources, releases the excess resources via the job scheduler <NUM> at Step <NUM>. Finally, the logs from each of the query processing components (the query compiler <NUM>, the query optimizer <NUM>, the job scheduler <NUM>, and the job manager <NUM>) are collected into the workload repository <NUM> at Step <NUM> to train the models (e.g., the peak resource requirement models for the resource predictor <NUM>) and further improve the future decisions. In an aspect, the resource shaper <NUM> may also mine the resource skylines from the workload repository <NUM> and use them during resource shaping.

Accordingly, the system <NUM> continuously learns from the past workloads and may therefore optimize performance for different subsets of the workload and fix errors in the early predictions. In some aspects, the system <NUM> is fully automatic and does not require any manual supervision or tuning from the users <NUM>. In some aspects, the system <NUM> may provide compiler flags where the users <NUM> may choose to explicitly opt-in or opt-out of resource optimization on a per job basis. In some aspects, if the models for the resource predictor <NUM> predict an allocation lower than the actual peak, the system <NUM> may split the past workload into "training," "validation," and "test" sets, and apply filters for models that perform poorly on the "validation" set. Alternatively and/or additionally, the system <NUM> may consider the different subsets of workloads from different customers (e.g., virtual clusters), and filter out the workload subsets (or customers) that do not benefit from resource optimization. This is because either the workloads may be too ad-hoc in nature or the customer has their own custom machinery for resource optimizations. Alternatively and/or additionally, the job manager <NUM> may observe the actual peak resource requirements and inform the workload insights service <NUM> to disable a model that produces incorrect predictions. Alternatively and/or additionally, the system <NUM> may retrain the predictor models, e.g., every day, for an initial deployment phase, thereby fixing errors in model predictions with newer training data. Alternatively and/or additionally, the resource shaper <NUM> may be made more resilient by adding the previously seen skyline in similar jobs and using that, in combination with the stage graph, to estimate the remaining peak needed for the job. Alternatively and/or additionally, the resource shaper <NUM> may use more accurate cost estimates of each stage as well as run the actual job manager code in simulation mode (wherever possible) to mimic the runtime behavior more accurately. Further details of the operation of the components of the system <NUM> are provided below.

In an aspect, the system <NUM> implements serverless query processing to shift the responsibility of resource allocation from the users <NUM> to query engines. Conventional serverless query processing includes estimating the fine-grained resource requirements for each query at compile time. However, the estimates in a conventional query optimizer are often off by orders of magnitudes, in particular in big data systems. Further, allocating and de-allocating resources is expensive, making a change in the allocation for a query undesirable. Additionally, a resource change may trigger query plan changes to use the new set of resources, which may adversely affect the overall performance. Yet further, given that a query runs for a relatively small time duration, there is not much room for adjusting the resources. In particular, if the resources are under-allocated, query performance may have suffered already before any resource adjustments could be applied.

A conventional serverless query processor may address some of these issues by relying on a user-specified resource limit, e.g., the maximum number of tokens that a query may use, and reserves them as guaranteed resources before starting the query execution. However, users rarely make an informed decision when specifying the maximum tokens.

For example, referring to <FIG>, an example token usage skyline <NUM> over time in a typical example job indicates a large gap between the user supplied tokens (corresponding to a default allocation <NUM> requested by the user <NUM>), and the actual token consumption <NUM>. In <FIG>, the resource consumption and the resulting gap between allocated and used tokens changes significantly as the query progresses. Over-provisioning of tokens results in high queuing latencies and resource wastage. In case of under-allocation, a serverless query processor may attempt to opportunistically use spare tokens. However, under-allocation may still result in poor and unpredictable query performance. In contrast, in some present aspect, the system <NUM> in <FIG> properly sizes the tokens for each recurring job, thus leading to opportunistic capacity (bonus tokens) for speeding up existing jobs and spare capacity for newer jobs, thereby significantly improving the overall system efficiency.

In some aspects, for big data, instead of treating jobs as a black box model, the system <NUM> determines the resource requirements of a job based on the characteristics of each job or how the resource requirements change in different stages of a job and/or over time. In some aspects, instead of using a static resource allocation, the system <NUM> uses resource modeling and optimization to build resource cost models for selecting resources for a given query plan and adapt over the course of job execution (e.g., during runtime). In some aspects, the system <NUM> allows for dynamic re-allocation of resources using a lightweight simulator that uses cost estimates of each stage from the query optimizer and replays the vertex scheduling strategy. In case the cost estimates are inaccurate, the system <NUM> may fix them separately using learned cost models. In some aspects, the system <NUM> finds the optimal resources for each operator in the query plan as part of query optimization by considering a transformation of operators into a stage graph and how cost varies with varying resources on the stage graph.

In an aspect, for example, the system <NUM> provides built-in resource optimization for systematic resource allocation for serverless query processing. In an aspect, for a large fraction of production workloads that are recurring in nature, the system <NUM> predicts a peak allocation for recurring jobs using machine learning models built from the telemetry of past jobs (e.g., query plans, runtime statistics, etc.). Further, for non-recurring jobs (e.g., ad-hoc jobs, non-Service Level Agreement (SLA) jobs, etc.), the system <NUM> computes a tight allocation which is the minimum possible allocation that does not cause noticeable degradation in performance. The system <NUM> may dynamically adapt the allocations based on the query execution graph. For this, the system <NUM> re-computes a new peak or tight allocation expected for the remainder of the query as the query execution progresses. At any time, if the newer computed allocation is lower than the current allocation, the system <NUM> releases the excess resources.

In an aspect, for example, the system <NUM> begins query processing using a peak allocation or a tight allocation depending on whether a job is recurring or not. <FIG> respectively illustrate a peak allocation <NUM>, an adaptive allocation <NUM>, and a tight allocation <NUM> for the example job in <FIG>. As compared to <FIG>, the area under the resource curve (e.g., the total resource consumption) in <FIG> is significantly reduced.

As compared to conventional query processing systems, the system <NUM> is plan-aware for determining the resource allocation, improves resource efficiency without degrading the query performance, and allows for resource optimizations to be automatic and transparent to the users.

Referring to <FIG>, an example job includes stages <NUM> that are connected in a directed acyclic graph (DAG) <NUM> with the data flow being from top to bottom. Each stage <NUM> includes one or more physical operators that may be processed locally in a single container. Instances of a stage <NUM> (also referred to as vertices) may process different partitions of data in parallel. One non-limiting example aspect may consider maximum degree of parallelism (also referred to as tokens) as the unit of resource. However, the present aspects are applicable to other dimensions such as container size, virtual machine (VM) type, etc..

In conventional query processing systems, a job may reserve a user-provided maximum number of tokens (the allocated resources) before the job starts executing. In this case, for example, <NUM>% to <NUM>% of the jobs may be over-allocated by as much as 1000x, indicating significant opportunities for right-sizing the resource allocation. In some cases, for example, <NUM>% to <NUM>% of jobs may be over-allocated with respect to their average resource consumption. As such, there is a significant gap between the peak and average resource consumption in conventional resource processing systems that use a user-provided maximum number of tokens. Reducing over-allocation improves the operational efficiency in big data analytics. Further, guaranteed resources may be freed up and used to submit more jobs. Additionally, the queuing time of jobs may be reduced by having the jobs request for less resources. Finally, the user experience may be improved by automating a corresponding parameter in jobs. In an aspect, for example, tight allocation may increase the allocation for significantly under-allocated jobs. This not only improves the job performance but also makes job performance more predictable, since right-sizing the allocation reduces the dependence on opportunistic resource allocation. Accordingly, some present aspects provide resource prediction to enable peak allocation, resource shaping to enable adaptive allocation, and resource tuning to enable tight allocation. Further details are provided below.

Referring back to <FIG>, in an aspect, the resource predictor <NUM> predicts the peak resources (e.g., peak allocation <NUM> in <FIG>) that would be required in a recurring job, e.g., jobs that are executed periodically with changing inputs and parameters. In an aspect, for example, recurring jobs may include jobs that process logs from one or more products and drive business decisions. Since the structure of the job remains the same, the peak resource requirements may be modeled as a function of the inputs and parameters. In an aspect, the system <NUM> is plan-aware and identifies the recurring jobs. In an aspect, for example, the system <NUM> uses a hash of the logical query plan of the job to identify recurring instances. In some aspects, since the inputs and the parameters may change, the system <NUM> may ignore the inputs and the parameters in the hash. Such a hash (also referred to as a signature) may be used for identifying common sub-expressions.

For model training, in one non-limiting aspect, a job may be identified as recurring if the corresponding hash value appears at least twice in the training dataset. For each such hash value, a model is trained using feature values and actual peak resource usage information from jobs with that hash value. During prediction, feature values from the target job are used to predict peak resource usage using the model trained for that hash value. If the model does not exist, either because this is a different job or because the hash value appeared only once in the training set, a default value requested/provided by the user may be used.

For each recurring job, the system <NUM> may consider different data characteristics such as cardinality, plan characteristics such as parameters, and optimizer-derived characteristics such as number of partitions, plan cost, etc. In an aspect, since the peak resource requirement is predicted at compile-time, only the features that are available at compile-time for each recurring job are considered, and runtime characteristics such as actual execution time are excluded.

In an aspect, the system <NUM> may consider multiple signatures in order to improve coverage of the models. For example, instead of using the hash of the entire query plan, the system <NUM> may consider a relaxed hash that only includes the root operator and leaf-level inputs. Queries having the same relaxed hash may have the same inputs but different plan shapes, which may indicate their peak resource requirements. In an aspect, the system <NUM> captures plan characteristics such as plan costs, partitions, etc., which may be indicators of resource requirements. The system <NUM> may also consider other types of relaxed hashes to group similar jobs and improve the coverage of the models.

For model selection, the system <NUM> may consider regression models such as Linear Regression, AdaBoost Regression, Extra-Trees Regression, Gradient Boosting Regression, and Random Forest Regression. For example, the system <NUM> may implement linear regression with standard normalization.

During model training, in an aspect, each recurring job in the training dataset may be classified into multiple groups, one for each hash value computed for the job. Then, models are built for each group. During prediction, for each job, hash values are considered in succession, stopping when the corresponding model is found which is then used to predict the peak resource usage/requirement for the job. If no model is found, the default value is used.

Accordingly, by creating one model per recurring job, the resource predictor <NUM> may accurately predict the peak resource usage/requirement for jobs. The resource predictor <NUM> may scale gracefully with the changes in data characteristics such as input sizes, etc..

In an aspect, once a job starts executing, the resource shaper <NUM> dynamically shapes the resource allocation based on the query execution graph (e.g., as in <FIG>). For example, in an aspect, the resource shaper <NUM> estimates the peak resource usage/requirement in the remaining of the job execution, and any excess resources are released. In an alternative aspect, instead of only releasing resources, the resource curve may be used to both release and request resources. As compared to requesting resources, releasing resources is a more lightweight operation without incurring the request overheads on the job manager <NUM> or the queuing overheads on the job execution. Therefore, the resource shaper <NUM> may passively inform the job manager <NUM> of the spare resources which may be recycled at any time. To detect the peak for the remaining query, the resource shaper <NUM> may invoke a query graph-based peak resource requirement estimator at any point during query execution, and excess resources may be released via communication with the job manager <NUM> and the job scheduler <NUM>.

In an aspect, for example, the resource shaper <NUM> may estimate the peak resources for the remaining of the job by converting a job graph into one or more trees. For example, the resource shaper <NUM> may perform "tree-ification" by removing one of the output edges of the Spool operators in the job graph, since Spool is the only operator that may have more than one consumers. For example, the resource shaper <NUM> may remove one of the output Spool edges since a stage containing the Spool operator cannot run concurrently with its consumer stages. In an aspect, the resource shaper <NUM> removes the edge with the consumer that has the maximum in-degree. In case of a tie, the resource shaper <NUM> may select a consumer at random. In an aspect, if the maximum in-degree of spool consumers is one, then no edge can be removed since the sub-graph is already a tree.

In an aspect, for example, the resource shaper <NUM> may determine a max-cut on the DAG of a job. Referring to <FIG>, for example, a stage graph <NUM> (e.g., DAG) of an example job may include twelve stages <NUM> over four inputs <NUM> and produce three outputs <NUM>. In this example, stages S2, S6, and S8 have spool operators, since they have two downstream consumers each. To convert the DAG into a set of trees <NUM>, the resource shaper <NUM> may remove one of the outgoing edges of the spools. For S8, for example, the resource shaper <NUM> may remove the edge with S11, since this edge has a higher in-degree than S10. For S2 and S6, the resource shaper <NUM> may pick an edge at random since their consumers have equal in-degrees of <NUM>. This results in three trees <NUM> corresponding to the three outputs <NUM>. In <FIG>, the number of vertices are indicated in square brackets for each of the stages <NUM>. In an aspect, for example, at a particular point in execution in <FIG>, the numbers <NUM> in brackets denote the completed vertices, the numbers <NUM> in brackets denote the running vertices, and the numbers <NUM> in brackets denote vertices that are yet to be scheduled. Given this particular point in execution, the resource shaper <NUM> may compute the maximum remaining peak resource requirement by computing the maximum width of each of the trees <NUM>, which is <NUM>, <NUM>, and <NUM> respectively, and then takes the sum of the individual tree widths, e.g., <NUM>. If the job started with, for example, <NUM> containers, then the system <NUM> may release <NUM> containers at this point in execution.

The below example code provides an example implementation of the resource shaper <NUM> in an aspect.

In the above example code, Algorithm <NUM> is the control loop of the resource shaper <NUM> that first converts the job graph into tree(s) and then recursively computes the remaining peak resource requirement in each of the tree root nodes. If the total remaining peak resource requirement is less than the current resources, then the job manager <NUM> makes the call to give up excess resources. Further, Algorithm <NUM> finds the remaining peak resource requirement by iteratively adding the peak resource requirements of the children of each parent node (Lines <NUM>-<NUM> in the above example code), and returns the max of the children and parent peak resource requirements (Line <NUM> in the above example code). Accordingly, the peak resource requirement estimation finds the max-cut in each of the trees generated from the job graph and takes the sum.

In an aspect, the resource tuner <NUM> finds the tight allocation (e.g., as in <FIG>) for non-recurring jobs, e.g., jobs that are not SLA sensitive and do not have a resource predictor anyways. In an aspect, for example, almost <NUM>% of the workloads may be non-recurring. In an aspect, the resource tuner <NUM> is plan-aware and hence may also be used for increasing the allocation to improve performance in under-allocated jobs. In an aspect, for example, starting from an original resource-cost curve, the resource tuner <NUM> may modify the resource-cost area and either tune cost with extra resources or tune resources for extra cost.

For example, referring to <FIG>, respectively, given an original resource-cost skyline <NUM> of a typical job (with the cost being in terms of job latency), the resource tuner <NUM> may increase the resources up to a limit to obtain a first modified resource-cost skyline <NUM> if it helps to reduce the cost of the job, or decrease resources to obtain a second modified resource-cost skyline <NUM> if the increase in cost is within a limit. In either case, the resource tuner <NUM> attempts to decrease the total area of the resource-cost rectangle <NUM>. For example, in <FIG>, the first modified resource-cost skyline <NUM> causes <NUM>% increase in resources for a <NUM>% reduction in cost, while the second modified resource-cost skyline <NUM> causes <NUM>% decrease in resources for a <NUM>% increase in cost. In both cases, the total area of the resource-cost rectangle <NUM> decreases from <NUM> to <NUM>, and hence either of these may be valid resource tunings. In such a case, the resource tuner <NUM> may choose cost reduction over resource reduction and pick the first modified resource-cost skyline <NUM> over the second modified resource-cost skyline <NUM>.

The below example code provides an example implementation of iterative tuning in the resource tuner <NUM> in an aspect.

In the above example code, Algorithm <NUM> finds the tight allocation for a job. Specifically, the resource tuner <NUM> simulates the job scheduler <NUM> to estimate the same sequence of vertex executions as would happen in the real environment. Algorithm <NUM> starts with an initial set of resources and iteratively (Lines <NUM>-<NUM> in the above example code) finds the alternate resource allocation that would improve the area of the resource-cost rectangle <NUM> while keeping cost and resource overheads within a threshold α (Lines <NUM>-<NUM> in the above example code). In an aspect for example, the threshold may be specified by the user <NUM>. In an alternative aspect, the threshold may be a default threshold, e.g., <NUM>%. To estimate the cost with a candidate resource allocation, Algorithm <NUM> simulates two components from the job manager <NUM>: (i) priority assignment for different stages in the job graph (Line <NUM> in the above example code), and (ii) priority queue based on execution of different vertices in each stage (Lines <NUM> and <NUM> in the above example code). Further details are provided below. In an aspect, although Algorithm <NUM> iterates in a hill-climbing manner, Algorithm <NUM> may be adapted to other exploration strategies, e.g., simulated annealing or even exhaustive search if the resource space is not too large.

The below example code provides an example implementation of the priority assignment in the iterative tuning of Algorithm <NUM> in the resource tuner <NUM> in an aspect.

In the above example code, Algorithm <NUM> implements the priority assignment logic that emulates the job manager <NUM>. In an aspect, for example, the leaf stages are assigned a priority of zero (e.g., most important), and all other stages are assigned a priority of one more than the maximum priority of any respective child stages. Such a priority assignment ensures that all child stages have been executed before the parent stage starts executing.

Referring to <FIG>, for example, in an aspect, the resource tuner <NUM> may perform priority assignment over the example job graph <NUM> in <FIG>, starting from a priority zero for all input stages <NUM> and ending with a priority <NUM> for all output stages <NUM>.

Finally, the resource tuner <NUM> may estimate the cost of a job with different resource allocations by simulating the execution of different stages in the job manager <NUM>. For example, in an aspect, the resource tuner <NUM> may put all stages, along with their priorities in a priority queue, and schedule the stage at the top of the queue as soon as resources are available.

The below example code provides an example implementation of cost simulation in the resource tuner <NUM> in an aspect.

In the above example code, Algorithm <NUM> provides the simulated run of a job with a given set of resources. Algorithm <NUM> adds all job stages into a priority queue (Line <NUM> in Algorithm <NUM>) and then loops until the queue is empty (Lines <NUM>-<NUM> in Algorithm <NUM>). In each iteration, Algorithm <NUM> first checks whether there are resources available to schedule more tasks (Line <NUM> in Algorithm <NUM>). If there are, then Algorithm <NUM> considers the highest priority stages and schedules one of their next vertices (Lines <NUM>-<NUM> in Algorithm <NUM>). For a stage vertex to be scheduled, all its dependency stages (the parent stages) need to be executed before (Lines <NUM>-<NUM> in Algorithm <NUM>). If all vertices of a stage have been scheduled, then the stage is removed from the queue (Lines <NUM>-<NUM> in Algorithm <NUM>). Algorithm <NUM> simulates task progress by picking the smallest cost task and advancing all other tasks by that cost (Lines <NUM>-<NUM> in Algorithm <NUM>). This minimum cost is added to the overall cost (Line <NUM> in Algorithm <NUM>) and returned in the end when the queue gets empty (Line <NUM> in Algorithm <NUM>). In some aspects, Algorithm <NUM> may ignore data skew, stage pipelining, vertex scheduling overheads, and/or other randomizations.

<FIG> is an example cost simulation <NUM> of Algorithm <NUM> over the priority-assigned stage graph of <FIG> for a resource allocation of <NUM> containers. The cost simulation <NUM> starts with scheduling stages S1 to S4 utilizing all <NUM> containers. Once these stages finish, their downstream stages S5, S5, and S6 are scheduled. Stage S9 gets scheduled as soon as stage S7 finishes. However, stage S12 which is the downstream stage of stage S7 needs to wait for stage S6 to finish. Except for the initial time interval of t1 - t2, the <NUM> containers are not all used at the same time, and resource shaping may still be applied after resource tuning.

The present aspects are not limited to the job manager scheduling examples described herein, and are applicable to other scheduling strategies for computing the corresponding estimated costs.

<FIG> and <FIG> provide flowcharts of example query methods <NUM> and <NUM> in a serverless query processing system comprising at least one processor and at least one memory, the at least one memory comprising instructions executed by the at least one processor to process queries. The following description of the example methods <NUM> and <NUM> makes reference to the systems and components described above with reference to <FIG> or described below with reference to <FIG>. For example, each one of the example methods <NUM> and <NUM> may be performed by components of the example serverless query processing system <NUM>, and is accordingly described with reference to <FIG>, as non-limiting examples of an environment for carrying out each one of the example methods <NUM> and <NUM>. Additionally, each one of the example methods <NUM> and <NUM> may be implemented on a computing device (see e.g., computing device <NUM> of <FIG>) operating in the example serverless query processing system <NUM>, and subcomponents of the computing device may also be described below.

Referring to <FIG>, at <NUM> the method <NUM> includes receiving a query. For example, in the aspect of <FIG>, the processor <NUM>, the query component <NUM>, the communications component <NUM>, and/or the user interface component <NUM> may receive a query. Accordingly, the processor <NUM>, the query component <NUM>, the communications component <NUM>, and/or the user interface component <NUM> may provide means for receiving a query. In an aspect, for example, as described above with reference to <FIG>, the system <NUM> may receive a query from the user <NUM> (which may be a person or an application) that interacts with the system <NUM>.

At <NUM> the method <NUM> includes determining whether the query is a recurring query or a non-recurring query. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may determine whether the query is a recurring query or a non-recurring query. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for determining whether the query is a recurring query or a non-recurring query. In an aspect, for example, as described above with reference to <FIG>, the system <NUM> may determine whether a query received from the user <NUM> is a recurring query or a no-recurring query. For example, the system <NUM> may identify recurring and non-recurring workloads from a workload repository <NUM> that includes query plans, stage graphs, and associated telemetry from previous job executions.

Optionally, at <NUM> the method <NUM> may include predicting, in response to determining that the query is the recurring query, a peak resource requirement during an execution of the query. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may predict, in response to determining that the query is the recurring query, a peak resource requirement during an execution of the query. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for predicting, in response to determining that the query is the recurring query, a peak resource requirement during an execution of the query. In an aspect, for example, as described above with reference to <FIG>, a query compiler <NUM> may look up the insight service <NUM> and load the resource predictor model for a job, and pass the compiled AST along with the predictor model to a query optimizer <NUM>, which infers the peak resource requirement using the predictor model.

Optionally, at <NUM> the method <NUM> may include computing, in response to determining that the query is the non-recurring query, a tight resource requirement corresponding to an amount of resources that satisfy a performance requirement over the execution of the query, wherein the tight resource requirement is less than the peak resource requirement. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may compute, in response to determining that the query is the non-recurring query, a tight resource requirement corresponding to an amount of resources that satisfy a performance requirement over the execution of the query, wherein the tight resource requirement is less than the peak resource requirement. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for computing, in response to determining that the query is the non-recurring query, a tight resource requirement corresponding to an amount of resources that satisfy a performance requirement over the execution of the query, wherein the tight resource requirement is less than the peak resource requirement. In an aspect, for example, as described above with reference to <FIG>, for non-recurring jobs, the query optimizer <NUM> may invoke the resource tuner <NUM> that finds a tight resource allocation corresponding to an amount of resources that satisfy a performance requirement over the execution of the query. In an aspect, for example, as described above with reference to <FIG>, the tight resource requirement in a tight allocation <NUM> is less than the peak resource requirement in a peak allocation <NUM>.

At <NUM> the method <NUM> includes allocating resources to the query based on an applicable one of the peak resource requirement or the tight resource requirement. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may allocate resources to the query based on an applicable one of the peak resource requirement or the tight resource requirement. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for allocating resources to the query based on an applicable one of the peak resource requirement or the tight resource requirement. In an aspect, for example, as described above with reference to <FIG>, a job scheduler <NUM> may schedule a job with the applicable one of the peak resource requirement or the tight resource requirement.

At <NUM> the method <NUM> includes starting an execution of the query using the resources. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may start an execution of the query using the resources. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for starting an execution of the query using the resources. In an aspect, for example, as described above with reference to <FIG>, a job manager <NUM> may start executing the job using the allocated resources.

Optionally, determining whether the query is the recurring query or the non-recurring query at <NUM> may further include determining that the query is the recurring query in response to a hash of a logical query plan of the query appearing more than once in a training dataset. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may determine that the query is the recurring query in response to a hash of a logical query plan of the query appearing more than once in a training dataset. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for determining that the query is the recurring query in response to a hash of a logical query plan of the query appearing more than once in a training dataset. In an aspect, for example, as described above with reference to <FIG>, the system <NUM> uses a hash of the logical query plan of a job to identify recurring instances. In some aspects, since the inputs and the parameters may change, the system <NUM> may ignore the inputs and the parameters in the hash.

Optionally, predicting the peak resource requirement at <NUM> may further include predicting the peak resource requirement using a machine learning model that is trained using past feature values and past actual peak resource usage information of past jobs that are associated with the hash. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may predict the peak resource requirement using a machine learning model that is trained using past feature values and past actual peak resource usage information of past jobs that are associated with the hash. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for predicting the peak resource requirement using a machine learning model that is trained using past feature values and past actual peak resource usage information of past jobs that are associated with the hash. In an aspect, for example, as described above with reference to <FIG>, the system <NUM> predicts a peak allocation for recurring jobs using machine learning models built from the telemetry of past jobs.

Optionally, predicting the peak resource requirement at <NUM> may further include predicting the peak resource requirement using the machine learning model and feature values of the query. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may predict the peak resource requirement using the machine learning model and feature values of the query. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for predicting the peak resource requirement using the machine learning model and feature values of the query. In an aspect, for example, as described above with reference to <FIG>, the system <NUM> predicts a peak allocation for recurring jobs using machine learning models built from the telemetry of past jobs including query plans, runtime statistics, etc. For each recurring job, the system <NUM> may consider different data characteristics such as cardinality, plan characteristics such as parameters, and optimizer-derived characteristics such as number of partitions, plan cost, etc..

Optionally, predicting the peak resource requirement at <NUM> may further include predicting the peak resource requirement at compile time using the machine learning model and feature values of the query that are available at compile time. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may predict the peak resource requirement at compile time using the machine learning model and feature values of the query that are available at compile time. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for predicting the peak resource requirement at compile time using the machine learning model and feature values of the query that are available at compile time. In an aspect, for example, as described above with reference to <FIG>, since the peak resource requirement is predicted at compile-time, only the features that are available at compile-time for each recurring job are considered, and runtime characteristics such as actual execution time are excluded.

Optionally, the method <NUM> may further include, subsequent to the starting, dynamically updating the allocation of the resource for a remainder of the execution of the query based on a query execution graph of the query. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may, subsequent to the starting, dynamically update the allocation of the resource for a remainder of the execution of the query based on a query execution graph of the query. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for, subsequent to the starting, dynamically updating the allocation of the resource for a remainder of the execution of the query based on a query execution graph of the query. In an aspect, for example, as described above with reference to <FIG>, once a job starts executing, the job manager <NUM> may invoke the resource shaper <NUM>, and in case of excess resources, releases the excess resources via the job scheduler <NUM>. The system <NUM> may dynamically adapt the allocations based on the query execution graph.

Optionally, the method <NUM> may further include re-computing the applicable one of the peak resource requirement or the tight resource requirement based on the query execution graph; and releasing any excess resources. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may re-compute the applicable one of the peak resource requirement or the tight resource requirement based on the query execution graph; and release any excess resources. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for re-computing the applicable one of the peak resource requirement or the tight resource requirement based on the query execution graph; and releasing any excess resources. In an aspect, for example, as described above with reference to <FIG>, once a job starts executing, the job manager <NUM> may invoke the resource shaper <NUM>, and in case of excess resources, releases the excess resources via the job scheduler <NUM>. In an aspect, for example, as described above with reference to <FIG>, the system <NUM> re-computes a new peak or tight allocation expected for the remainder of the query as the query execution progresses. At any time, if the newer computed allocation is lower than the current allocation, the system <NUM> releases the excess resources.

Optionally, the re-computing may further include converting the query execution graph into one or more trees by removing one edge from output edges of each operator that has more than one consumer; and computing a maximum remaining peak resource requirement by computing a maximum width of each tree and summing the maximum width of all trees. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may convert the query execution graph into one or more trees by removing one edge from output edges of each operator that has more than one consumer; and compute a maximum remaining peak resource requirement by computing a maximum width of each tree and summing the maximum width of all trees. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for converting the query execution graph into one or more trees by removing one edge from output edges of each operator that has more than one consumer; and computing a maximum remaining peak resource requirement by computing a maximum width of each tree and summing the maximum width of all trees. In an aspect, for example, as described above with reference to <FIG>, the resource shaper <NUM> may estimate the peak resources for the remaining of the job by converting a job graph into one or more trees. For example, the resource shaper <NUM> may perform "tree-ification" by removing one of the output edges of the Spool operators in the job graph, since Spool is the only operator that may have more than one consumers. In an aspect, for example, as described above with reference to <FIG>, at each particular point in execution, the resource shaper <NUM> may compute the maximum remaining peak resource requirement by computing the maximum width of each of the trees <NUM>, which is <NUM>, <NUM>, and <NUM> respectively, and then takes the sum of the individual tree widths, e.g., <NUM>.

Optionally, computing the tight resource requirement at <NUM> may further include computing the tight resource requirement that corresponds to a minimum amount of resources that satisfy the performance requirement over the execution of the query. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may compute the tight resource requirement that corresponds to a minimum amount of resources that satisfy the performance requirement over the execution of the query. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for computing the tight resource requirement that corresponds to a minimum amount of resources that satisfy the performance requirement over the execution of the query. In an aspect, for example, as described above with reference to <FIG>, for non-recurring jobs (e.g., ad-hoc jobs, non-SLA jobs, etc.), the system <NUM> computes a tight allocation which is the minimum possible allocation that does not cause noticeable degradation in performance.

Optionally, computing the tight resource requirement at <NUM> may further include estimating a sequence of vertex executions in a query execution graph of the query by simulating a job scheduler; and starting with an initial set of resources, iteratively finding an alternative resource allocation that decreases an area of a resource-cost rectangle circumscribing a resource-cost curve of the execution of the query while keeping cost and resource overheads within a threshold. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may estimate a sequence of vertex executions in a query execution graph of the query by simulating a job scheduler; and starting with an initial set of resources, iteratively find an alternative resource allocation that decreases an area of a resource-cost rectangle circumscribing a resource-cost curve of the execution of the query while keeping cost and resource overheads within a threshold. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for estimating a sequence of vertex executions in a query execution graph of the query by simulating a job scheduler; and starting with an initial set of resources, iteratively finding an alternative resource allocation that decreases an area of a resource-cost rectangle circumscribing a resource-cost curve of the execution of the query while keeping cost and resource overheads within a threshold. In an aspect, for example, as described above with reference to <FIG>, the resource tuner <NUM> attempts to decrease the total area of the resource-cost rectangle <NUM>. Specifically, the resource tuner <NUM> simulates the job scheduler <NUM> to estimate the same sequence of vertex executions as would happen in the real environment, including starting with an initial set of resources and iteratively finding the alternate resource allocation that would improve the area of the resource-cost rectangle <NUM> while keeping cost and resource overheads within a threshold.

Optionally, computing the tight resource requirement at <NUM> may further include assigning priorities to each stage in the query execution graph of the query, wherein a priority assigned to a stage is one more than a maximum priority assigned to child stages of the stage. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may assign priorities to each stage in the query execution graph of the query, wherein a priority assigned to a stage is one more than a maximum priority assigned to child stages of the stage. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for assigning priorities to each stage in the query execution graph of the query, wherein a priority assigned to a stage is one more than a maximum priority assigned to child stages of the stage. In an aspect, for example, as described above with reference to <FIG>, the resource tuner <NUM> assigns a priority of zero (e.g., most important) to the leaf stages, and all other stages are assigned a priority of one more than the maximum priority of any respective child stages. Such a priority assignment ensures that all child stages have been executed before the parent stage starts executing. In an aspect, for example, as described above with reference to <FIG>, the resource tuner <NUM> may perform priority assignment over the example job graph <NUM> in <FIG>, starting from a priority zero for all input stages <NUM> and ending with a priority <NUM> for all output stages <NUM>.

Optionally, computing the tight resource requirement at <NUM> may further include queuing stages of the query execution graph of the query in a priority queue based on the priorities. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may queue stages of the query execution graph of the query in a priority queue based on the priorities. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for queueing stages of the query execution graph of the query in a priority queue based on the priorities. In an aspect, for example, as described above with reference to <FIG>, the resource tuner <NUM> may estimate the cost of a job with different resource allocations by simulating the execution of different stages in the job manager <NUM>. For example, in an aspect, the resource tuner <NUM> may put all stages, along with their priorities in a priority queue.

Optionally, computing the tight resource requirement at <NUM> may further include processing the priority queue comprising scheduling any stages at a top of the priority queue based on an availability of resources. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may process the priority queue comprising scheduling any stages at a top of the priority queue based on an availability of resources. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for processing the priority queue comprising scheduling any stages at a top of the priority queue based on an availability of resources. In an aspect, for example, as described above with reference to <FIG>, the resource tuner <NUM> may schedule the stage at the top of the queue as soon as resources are available.

Optionally, computing the tight resource requirement at <NUM> may further include, for each candidate resource allocation, estimating a cost of the processing of the priority queue. For example, in an aspect, the processor <NUM> and/or the query component <NUM> may, for each candidate resource allocation, estimate a cost of the processing of the priority queue. Accordingly, the processor <NUM> and/or the query component <NUM> may provide means for, for each candidate resource allocation, estimating a cost of the processing of the priority queue. In an aspect, for example, as described above with reference to <FIG>, the resource tuner <NUM> may implement cost simulation <NUM> over the priority-assigned stage graph of <FIG> for a resource allocation of <NUM> containers.

Referring to <FIG>, at <NUM> the method <NUM> includes transmitting a query to a serverless query processing system. For example, in the aspect of <FIG>, the processor <NUM>, the query component <NUM>, the communications component <NUM>, and/or the user interface component <NUM> may transmit a query to a serverless query processing system. Accordingly, the processor <NUM>, the query component <NUM>, the communications component <NUM>, and/or the user interface component <NUM> may provide means for transmitting a query to a serverless query processing system. In an aspect, for example, as described above with reference to <FIG>, a user <NUM> (which may be a person or an application) that interacts with the system <NUM> may send a query to the system <NUM>.

At <NUM> the method <NUM> includes skipping transmission, to the serverless query processing system, of an amount of resources required for an execution of the query, wherein the skipping is configured to cause the serverless query processing system to determine and allocate the amount of resources required for the execution of the query. For example, in an aspect, the processor <NUM>, the query component <NUM>, the communications component <NUM>, and/or the user interface component <NUM> may skip transmission, to the serverless query processing system, of an amount of resources required for an execution of the query, wherein the skipping is configured to cause the serverless query processing system to determine and allocate the amount of resources required for the execution of the query. Accordingly, the processor <NUM>, the query component <NUM>, the communications component <NUM>, and/or the user interface component <NUM> may provide means for skipping transmission, to the serverless query processing system, of an amount of resources required for an execution of the query, wherein the skipping is configured to cause the serverless query processing system to determine and allocate the amount of resources required for the execution of the query. In an aspect, for example, as described above with reference to <FIG>, the user <NUM> may not indicate the amount of resources required for the execution of the query. Instead, the system <NUM> may determine whether a query received from the user <NUM> is a recurring query or a no-recurring query. Further, a query compiler <NUM> may look up the insight service <NUM> and load the resource predictor model for a job, and pass the compiled AST along with the predictor model to a query optimizer <NUM>, which infers the peak resource requirement using the predictor model. For non-recurring jobs, the query optimizer <NUM> may invoke the resource tuner <NUM> that finds a tight resource allocation corresponding to an amount of resources that satisfy a performance requirement over the execution of the query.

At <NUM> the method <NUM> includes receiving results of the execution of the query from the serverless query processing system. For example, in an aspect, the processor <NUM>, the query component <NUM>, the communications component <NUM>, and/or the user interface component <NUM> may receive results of the execution of the query from the serverless query processing system. Accordingly, the processor <NUM>, the query component <NUM>, the communications component <NUM>, and/or the user interface component <NUM> may provide means for receiving results of the execution of the query from the serverless query processing system. In an aspect, for example, as described above with reference to <FIG>, a job scheduler <NUM> schedules the job with the peak resource requirement, and a job manager <NUM> outputs the results which may be provided back to the user <NUM>.

Optionally, the method <NUM> may further include transmitting, to the serverless query processing system, a selection of a mode of operation for the serverless query processing system to determine and allocate the amount of resources required for the execution of the query. For example, in an aspect, the processor <NUM>, the query component <NUM>, the communications component <NUM>, and/or the user interface component <NUM> may transmit, to the serverless query processing system, a selection of a mode of operation for the serverless query processing system to determine and allocate the amount of resources required for the execution of the query. Accordingly, the processor <NUM>, the query component <NUM>, the communications component <NUM>, and/or the user interface component <NUM> may provide means for transmitting, to the serverless query processing system, a selection of a mode of operation for the serverless query processing system to determine and allocate the amount of resources required for the execution of the query. In an aspect, for example, as described above with reference to <FIG>, the system <NUM> may provide compiler flags where the users <NUM> may choose to explicitly opt-in or opt-out of resource optimization on a per job basis.

Optionally, transmitting the selection of the mode of operation may further include indicating to the serverless query processing system whether to adaptively change the amount of resources during the execution of the query. For example, in an aspect, the processor <NUM>, the query component <NUM>, the communications component <NUM>, and/or the user interface component <NUM> may indicate to the serverless query processing system whether to adaptively change the amount of resources during the execution of the query. Accordingly, the processor <NUM>, the query component <NUM>, the communications component <NUM>, and/or the user interface component <NUM> may provide means for indicating to the serverless query processing system whether to adaptively change the amount of resources during the execution of the query. In an aspect, for example, as described above with reference to <FIG> and <FIG>, the user <NUM> may select the adaptive allocation <NUM>.

Thus, the described apparatus and methods introduce a novel way for serverless query processing optimization.

<FIG> illustrates an example computing device <NUM> including additional optional component details as those shown in <FIG>. In an example, the computing device <NUM> may include a processor <NUM> for carrying out processing functions associated with one or more of components and functions described herein. The processor <NUM> may include a single or multiple set of processors or multi-core processors. Moreover, the processor <NUM> may be implemented as an integrated processing system and/or a distributed processing system. In an aspect, for example, the processor <NUM> may perform the function of a query component <NUM> which may be configured to perform the function of any component described above, such as the user <NUM>, the resource predictor <NUM>, the resource tuner <NUM>, the resource shaper <NUM>, the workload insights service <NUM>, the query compiler <NUM>, the query optimizer <NUM>, the job scheduler <NUM>, the job manager <NUM>, or any other component described above.

The computing device <NUM> may further include memory <NUM>, such as for storing local versions of applications being executed by the processor <NUM>, related instructions, parameters, etc. The memory <NUM> may include a type of memory usable by a computer, such as random access memory (RAM), read only memory (ROM), tapes, magnetic discs, optical discs, volatile memory, non-volatile memory, and any combination thereof. Additionally, the processor <NUM> and the memory <NUM> may include and execute an operating system executing on the processor <NUM>, one or more applications, display drivers, etc., as described herein, and/or other components of the computing device <NUM>.

Further, the computing device <NUM> may include a communications component <NUM> that provides for establishing and maintaining communications with one or more other devices, parties, entities, etc. utilizing hardware, software, and services as described herein. The communications component <NUM> may carry communications between components on the computing device <NUM>, as well as between the computing device <NUM> and external devices, such as devices located across a communications network and/or devices serially or locally connected to the computing device <NUM>. For example, the communications component <NUM> may include one or more buses, and may further include transmit chain components and receive chain components associated with a wireless or wired transmitter and receiver, respectively, operable for interfacing with external devices.

Additionally, the computing device <NUM> may include a data store <NUM>, which can be any suitable combination of hardware and/or software, that provides for mass storage of information, databases, and programs employed in connection with examples described herein. For example, a data store <NUM> may be or may include a data repository for applications and/or related parameters not currently being executed by processor <NUM>. In addition, the data store <NUM> may be a data repository for an operating system, application, display driver, etc., executing on the processor <NUM>, and/or one or more other components of the computing device <NUM>.

The computing device <NUM> may also include a user interface component <NUM> operable to receive inputs from a user of the computing device <NUM> and further operable to generate outputs for presentation to the user (e.g., via a display interface to a display device). The user interface component <NUM> may include one or more input devices, including but not limited to a keyboard, a number pad, a mouse, a touch-sensitive display, a navigation key, a function key, a microphone, a voice recognition component, or any other mechanism capable of receiving an input from a user, or any combination thereof. Further, the user interface component <NUM> may include one or more output devices, including but not limited to a display interface, a speaker, a haptic feedback mechanism, a printer, any other mechanism capable of presenting an output to a user, or any combination thereof.

Accordingly, in one or more examples, one or more of the functions described may be implemented in hardware, software, firmware, or any combination thereof. By way of example, and not limitation, such computer-readable media can comprise RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to carry or store desired program code in the form of instructions or data structures and that can be accessed by a computer. Disk and disc, as used herein, includes compact disc (CD), laser disc, optical disc, digital versatile disc (DVD), and floppy disk where disks usually reproduce data magnetically, while discs reproduce data optically with lasers.

Claim 1:
A method of serverless query processing, in a serverless query processing system comprising at least one processor and at least one memory, the at least one memory comprising instructions executed by the at least one processor to process queries, the method comprising:
receiving (<NUM>) a query;
determining (<NUM>) whether the query is a recurring query or a non-recurring query;
predicting (<NUM>), in response to determining that the query is the recurring query, a peak resource requirement (<NUM>) during an execution of the query, the peak resource requirement being predicted based on a query specific predictor model learned from data from previous executions of the query;
computing (<NUM>), in response to determining that the query is the non-recurring query, a tight resource requirement (<NUM>) corresponding to an amount of resources that satisfy a performance requirement over the execution of the query, starting from an original resource-cost curve;
allocating (<NUM>) resources to the query based on an applicable one of the peak resource requirement or the tight resource requirement;
starting (<NUM>) the execution of the query using the resources; and
dynamically updating the allocation of the resource for a remainder of the execution of the query based on a query execution graph (<NUM>) of the query, including re-computing the applicable one of the peak resource requirement or the tight resource requirement based on the query execution graph; and
releasing any excess resources.