Query optimization is a pivotal part of every database management system (DBMS) since it determines the eficiency of query execution. Numerous works have introduced Machine Learning (ML) techniques to this field, but few of them are proven practical due to long training time, lack of interpretability, and integration cost. A recent study provides a practical method to optimize queries by recommending per-query hints but it sufers from two inherited problems. First, it follows the regression framework to predict the absolute latency of each query plan, which is very challenging because the latencies of query plans for a certain query may span multiple orders of magnitude. Second, it requires training a model for each dataset, which restricts the application of the trained models in practice.
SQL hint, query optimization, learning-to-rank, representation learning
© 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License finite set of hint sets are predefined and all hint sets result
dinality estimation, end-to-end query optimization, etc., the accuracy of fast query plans for the accuracy of slow
pling [5] to recommend SQL hints. These hints ofer
adtional neural networks (TCNN) [
Query optimization is vital to the performance of every database management system (DBMS). A SQL query typically has many candidate plans that are equivalent in terms of final output but difer a lot in execution latency.
The goal of query optimization is to select the candidate plan with the lowest latency for each query from a vast search space with suficient accuracy.
Query optimization has been studied for decades [
0000-0003-2447-4107 (X. Xu); 0000-0001-6473-8205 (Z. Zhao); mate the Cost Orders of query plans to cOOperate with DBMS leveraging Learning-To-Rank (LTR) techniques.
COOOL is designed on top of an existing DBMS, and we
make similar assumptions as Bao in order to inherit its
advantages for practical applicability: we assume that a
in semantically equivalent query plans. We leverage the
widely used TCNN [
gression approach has a dimensional collapse [16] in the
LTR is a supervised learning framework to train mod- plan embedding space. Whereas COOOL does not have a els for ranking tasks. There are primarily three categories dimensional collapse using the same embedding method. of LTR approaches: pointwise, pairwise, and listwise.
The dimensional collapse will hurt the performance of Most pointwise methods are the same as the regression ML methods in building a unified model because the colparadigm. Pairwise methods concern the relative order lapsed dimensions may be diferent for diferent datasets. between two items, and listwise methods focus on the This can result in features learned from one dataset beorder of items in the entire list. The three approaches coming noise when applied to another dataset. Furthercan be applied to most existing models, e.g., neural netmore, Bao requires more efort to implement because it is works, and the only diference lies in the loss function. fully integrated into PostgreSQL, while COOOL is built To train an LTR model for query optimization, we use the on top of PostgreSQL. orders of latencies as labels, which has the potential to be more robust than regression models against the large range of orders of magnitude in query plan latencies.
By transforming the absolute cost estimation problem into relative cost order prediction, COOOL can utilize LTR techniques to train the TCNN so that the output tells which plan is the best. In this paper, we investigate the performance of pairwise (COOOL-pair) and listwise (COOOL-list) approaches on SQL hints recommendation for query optimization.
COOOL methods (LTR approaches) have advantages over BAO (regression approach) for the following reasons. (1) Accurately estimating the cost of every query plan is not necessary since the optimizer only needs to select one of them to execute. A higher accuracy for a regression-based model does not always lead to the optimal plan selection because improving the accuracy on the slow query plans does not directly help. On the contrary, predicting the cost orders of query plans with high accuracy is more likely to help find the optimal one, which is exactly the objective of LTR. (2) Predicting the exact cost of a plan is extremely dificult. The plan execution latency ranges from several milliseconds to thousands of seconds. Minor structure diferences in semantically equivalent plans may lead to large latency diferences. The regression paradigm aims to minimize 2 error, but the squared error formula is sensitive to anomalous large or small latencies, making model performance unstable [14]. Even though normalization can alleviate this, it may distort the latency distribution. By contrast, LTR approaches focus on the cost orders rather than the exact costs, which can alleviate the impact of outlier-prone data distributions.
We compare COOOL and BAO on both single-dataset tasks and multiple-dataset tasks and provide elaborate analysis on how to maintain a unified model to improve query plans from multiple datasets. Our experiments in various settings, achieving as large as 6.09× total query execution speedup over PostgreSQL on single-dataset tasks and 6.73× speedup on multiple-dataset tasks. Moreover, we investigate the regression framework and ranking strategies from the perspective of representation To summarize, we make the following contributions: • We propose COOOL, a learned model that predicts Cost Orders of the query plans to cOOperate with DBMS by LTR techniques, to recommend better SQL hints for query optimization. To our best knowledge, it is the first end-to-end query optimization method that maintains a unified model to optimize queries from multiple datasets. • We theoretically show that COOOL can distinguish between good and bad query plans when optimizing the loss functions, and verify that COOOL is superior to regression approaches from the representation learning perspective. • Comprehensive experiments on
join-orderbenchmark and TPC-H show that COOOL can outperform
PostgreSQL and
state-ofthe-art methods on multiple dimensions of evaluation criteria on both single-dataset and multiple-dataset tasks. 2. Preliminaries (1) (2) show that COOOL can consistently improve query plans is a function that takes the candidate plan tree as input learning [15]. We show that the model trained by the re- highest predicted ranking score in the scenario of LTR.
hint set Let {
1, hint set denote the set of queries and 2, … , } be the set of hint sets.
ℋ
= Each ∈ ℋ contains only boolean flag SQL hints (e.g., enable hash join, disable index scan). For any query ∈
and ∈ {1, 2, … , } , the traditional optimizer can generate the corresponding plan tree with the = (,
).
Let = { 1 , 2 , … , } denote the set of candidate plans of query . The query plans in are semantically equivalent, but may have diferent execution latencies. A model and produces a score for the plan tree.
= (, ; )⃗, where ⃗ is the parameter of the model to be trained. The query execution engine then selects the plan with the ̂ = arg max , where ̂
responding to the minimum estimated cost. 2.2. Learning-To-Rank (LTR) wise loss function also coincides with the listMLE loss by [21]. [21] proved that this loss function is consistent, which means as the size of the dataset goes to infinity,
To apply a pairwise loss function, the full rankings is the hint set with the maximum score, cor- the learned ranking converges to the optimal one. LTR is a machine learning approach aiming to auto- for all ∈ need to be converted to pairwise comparmatically rank items based on their relevance or impor- isons. This process is called rank-breaking [22]. A ranktance [17]. It is a natural approach for the SQL hint recommendation task, which selects the optimal query plan for execution, as shown in Equation (3).
In the context of LTR, ℋ is the set of items, and the breaking method defines how the full rankings should be converted to pairwise comparisons. Basic breakings include full breaking, adjacent breaking, and others [22].
Full breaking means extracting all pairwise comparisons goal is to recommend the best item from ℋ for each ∈ . from a ranking, and adjacent breaking means extracting (3) ’s (5) (6) denote the total order of query plans w.r.t. where ’s are functions of the parameter ⃗ defined in Equation (2). The rankings of multiple queries are assumed to be independent. Therefore, the probability of multiple rankings is simply the product of the probability of each individual ranking. The marginal probability of
PrPL(
≻ ; )⃗ = exp( ) exp( ) +exp( )
.
Given the training data { |∀ ∈ }
, the listwise loss function is simply the negative log-likelihood function: ℒlist( )⃗ = − ∑ ln PrPL( ; )⃗, ∈ has the highest latency. hand, full breaking is proven consistent [22, 23]. Other only adjacent pairwise comparisons. For example, given a ranking 1 ≻ 2 ≻ 3, full breaking converts it to ( 1 ≻ 2, ( 1 ≻ 3, 2 ≻ 3) while adjacent breaking converts it to 1 ≻ 2, 2 ≻ 3). Though adjacent breaking is simple and plausible, [22] proved that adjacent breaking can lead to inconsistent parameter estimation, which means that even if the model is trained using an infinite amount of data, it may not make unbiased predictions. On the other breakings are more complicated and beyond the scope of this paper, so we employ the full breaking strategy.
Let = { 1, 2, … , } be the dataset of pairwise comparisons, where ∀ ∈ {1, 2, … , } , has the form of 1 ≻ . Here denotes the corresponding query for 2 . For diferent values, may refer to the same query since diferent pairwise comparisons can be extracted from the same query. The objective function is =1 ℒpair( )⃗ = − ∑ ln PrPL( ; )⃗, (7) where PrPL( ; )⃗ is defined in Equation (5). The model parameter can be estimated by maximizing pair( )⃗ .
This is equivalent to maximizing the composite marginal log-likelihood based on Equation (5). [24] and [23] proved that ⃗can be eficiently estimated under a consistent rank breaking method. And full breaking, which extracts all pairwise comparisons from the full rankings, is one of the consistent breaking methods.
The data flow pipeline of COOOL is shown in Figure 1, where model-related modules are shown in green, and existing DBMS modules are displayed in blue. Given a query (SQL), we use the hint sets in ℋ to generate the corresponding query plans 1, 2, … , (with possible duplicates). At the training stage, we execute plans and training inference interface
Query Optimizer ! # ⋯ " ! # ⋯ " Result
Execution Engine collect their performance as training data. Then we utilize the pairwise or listwise approach to train the ranking scorer. At the inference stage, when a user submits a query, the traditional optimizer will generate query plans by utilizing the corresponding hint sets. Next, the scorer will compute the relative ranking score of each plan and recommends the optimal one for the execution engine to obtain results. For the models trained by diferent methods, they are exactly the same at the inference stage.
Though allowing fine-grained hints (e.g., allows nested loop joins between specific tables, others not.) are available, it will bring an exponential cansordt idate plan search space, which significantly increases training and inference overhead. We make the same assumption as Bao for practicality.
Bao requires more efort to implement because it is fully integrated into PostgreSQL, while we build on top of PostgreSQL, which makes it easy for COOOL to migrate to other DBMSs. Moreover, we take a step forward to maintain a unified model to optimize queries from diferent datasets, which has not been investigated in the previous end-to-end query optimization studies.
The architecture of COOOL is shown in Figure 2, with model-related modules depicted in green, existing DBMS modules in blue, and training stages in red. We utilize the underlying DBMS optimizer to generate candidate plans using the hint sets in ℋ. Then we vectorize plan tree nodes and binarize the plan, facilitating TCNN application to acquire the plan embedding ⃗. Subsequently, we employ an MLP to compute the score of each plan, supporting either pairwise or listwise training loops.
Data Collection Our approach is trained in a standard
supervised learning paradigm. For the given queries, we
generate query plans that correspond to the hint sets
ℋ for each query by the underlying traditional optimizer. 4.1. Cost Order Estimation
Then we sent them to the execution engine and record
the observed execution performance of each query plan. Each hint set corresponds to a query plan tree, so
recomThe collected data is used to train the neural ranking mending the optimal hint set for given queries is to select
scorer, and the training stage is separate from the DBMS. the plan tree with the maximum ranking score, as shown
in Equation (3). Similar to [
Cost Order Estimation To execute the optimal plan
with minimum estimated latency, we need to recommend
its corresponding hint set to the DBMS. The scorer takes
a plan tree as input and outputs the ranking score of Plan Tree Vectorization We can use the EXPLAIN
the plan, the estimated latency orders can be acquired command provided by the underlying optimizer to
obby sorting the scores of all candidate plans. Specifically, tain the plan tree text, as shown in Equation (1). First,
we first transform the nodes of the input plan tree into we need to transform each node in the plan tree into a
vectors, then feed the vector tree into a plan embedding vector. The same as in [
plying each hint set to the given query will generate semantically equivalent plans. Besides, the hints are applied to the entire query rather than the partial plan.
One-hot Node Operation Type Encoding. We summarize the types of all operations (nested loop, hash join, merge join, seq scan, index scan, index only scan, and bitmap index scan) in the plan trees and number these seven operations. Then we create a vector for each node with the number of types of bits, and we set the bit of the type corresponding to each node to the high bit. For One-hot operation type
Card. Cost Aggregate
Loop Join Loop Join
Index Scan Loop Join
Index Scan Seq Scan
Index Scan !
" ! # ⋯ ⋯ # "
Loop Join
Null Loop Join
Index Scan Loop Join
Index Scan Seq Scan
Index Scan Pairwise Training Listwise Training ( #
TCNN ℒ!"#$ ⃗ ℒ%#&'
D e n s e
D
e
n
s
e
instance, ( ) is the one-hot encoding of node and introduced in plan representation in [6], and it was
well ( )[] = 1 indicates node is the -th operation type established in [
TCNN was proposed in [
the plan embedding vector as input and output a scalar as the ranking score , i.e., = MLP()⃗ . Stacking fully connected layers and non-linear activation functions in the MLP can enhance the representation ability, and this practice has been widely adopted in query optimizations [6, 14]. We add a hidden layer and an activation function for simplicity. The cost orders can be obtained by sorting the ranking scores of all candidate plans.
Finally, we can leverage plan embedding to compute the relative ranking score. We use a simple MLP to take 4.3.1. Theoretical Analysis obtain plan embedding by ⃗=
TCNN() , where ⃗∈ ℝ ℎ
During the inference stage, we use the learned model is the vector of plan representation and ℎ is the size of to compute the score for each candidate plan and sort the scores to obtain the corresponding orders, then we select the estimated best plan for each query to execute.
In this section, we briefly analyze how
COOOL learns from the order of latencies of diferent query plans. To show that, we consider the query plans { 1, 2, … , } with the corresponding latencies { 1, 2, … , } for a given query ∈ . Our goal is to select the best plan using the model.
At the training stage, they have diferent initial scores { 1, 2, … , }. Without loss of generality, we assume 1 > 2 > … > . We focus on the diference between the model outputs of adjacent query plans, we denote = +1 − , ∀ ∈ {1, 2, … , − 1} . For convenience, we define The loss function of the listwise approach can be written −1 =0 .
The training loop consists of three parts: data collec- 0 = 0. Then ∀ = {1, 2, … , } , we have = 1 + ∑ tion and deduplication, label mapping and pairwise data extraction, and model training and evaluation. as:
Let train denote the set of training queries. We generate plans for each query ∈ train by the traditional optimizer, as shown in Equation (1).
Then we sent the plans to the execution engine, and record each data point (query = , plan = , latency = ). There are duplicate query plans because, for a given query, diferent hints may result in the same query plan. We remove the duplicate query plans for pairwise and listwise training loops.
Because a lower latency indicates a better plan, we use the reciprocal of the latency of each query plan as the label to reverse the orders of query plans. Any other mapping function that reverses the orders works equivalently because only the orders matter.
After the label mapping, we get a list of query plans ordered by the reciprocals of their latencies for each query. For each list of query plans ( ≤ after dedu plication), we extract all ( ) pairwise comparisons to 2 1, 2, … , }, where for any get the pairwise data = { ∈ {1, 2, … , } , = 1 ≻ 2 .
At the training stage, the model parameter ⃗ is updated by optimizing the loss function. Specifically, for the listwise approach, the model parameter ⃗ is computed by minimizing the listwise loss defined in Equation (6). For the pairwise approach, ⃗ is computed by minimizing the pairwise loss defined in Equation ( 7). ℒ = − ln ∏ =1 ∑ exp(
−+1 ) −+1 exp( ) =1 = − ∑ ln = − ∑ ln =1 =1
− =1 =0 exp( 1 + ∑ − =0 ) ∑ −+1 exp( 1 + ∑ =1
−=10 ) − exp(∑=0 ) ∑ −+1 exp(∑−=10 ) =1 −+1 =1 −1 =0 = − ∑ (∑ − ln( ∑ exp(∑ ))) .
In this equation, the first equality is obtained by substituting Equation (4) in Equation (6), and the second equality is obtained by substituting with 1 + ∑ The third equality is obtained by dividing both the nuwith respect to for any ∈ {1, 2, … , − 1} : merator and denominator by exp( 1)since exp( 1) > 0. And the last equality is due to the property of the ln() function. Now we compute the partial derivative of ℒ −1 =0 .
ℒ − =1 = − ∑ (1 − ∑ ∑ −=++11 exp(∑−=10 )) < 0. −+1 exp(∑−=10 ) =1 (9)
The inequality holds because when 1 ≤ ≤ − , we have ∑ −+1 exp(∑−=10 ) <∑ =+1 −+1 exp(∑−=10 ).This =1 means ∀ ∈ {1, 2, … , } , an increase in leads to a decrease in the loss function ℒ . tends to go up while the loss function ℒ is minimized during the training process, which is desired. We omit the theoretical analysis of the pairwise approach, as it follows a similar logic to the listwise method.
To summarize, by minimizing ℒ or ℒ , the differences between the ranking scores of diferent query plans tend to increase, which means that our approaches are able to distinguish the best plans from others.
To intuitively demonstrate the efectiveness of our approaches, we present an illustrative example to explain how the regression and ranking strategies work based on Section 4.3.1.
Given the assumption that 1 > 2 > … > , where plan tree has the lowest latency represents the optimal plan. For the regression paradigm, the model endeavors to learn to minimize the gap between each of the model output score and the corresponding latency . The pairwise ranking strategy enables the model to learn to discriminate the preferable plan by assigning it a higher score, whereas the listwise ranking strategy allows the model to learn to provide the order score of each plan in the given plan list. Essentially, the regression and ranking strategies train the model to output ideal scores of plan trees under their respective training paradigms, whereby the optimal plan selection operation is accomplished through the procedure of sorting the model output scores. On the one hand, the three strategies have diferent objectives and train the model in diferent ways, while the goal of query optimization is to simply select the optimal single plan, which is the approach of the ranking strategies. On the other hand, for the scenario of unseen query plans, it may be dificult to predict the exact latency of the plans, yet predicting the orders of plans may alleviate this issue.
In summary, the proposed COOOL methods can effectively distinguish between better and worse plans to achieve excellent optimization performance.
Datasets and Workloads To promote reproducibility, we use two widely-used open-source datasets (IMDB, TPC-H) and their corresponding workloads (JOB, TPCH). To maintain a fair comparison, we do not alter the original queries. • TPC-H. TPC-H [27] is a standard analytical benchmark that data and queries are generated from uniform distributions. We use a scale factor of 10. There are 22 templates in TPC-H, we omit templates #2 and #19 because some nodes in their plan trees have over two child nodes, which makes tree convolution operation unable to handle. For each template, we generate 10 queries by the oficial TPC-H query generation program 1. Baseline Methods. We compare our proposed model with traditional and state-of-the-art (SOTA) methods as follows.
• PostgreSQL: We use the optimizer of PostgreSQL (version 12.5) itself with default settings. • Bao: We substantially optimize the Bao source code2 as follows. First, we use all 48 hint sets in Bao paper, rather than the 5 hint sets in the open-sourced code. Second, because we use the standard benchmarks without modifying queries, we train Bao on all suficiently explored execution experiences of the training set.
Model Implementation We use a three-layer TCNN and the number of channels are respectively set as {256, 128, 64}, the plan embedding size ℎ is 64, and the hidden size of MLP is set as 32. The activation function is Leaky ReLU [28], the optimizer is Adam [29] with an initial learning rate of 0.001, the batch size is 128, we apply an early stopping mechanism in 10 epochs on the training loss, we save the model that performed best on the validation set and report the results on the test set. The validation set is 10% of the training set, except for TPC-H “repeat” settings, where we use 20% of the training set. We implement our models in Pytorch 1.12.0.
virtual machine with 16 GB of RAM, an 8-core Xeon(R) Platinum 8260 2.4GHz CPU, and an NVIDIA V100 GPU.
For excellent PostgreSQL performance, we set PostgreSQL configurations suggested by PGTune 3 in this paper: 4 GB of shared bufers, 12 GB of efective cache size, etc. • Join Order Benchmark (JOB). JOB [26] contains 113 analytical queries, which are designed to stress test query optimizers over the Internet Movie Data Base (IMDB) collected from the real world. These queries from 33 templates involve complex joins (ranging from 3 to 16 joins, aver- 1https://www.tpc.org/tpc_documents_current_versions/current_ aging 8 joins per query). specifications5.asp 2https://github.com/learnedsystems/baoforpostgresql 3https://pgtune.leopard.in.ua/#/ Scenario Descriptions To comprehensively evaluate the performance of models, we examine three scenarios: single instance, workload transfer, and maintaining a model (i.e., a unified model). The first scenario is common in ML for query optimization, which refers to learning a model for each dataset. The others are not com- tings, we have two options for selecting test sets from monly studied but are crucial for ML model deployment the dataset: we can either randomly select templates/in the DBMS. Workload transfer indicates the scenario queries, denoted by rand, or choose the slowest temwhere a model is trained on one workload and evaulated plates/queries, referred to as slow. on another. The last scenario implies training a model to Therefore, we can establish four evaluation criteria for improve query plans from diferent datasets. a single dataset in a specific scenario. Definition of Latency and Speedup We repeat each experiment 10 times and exclude the best and the worst test results except for the unified model scenario, then we report the average performance of the rest runs. There are two aspects of performance we consider: one is latency, and the other is speedup. The total execution latency is defined as the sum of per-query execution latency. The speedup represents the acceleration ratio of executing queries with the ML model compared to using PostgreSQL’s default optimizer under the same PostgreSQL configurations. A speedup greater than 1 indicates that the model performs better than the default PostgreSQL optimizer.
Research Questions (RQs) We conduct extensive experiments to primarily answer the following RQs: • RQ1: can COOOL achieve the best performance compared to the baseline methods in terms of total query execution latency and improvement on slow queries? • RQ2: is it possible to directly transfer a schema
agnostic model to another dataset?
• RQ3: can the proposed methods improve query
plans from diferent datasets compared with
PostgreSQL by maintaining a unified model?
• RQ4: can the experiments provide some insight
on why COOOL methods are better than the
regression-based approach?
Model Performance Evaluation Criteria According
to the evaluation details in the previous works [
First, we consider two situations that frequently arise Observations In Table 1, there are four settings for in practical settings, which we refer to as adhoc and each of the two workloads and we observe that: repeat. The former refers to a common real-world sit- • The listwise approach (COOOL-list) achieves the uation where the test templates have not been covered best performance in most settings, and beats Bao in the model’s training set, we use queries from seven by large margins in almost all settings except for templates in the JOB dataset and four templates in the “repeat-rand” on JOB, where COOOL is slightly TPC-H dataset respectively as test sets for this setting. slower than Bao.
The latter represents the queries in the test data are “sim- • The pairwise approach (COOOL-pair) also outilar” to the queries in the training data, but not the same. performs Bao in almost all settings except for Here “similar” means the queries are from the same tem- “adhoc-rand” on TPC-H. It achieves the best perplates as in the training data. In practice, we take one formance on three settings (“repeat-rand” on JOB, or multiple queries from each template as the test set “adhoc-slow” and “repeat-slow” on TPC-H). In and keep the remaining queries in the training set. For most settings, the performances of COOOL-pair the JOB dataset, we take one query from each template and COOOL-list are similar. and for the TPC-H dataset, we take two queries from • Bao does not have the best performance under each template as test data. For queries from the same any of these settings. For “adhoc-slow” on JOB, template, we take their average latency to represent the Bao even has a total execution latency regression, corresponding template’s latency. which means the running speed is lower than the
Then, to substantially evaluate the general and tail PostgreSQL optimizer itself. latency query performance, we develop two methods to select the test sets. For both “adhoc” and “repeat” set
Combined with Figure 3, we have the following observations: • Bao is significantly worse than COOOL on some queries under “slow” settings (20c in “repeatslow” on JOB and template 9 in “repeat-slow” on TPC-H.). “Slow” settings are obviously more challenging for ML models than “rand” settings and COOOL has clear advantages over Bao. • Both COOOL and Bao are close to optimal on
“repeat-rand” scenarios for JOB and TPC-H data. • It happens that Bao or COOOL are not as good as PostgreSQL on a small number of queries, which is normal for ML models. Nevertheless, performance regressions occur less frequently on COOOL models than Bao models in most settings, and COOOL-pair has the lowest number of query regressions for these settings. See Table 2 for details.
To summarize, we observe that COOOL methods have advantages over Bao in speeding up total query execution, alleviating individual query performance regression, and optimizing slow queries. Besides, although COOOLlist is better than COOOL-pair in total query execution latency speedups, it is not as good in avoiding individual query regression.
It is widely acknowledged that an instance-optimized model may exhibit poor performance on another workload because it does not learn the patterns from the unseen data. Despite most ML models being schema specific, hindering model transferability, there is limited research on schema agnostic models. In this section, our goal is to provide an intuitive perspective on directly transferring a learned model to another workload. More concretely, we train a model on a source workload and then test its performance on another workload, namely target workload (source→target).
We conduct experiments on training on JOB data and evaluating the model on TPC-H data (JOB→TPC-H), as well as training a model on TPC-H data and evaluating its performance on JOB data (TPC-H→JOB). In these settings, we also consider the aforementioned “adhoc” and “repeat” scenarios under “rand” and “slow” settings. To make an intuitive comparison, we train the model on the source workload’s training set and show the performance on the target workload’s test set.
The overall query execution speedups are shown in Table 4, and we have the following observations. • The diference of the performances of models is unstable compared with the corresponding instance-optimized models, and most settings have a performance decline. Our experiments show that directly applying a model trained on one workload to another workload cannot obtain good performances even if the model is schema agnostic. • Compared with instance-optimized models, most models learned on TPC-H perform worse on JOB. By contrast, there is a performance improvement on “TPC-H adhoc” settings especially on “TPC-H adhoc-slow”. We may conclude that the data in JOB may benefit TPC-H and especially improve the performance of slow queries. We will provide a deeper analysis in Section 5.5.2. • We show the plan tree statistics for nodes and depth of the two workloads in Table 3. On the one hand, it indicates that JOB is more complicated than TPC-H, so directly transferring a model learned on JOB helps optimize queries from TPC-H. On the other hand, it suggests that data distributions in diferent datasets afect the performance of ML models in workload transfer, because the experiment results on “TPCH repeat” settings demonstrate that a model learned on the templates from JOB cannot achieve the same performance as that learned on the template from (a) JOB repeat-rand (b) JOB repeat-slow (c) TPC-H repeat-rand (d) TPC-H repeat-slow
Based on the observations, introducing JOB data has a better performance than the model trained on TPCH “adhoc” settings. We can conclude that for a given workload, using the training data from the same workload may not obtain satisfactory performance. Therefore, how to utilize data from other workloads is an emerging problem for query optimization models.
In this section, our objective is to explore whether it is possible to train a model on multiple datasets to improve query plans in comparison with PostgreSQL. Similar to the previous section, we consider the four scenarios for each dataset. For each scenario, the training data of JOB and TPC-H were combined as the new training set and the model is respectively evaluated on JOB and TPC-H test sets. The results are summarized in Table 5. We also depict queries with an execution latency greater than 1s on PostgreSQL. Combined with the observation in Figure 4, we can get the following conclusions: • The performances of both COOOL approaches are close to optimal. This echoes our observation that JOB training data help improve the model performances on TPC-H. • On the other hand, the model performances on
JOB test data are hurt by the TPC-H training data.
For example, both Bao and COOOL methods have poor performances on query 19d in Figure 4b. • In terms of the number of regressions in execution time, we list the results in Table 6. Both COOOLpair and COOOL-list perform better than Bao, and COOOL-list has the lowest number of query regressions for these settings.
The individual query performance in “repeat” settings of the unified models are shown in Figure 4, where we • COOOL-pair performs the best in all “adhoc” settings and COOOL-list performs the best in all “repeat” settings. They have similar overall performances, and outperform Bao in almost all scenarios. • COOOL-pair has the most performance boost when the model is trained using both JOB and Summary on Model Performances Diferent data TPC-H datasets (unified model) compared with distributions in diferent datasets is a challenge for a uniTable 1, especially on TPC-H where the unified ifed query optimization model, but COOOL models are model beats the single-instance model in three able to alleviate this issue to learn a unified model better out of four scenarios. than the SOTA regression approach to speed up total • Does a diferent training dataset help? We ob- query execution, alleviate individual query regression, serve that JOB data help improve the model per- and optimize slow queries. Our experiments have shown formance on TPC-H test data, especially under the overwhelming advantages of our proposed models. “adhoc” scenarios. While TPC-H training data do For the single instance scenarios, COOOL-list achieves not help improve the model performance on JOB the best performance in total query execution speedups test data under most scenarios. We believe this is while COOOL-pair is the best to reduce the number of because JOB queries are more complicated (more individual query regressions. When a unified model is nodes and larger depth than TPC-H queries as trained using multiple datasets, COOOL-list performs shown in Table 3). the best in “repeat” settings, while COOOL-pair is the best in “adhoc” settings and exhibits no total query execution performance regression. COOOL-pair is the best workloads in the scenarios of the single instance, workload transfer, and unified model.
JOB
Therefore, we can conclude that COOOL exhibits comparable practicality to Bao.
We have conducted extensive experiments and obtained promising results. But it is not clear how the ranking strategies afect the model training. This section aims to provide insight on why the two COOOL models outperform Bao, especially for the unified model training.
Let an ℎ-dimensional vector zi denote the embedding for query plan . We compute the covariance matrix approach among the three models in terms of performance and stability.
In COOOL methods, we use exactly the same plan representation model as Bao to confirm that the improvements are brought by our LTR methods. We analyze the “adhocslow” setting of the two workloads in this section.
We compare the space and time eficiency of our approaches and the SOTA method.
• Space complexity. The two COOOL models use a
TCNN with the same structure and hidden sizes sumption of the model is about 0.5MB, which is eficient enough in practice. • The number of training samples. Let denote the number of training queries. And there are candidate hint sets in ℋ for each query. The number of training samples of Bao is denote the number of unique query plans for each
. Let query given ℋ, where 1 ≤ ≤ , number of samples is Θ(∑=1 is 132,353, i.e., 529,412 bytes. The storage con- ∈ ℝ ℎ×ℎ for all plan embeddings obtained by the model.
Formally, 1 =1 =
∑(zi − z)(zi − z)⊤, where is the number of plans, z = 1 ∑=1 zi. Then, we apply singular value decomposition on s.t. = ⊤ where = (
). Then we can obtain the singular 2
value spectrum in sorted order and logarithmic scale
) (lg( )). We depict the singular value spectrum of the
plan embedding space of the three models learned in
diferent scenarios in “adhoc-slow” setting, as shown in
Figure 5. We have the following observations.
framework cannot. Third, the range and the trend
of the curves of COOOL-pair and COOOL-list are
diferent, which may explain the diferent
performances of the two models in diferent scenarios.
• The dimensional collapse issue may not greatly
hurt single instance optimization since the
embedding space is learned from one workload and
the latent collapsed dimensions are fixed when
the model converges. Because the collapsed
dimensions may be diferent in diferent datasets,
there may be orthogonal situations, which may
cause the subspace representation learned in one
dataset to be noise in another, resulting in
unstable performance. Therefore, it may limit the
scalability of machine learning query
optimization models.
• In Figure 5a, we observe a significant drop in
singular values on a logarithmic scale (lg( )) in all
tasks. The curve approaches zero (less than 1e-7)
in the spectrum, indicating that a dimensional
collapse [16] occurs in Bao’s embedding space in
each of Bao’s experimental scenarios. The model
learned on JOB even collapsed in half of the plan
embedding space. Bao’s plan embedding vectors
only spans a lower-dimensional subspace, which
harm the representation ability of the model and
therefore hurt the performance. Moreover, the
models in the single instance scenario on diferent
datasets result in a diferent number of collapsed
dimensions. Based on the workload transfer
scenario curves, we observe that the plan embedding To sum up, dimensional collapse in plan tree
embedspace of the target workload spans the same num- ding space is a challenge for machine learning query
optiber of dimensions as the source workload. So we mization models in maintaining a unified model to learn
can conclude that the embedding space is depen- from diferent workloads. The two variants of COOOL
dent on the training data. have the exact same model as Bao but consistently
outper• In Figures 5b and 5c, singular values of the form Bao in almost all scenarios and settings. We provide
COOOL approaches do not drop abruptly and some insight on why COOOL methods outperform Bao
greater than 1e-7, meaning that there is no col- from the query plan representation perspective. It may
lapse in their plan embedding space. The plan em- guide researchers to further improve the performance of
bedding methods of Bao and COOOL are the same, ML models for query optimization.
and the comparison reflects that the embedding
spaces learned from the regression framework 6. Related work
and ranking strategies are significantly diferent.
• The spectrum of Bao’s unified model is closer 6.1. Machine Learning for Query
to the spectrum of the learned representation
from TPC-H data than that learned from JOB data, Optimization
whereas the spectra of COOOL-pair and COOOL- Traditional cost-based query optimizers aim to select
list are closer to the spectrum of the representa- the candidate plan with the minimum estimated cost,
tion from JOB data than that learned from TPC-H where cost represents the execution latency or other
data. In fact, the number of training samples of user-defined resource consumption metrics. Various
TPC-H is greater than that of JOB, but JOB is more techniques have been proposed in cost-based
optimizcomplicated than TPC-H (see Table 3). When ers [30, 31, 32], such as sketches, histograms, probability
learning from multiple datasets, Bao’s perfor- models, etc. Besides, they work with diferent
assumpmance is afected more by the datasets with more tions (e.g., attribute value independence [33], uniformity
samples. By contrast, the two COOOL methods [34], data independence [35]) and when these cannot
are able to learn from sophisticated query plans. be met, the techniques usually fall back to an educated
• Singular values are related to the latent informa- guess [36]. Traditional optimizers have been studied for
tion in the covariance matrix. We can get three decades [
In recent years, some studies have attempted to build
end-to-end ML models for query optimization [
They all use a TCNN to predict the cost/latency of query
plans and leverage a deep reinforcement learning
framework to train the model. Though they have made
improvements compared with the previous works of
replacing some components of the optimizer with ML models,
an optimizer should be evaluated in multiple dimensions
[
In this paper, we propose COOOL that predicts cost orders of query plans to cooperate with DBMS by LTR techniques to recommend SQL hints for query optimization.
COOOL includes both pairwise and listwise methods, which can improve overall query execution speed, especially on slow queries, and alleviate individual query regression. Moreover, COOOL makes a step forward to maintaining a unified end-to-end query optimization ML model on two datasets. We shed some light on why COOOL approaches outperform Bao from the representation learning perspective, and the elaborated analysis may provide preliminary for large-scale pre-trained query optimization models. While COOOL methods are promising, they cannot estimate the cost of the recommended query plan, or quantitatively compare the costs of two query plans.
For future work, we plan to investigate the evaluation metrics for ranking candidate plans that difer by multiple orders of magnitude in execution latency for query optimization, which facilitates the introduction of state-of-the-art LTR techniques. LTR is still an active research field in recent years, so there are considerable future works to be explored in query optimization. Besides, developing a large-scale pre-trained query optimization model to improve query plans from multiple datasets and quantitatively comparing the costs of diferent query plans accurately are also challenging future directions.
The objective of LTR is to develop ML models that can automatically rank items according to their relevance or significance (such as relevance score or query latency). LTR is an active research topic [47] and has many applications in information retrieval [17], meta-search engines [48], recommendation systems [49], preference learning [50], etc. A search engine or a recommendation system usually needs to rank a large and variable number of items (webpages, movies, for example). The SQL hint recommendation problem is more like the preference learning problem, where a relatively small and fixed number of items (SQL hints in our case), are to be ranked for each user (SQL query in our case). Many studies have been conducted in the field of LTR (see the survey [ 51, 52, 17] for a comprehensive review). We briefly discuss PlackettLuce model [18, 19] in this section. Plackett-Luce model, which was later used as a listwise loss function in information retrieval [17] and softmax function in classiifcation tasks [ 20], is one of the most popular models in preference learning, which fits the task of SQL hint programming language processing, in: Thirtieth [16] T. Hua, W. Wang, Z. Xue, S. Ren, Y. Wang, AAAI conference on artificial intelligence, 2016. H. Zhao, On feature decorrelation in self-supervised [5] W. R. Thompson, On the likelihood that one un- learning, in: 2021 IEEE/CVF International Conknown probability exceeds another in view of the ference on Computer Vision, ICCV 2021, Monevidence of two samples, Biometrika 25 (1933) treal, QC, Canada, October 10-17, 2021, IEEE, 285–294. 2021, pp. 9578–9588. URL: https://doi.org/10.1109/ [6] R. C. Marcus, P. Negi, H. Mao, C. Zhang, M. Al- ICCV48922.2021.00946. doi:10.1109/ICCV48922. izadeh, T. Kraska, O. Papaemmanouil, N. Tatbul, 2021.00946.
Neo: A learned query optimizer, Proc. VLDB En- [17] T.-Y. Liu, Learning to rank for information retrieval, dow. 12 (2019) 1705–1718. URL: http://www.vldb. Foundations and Trends in Information Retrieval 3 org/pvldb/vol12/p1705-marcus.pdf. doi:10.14778/ (2009) 225–331.
3342263.3342644. [18] R. L. Plackett, The analysis of permutations, Journal [7] H. Liu, M. Xu, Z. Yu, V. Corvinelli, C. Zuzarte, Car- of the Royal Statistical Society Series C: Applied dinality estimation using neural networks, in: Pro- Statistics 24 (1975) 193–202. ceedings of the 25th Annual International Confer- [19] R. D. Luce, Individual choice behavior, 1959. ence on Computer Science and Software Engineer- [20] B. Gao, L. Pavel, On the properties of the ing, 2015, pp. 53–59. softmax function with application in game the[8] J. Sun, G. Li, An end-to-end learning-based cost ory and reinforcement learning, arXiv preprint estimator, Proc. VLDB Endow. 13 (2019) 307–319. arXiv:1704.00805 (2017).
URL: http://www.vldb.org/pvldb/vol13/p307-sun. [21] F. Xia, T.-Y. Liu, J. Wang, W. Zhang, H. Li, Listwise pdf. doi:10.14778/3368289.3368296. approach to learning to rank: theory and algorithm, [9] Z. Yang, E. Liang, A. Kamsetty, C. Wu, Y. Duan, in: Proceedings of the 25th international conference X. Chen, P. Abbeel, J. M. Hellerstein, S. Krishnan, on Machine learning, 2008, pp. 1192–1199. I. Stoica, Deep unsupervised cardinality estimation, [22] H. Azari Soufiani, W. Chen, D. C. Parkes, L. Xia, arXiv preprint arXiv:1905.04278 (2019). Generalized method-of-moments for rank aggrega[10] Z. Yang, A. Kamsetty, S. Luan, E. Liang, Y. Duan, tion, Advances in Neural Information Processing X. Chen, I. Stoica, Neurocard: one cardinality es- Systems 26 (2013). timator for all tables, Proceedings of the VLDB [23] Z. Zhao, L. Xia, Composite marginal likelihood Endowment 14 (2020) 61–73. methods for random utility models, in: Interna[11] M. Akdere, U. Çetintemel, M. Riondato, E. Upfal, tional Conference on Machine Learning, PMLR, S. B. Zdonik, Learning-based query performance 2018, pp. 5922–5931. modeling and prediction, in: 2012 IEEE 28th In- [24] A. Khetan, S. Oh, Data-driven rank breaking for ternational Conference on Data Engineering, IEEE, eficient rank aggregation, in: International Confer2012, pp. 390–401. ence on Machine Learning, PMLR, 2016, pp. 89–98. [12] W. Wu, Y. Chi, S. Zhu, J. Tatemura, H. Hacigümüs, [25] T. M. Mitchell, The need for biases in learning genJ. F. Naughton, Predicting query execution time: eralizations, Citeseer, 1980.
Are optimizer cost models really unusable?, in: [26] V. Leis, A. Gubichev, A. Mirchev, P. Boncz, A. Kem2013 IEEE 29th International Conference on Data per, T. Neumann, How good are query optimizers, Engineering (ICDE), IEEE, 2013, pp. 1081–1092. really?, Proceedings of the VLDB Endowment 9 [13] F. Ventura, Z. Kaoudi, J. A. Quiané-Ruiz, V. Markl, (2015) 204–215.
Expand your training limits! generating training [27] M. Poess, C. Floyd, New tpc benchmarks for dedata for ml-based data management, in: Proceed- cision support and web commerce, ACM Sigmod ings of the 2021 International Conference on Man- Record 29 (2000) 64–71.
agement of Data, 2021, pp. 1865–1878. [28] B. Xu, N. Wang, T. Chen, M. Li, Empirical evaluation [14] Z. Yang, W. Chiang, S. Luan, G. Mittal, M. Luo, of rectified activations in convolutional network, I. Stoica, Balsa: Learning a query optimizer with- arXiv preprint arXiv:1505.00853 (2015). out expert demonstrations, in: Z. Ives, A. Boni- [29] D. P. Kingma, J. Ba, Adam: A method for stochastic fati, A. E. Abbadi (Eds.), SIGMOD ’22: International optimization, in: 3rd International Conference on Conference on Management of Data, Philadel- Learning Representations, ICLR 2015, San Diego, phia, PA, USA, June 12 - 17, 2022, ACM, 2022, CA, USA, May 7-9, 2015, Conference Track Proceedpp. 931–944. URL: https://doi.org/10.1145/3514221. ings, 2015.
3517885. doi:10.1145/3514221.3517885. [30] Y. E. Ioannidis, V. Poosala, Balancing histogram [15] D. Zhang, J. Yin, X. Zhu, C. Zhang, Network repre- optimality and practicality for query result size essentation learning: A survey, IEEE transactions on timation, Acm Sigmod Record 24 (1995) 233–244. Big Data 6 (2018) 3–28. [31] G. Cormode, M. Garofalakis, P. J. Haas, C. Jermaine, et al., Synopses for massive data: Samples, [46] V. Leis, B. Radke, A. Gubichev, A. Mirchev, P. Boncz, histograms, wavelets, sketches, Foundations and A. Kemper, T. Neumann, Query optimization Trends® in Databases 4 (2011) 1–294. through the looking glass, and what we found run[32] G. Cormode, M. Garofalakis, Histograms and ning the join order benchmark, The VLDB Journal wavelets on probabilistic data, IEEE Transactions 27 (2018) 643–668. on Knowledge and Data Engineering 22 (2010) [47] H.-T. Yu, R. Piryani, A. Jatowt, R. Inagaki, H. Joho, 1142–1157. K.-S. Kim, An in-depth study on adversarial [33] S. Christodoulakis, Implications of certain assump- learning-to-rank, Information Retrieval Journal tions in database performance evauation, ACM 26 (2023) 1.
Transactions on Database Systems (TODS) 9 (1984) [48] C. Dwork, R. Kumar, M. Naor, D. Sivakumar, Rank 163–186. aggregation methods for the web, in: Proceedings [34] Y. E. Ioannidis, S. Christodoulakis, Optimal his- of the 10th international conference on World Wide tograms for limiting worst-case error propagation Web, 2001, pp. 613–622. in the size of join results, ACM Transactions on [49] A. Karatzoglou, L. Baltrunas, Y. Shi, Learning to Database Systems (TODS) 18 (1993) 709–748. rank for recommender systems, in: Proceedings of [35] A. Deshpande, M. Garofalakis, R. Rastogi, Inde- the 7th ACM Conference on Recommender Systems, pendence is good: Dependency-based histogram 2013, pp. 493–494. synopses for high-dimensional data, ACM SIGMOD [50] Z. Zhao, A. Liu, L. Xia, Learning mixtures of ranRecord 30 (2001) 199–210. dom utility models with features from incomplete [36] V. Poosala, Y. E. Ioannidis, Selectivity estimation preferences, arXiv preprint arXiv:2006.03869 (2022). without the attribute value independence assump- [51] A. Rahangdale, S. Raut, Machine learning methtion, in: VLDB, volume 97, 1997, pp. 486–495. ods for ranking, International Journal of Software [37] Y. E. Ioannidis, Query optimization, ACM Comput- Engineering and Knowledge Engineering 29 (2019) ing Surveys (CSUR) 28 (1996) 121–123. 729–761. [38] G. Lohman, Is query optimization a “solved” prob- [52] J. Guo, Y. Fan, L. Pang, L. Yang, Q. Ai, H. Zamani, lem, in: Proc. Workshop on Database Query Op- C. Wu, W. B. Croft, X. Cheng, A deep look into timization, volume 13, Oregon Graduate Center neural ranking models for information retrieval, Comp. Sci. Tech. Rep, 2014, p. 10. Information Processing & Management 57 (2020) [39] S. Krishnan, Z. Yang, K. Goldberg, J. Hellerstein, 102067.
I. Stoica, Learning to optimize join queries with deep reinforcement learning, arXiv preprint arXiv:1808.03196 (2018). A. Online Resources [40] R. Marcus, O. Papaemmanouil, Deep reinforcement learning for join order enumeration, in: Proceed- The source code of our paper is available at https://github. ings of the First International Workshop on Exploit- com/xianghongxu/COOOL. ing Artificial Intelligence Techniques for Data Management, 2018, pp. 1–4. [41] I. Trummer, J. Wang, Z. Wei, D. Maram, S. Moseley, S. Jo, J. Antonakakis, A. Rayabhari, Skinnerdb: Regret-bounded query evaluation via reinforcement learning, ACM Transactions on Database
Systems (TODS) 46 (2021) 1–45. [42] J. Zhang, Alphajoin: Join order selection à la al
phago, in: PVLDB-PhD, 2020. [43] X. Zhou, G. Li, C. Chai, J. Feng, A learned query rewrite system using monte carlo tree search, Proceedings of the VLDB Endowment 15 (2021) 46–58. [44] G. Li, X. Zhou, L. Cao, Ai meets database: Ai4db and db4ai, in: Proceedings of the 2021 International Conference on Management of Data, 2021, pp. 2859–2866. [45] X. Zhou, C. Chai, G. Li, J. Sun, Database meets artificial intelligence: A survey, IEEE Transactions on Knowledge and Data Engineering 34 (2020) 1096–1116.