HYBRID COST MODEL FOR EVALUATING QUERY EXECUTION PLANS

Aspects of the disclosure include hybrid cost model-based techniques for evaluating query execution plans. A non-limiting example method includes inputting, to a plurality of base cost models including one or more learned cost models and a classic cost model, a query and a search space including a plurality of candidate query execution plans. Each base cost model outputs a predicted execution time or cost for each plan of the plurality of candidate query execution plans and a real execution time for each plan is determined. The method includes generating a training label including the query and a model of the base cost models having a highest correlation between the predicted and real execution times and training a query classifier on training data including the training label to predict which base cost model of the plurality of base cost models is a most suitable cost model for planning a given query.

The following disclosure(s) are submitted under 35 U.S.C. 102(b)(1)(A):

BACKGROUND

The present disclosure generally relates to relational database management, and more specifically, to computer systems, computer-implemented methods, and computer program products for providing a hybrid cost model for evaluating query execution plans.

A relational database management system (RDBMS) often relies on structured query language (SQL) to manage data stored in a relational database. An RDBMS may typically include single column statistics that are usually collected on individual columns in a so-called relation. A relation may include tuples and/or attributes that describe the relationship(s) and/or the defining feature(s) in a table or between tables in a relational database. For example, a relation can include data values on a table and the relational database may store the data values as relations or tables. A collection of relations or tables may be stored on a database as a relational model.

Queries can be executed against a relational database using an RDBMS. A query refers to a specific request or command issued to the RDBMS to retrieve, manipulate, and/or update data stored in a relational database. Queries allow users to interact with the database and to perform various operations such as retrieving specific records, filtering data based on certain criteria, aggregating information, joining tables, and modifying data. Queries are typically written using SQL, which provides a standardized syntax and set of commands to interact with the database.

While all query plans for a given query are equivalent in terms of their final output, each will vary in execution cost, which is the amount of time and resources needed to run a respective query. The cost difference across query plans can be several orders of magnitude large. Therefore, when a query is executed, a query optimizer (often itself a component/module of the RDBMS) analyzes the query and determines the most efficient execution plan. To determine the most efficient plan, the query optimizer examines alternative plans and searches for the cheapest one in terms of execution cost. The cheapest query plan is often referred to as the optimal query plan.

In a typical architecture, a query plan is constructed bottom-up by the plan operators as building blocks, with each operator associated with a certain estimated cost (e.g., an amount of hardware resources utilized, an elapsed time, etc.). The overall cost of a given plan is the accumulated cost resulting from all plan operators involved when suitably accounting for portions of the query that are executed (if, e.g., elapsed time is used to cost the query). To select an optimal query plan, a query optimizer uses a cost model to evaluate several alternative query plans in its search space. The plan with the minimum estimated cost is typically selected for executing the query.

SUMMARY

Embodiments of the present disclosure are directed to hybrid cost model-based techniques for evaluating query execution plans. A non-limiting example method includes inputting, to a plurality of base cost models including one or more learned cost models and a classic cost model, a query and a search space including a plurality of candidate query execution plans. Each base cost model outputs a predicted execution time or cost for each plan of the plurality of candidate query execution plans and a real execution time for each plan is determined. The method includes generating a training label including the query and a model of the base cost models having a highest correlation between the predicted and real execution times and training a query classifier on training data including the training label to predict which base cost model of the plurality of base cost models is a most suitable cost model for planning a given query.

Other embodiments of the present disclosure implement features of the above-described method in computer systems and computer program products.

Additional technical features and benefits are realized through the techniques of the present disclosure. Embodiments and aspects of the disclosure are described in detail herein and are considered a part of the claimed subject matter. For a better understanding, refer to the detailed description and to the drawings.

The diagrams depicted herein are illustrative. There can be many variations to the diagram or the operations described therein without departing from the spirit of the disclosure. For instance, the actions can be performed in a differing order or actions can be added, deleted or modified.

In the accompanying figures and following detailed description of the described embodiments of the disclosure, the various elements illustrated in the figures are provided with two or three-digit reference numbers. With minor exceptions, the leftmost digit(s) of each reference number correspond to the figure in which its element is first illustrated.

DETAILED DESCRIPTION

Queries can be executed against a relational database using a relational database management system (RDBMS). When a query is received by the RDBMS, a query optimizer (often itself a component/module of the RDBMS) analyzes the query and determines the most efficient execution plan. In a typical architecture, a query optimizer uses a so-called classic cost model (CCM) to evaluate several alternative query plans in its search space. The plan with the minimum estimated cost is typically selected for executing the query.

The CCM uses statistics from the underlying data, as well as environmental specifications such as hardware and concurrency settings, in making cost estimations. In many configurations, the CCM estimates the cost of each operator and accumulates the costs of all operators in the plan to estimate the total cost. To arrive at an optimal plan with the lowest total cost, the CCM relies, in particular, on the size of the data flowing through each operator, also known as the “cardinality”. However, the true cardinalities are typically unknown at compile-time. Therefore, the query optimizer and/or CCM uses various methods to estimate cardinality.

The purpose of cardinality estimation is to predict the number of rows that a query is likely to process through each plan operator without executing the query plan. The query optimizer uses the result of the cardinality estimate to compute the total cost of the alternative plans and ultimately select the best one (that is, the plan with the lowest cost). Unfortunately, cardinality estimation is not always accurate, because realistic databases hardly satisfy the assumptions of independence and uniformity which are typically assumed in classic estimation methods. As a result, the CCM may lead the query optimizer to choose poor query plans.

The inaccuracy in cardinality estimates and the simplifying assumptions used in CCMs have motived an outpouring of research in the area of Machine Learning (ML) based cost estimation. ML-based models, also referred to as learned cost models (LCMs), do not rely on cardinality estimations and do not require simplifying assumptions; instead, these models estimate the cost by learning from runtime. Similar to any other ML-based methods, however, LCMs are likely to produce poor estimates when the sample is not drawn from the distribution represented by the training data. In other words, while LCMs can improve the average performance of a query optimizer, their accuracy can be poor for queries and plans that they have not seen in training. Therefore, ML-based LCMs are likely to generate poor plans if there are no mechanisms in place to handle out-of distribution samples.

This disclosure introduces new methods, computing systems, and computer program products for providing a hybrid cost model for evaluating query execution plans. Rather than relying solely on the CCM, or on an LCM, the hybrid cost model described herein leverages a meta-ensemble model, referred to herein as a query classifier, to route queries to LCMs (ML-based cost models) only when those models are expected to outperform the CCM. In some embodiments, this is achieved by training the query classifier to take queries as input and to output, for a respective query, a prediction as to which cost model (e.g., CCM, LCM 1, LCM 2, etc.) would produce the most accurate cost estimations. The query can then be routed to the corresponding model for costing the alternative plans. In this manner, the hybrid cost model can strike a balance between the available LCMs and the CCM that finds, for each query, the best performance available amongst the LCMs and CCM.

A query execution plan architecture that leverages a hybrid cost model having a query classifier in accordance with one or more embodiments described herein offers various technical advantages over prior approaches to evaluating query execution plans. Unlike prior approaches, the query classifier described herein ensures that each query is routed to the best available model for costing the alternative plans. Notably, when the available LCMs cannot outperform the CCM for a given query, that query can bypass the LCMs and fall back to a CCM-based cost estimation, meaning that edge-cases (e.g., those having out-of distribution samples) with typically poor LCM performance are natively avoided. Other advantages are possible.

For example, a set of LCMs can be trained to specialize on certain classes of queries. In this manner the LCMs and CCM can make up a collection of “base models” to handle a variety of cost estimation tasks. In some embodiments, alternative plans for each query in a training set are evaluated using each of the base models. The quality of the cost estimates generated by each model is determined by evaluating the correlation between the respective estimates and runtime. Advantageously, each query can then be labeled by the base model that produces cost estimates with the highest correlation to runtime. The query classifier (itself a sort of classification model) can then be trained on the labeled data (that is, a corpus of training query-best model pairs) to take queries as input and to predict which base model(s) would produce the best plan. In short, the hybrid cost model architecture described herein benefits from the advantage of using specially-built LCMs while minimizing regressions by falling back on the CCM when necessary. This hybrid cost model architecture proposes a query classifier that learns to route queries to a base cost model (either learned or classic) that is expected to provide estimates with a higher correlation with runtime.

It is to be understood that the block diagram of FIG. 1 is not intended to indicate that the computing environment 100 is to include all of the components shown in FIG. 1. Rather, the computing environment 100 can include any appropriate fewer or additional components not illustrated in FIG. 1 (e.g., additional memory components, embedded controllers, modules, additional network interfaces, etc.). Further, the embodiments described herein with respect to the computing environment 100 may be implemented with any appropriate logic, wherein the logic, as referred to herein, can include any suitable hardware (e.g., a processor, an embedded controller, or an application specific integrated circuit, among others), software (e.g., an application, among others), firmware, or any suitable combination of hardware, software, and firmware, in various embodiments.

Systems for providing and training a hybrid cost model for evaluating query execution plans are now described with reference to FIGS. 2 and 3. FIG. 2 depicts a block diagram of components of the hybrid cost model 150 of FIG. 1 according to one or more embodiments described herein. In some embodiments, the hybrid cost model 150 includes two key components: a set of base cost models 202 and a query classifier 204. The subsequent sections elaborate on these components in greater detail.

The Learned Cost Models

In some embodiments, the base cost models 202 are composed of one or more LCMs 206 (here, LCM #1, LCM #2, . . . , LCM #n), along with a CCM 208. In some embodiments, each learned cost model of the LCMs 206 can be trained to predict plan execution times for a certain class of queries. In some embodiments, each learned cost model can be trained to predict plan execution times for a unique class of queries, although some degree of overlap between the scope of learned cost models is within the contemplated scope of this disclosure.

In some embodiments, the classes of queries can be defined based on their level of complexity (e.g., a number of join and local predicates, number and presence of aggregations, etc. define the classes), based on their coverage of the database schema (subsets of the schema define the classes), based on data statistics, based on their respective configuration, application, and/or workload characteristics, and/or a combination of these factors or other factors. Alternatively, a single learned cost model can be trained on all classes of queries (that is, “n” can be one, although this configuration is not separately shown). The choice of model granularity comes down to balancing the benefits of model specialization versus the risk of severe over-fitting to a certain class(es).

FIG. 3 shows a process 300 to train a learned cost model 302 (itself any or all of the LCMs 206 described with respect to FIG. 2) in accordance with one or more embodiments. As shown in FIG. 3, given a query 304 (observe that, while the following discussion is largely in view of a single query, the overall process can be repeated as described for any number of queries and such discussion is otherwise omitted for clarity), one or more potentially optimal query plans (candidate plans) can be generated via query plan generation 306 using various techniques. In some embodiments, candidate plans are generated according to (in whole or in part) hints or hint sets 308. In some embodiments, the hint sets 308 enable and/or disable certain operators in the plan (e.g. enable nested loop join, disable index access, etc.). In this manner, hint sets 308 help ensure a diversity in plans used for training in such a way that local optimums, which can potentially be the true optimum, are included in the training data. Hint sets 308 can include, for example, Hint 1: {merge join, nest loop join, hash join, index scan, table scan}, Hint 2: {merge join, nest loop join, hash join, table scan}, Hint 3: {merge join, nest loop join, hash join, index scan}, Hint 4: {nest loop join, hash join, table scan}, Hint 5: {nest loop join, hash join, index scan}, Hint 6: {nest loop join, hash join, index scan, table scan}, Hint 7: {merge join, nest loop join, table scan}, Hint 8: {merge join, nest loop join, index scan}, Hint 9: {merge join, nest loop join, index scan, table scan}, Hint 10: {nest loop join, table scan}, Hint 11: {nest loop join, index scan}, and Hint 12: {nest loop join, index scan, table scan}. Other hints are possible and within the contemplated scope of this disclosure. Note that, upon using each of these hints, the operators included in the set are enabled and other operators are disabled. In some embodiments, candidate plans are generated randomly (random plan generation). In some embodiments, candidate plans are generated using a combination of random generation, hints, and/or any other technique that can diversify the plans to be used for model training.

As further shown in FIG. 3, in the next step, the query 304 is executed using each of the generated plans, and these real execution times are collected as labels for the respective learned cost model (as shown, runtime labeling 310). Concurrently, or separately, features required to represent plan trees and to train the cost model to learn the associations between patterns in the plan trees and runtime are extracted from the query 304 (as shown, feature extraction 312). For example, in some embodiments, the query 304 is encoded into a vector(s) of numeric values that are consumable by machine learning architectures (e.g., the learned cost model 302). In some embodiments, the encoding captures information about the base tables, local predicates, join predicates, correlations, skewness of predicate columns, etc., of the query 304.

In some embodiments, the extracted features are used for plan representation (here, building plan representations 314). In some embodiments, a vectorized tree having a plurality of nodes is used as the representation of a query plan, where each node of the plan tree is or encodes a vector containing information about the operator type and the tables accessed. In some embodiments, a classic optimizer's chosen query execution plan is used to extract the operator type, cardinality estimation, and cost estimation for each node as a node feature vector. As used herein, a “classic” optimizer refers to the cost or rules-based query optimizer employed by an RDBMS. In some embodiments, a representation of each node is generated as the estimated cardinality and cost as well as a one-hot encoding of the operator types (not separately shown).

In some embodiments, the learned cost model 302 includes an architecture having multiple layers of a Tree Convolutional Neural Net (TCNN) 316, configured to receive the plans from building plan representations 314. In some embodiments, the TCNN 316 is an extension of Convolutional Neural Nets (CNNs) for processing binary tree-structured data. In some embodiments, the TCNN 316 (also referred to as the TCNN model or TCNN module) takes the vectorized plan tree as input and learns kernels that capture the relationship(s) between the parent nodes and the child nodes. In some embodiments, the TCNN 316 produces a new vectorized tree. In some embodiments, the nodes of this tree are then aggregated into a one-dimensional vector by dynamic pooling. In some embodiments, the vector produced by the TCNN module is fed to a Multilayer Perceptron (MLP) 318, which, in its final layer, predicts the execution time. Alternatively, or in addition, in some embodiments, query level information (e.g., query features from feature extraction 312) is processed using one or more fully connected layers of the MLP 318 and the resultant vector is combined with the plan level information (e.g., a plan representation from building plan representations 314) and fed to the TCNNs 316.

As further shown in FIG. 3, in some embodiments, the learned cost model 302 is trained by creating a number of plans (refer to query plan generation 306), iterating through the respective plan tree and corresponding real execution times for each plan, using the learned cost model 302 to predict the execution time given a query plan (here, the predicted runtime 320), and updating the learned cost model 302 (e.g., update weights of the layers of the MLP and/or TCNN) to reduce the difference between the real and predicted execution times. While not meant to be particularly limited, prediction accuracy can be improved, for example, using loss functions such as cross-entropy loss for classification tasks, back-propagation, and error computing (e.g., mean squared error, etc.) (jointed referred to as error computing and back-propagation 322). In some embodiments, this overall process can be repeated for any number of queries. In some embodiments, each query will share some or all of the underlying characteristics for which the respective learned cost model is being trained to target (that is, the type of query for which the respective learned cost model is optimized).

The process 300 can be repeated to train any number of learned cost models (any or all of the LCMs 206 described with respect to FIG. 2). In some embodiments, the process 300 is repeated to train multiple learned cost models, each based on application, query, and/or workload characteristics. In some embodiments, each of the learned cost models is trained based on a different combination of application, query, and/or workload characteristics.

The Query Classifier

Referring again to FIG. 2, the hybrid cost model 150 includes a query classifier 204. In some embodiments, the query classifier 204 is trained to determine which cost model of the base cost models 202 should be used for planning a given query 210.

In some embodiments, the query classifier 204 takes a representation of query-level features of a query 210 as input (here, query encoding 212), which complements information from plan-level features (here, plan encoding 214) sourced from a query plan generation module (here, query plan generation 306) with or without hint sets 308. Query and plan encoding can be completed in a similar manner as described with respect to FIG. 3. For example, in some embodiments, query encoding 212 uses the structural information of a respective query's join graph and encodes information about the tables, local predicates, join predicates, aggregations, etc. (that is, query representations are produced using a join graph structure), and plan encoding 214 encodes machine-interpretable features of each respective plan. Notably, the encoded representation of the query is agnostic to the plan (join orders and plan operators) that will be used to execute the query.

In some embodiments, a label generator 216 generates the labels required for training the query classifier 204. In some embodiments, the label generator 216 collects predicted execution times from the one or more corresponding LCM(s) 206 and the estimated cost from the CCM 208. In some embodiments, for each query (e.g., the query 210), the label generator 216 computes a correlation value or metric between the estimated value from each base model and the actual (real) runtime. For example, in some embodiments, the label generator 216 computes, for each query, the Pearson correlation between the estimated value (the predicted execution time or cost) from each base model and the actual runtime.

In some embodiments, the query classifier 204 is configured to output or otherwise identify the model of the base cost models 202 with the highest correlation with runtime as the most suitable for the respective query 210. In some embodiments, the identified model (i.e., the “best” model in this context) having the highest runtime correlation is paired to the respective query, for example in a 2-tuple. This process can be repeated for any number of queries to generate an arbitrary number of query-best model labels. In some embodiments, each query can be labeled with the respective base model having the maximum Pearson correlation among all base cost models 202.

In some embodiments, the query representations (refer to query encoding 212) and the labels (refer to label generator 216) are used to train the query classifier 204 to learn to predict the most suitable cost model for a given query. In some embodiments, a final layer of the query classifier 204 uses a SoftMax activation function, which produces a likelihood of superiority of each base model. In this manner, the output values can alternatively be used as weights. In other words, in scenarios where the query classifier 204 reports similar (within any desired threshold) predictions (scores) for two or more models, the predictions made by those models can be combined in a weighted fashion rather than simply choosing one and discarding the other.

Implementation at Runtime

In some embodiments, the trained query classifier 204 can be leveraged for optimal plan selection at runtime. To illustrate, consider an incoming query 210. Query plan generation 306 might generate 10 (or more, or fewer, as desired) candidate plans for this particular query. These 10 plans can be evaluated using the base cost models 202 (LCM #1, LCM #2, . . . , LCM #n and the CCM 208) as routed via the query classifier 204 as previously described. For example, the query classifier 204 can apply pre-trained model weights to the set of “selected plans” that each model thinks is the “best” plan (that is, the plan having the most optimal query execution metrics among the candidate plans) to identify a selected plan 218. In some embodiments, the selected plan 218 can then be executed using an execution engine 220 and, advantageously, the query 210 can thus be resolved using the plan selected by the most correlated (accurate) LCM, CCM, or weighted combination of LCMs and CCMs.

New Learned Cost Model Identification

Observe that any time the CCM 208 is selected as the best model (meaning that the CCM 208 is predicted to outperform the LCMs 206), the practical meaning is that the current selection of LCMs 206 was not able to handle the particulars of the respective query. In some embodiments, this scenario is treated as an edge case for identifying opportunities for new LCMs. For example, in some embodiments, one or more features of the encoded queries and/or respective plans are used to train a new, dedicated LCM for this particular type of query (refer to FIG. 3). In this manner, the selection of LCMs will increase over time to accommodate an ever-increasing range of queries without needing to fall back to the CCM 208.

Referring now to FIG. 4, a flowchart 400 for evaluating query execution plans using a hybrid cost model is generally shown according to an embodiment. The flowchart 400 is described in reference to FIGS. 1-3 and may include additional blocks not depicted in FIG. 4. Although depicted in a particular order, the blocks depicted in FIG. 4 can be rearranged, subdivided, and/or combined. In exemplary embodiments, the method 400 can be performed by a computing environment (e.g., computing environment 100 shown in FIG. 1).

At block 402, the method includes inputting, to a plurality of base cost models including one or more learned cost models and a classic cost model, a query and a search space including a plurality of candidate query execution plans. In some embodiments, the learned cost models are trained to estimate, for an input comprising a query and one or more plans, an execution time for each plan. In some embodiments, the classic cost model is configured to calculate the expected execution cost based on the estimated cardinalities and other characteristics of an input query plan's operators.

In some embodiments, each of the one or more learned cost models are trained to predict plan execution times for a specific class of queries. In some embodiments, the specific class of queries is defined based on at least one of a level of complexity, data statistics, a coverage of the database schema, configuration, application and workload characteristics, and a combination thereof.

At block 404, the method includes outputting, from each base cost model of the plurality of base cost models, a predicted execution time or cost for each plan of the plurality of candidate query execution plans.

At block 406, the method includes determining a real execution time for each plan of the plurality of candidate query execution plans.

In some embodiments, the method includes determining, for each predicted execution time for each plan made by each base cost model, a correlation metric between the predicted execution time and the real execution time. In some embodiments, the correlation metric includes a Pearson correlation between the respective predicted execution time or cost and the real execution time.

In some embodiments, the method includes ordering the determined correlation metrics to identify the model of the base cost models having a highest correlation between the predicted execution time and the real execution time for the respective query.

At block 408, the method includes generating a training label including the query and a model of the base cost models having a highest correlation between the predicted execution time and the real execution time for the respective query. In some embodiments, this process is repeated for any number of queries to generate a corpus for training labels (that is, to generate training data of any desired size).

At block 410, the method includes training a query classifier on training data including the training label to predict which base cost model of the plurality of base cost models is a most suitable cost model for planning a given query.

In some embodiments, the method includes receiving, at runtime, a new query. In some embodiments, the method includes selecting, using the trained query classifier, the most suitable cost model of the plurality of base cost models for planning the new query.

In some embodiments, the method includes executing the new query against a database using an optimal plan selected by the most suitable cost model.

Various embodiments of the disclosure are described herein with reference to the related drawings. Alternative embodiments of the disclosure can be devised without departing from the scope of this disclosure. Various connections and positional relationships (e.g., over, below, adjacent, etc.) are set forth between elements in the following description and in the drawings. These connections and/or positional relationships, unless specified otherwise, can be direct or indirect, and the present disclosure is not intended to be limiting in this respect. Accordingly, a coupling of entities can refer to either a direct or an indirect coupling, and a positional relationship between entities can be a direct or indirect positional relationship. Moreover, the various tasks and process steps described herein can be incorporated into a more comprehensive procedure or process having additional steps or functionality not described in detail herein.