#  Lero: A Learning-to-Rank Query Optimizer

Rong Zhu#, Wei Chen# Alibaba GroupHangzhouChina red.zr, wickeychen.cw@alibaba-
inc.com ,  Bolin Ding  Alibaba GroupHangzhouChina<EMAIL_ADDRESS>,
Xingguang Chen  Alibaba Group, The Chinese University of Hong
KongHangzhouChina<EMAIL_ADDRESS>,  Andreas Pfadler  Alibaba
GroupHangzhouChina<EMAIL_ADDRESS>,  Ziniu Wu
Massachusetts Institute of TechnologyMAUSA<EMAIL_ADDRESS>and  Jingren Zhou∗
Alibaba GroupHangzhouChina<EMAIL_ADDRESS>
###### Abstract.

A recent line of works apply machine learning techniques to assist or rebuild
cost-based query optimizers in DBMS. While exhibiting superiority in some
benchmarks, their deficiencies, e.g., unstable performance, high training
cost, and slow model updating, stem from the inherent hardness of predicting
the cost or latency of execution plans using machine learning models. In this
paper, we introduce a learning-to-rank query optimizer, called Lero, which
builds on top of a native query optimizer and continuously learns to improve
the optimization performance. The key observation is that the relative order
or rank of plans, rather than the exact cost or latency, is sufficient for
query optimization. Lero employs a pairwise approach to train a classifier to
compare any two plans and tell which one is better. Such a binary
classification task is much easier than the regression task to predict the
cost or latency, in terms of model efficiency and accuracy. Rather than
building a learned optimizer from scratch, Lero is designed to leverage
decades of wisdom of databases and improve the native query optimizer. With
its non-intrusive design, Lero can be implemented on top of any existing DBMS
with minimal integration efforts. We implement Lero and demonstrate its
outstanding performance using PostgreSQL. In our experiments, Lero achieves
near optimal performance on several benchmarks. It reduces the plan execution
time of the native optimizer in PostgreSQL by up to $70\%$ and other learned
query optimizers by up to $37\%$. Meanwhile, Lero continuously learns and
automatically adapts to query workloads and changes in data.

PVLDB Reference Format:
Rong Zhu, Wei Chen, Bolin Ding, Xingguang Chen, Andreas Pfadler, Ziniu Wu,
Jingren Zhou. PVLDB, 16(6): XXX-XXX, 2023.
doi:XX.XX/XXX.XX

†† $\\#$ Equal contribution. $*$ Corresponding author.
This work is licensed under the Creative Commons BY-NC-ND 4.0 International
License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a
copy of this license. For any use beyond those covered by this license, obtain
permission by emailing<EMAIL_ADDRESS>Copyright is held by the
owner/author(s). Publication rights licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 16, No. 6 ISSN 2150-8097.
doi:XX.XX/XXX.XX

PVLDB Artifact Availability:
The source code, data, and/or other artifacts have been made available at
https://github.com/Blondig/Lero-on-PostgreSQL.

##  1\. Introduction

Query optimizer plays one of the most significant roles in databases. It aims
to select an efficient execution plan for each query. Improving its
performance has been a longstanding problem. Traditional cost-based query
optimizers (Selinger et al., 1989) find the plan with the minimum estimated
cost, which is a proxy of execution latency or other user-specified metrics
about resource consumption. Such cost models contain various formulas to
approximate the actual execution latency, whose magic constant numbers are
exhaustively and extensively tuned based on engineering practice. Recent works
(Marcus et al., 2019; Yang et al., 2022; Marcus et al., 2021) refine
traditional cost models and plan enumeration algorithms with machine learning
techniques. Although some progress has been made, they still suffer from
deficiencies caused by the intrinsically difficult latency prediction problem.

In this paper, we propose Lero, a learning-to-rank query optimizer which
features a new lightweight pairwise machine learning model for query
optimization. Lero adopts a non-intrusive design, with minimal modification to
the existing system components in DBMS. Instead of building from scratch, Lero
is designed to leverage decades of wisdom of query optimizers without extra,
potentially significant, cold-start learning costs. Lero can quickly improve
quality of query optimization by judiciously exploring different optimization
opportunities and learning to rank them more accurately.

###  1.1. From Heuristic-Based Costing Models to Machine Learning Models

Traditional cost-based query optimizers (Selinger et al., 1989) have three
major components: cardinality estimator, cost model, and plan enumerator. For
an input query $Q$, cardinality estimator can be invoked to estimate the
cardinality, i.e., the number of tuples in the output, for each sub-query of
$Q$. The cost of a plan $P$ (with physical operators, e.g., merge join and
hash join) for the query $Q$ is a proxy of latency or other user-specified
metrics regarding the efficiency of executing $P$. The cost model ${\sf
PlanCost}(P)$ estimates $P$’s cost and is usually a function of estimated
cardinalities of $Q$’s sub-queries. The plan enumerator considers valid plans
of $Q$ in its search space and returns the one with the minimum estimated cost
for execution.

Various heuristics were essential in developing these components. For example,
independence between attributes across tables is assumed and utilized for
estimating cardinalities of joins of multiple tables (Tzoumas et al., 2011;
Leis et al., 2015). Magic constant numbers are prevalent in cost models. They
are often calibrated and tuned over years to ensure that the estimated cost
matches the plan’s performance well empirically, under certain system and
hardware configurations though. It is realized that such heuristics are not
always reliable for varying data distributions or system configurations. As a
result, cost models may produce significant errors and the plan generated from
the traditional query optimizer may have poor quality (Tzoumas et al., 2011;
Leis et al., 2015; Han et al., 2021; Doraiswamy et al., 2008).

It is a natural idea to develop machine learning models to replace traditional
cardinality estimators, heuristic-based cost models, and plan enumerators. For
example, there are works on learning cardinality estimators (refer to (Han et
al., 2021; Zhu et al., 2022) for a survey). For learning cost models,
different model parameters, instead of fixed magic constant numbers in
traditional cost models, can be learned from different datasets and workloads
to enable finer-grained characterization of various data distributions and
system configurations, thus providing instance-level optimization of each
query. A recent line of works on learned query optimizers are built upon the
above idea and demonstrate some promising results (Marcus et al., 2019; Yang
et al., 2022; Marcus et al., 2021).

Neo (Marcus et al., 2019) and Balsa (Yang et al., 2022) provide end-to-end
learned solutions for query optimization. A plan value function ${\sf
PlanVal}()$, inspired by the value networks in deep reinforcement learning, is
learned to replace the traditional cost model ${\sf PlanCost}$. For a partial
plan $P^{\prime}$ of the query $Q$, the machine learning model ${\sf
PlanVal}(P^{\prime},Q)$ predicts the minimum latency of a complete plan $P$
that contains $P^{\prime}$ as a sub-plan, with statistics and patterns about
the tables, predicates, and joins involved in $P^{\prime}$ and $Q$ as input
features. With ${\sf PlanVal}$, Neo and Balsa use their best-first search
strategies to find the best plan with the minimum estimated latency.

Bao (Marcus et al., 2021) learns to steer a native query optimizer. It tunes
the native query optimizer with different sets of hints to generate a number
of different candidate plans for the query $Q$. Each hint set forces/disables
some operations, e.g., index scan or hash join, so the query optimizer may
output a different, and possibly better, execution plan. Bao uses a machine
learning model ${\sf PlanVal}(P,Q)$ to estimate the quality (e.g., latency) of
each candidate plan $P$ and select the best candidate for execution.
Meanwhile, Bao periodically updates its model parameters based on execution
statistics using Thompson sampling (Thompson, 1933), as solving a contextual
multi-armed bandits problem (Zhou, 2015) to minimize the overall performance
regret.

Although learned query optimizers exhibit superiority than traditional ones in
some applications (Negi et al., 2021), their performance is far from
satisfactory. They still suffer from three major deficiencies:

  * $\bullet$

Unstable performance. These learned models are easily to produce inaccurate
latency estimates, which leads to sub-optimal plans. Sometimes, the
performance regression is very significant. As shown in Section 6.2, their
performance could even be worse than PostgreSQL’s native query optimizer on
TPC-H benchmark.

  * $\bullet$

High learning cost. The cost of learning a query optimizer includes both the
cost of exploring and executing different query plans and the cost of model
training. Some models (Marcus et al., 2019; Yang et al., 2022) require tens to
hundreds of training iterations to coverage, and execute all newly explored
plans in each iteration. For complex datasets, this would consume several days
to even weeks.

  * $\bullet$

Slow model updating. Existing learned optimizers need to update their latency
prediction models to fit dynamic data, which is very challenging especially
considering that the latency of the same plan may vary on dynamic data. Thus,
model updating in this case requires huge efforts (training data and cost),
and easily leads to performance regression, as shown in Section 6.4.

We recognize that, the deficiencies of both traditional and newly proposed
learned query optimizers stem from the notoriously difficult problem of
predicting the execution latency or cost of a plan. The exact execution
latency depends on numerous factors (Reddy and Haritsa, 2005; Marcus and
Papaemmanouil, 2019; Leis et al., 2015; Wu et al., 2013; Li et al., 2012),
e.g., underlying data distribution, workload patterns, and system environment.
Training such a prediction model is a costly operation, which requires
collecting a large volume of training data, by executing query plans and
measuring latency statistics, and a lengthy training process to explore the
huge hypothesis space.

Moreover, cardinality and cost estimations are only partial factors for query
optimization. No matter whether with the traditional calibrated
estimators/models or with the learned models trained on previous statistics,
improving the estimations’ accuracy does not necessarily lead to improvement
in query optimization.

Is it really necessary to predict the latency? We ask such a fundamental
research question: for the purpose of query optimization, do we really need to
estimate/predict the execution latency (or any other performance-related
metric) of every possible query plan? With the goal of finding the best
execution plan, training a machine learning model to predict the exact latency
(cost) is an overkill.

###  1.2. A Learning-to-Rank Query Optimizer

In this paper, we introduce a learning-to-rank query optimizer, called Lero.
In essence, what we need for query optimization is a learned oracle that is
able to _rank_ a set of candidate query plans with respect to their execution
efficiency.

Looking back, traditional cost models are essentially “human learning” models,
whose parameters, i.e., magic constant numbers, have been tuned with decades
of engineering efforts. Under the learning-to-rank paradigm, traditional and
learned cost models can be regarded as pointwise approaches (Liu, 2009), which
outputs an ordinal score (i.e., estimated cost) for each plan to rank them.
Lero adopts an effective pairwise learning-to-rank approach without discarding
human wisdom in developing traditional cost models and query optimizers. We
summarize our contributions as follows.

  * $\bullet$

Lero applies learning-to-rank paradigm to query optimization. Compared to
previous proposals to learn cost models or cardinalities which are partial
factors for query optimization, Lero directly ranks and learns to improve
plans’ quality. Lero is more effective in selecting plans with good quality.

  * $\bullet$

Lero adopts a pairwise approach which learns to compare two plans and predict
the better one. Compared to other pointwise approaches, training such a binary
classifier is often easier(Johannes and Eyke, 2011). Lero has significantly
lower training costs, requiring fewer training samples, and much less time to
train. A pairwise comparison model is also used for index tuning in (Ding et
al., 2019). Lero implements a novel deep learning model which consists of a
classifier over two plan embeddings with shared parameters. The model is able
to capture the detailed structural properties for given plans and is proven
more effective in the context of query optimization.

  * $\bullet$

Lero is able to explore and learn new plan space (and new optimization
opportunities) more effectively. Instead of using query-level hints as
previous proposals (Marcus et al., 2021), Lero can be equipped with various
strategies to adjust cardinality estimates at expression level to effectively
consider diversified plans and prioritize exploring more promising ones.

  * $\bullet$

Lero leverages decades of wisdom of databases and query optimization, rather
than building a brand new optimizer from scratch. Lero starts with the default
behavior of the native query optimizer and gradually learns to improve.
Therefore, Lero is guaranteed with a good initial quality and does not need a
lengthy cold-start training process.

  * $\bullet$

Lero employs a non-intrusive design. It can be implemented on top of any
existing DBMS and integrated seamlessly with the native query optimizer. To be
specific, Lero takes advantage of public interfaces provided by most DBMSs and
jointly works with the native query optimizer to improve optimization quality.

We implement Lero on PostgreSQL (Ler, 2022) and conduct extensive experiments
to evaluate its efficiency and effectiveness. Lero reduces the execution time
of the native query optimizer in PostgreSQL by up to $70\%$ and other learned
query optimizers by up to $37\%$. Experiments show that Lero adapts faster
with stable performance to various query workloads and dynamically changing
data.

Organization. Section 2 outlines Lero’s pairwise learning-to-rank system
architecture and key components. Section 3 presents the design of Lero’s
comparator model and describes how to train and infer using the model. Section
4 describes how Lero explores different plans and new optimization
opportunities, for the purposes of both plan selection and model training.
Extensions are discussed in Section 5. We report detailed evaluation results
in Section 6. We cover related work in Section 7 and conclude in Section 8.

##  2\. System Overview

Lero is a learning-to-rank query optimizer which continuously explores
different query plans, observes their performance, and learns to rank them
more accurately. Lero adopts a _pairwise_ approach whose objective is to
predict which of two plans is more efficient. Compared with other learning-to-
rank approaches, e.g., pointwise and listwise (Liu, 2009), Lero’s pairwise
approach makes the best trade-off between model accuracy and learning
efficiency for our task.

Figure 1 shows the overall architecture of Lero. For each input query $Q$, the
plan explorer works with the native query optimizer to generate a number of
potentially good and diversified candidate plans $P_{1},P_{2},\dots,P_{n}$.
The _pairwise_ plan comparator model ${\sf CmpPlan}$ is then invoked to select
the best plan $P^{*}$ from the candidates for answering $Q$. In system
background, the model trainer executes other candidate plans using idle
workers whenever system resources become available, collects the latency
information into the runtime stats repository, and continuously trains the
comparator model ${\sf CmpPlan}$ and updates it periodically. Such design
enables the comparator model to be continuously trained and become better over
time without affecting normal database services. The three components are
briefly introduced as follows.

Plan Comparator Model. Formally, let ${\sf CmpPlan}(P_{1},P_{2})$ be an oracle
comparing any two plans $P_{1}$ and $P_{2}$ of a query:

(1) ${{\sf CmpPlan}}(P_{1},P_{2})=\begin{cases}0&\text{if }{\sf
Latency}(P_{1})<{\sf Latency}(P_{2})\\\ 1&\text{if }{\sf Latency}(P_{1})>{\sf
Latency}(P_{2})\end{cases},$

with ties broken arbitrarily. We use execution latency ${\sf Latency}(P)$ as
the performance metric, but it can be easily generalized.

Our comparator model is to learn the above oracle ${\sf CmpPlan}$. To be more
specific, we organize the training datasets (e.g. from runtime stats
repository) in the form of ($P_{i}$, $P_{j}$, $label$) for all pairs of
executed plans of each query where $label$ indicates which plan in a pair is
better. The learning goal is to fit the output of the oracle in Eq. (1). We
also use ${\sf CmpPlan}$ to denote the learned plan comparator model (or
comparator for short). The design of ${\sf CmpPlan}$, including training and
inference techniques, is described in Section 3.

Figure 1. System architecture of Lero.

Plan Explorer. For a query, the plan explorer generates a variety of $n$
candidate plans $P_{1},P_{2},\ldots,P_{n}$. While the best one chosen by the
comparator is returned by the optimizer for query execution, the rest
candidate plans are used by the model trainer to refine the model. Therefore,
the candidate plans serve the purposes of both plan selection and model
training, and they should: i) contain some truly good candidates (although we
do not have to know who they are) and ii) be sufficiently diversified so that
the model could learn to distinguish between good and bad plans.

To satisfy the two requirements, our plan explorer uses the cardinality
estimator as the tuning knob to generate more plans for each query: the
cardinality estimates of sub-queries are purposely scaled up/down before being
fed into the cost model for the native query optimizer to generate different
candidate plans. In particular, it is shown that diversity can be introduced
in the generated plans by tuning selectivities (cardinalities) of predicates
in a query (Doraiswamy et al., 2008; Dey et al., 2008). Our plan explorer is
built on the intuition that the plan from the native query optimizer is
usually not too bad; by tuning cardinality estimates, it may either generate
some better plans in the neighboring plan space (if tuning towards the true
cost of a sub-query which was incorrectly estimated), or some worse plans
(tuning in the opposite direction). Plans with various quality also increase
the diversity among candidates to train the comparator, and it is the
comparator’s job to identify the best among them.

Details about our plan exploration strategy are described in Section 4. One
obvious advantage of our plan explorer is that the cardinality estimator is an
essential component in almost all query optimizers, and thus the strategy and
the implementation of our plan explorer can be easily migrated to different
databases.

Model Trainer. For each query, the trainer executes other candidate plans
generated by the plan explorer, whenever system resources become available,
and adds their plan information and execution statistics into the runtime
stats repository. Such information is further used for training and updating
the comparator model ${\sf CmpPlan}$. By doing so, Lero is able to _explore_
new plan space as much as possible and _learn_ from its potential mistakes. In
real-world distributed systems, idle workers and computation resources
commonly exist due to scheduling (Kanet and Sridharan, 2000) or
synchronization (Chen et al., 2016). Some platforms (Chaiken et al., 2008;
Negi et al., 2021) provide an individual environment for performance testing,
which can be also used as a resource for executing candidate plans and
collecting runtime stats.

##  3\. A Learned Plan Comparator

The comparator ${\sf CmpPlan}$ is trained/updated to fit a training dataset
from the runtime stats repository which continuously monitors query execution
and collects execution information.

Figure 2. Plan encoding and the structure of our plan comparator model
($d=1$).

###  3.1. Model Design

The overall model architecture of our comparator ${\sf CmpPlan}(P_{1},P_{2})$
is shown in Figure 2. It consists of _plan embedding layers_ followed by a
_comparison layer_. The plan embedding layer is carefully designed to
effectively capture all the crucial information about a query plan, including
tables, operators, and plan structural properties, etc., and the comparison
layer compares embeddings ($1$-$dim$ or $d$-$dim$ vectors output by the
embedding layers) from the two plans and calculates their difference in terms
of plan quality for the comparison purpose.

Plan Embedding Layers. The plan embedding layers of ${\sf CmpPlan}$ map
$P_{1}$ and $P_{2}$ from the original feature space to a one-dimensional
(1-$dim$) embedding space, in order to learn differences between plans. A sub-
model ${\sf PlanEmb}$ takes features from each plan and generate its plan
embedding, ${\sf PlanEmb}(P_{i})\in\mathbb{R}$ for each plan $P_{i}$
($i=1,2$). We use the parameter sharing technique in machine learning: the two
plan embeddings, ${\sf PlanEmb}(P_{1})$ and ${\sf PlanEmb}(P_{2})$, are
generated by two copies of ${\sf PlanEmb}$, which are two components in ${\sf
CmpPlan}$ sharing the same model structure and learnable parameters.

Judicious design of embedding model to capture critical information in the
tree-structured plan is crucial for the overall model’s effectiveness and
efficiency. Lero builds on top of the tree convolution model, similar to (Mou
et al., 2016; Marcus et al., 2019, 2021) but with significant improvements. As
in Figure 2, a plan $P$ is featurized as a tree structure of vectors. The
vector for each sub-plan $P_{j}$ that answers sub-query $Q_{j}$ (corresponding
to a tree node) concatenates: a one-hot encoding of the last operation on
$P_{j}$, the cardinality estimate, the row width of $Q_{j}$’s output, and 0/1
encoding of tables touched by $Q_{j}$. As the cardinality ${\sf C}(Q_{j})$
spans in a wide range, we use a min-max normalization over $\log({\sf
C}(Q_{j}))$ in the feature vector. Unlike previous approaches (Marcus et al.,
2021, 2019), the vector does not include the estimated cost, as it is strongly
correlated with the estimated cardinality and row width and it may introduce
additional inaccuracy of the cost model.

The tree convolution operation slides multiple triangle shaped filters over
each node and its two children to transform the plan into another tree.
Finally, vectors on the tree nodes are flattened to be fed into a neural
network to generate the plan embedding.

It is worth noting that previous works use machine learning models to predict
latency. Our embedding model ${\sf PlanEmb}$ and comparator ${\sf CmpPlan}$
are trained and used differently. Instead of predicting plan latency, ${\sf
PlanEmb}$ tries to extract key information from plans and enables the
comparison layer of ${\sf CmpPlan}$ to compare two plans. The learned 1-$dim$
plan embedding can be interpreted as a ranking criteria, and all pairs of
plans for a query are comparable based on ${\sf PlanEmb}(\cdot)$. Thus, the
scale of ${\sf PlanEmb}(P)$ for a plan $P$ is not restricted, and its value
does not have to be proportional to (or approximate) $P$’s performance metric,
e.g., latency. Such flexibility allows the overall model to be more effective
and easier to train.

Comparison Layer. The plan embedding model ${\sf PlanEmb}(\cdot)$ is learned
together with ${\sf CmpPlan}$ via pairwise comparisons of plans, with binary
labels indicating which one is better for each pair. Thus, in the comparison
layer of ${\sf CmpPlan}$, we feed the difference $x={\sf PlanEmb}(P_{1})-{\sf
PlanEmb}(P_{2})$ of embeddings of two plans into a logistic activation
function $\phi(x)=(1+\exp(-x))^{-1}$ to generate the model’s final output
(indicating whether $P_{1}$ or $P_{2}$ is better):

(2) ${\sf CmpPlan}(P_{1},P_{2})=\phi({\sf PlanEmb}(P_{1})-{\sf
PlanEmb}(P_{2})),\vspace{-0.2em}$

which is within $(0,1)$ and can be interpreted as how likely $P_{2}$ is more
preferable than $P_{1}$. This is consistent with the learning goal of our
comparator model as in Eq. (1): $P_{1}$ is more preferable if ${\sf
CmpPlan}(P_{2},P_{1})<0.5$ or approaches to $0$, and $P_{2}$ is more
preferable if ${\sf CmpPlan}(P_{2},P_{1})>0.5$ or approaches to $1$.
Equivalently, a smaller 1-$dim$ plan embedding is more preferable. More
formally,

$\small{\sf CmpPlan}(P_{1},P_{2})\rightarrow\begin{cases}0&\text{if }{\sf
PlanEmb}(P_{1},Q)\ll{\sf PlanEmb}(P_{2},Q)\\\ 1&\text{if }{\sf
PlanEmb}(P_{1},Q)\gg{\sf PlanEmb}(P_{2},Q)\end{cases}.\vspace{-0.2em}$

From how the model’s output is derived in (2) and the fact that
$\phi(a-b)+\phi(b-a)=1$, our comparator model preserves two nice properties:
i) (commutativity) ${\sf CmpPlan}(P_{1},P_{2})=1-{\sf CmpPlan}(P_{2},P_{1})$,
that is, exchanging the order of input plans does not affect the comparison
result; ii) (transitivity): ${\sf CmpPlan}(P_{1},P_{2})<0.5$ and ${\sf
CmpPlan}(P_{2},P_{3})<0.5$ $\Rightarrow$ ${\sf CmpPlan}(P_{1},P_{3})<0.5$,
that is, $P_{1}$ is better than $P_{2}$ and $P_{2}$ is better than $P_{3}$
imply that $P_{1}$ is better than $P_{3}$. Thus, the comparator ${\sf
CmpPlan}(\cdot,\cdot)$ induces a total order of all plans, and we could select
$P^{*}=\operatorname*{arg\,min}_{P_{1}\ldots P_{n}}{\sf PlanEmb}(P_{i})$ with
the minimum value of ${\sf PlanEmb}(\cdot)$ as the best plan for execution.

Loss Function. The goal of ${\sf CmpPlan}$ is to maximize the likelihood of
outputting the right order between any two plans, so that the best plan can be
selected. Thus, the loss function of ${\sf CmpPlan}$ is designed towards this
goal. Conceptually, let $\mathcal{A}$ be a (randomized) algorithm that decides
which one of $P_{1}$ and $P_{2}$ is more preferable based on the model’s
output ${\sf CmpPlan}(P_{1},P_{2})\in(0,1)$:

(3) $\mathcal{A}(P_{1},P_{2})\rightarrow\begin{cases}P_{1}&\text{with
probability }1-{\sf CmpPlan}(P_{1},P_{2})\\\ P_{2}&\text{with probability
}{\sf CmpPlan}(P_{1},P_{2})\end{cases}.$

We have ${\sf CmpPlan}(P_{1},P_{2})+{\sf CmpPlan}(P_{2},P_{1})=1$ by the
commutativity. Thus, the algorithm $\mathcal{A}$ is well-defined:
$\mathcal{A}(P_{1},P_{2})$ and $\mathcal{A}(P_{2},P_{1})$ output $P_{1}$ with
the same probability. Let $P_{1}\prec P_{2}$ denote the event that ${\sf
Latency}(P_{1})<{\sf Latency}(P_{2})$ and $P_{1}\succ P_{2}$ vice versa. The
goal is to train ${\sf CmpPlan}$ such that $\mathcal{A}$ is as accurate as
possible. Suppose we have a workload of queries in $\mathcal{W}=\\{Q\\}$ and a
set of candidate plans ${P}(Q)=\\{P_{1},\ldots,P_{n}\\}$ for each query, as
the training data. We use $\mathcal{A}$ to compare all pairs of candidate
plans for each $Q\in\mathcal{W}$; the probability that $\mathcal{A}$ makes no
mistake is:

(4) $\displaystyle\small{\rm
ACC}(\mathcal{A},\mathcal{W})=\prod_{Q\in\mathcal{W}}$
$\displaystyle\left(\prod_{P_{i}\prec P_{j}\in{P}(Q)}(1-{\sf
CmpPlan}(P_{i},P_{j}))\right.$ $\displaystyle\left.\cdot\prod_{{P_{i}\succ
P_{j}\in{P}(Q)}}{\sf CmpPlan}(P_{i},P_{j})\right).\vspace{-0.5em}$

We train ${\sf CmpPlan}$ to fit the observed orders of plans for queries in
$\mathcal{W}$, so the loss function is chosen to be $L=-\log{\rm
ACC}(\mathcal{A},\mathcal{W})$:

(5) $\displaystyle\small L=-\sum_{Q\in\mathcal{W}}\sum_{P_{i},P_{j}\in{P}(Q)}$
$\displaystyle\left(\mathbb{I}_{P_{i}\prec P_{j}}\cdot\log(1-{\sf
CmpPlan}(P_{i},P_{j}))\right.$ $\displaystyle\left.+\mathbb{I}_{P_{i}\succ
P_{j}}\cdot\log({\sf CmpPlan}(P_{i},P_{j}))\right),\vspace{-0.8em}$

where the indicator function $\mathbb{I}_{\rm{x}}$ returns $1$ if the
condition $\rm{x}$ holds and $0$ otherwise. $L$ coincides with the cross-
entropy loss in classification.

###  3.2. Model Training

Instead of training from scratch, we pre-train our comparator model ${\sf
CmpPlan}$ offline first on synthetic workloads to inherit the wisdom of the
native query optimizer and its cost model. It is then continuously trained and
updated online on real workloads with training data collected during actual
executions of query plans.

Model Pre-training: Starting from Traditional Wisdom. To
leverage decades of wisdom of cost models developed in DBMSs, we pre-train the
comparator model using the estimated costs of candidate plans (without
executing them) generated from a sample workload of queries in an offline
training stage. After pre-training, the 1-$dim$ embedding ${\sf PlanEmb}(P)$
is expected to be an approximation to the native estimated cost ${\sf
PlanCost}(P)$. Thus, the model is bootstrapped to perform similarly to the
native query optimizer at the beginning. As more and more queries are
executed, ${\sf CmpPlan}$ is continuously improved and tuned to adapt to
possibly dynamic data distribution and workloads that drift over time.

In the native cost model, the cost of a plan is usually a piecewise linear or
quadratic function of estimated cardinalities of sub-queries with magic
constants as co-coefficients for different operators. The goal of pre-training
${\sf PlanEmb}(P)$ is to learn such functions in a data-agnostic way, so as to
handle any unseen query. Thus, we could pre-train ${\sf PlanEmb}(P)$ purely
using synthetic workloads. Namely, we randomly generate a number of plans with
different join orders and predicates on different tables, and featurize them
as the training data; we also randomly set the cardinality for each sub-plan
of each plan and feed them into the native cost model (without executing the
plans) to derive the estimated plan costs as labels. As the cost models are
often in a class of functions with simple structures, the model pre-training
converges very fast.

Pairwise Training. In the online stage, we train and update the comparator
${\sf CmpPlan}$ in the pairwise comparison framework. For each query $Q$, its
candidate plans $\\{P_{1},\ldots,P_{n}\\}$ are generated by the plan explorer
to be introduced in Section 4; these plans are executed by idle workers,
whenever system resources become available, with execution statistics
collected in the runtime stats repository. According to the loss function in
Eq. (5), we construct $n(n-1)$ training data points for each query: for each
pair $(i,j)$ with $1\leq i\neq j\leq n$, we construct a data point with
features $(P_{i},P_{j})$ and label $1$ if ${\sf Latency}(P_{i})>{\sf
Latency}(P_{j})$, and $0$ otherwise.

Periodically, we use an SGD optimizer to update ${\sf CmpPlan}$ together with
${\sf PlanEmb}$ by backward propagation with the training dataset constructed
above. For parameters in the sub-model ${\sf PlanEmb}$, as they are shared in
two copies of ${\sf PlanEmb}$ that output ${\sf PlanEmb}(P_{i})$ and ${\sf
PlanEmb}(P_{j})$, respectively, we add up the gradients from the two copies
for each shared parameter together to update this parameter in the model ${\sf
PlanEmb}$.

Our comparator, by nature of its design, adapts fast to dynamically changing
data during the processing of model training and updating. When tuples are
inserted or deleted into the database, the relative orders of two plans (i.e.,
labels of ${\sf CmpPlan}$) are more robust than their execution latencies
(i.e., labels of a latency prediction model). The latter would vary for the
same plan even when tuples from the same distribution are inserted, which
makes the training of a latency prediction model costly especially on dynamic
data. Our experimental study in Section 6.4 verifies the above intuition.

##  4\. Plan Exploration Strategy

The plan explorer of Lero generates a list of candidate plans $P_{1},$
$\ldots,$ $P_{n}$ for a query $Q$, for two purposes. First, for the purpose of
query optimization, Lero applies the comparator model to identify the best
plan among the candidates for execution. Thus the candidate list must include
some truly good plans for consideration.

Second, for the purpose of plan exploration, Lero _prioritizes_ exploring
other promising plans for the query. By executing them and comparing their
performance pairwise, Lero is able to catch past optimization mistakes and
adjust the model timely using the newly observed runtime information. In
addition, whenever system resources are available, other candidate plans which
are diversified sufficiently (e.g., with different join orders or in different
shapes such as left-deep and bushy trees) are also considered so that Lero
learns new plan space and improves the model over time.

For the ease of deployment, Lero makes minimal changes to the native query
optimizer. Therefore, the plan explorer should be able to be implemented in a
lightweight way, e.g., through re-implementing some system provided
interfaces. Meanwhile, we hope that the framework of Lero could be generally
used in any DBMS; thus, the strategy should not be system-specific.

Existing Plan Exploration Methods. A straightforward strategy is to explore a
random sample of valid plans for each query, which is used by reinforcement
learning-based approaches such as Neo (Marcus et al., 2019) and Balsa (Yang et
al., 2022). The obvious drawback is that, with high likelihood, high-quality
plans could be missing in a random sample; otherwise, the sample size has to
be so large that executing these sample plans would be too costly for model
training.

Bao (Marcus et al., 2021) explores plans by tuning a set of hints (boolean
flags) to disable/force certain types of optimization rules. For example, the
native query optimizer initially generates a plan with merge join for a query;
with a hint set that disables merge join and forces indexed nested loop join,
it would generate a different candidate plan. However, this optimizer-level
tuning strategy has two drawbacks.

First, a hint set is typically applied for the whole query during the entire
plan search procedure. If different parts of a query have different optimal
choices, tuning a flag at a query level may miss opportunities for finding
high-quality plans. For example, let $Q$ be a query joining two sub-queries
$Q_{1}$ and $Q_{2}$ where the best join operations for $Q_{1}$ and $Q_{2}$ are
indexed nested loop join and merge join, respectively. The query optimizer may
use merge join for both $Q_{1}$ and $Q_{2}$ due to cardinality estimation
errors. With a hint set disabling/forcing either merge join or indexed nested
loop join, at most one of $Q_{1}$ and $Q_{2}$ could select the right
operation. In such cases, the optimal plan can never be included in the
candidate list.

Second, the set of available hints is system specific. An optimizer usually
contains hundreds of flags to enable/disable certain optimization rules.
Enumerating all kinds of combinations is infeasible in practice. Selecting an
effective subset of hint sets manually requires a deep understanding on the
system and comprehensive analysis on the workload (Negi et al., 2021).

Thus, it motivates us to pursue other routes for designing a plan exploration
strategy. We introduce our tuning knob in Section 4.1, followed with practical
heuristic strategies in Section 4.2.

###  4.1. Cardinality as Knob for Plan Explorer

Lero uses the cardinality estimator as the tuning knob for our plan explorer.
In the native cost-based query optimizer, the estimated cardinality for each
sub-query of an input query $Q$ is fed into the cost model to guide plan
enumeration and selection. Each time with different cardinality estimates on
one or more sub-queries, the query optimizer would select a different plan for
$Q$. In Lero’s plan explorer, we tune (magnify or reduce) the estimated
cardinalities multiple times to generate a list of different candidate plans.

Formally, let ${\sf C}()$ be the native cardinality estimator in DBMS. For
each sub-query $Q^{\prime}$ of a query $Q$, ${\sf C}(Q^{\prime})$ gives a
cardinality estimate. Instead of invoking ${\sf C}()$ in the cost model, we
ask the query optimizer to invoke a tuned estimator $\widetilde{\sf C}()$, so
it would generate a different plan. Our plan explorer would tune ${\sf C}()$
in different ways; with different tuned estimators fed into the cost model,
the query optimizer generates different plans as the candidates
$P_{1},\ldots,P_{n}$.

Using the cardinality estimator as a tuning knob has following advantages.
First, in cost-based query optimizers, cardinality estimates decide the
estimated costs, and thus determine join orders and physical operations on
tables and sub-queries. Therefore, under the same resource budget (e.g. work
memory) for plan execution, tuning cardinality estimates would be highly
possible to introduce diversity in candidate plans, possibly with different
join orders or different operators (e.g., sort-merge join v.s. nested loop
join). Second, cardinality tuning is platform-independent. For most DBMSs,
there exist system-provided interfaces to modify the estimated cardinality,
which is friendly for system deployment.

A Brute-Force Exploration Strategy. Let ${\sf C}^{*}()$ be the true
cardinality. For any query $Q$, the difference between ${\sf C}^{*}(Q)$ and
the DBMS’s estimate ${\sf C}(Q)$ is unknown. However, with a reasonable number
of different ways to tune ${\sf C}(Q)$, we can ensure that at least one tuned
estimator $\widetilde{\sf C}(Q)$ is close to ${\sf C}^{*}(Q)$, in terms of
q-error, which is defined as ${\rm QE}({\rm estimate},{\rm
true})=\max\\{\frac{\rm estimate}{\rm true},\frac{\rm true}{\rm estimate}\\}$.

We tune the cardinality estimator ${\sf C}()$ with exponentially varying step
sizes. Suppose we know an upper bound of the q-error of ${\sf C}()$, namely,
${\rm QE}({\sf C}(Q^{\prime}),{\sf C}^{*}(Q^{\prime}))\leq\Delta$ for any sub-
query $Q^{\prime}$ of $Q$. Let

(6)
$F_{\alpha}^{\Delta}=\\{\alpha^{t}\mid\lfloor-\log_{\alpha}\Delta\rfloor\leq
t\leq\lceil\log_{\alpha}\Delta\rceil,t\in\mathbb{Z}\\}\vspace{-0.3em}$

be the set of guesses of scaling factors. For each $f=\alpha^{t}\in
F_{\alpha}^{\Delta}$, we tune ${\sf C}(Q^{\prime})$ as $\widetilde{\sf
C}(Q^{\prime})=f\cdot{\sf C}(Q^{\prime})$. Then there is at least one $f\in
F_{\alpha}^{\Delta}$ such that ${\rm QE}(f\cdot{\sf C}(Q^{\prime}),{\sf
C}^{*}(Q^{\prime}))\leq\alpha$. The estimation of $\Delta$ does not need to be
tight, since the number of guesses
$|F_{\alpha}^{\Delta}|=\Theta(\log_{\alpha}\Delta)$ depends logarithmically on
$\Delta$. In practice, it can be set based on users’ experience or q-error
distribution on historical queries.

In order to explore plans for the query $Q$, we repeat the above tuning
process recursively for all of its sub-queries: for each sub-query
$Q^{\prime}$ of $Q$, we pick a scaling factor $f_{Q^{\prime}}\in
F_{\alpha}^{\Delta}$ and set $\widetilde{\sf
C}(Q^{\prime})=f_{Q^{\prime}}\cdot{\sf C}(Q^{\prime})$. For each combination
of scaling factors $\langle f_{Q^{\prime}}\rangle_{Q^{\prime}\subseteq Q}$, we
construct an estimator $\widetilde{\sf C}()$ defined for all the sub-queries
of $Q$, and we can feed it into the cost model to generate a candidate plan.

From the way how tuned estimators are constructed above, there is at least one
combination of scaling factors such that the resulting $\widetilde{\sf C}()$
satisfies ${\rm QE}(\widetilde{\sf C}(Q^{\prime}),{\sf
C}^{*}(Q^{\prime}))\leq\alpha$ for all sub-queries of $Q$. Theoretically, a
near-optimal candidate plan under a specific cost model can be generated by
the optimizer using an estimator $\widetilde{\sf C}()$ with q-error bounded by
$\alpha$; more formally, from (Moerkotte et al., 2009), with some mild
assumptions about the cost model, the optimal plan under $\widetilde{\sf C}()$
is no worse than the optimal plan under ${\sf C}^{*}()$ by a factor of
$\alpha^{4}$.

Ensuring that at least one candidate plan is near-optimal suffices for the
purpose of optimization, as it is the comparator’s job to identify it among
all candidates. However, the overhead of the above method is too high: the
number of different sub-queries $Q^{\prime}$ is at least $2^{q}$ where $q$ is
the number of tables in $Q$, and
$|F_{\alpha}^{\Delta}|=\Theta(\log_{\alpha}\Delta)$; thus, the total number of
combinations of scaling factors is $\Theta(\log_{\alpha}^{2^{q}}\Delta)$. From
the above discussion, we can prove the following results.

###### Proposition 0.

In the above brute-force exploration strategy, the number of candidate plans
generated is at most ${\rm O}(\log_{\alpha}^{2^{q}}\Delta)$; with some mild
assumptions about the cost model as in (Moerkotte et al., 2009), at least one
of them is no worse than the optimal plan by a factor of $\alpha^{4}$.

The list of candidate plans generated in the above way is too long, which is
unbearably costly for model training. We propose more effective heuristic
methods in the following subsection.

###  4.2. Priority-Based Heuristic Methods

Plan exploration is conducted in background whenever system resources become
available. The key idea of our heuristics is to _prioritize_ exploring where
the native optimizer is likely to make mistakes. In addition, instead of
exploring all possibilities and tuning cardinality estimates for all sub-
queries simultaneously as in the brute-force strategy, we introduce a
heuristic which focuses on mistakes in estimating cardinalities for size-$k$
sub-queries on $k$ tables (for each different $k\geq 1$ at one time). 111We
also consider heuristics based on plan diagram (Doraiswamy et al., 2008; Dey
et al., 2008), which can be found in Appendix B.

Algorithm ${\sf plan\\_explorer}(Q,\alpha,\Delta)$

1: Priority queue ${\sf candidate\\_plans}\leftarrow\varnothing$

2: for each $f\in F_{\alpha}^{\Delta}$ in the increasing order of $|\log f|$
do

3: for $k\leftarrow 1$ to $q$ (the number of tables in $Q$) do

4: Inside query optimizer: let ${\sf C}()$ be the default cardinality
estimator in native query optimizer

5: $\widetilde{\sf C}(Q^{\prime})\leftarrow f\cdot{\sf C}(Q^{\prime})$ for
size-$k$ sub-queries $Q^{\prime}\in{\sf sub}_{k}(Q)$

6: $\widetilde{\sf C}(Q^{\prime})\leftarrow{\sf C}(Q^{\prime})$ for sub-
queries $Q^{\prime}\in{\sf sub}(Q)-{\sf sub}_{k}(Q)$

7: feed cardinality $\widetilde{\sf C}()$ into the cost model to generate a
plan $P$

8: ${\sf candidate\\_plans}\leftarrow{\sf candidate\\_plans}\cup\\{P\\}$

9: return ${\sf candidate\\_plans}$

Figure 3. Plan exploration strategy in Lero.

The necessity of considering $k>1$ is because the difficulty (as well as the
error) of estimating cardinality of size-$k$ sub-queries increases
significantly as $k$ increases (due to cross-table correlation among columns).
Thus, the native optimizer tends to make mistakes in generating partial plans
for sub-queries on a larger number $k>1$ of tables. As a trade-off between
efficiency and effectiveness, the following strategy tries to guess where the
biggest mistake is (by enumerating all possible values of $k$), and tune
cardinality estimates for all size-$k$ sub-queries together.

The plan explorer in Lero is illustrated in Figure 3. In the outer loop (line
2), we enumerate a scaling factor $f\in F_{\alpha}^{\Delta}$, in the
increasing order of $|\log f|$ with ties broken arbitrarily. That is, we
prioritize exploring the neighboring plan space surrounding the native
optimizer’s choice (with $f$ closer to $1$), where plan quality is not too bad
and the optimizer is likely to make mistakes, if any. Let ${\sf sub}_{k}(Q)$
be the set of size-$k$ sub-queries of a query $Q$ on $q$ tables. An extensive
experimental study in (Leis et al., 2015) shows that sub-queries with the same
size are often underestimated together with similar q-errors. Thus, in the
inner loop, we enumerate $k$ and tune the cardinality estimates for all sub-
queries $Q^{\prime}\in{\sf sub}_{k}(Q)$ together, resulting in a tuned
estimator $\widetilde{\sf C}$ (lines 5-6) to be fed into the optimizer. The
resulting candidate plans are maintained in a priority queue for evaluation
and execution whenever system resources allow. Considering the sizes of the
two loops in lines 2-3, the following result is obvious.

###### Proposition 0.

In the heuristic strategy in Figure 3, the number of candidate plans generated
is at most ${\rm O}(q\cdot\log_{\alpha}\Delta)$.

Encouraging Diversity in Candidates. An important goal of our plan explorer is
to generate diversified candidates. In Figure 4, we give conceptual examples
of typical cases when our plan explorer encourages diversity in the candidates
(with different plan shapes and join orders), for a query joining four tables,
$A\bowtie B\bowtie C\bowtie D$:

(Diversity of plan shapes) Two valid plans $P_{1}$ and $P_{2}$ have different
shapes (left-deep tree and bushy tree, respectively). When we tune cardinality
estimates for size-2 sub-queries ($k=2$ in line 2 of Figure 3), different
values of $f$ would encourage different plan shapes. Namely, when $f\ll 1$,
two sub-queries $A\bowtie B$ and $C\bowtie D$ in $P_{2}$ have reduced
cardinality estimates in $\widetilde{\sf C}()$, while only one sub-query
$A\bowtie C$ in $P_{1}$ has a reduced cardinality estimate. As a result, the
estimated cost of $P_{2}$ is reduced more than that of $P_{1}$, and thus a
bushy tree is more likely to be generated by our plan explorer and included in
the candidate list. When $f\gg 1$, with a similar logic, a left-deep tree is
more likely to appear in the candidate list.

(Diversity of join orders) Plans $P_{3}$ and $P_{4}$ are both left-deep trees
but have different join orders. In Figure 4, the length of bar on each single
and joined table represents its size. $P_{3}$ first executes $A\bowtie B$
which has a large estimated cardinality, while $P_{4}$ first executes
$C\bowtie D$ which is estimated to be much smaller. When we tune cardinality
estimates for size-2 sub-queries, we multiply both estimates with a scaling
factor $f$. Suppose $P_{3}$ and $P_{4}$ have similar total estimated cost
before tuning. When $f\ll 1$, the decrease of the tuned cardinality estimate
$\widetilde{\sf C}(A\bowtie B)-{\sf C}(A\bowtie B)$ for $A\bowtie B$ is more
significant than $\widetilde{\sf C}(C\bowtie D)-{\sf C}(C\bowtie D)$, and thus
$P_{3}$ is more likely to be in the candidate list; when $f\gg 1$, the
increase $\widetilde{\sf C}(A\bowtie B)-{\sf C}(A\bowtie B)$ is more
significant, and thus $P_{4}$ is more preferable.

Figure 4. Intuitions on why our plan explorer based on sub-query grouping
encourages diversity.

Some Implementation Details. The tuned estimator $\widetilde{\sf C}()$ in our
plan explorer (in Figure 3) is not constructed explicitly by setting the
cardinality estimate for every possible sub-query $Q^{\prime}$ of $Q$ (as in
lines 5-6). Instead, we only need a “hook” to the native cardinality estimator
${\sf C}()$: if the size of a sub-query $Q^{\prime}$ is $k$, we invoke ${\sf
C}(Q^{\prime})$ and return $f\cdot{\sf C}(Q^{\prime})$ as $\widetilde{\sf
C}(Q^{\prime})$; otherwise, we just return ${\sf C}(Q^{\prime})$. We implement
Lero on PostgreSQL. Thanks to Lero’s non-intrusive design, the implementation
is straightforward. The only major modification to PostgreSQL is a hook
function pg_hint_plan that implements the tuned cardinality estimator
$\widetilde{\sf C}()$ in the above way. Our implementation on PostgreSQL can
be easily ported to other databases that offer similar interfaces for
cardinality estimators.

##  5\. Extensions and Discussion

Comparator with $d$-$dim$ Embedding. Our comparator ${\sf CmpPlan}$ could be
extended to a $d$-dimensional ($d$-$dim$) embedding space. We only need to
leave the dimensionality of the last plan embedding layer (in Figure 2) as
$d>1$, with the hope to summarize more sophisticated statistical and
structural information about each plan in plan embeddings. After that, the
comparison layer is a learnable linear layer that compares the two $d$-$dim$
embeddings ${\sf PlanEmb}(P_{1})\in\mathbb{R}^{d}$ and ${\sf
PlanEmb}(P_{2})\in\mathbb{R}^{d}$, and outputs $0$ ($P_{1}$ is better) or $1$
($P_{2}$ is better). We defer detailed analysis to Appendix A.

How to Handle Varying Resource Budget. Traditionally, each query is assigned a
resource budget (e.g. work memory) under which the query is optimized and
later executed. It is the database engine’s responsibility to guarantee each
query receives its assigned budget at runtime and ensure performance isolation
among different queries to avoid any resource contention. This is an
orthogonal task to query optimization. When resource condition in the database
engine changes dramatically and the assigned budget for a query can no longer
be guaranteed at runtime, re-optimization for the query under a different
budget might be triggered.

We assume constant resource budget per plan execution in this paper. In
principle, Lero can include resource budget information into the feature set
of our comparator model, namely, as inputs to the plan embedding layers. In
this way, the resulting plan embeddings encode such information about
available resource, and plans can be compared in the comparison layer under
different resource budgets at runtime. This augmented design will bring more
challenges in model training, as the comparator now needs to observe runtime
stats under various resource budgets to be fully trained, which we leave for
future work.

##  6\. Experimental Evaluation

We make our implementation of Lero open-source (Ler, 2022). We also implement
recently proposed learned query optimizers, Neo (Marcus et al., 2019) and Bao
(Marcus et al., 2021), and use Balsa’s open-source implementation in (Yang et
al., 2022; Bal, 2022) on PostgreSQL. We describe our experimental setup in
Section 6.1. We first answer the most crucial questions about Lero’s
performance:

  * $\bullet$

How much improvement on query execution performance could Lero achieve in
comparison with PostgreSQL’s native and other learned query optimizers?
(Sections 6.2 and 6.8)

  * $\bullet$

How much is Lero’s query optimization cost? (Section 6.3)

  * $\bullet$

Could Lero adapt to workloads on dynamic data? (Section 6.4)

We then examine the design choices and settings in Lero and understand how
they affect the performance of Lero:

  * $\bullet$

What are the benefits of using pre-training in Lero? (Section 6.5)

  * $\bullet$

Is the proposed plan exploration strategy efficient and effective? How is it
compared with alternative strategies? (Section 6.6)

  * $\bullet$

With less or limited idle resource, could Lero still achieve similar
performance gains? (Section 6.7)

###  6.1. Experimental Setup

Benchmarks. We evaluate all the query optimizers on three widely used
benchmarks.

  * $\bullet$

The IMDB dataset has 21 tables on movies and actors, and its JOB workload
(Leis et al., 2015) has 113 realistic queries. For large-scale evaluation in
most of our experiments, we generate a workload of 1,000 queries from JOB
(similar to the one in (Marcus et al., 2021)): each time we randomly sample a
query template from JOB, fetch its join template and attach some randomly
generated predicates to it.

  * $\bullet$

The STATS dataset and STATS-CEB workload (Han, 2021; Han et al., 2021) are
recently proposed to evaluate the end-to-end performance of query optimizer.
STATS contains $8$ tables of user-contributed content on the Stats Stack
Exchange network. Its data distribution is more complex than IMDB. STATS-CEB
contains 146 query templates varying in join sizes and types. We generate a
query workload using the same approach as described above.

  * $\bullet$

The TPC-H (Council(TPC), 2021b) has its data synthetically generated under a
uniform distribution. We set the scale factor to $10$, and use its query
templates #3, 5, 7, 8, 9, 10 for workload generation. Under each template, we
generate a number of queries with varying predicates. We exclude other
templates which are either too simple (on only one or two tables), or with
views or nested SQL queries. Queries with views or nested SQL queries cannot
be fully optimized by Lero due to a limitation of our implementation: to tune
cardinality estimations for operators in the plans, we modify the hook
function pg_hint_plan, which does not support to impose any hints on views and
nested SQL queries. We would try to fix this limitation in the future
implementation.

  * $\bullet$

The TPC-DS (Council(TPC), 2021a) is another benchmark for evaluating database
performance. Similar to TPC-H, we also set its scale factor to $10$ and
exclude all templates that are either too simple or can not be supported by
the pg_hint_plan hook function. The remaining 23 templates are used to
generate a query workload with various predicates in a similar way to TPC-H.

Learned Optimizers in Comparison. Neo and Balsa need to find a plan to execute
using their latest model in each training epoch, and use the execution
statistics to update the model. The generated plans are unknown before each
epoch, so the training can only be done sequentially, which leads to a very
long training time even with unlimited resource. By their evaluation (Marcus
et al., 2019; Yang et al., 2022), the models converge after tens of epochs. On
the contrary, both Bao and Lero can simultaneously run the selected plans and
collect the training data in background, which greatly expedite the training
process.

In our experiments, neither Neo nor Balsa could match the performance of
PostgreSQL’s native query optimizer after training for 72 hours on all of our
datasets, except the original JOB workload (with 113 queries) on the IMDB
dataset. On the contrary, Bao often outperforms PostgreSQL after training for
several hours. Thus, we only report performance of Bao and Lero in most of our
experiments in Sections 6.2-6.7. We compare Lero with Balsa on IMDB with the
original JOB workload in Section 6.8. Bao and Balsa have demonstrated their
superiority over Neo in (Marcus et al., 2021; Yang et al., 2022), so we do not
further compare with it in the rest experiments.

As described in (Marcus et al., 2021), Bao selects one candidate plan by
Thompson sampling to execute and collects its execution time to update its
model periodically. To have a fair comparison with Lero, we also implement an
extended version of Bao, called Bao+, which witnesses more plans for model
training. For each training query, it runs all candidate plans generated by
its hint set tuning strategy using idle computation resource and collects
their execution time to update the model periodically, in a similar way to
Lero.

Evaluation Scenarios We compare Lero with PostgreSQL’s native query optimizer
and other learned optimizers in different settings. PostgreSQL’s native query
optimizer does not need a separate training phase. For fair comparisons with
the native and learned optimizers, we use the “time series split” strategy
(Marcus et al., 2021) for training and evaluating Bao, Bao+, and Lero. Namely,
unique queries in a workload are randomly shuffled as $Q_{1},Q_{2},\ldots$.
The learned optimizers are always evaluated on queries that have never seen
during the procedure of model training and updating. In the experiments, we
evaluate their performance under two realistic scenarios:

  * $\bullet$

Performance curve since deployment. The learned optimizers are continuously
updated since deployed for each workload. Bao+ and Lero may execute multiple
candidate plans for a query on idle workers. When $Q_{t+1}$ is evaluated, all
learned optimizers are only trained with information from earlier queries
$Q_{1},\ldots,Q_{t}$. Their models are updated in the background every 100
queries on IMDB and STATS, every 30 queries on TPC-H and every 50 queries on
TPC-DS. By reporting the (accumulated) latency on each $Q_{t+1}$, we meter the
performance of different optimizers since the deployment and how quickly they
adapt to a new workload.

  * $\bullet$

Performance with stable models. The learned optimizers tend to be stable (that
is, the model training process converges) after seeing a sufficient number of
queries in the workload, i.e., $Q_{1},\ldots,Q_{T}$ (training queries), then
we would use the optimizers to evaluate queries $Q_{T+1},$ $Q_{T+2},$ $\ldots$
(test queries) without further updating the models. The numbers of test
queries on IMDB, STATS, TPC-H and TPC-DS are 113, 146, 30 and 115,
respectively. By reporting their (average) performance on $Q_{T+1},$
$Q_{T+2},$ $\ldots$, we compare the performance of learned optimizers after
they are deployed on a workload and stabilized for a while.

Setup. We deploy learned optimizers on a Linux machine with an Intel(R)
Xeon(R) Platinum 8163 CPU running at 2.5 GHz, 96 cores, 512GB DDR4 RAM and 1TB
SSD. It is also equipped with one NVIDIA RTX-2080TI GPU for model training and
inference. PostgreSQL 13.1 is installed and configured with 4GB shared
buffers.

###  6.2. Query Performance

We compare Lero with other optimizers for the two scenarios in Section 6.1.
For the hyper-parameters of Lero, we set the cardinality tuning factor
$\alpha=10$ and q-error upper bound $\Delta={10}^{2}$, so the set of scaling
factors is $F_{\alpha}^{\Delta}=\\{{10}^{-2},{10}^{-1},1,10,{10}^{2}\\}$. For
Bao and Bao+, we use the same family of 48 hint sets (Marcus, 2020a) for plan
generation. As in Bao’s original implementation (Marcus, 2020b), Bao and Bao+
select the same plan as PostgreSQL’s optimizer for the first 100 queries while
their machine learning models are trained and warmed up.

| Execution Time (in hour)
---|---
Query Optimizer | STATS | IMDB | TPC-H | TPC-DS
PostgreSQL | 20.19 | 1.15 | 0.94 | 1.68
Bao | 15.32 | 0.47 | 1.17 | 1.55
Bao+ | 13.85 | 0.41 | 0.89 | 1.57
Lero | 11.32 | 0.35 | 0.74 | 1.47
Fastest Found Plan | 10.73 | 0.19 | 0.72 | 1.39

Table 1. Overall performance of different query optimizers.

Figure 5. Per-query execution time of different query optimizers in comparison
with PostgreSQL on the STATS benchmark.

####  6.2.1. Performance with Stable Models

We first compare the performance of different optimizers, after Bao, Bao+, and
Lero have been deployed for a while and the model training converges after
seeing all training queries. We will then use the learned optimizers to
process the unseen test queries. Table 1 reports their performance on
finishing all test queries on all benchmarks. “Fastest Found Plan” refers to
the fastest plan generated by exhaustively search for each query. Overall,
Lero achieves the best performance, compared with Bao, Bao+, and PostgreSQL’s
optimizer. Its performance is close to the fastest found plans on STATS, TPC-H
and TPC-DS.

  * $\bullet$

Lero’s execution time is $70\%$, $44\%$, $21\%$ and $13\%$ less than
PostgreSQL’s native query optimizer on IMDB, STATS, TPC-H, and TPC-DS,
respectively. This demonstrates Lero’s practical value and advantages over the
traditional optimizer in this scenario.

  * $\bullet$

Lero’s execution time is $26\%$, $25\%$, $37\%$ and $5\%$ less than Bao on
IMDB, STATS, TPC-H and TPC-DS, respectively. This verifies the effectiveness
of our learning-to-rank paradigm and the pairwise trained comparator model
(rather than a model predicting the exact latency). Moreover, compared with
the hint set tuning approach in Bao, the plan explorer in Lero is able to
generate better and more diversified plans, as described in Section 4.2, for
the comparator model to learn and achieve superior query performance. Detailed
comparison and experimental analysis of different plan exploration strategies
will be given in Section 6.6.

  * $\bullet$

Bao+ learns from all the candidate plans generated by hint set tuning and
achieves a decent performance improvement over Bao. Nevertheless, Lero’s
execution time is still around $20\%$ less than Bao+ on the three benchmarks,
due to Lero’s more effective pairwise learning-to-rank model and plan
exploration strategy.

Figure 6. Performance curve of different query optimizers since deployment on
benchmarks.

####  6.2.2. Analysis of Performance Improvement/Regression.

Figure 5 compares the per-query execution time of each learned optimizer (Bao,
Bao+ and Lero) with PostgreSQL on the 146 test queries of STATS. We do not
plot the 47 queries, for each of which PostgreSQL and all the three learned
optimizers choose the same plan for execution. We sort all remaining queries
by latency differences between each optimizer and PostgreSQL from slowdown to
speedup to visualize performance regression/improvement of Lero and others.

In comparison to Bao and Bao+, Lero significantly reduces performance
regressions and brings much more performance gains. Only 9 queries ($6.2\%$)
are slowed down in Lero (for more than one second) among 146 queries, while 33
queries are accelerated significantly. Bao and Bao+ cause regressions for 29
queries each, which are even more than the number of queries they are able to
improve (26 in Bao and 24 in Bao+). When performance regression does happen in
Lero, the relative slowdown of execution time, however, is much smaller. For
instance, for the STATS workload, the maximum slowdown in Lero is $246s$,
which translates to a relative performance regression of $5.2\%$, while the
maximum slowdown in Bao is $1,276s$ with a relative performance regression of
$46.5\%$. Appendix C provides more detailed analysis on how the plans selected
by different optimizers rank among the truly best plans, which explains the
performance improvement in Lero.

####  6.2.3. Performance Curves since Deployment

In Figure 6, we meter the performance curves of learned optimizers since their
deployment for each workload, i.e., accumulated execution time of the best
plans chosen by different optimizers in each workload (see Section 6.1 for the
definition). The “Fastest Found Plan” curve refers to the conceptual latency
lower bound as is defined in Section 6.2.1.

  * $\bullet$

The training of Lero converges faster. After seeing 200 queries in IMDB, 100
queries in STATS, TPC-H and TPC-DS respectively, Lero’s performance is
consistently better than PostgreSQL and other learned optimizers. While Bao
and Bao+ eventually outperform PostgreSQL, they do so after seeing much more
queries. This confirms that training Lero’s learning-to-rank model for query
optimization is much more effective than training the latency prediction
models in Bao and Bao+.

  * $\bullet$

The performance gaps between Lero and Bao/Bao+ gradually enlarge as more and
more queries are executed. Eventually, Lero brings much more significant
performance gain over PostgreSQL than Bao and Bao+ do. Its total execution
time (right-end of each in Figure 6) is, e.g., $47\%$, $38\%$ and $23\%$ less
than PostgreSQL, Bao and Bao+, respectively, on STATS.

  * $\bullet$

Lero’s performance is more robust. It consistently outperforms PostgreSQL on
all the benchmarks while the performance of Bao and Bao+ is sometimes worse
than PostgreSQL (e.g. on TPC-H and TPC-DS). This is due to the intrinsic
hardness of latency prediction which could require more training data and more
time to converge in order to demonstrate any performance gain.

###  6.3. Query Optimization Cost

While achieving significant improvement in query execution performance, Lero
spends extra query optimization time in generating a list of candidate plans
for an input query and applying the comparator model to pick the best
candidate. The average query optimization time per-query of different
optimizers is reported in Table 2. We observe that this extra cost in query
optimization is very low. In particular, the total extra cost is only at most
$2.4\%$ of the total query execution time on IMDB and less than $0.1\%$ on
STATS, TPC-H and TPC-DS. Whereas, Lero saves $13\%$ to $70\%$ execution time
in comparison with PostgreSQL on these benchmarks.

###  6.4. Adapting to Dynamic Data

We now examine the performance of learned query optimizers on dynamic data. We
use the STATS dataset for the experiment as each tuple is associated with a
time stamp. We split the data by time. Initially, the earliest $50\%$ of the
data is stored in the database. After the first 200 queries are executed on
this database, we add $12.5\%$ of the data into the database in the order of
time stamps every 200 following queries. The goal is to evaluate how well
different learned optimizers adapt to dynamic data by updating their models.

We report the performance curve since deployment for each optimizer on dynamic
data in Figure 7(a), as well as their performance with stable models in Figure
7(b).

Lero outperforms PostgreSQL, Bao, and Bao+ in both settings. After 1,000
queries, Lero’s accumulated query execution time is $50\%$ less than
PostgreSQL and $38\%$ less than Bao/Bao+ (right-end of Figure 7(a)). In
parallel to query processing, all the learned optimizers continuously refine
their models to adapt to the dynamic changes of data. It turns out that Lero
adapts to such data changes better than the other two learned optimizers.
Eventually, after all the data changes are done, Lero’s query performance
(Figure 7(b)) is $33\%$, $29\%$ and $10\%$ better than PostgreSQL, Bao and
Bao+, respectively.

In Figure 7(a), we observe Lero’s robust performance, for the reason analyzed
at the end of Section 3.2. Only Lero consistently performs better than
PostgreSQL, while Bao is worse than PostgreSQL at the beginning and Bao+
performs worse in the middle.

(a) Performance since deployment (b) Performance  with  stable  models

Figure 7. Performance of optimizers on dynamic data.

Time (in millisecond) | PostgreSQL | Bao/Bao+ | Lero
---|---|---|---
IMDB | $842$ | $856$ | $1,736$
STATS | $7$ | $8.1$ | $16$
TPC-H | $5.3$ | $6.2$ | $12.6$
TPC-DS | $6.7$ | $8.5$ | $15.8$

Table 2. Average query optimization time per query.

###  6.5. Importance of Pre-Training

Lero relies on the pre-training procedure to learn from the native query
optimizer and better bootstrap its own model. The pre-training time is only
around 5 minutes on each of these benchmarks. It converges fast as the native
cost model often consists of functions with simple structures, i.e., piecewise
linear or quadratic function of estimated cardinalities of sub-queries with
magic constants as coefficients for different operators.

In this experiment, we evaluate the impact of the pre-training procedure on
Lero’s performance. We start with either a pre-trained comparator model, or a
cold-start model with random parameters; both are continuously trained/updated
as more and more queries are executed. Figure 8 illustrates their performance
curves on IMDB and STATS for the first 500 queries (the results on TPC-H are
similar, so the figure is omitted due to the space constraint).

With pre-training, for the initial 100 queries, Lero could generate almost the
same plans as PostgreSQL since its comparator is pre-trained to fit
PostgreSQL’s native cost model; thus, their performances are very close (this
can be also observed in our former experiments where Lero is pre-trained).
Note that Lero does not need to execute any query during the pre-training
procedure, as introduced in Section 3.2. Without pre-training, Lero’s
performance can be worse than PostgreSQL for the first 200 queries before it
eventually catches up. After executing nearly 300 queries, the slope of the
two methods are almost the same. This indicates that Lero with a cold-start
could catch up but with more training time.

Proper pre-training from the knowledge of the native query optimizer gives
Lero a good starting point and also accelerates its model’s convergence. With
pre-training, Lero could consistently outperform PostgreSQL after the initial
100 queries, while with a cold-start comparator, Lero consistently outperforms
PostgreSQL only after seeing nearly 200 queries.

Figure 8. Effects of pre-training on Lero’s performance curve.

|  | Average | Plans Faster | Plans Slower
---|---|---|---|---
Dataset | Strategy |  $\\#$ of Plans | than PostgreSQL | than PostgreSQL
IMDB |  Lero’s plan explorer | 9 | 47% | 42%
Hint set tuning | 16 | 36% | 57%
STATS |  Lero’s plan explorer | 5 | 31% | 49%
Hint set tuning | 19 | 25% | 69%
TPC-H |  Lero’s plan explorer | 7 | 24% | 64%
Hint set tuning | 15 | 6% | 88%

Table 3. Number and quality of unique candidate plans generated by different
plan exploration strategies.

Figure 9. Performance curves of Lero since deployment with different plan
exploration strategies.

###  6.6. Plan Exploration Strategies

Recall that, for each query, the plan explorer in Lero generates a list of
candidate plans, which need to include some truly good plans (for query
optimization) and be diversified (for model to learn new knowledge). Besides
the plan exploration strategy described in Figure 3, we also implement two
other alternative approaches in Lero to compare their performance: 1) the hint
set-based strategy introduced in Bao and 2) a random strategy which randomly
generates a number of plans.

Table 3 compares the quality and diversity of candidate plans generated by our
plan explorer with those generated by the hint set-based strategy. On the
third column, we report the number of unique plans without duplication. On one
hand, even with better performance, Lero’s plan explorer actually generates
fewer candidate plans per query on average than the hint set-based strategy
(duplicate plans may be output in different iterations of lines 4-8 in Figure
3), which helps bring down the exploration cost. On the other hand, a higher
percentage of candidate plans generated by Lero’s plan explorer run faster
than the plan generated by PostgreSQL’s native optimizer, which proves such
candidate plans worthy to explore and learn further. With cardinality tuning,
Lero’s plan explorer is able to generate more diversified plans while the hint
set-based strategy typically generates plans with minor difference.

Figure 9 reports performance curves of Lero using different plan exploration
strategies on IMDB and TPC-H (performance on STATS is similar to the one on
IMDB, and thus is omitted due to the space limits). Both Lero’s plan explorer
and the hint set-based tuning strategy perform much better than the random
strategy. We also observe that replacing Lero’s plan explorer with the hint
set-based tuning strategy performs worse. The hint set-based strategy has some
intrinsic limitations, as analyzed at the beginning of Section 4. Lero’s plan
explorer generates good and diversified plans for the pairwise comparator
model to explore and learn more effectively.

Figure 10. Performance curves of Lero since deployment with different amounts
of idle resource.

###  6.7. Effects of Idle Resource

We examine the performance curve of Lero since deployment with different
amounts of idle computation resource. By default, when an incoming query
$Q_{t+1}$ is to be processed, the comparator model in Lero is trained and
updated using execution statistics of different candidate plans for earlier
queries $Q_{1},Q_{2},\dots,Q_{t}$. Such statistics are collected by running
candidate plans in idle resource. When the idle resource is limited, we may
only be able to finish executing candidate plans for a fraction of earlier
queries $Q_{1},Q_{2},\dots,Q_{t}$. With only the first $50\%$, $25\%$, and
$12.5\%$ earlier queries having all of their candidates executed on idle
resource, we re-run the experiments in Section 6.2.3. We demonstrate in Figure
10 that the performance of Lero can still be improved over time and converge
eventually.

Even with limited idle resource, the initial performance of Lero is no worse
than PostgreSQL, thanks to the pre-training procedure. However, at the
beginning, the quality of the selected plans is indeed worse than the default
setting (when $100\%$ of earlier queries have their candidate plans executed
on idle resource), because the comparator model is not fully trained. We
observe that the model still converges fast even with very limited idle
resource. For instance, when only $12.5\%$ queries have their candidate plans
executed and explored, the model converges after the first 500 and 200 queries
on IMDB and STATS, respectively.

Regardless of under which configuration, Lero becomes stable eventually and
performs almost the same (curves become parallel towards the right end). This
implies that limited idle resource would definitely slow down the model’s
learning and convergence, but has little impact on the ultimate performance of
Lero.

| Random Split | Slow Split
---|---|---
Speedup Ratio | Train | Test | Train | Test
Bao | $1.62$ | $1.49$ | $1.17$ | $1.05$
Bao+ | $2.93$ | $1.58$ | $4.01$ | $1.74$
Balsa | $2.46$ | $1.55$ | $1.23$ | 2.31
Lero | 3.54 | 1.59 | 4.38 | 1.34

Table 4. Learned optimizers on IMDB with original JOB.

###  6.8. Comparison with Balsa

We compare Lero with Balsa on IMDB with the original JOB workload. We use its
open-source implementation in (Bal, 2022; Yang et al., 2022) and prepare the
dataset in the same way as (Yang et al., 2022). Specifically, the 113 queries
in JOB are split into a training set (with 94 queries) and a testing set (with
19 queries) in two ways: 1) random split and 2) the test set consists of the
19 slowest-running queries. We run Balsa using its default settings and
compare it with Lero, Bao, and Bao+.

Table 4 exhibits the speedup ratio of each learned query optimizer in
comparison to PostgreSQL’s native optimizer. The performance of Balsa matches
or outperforms Bao, which is consistent with the results in (Yang et al.,
2022). Both Bao and Balsa try to predict plan latency to guide plan search,
while Balsa has higher freedom of exploration (Bao’s search space is limited
by hint set tuning) (Yang et al., 2022). Thus, it performs better than Bao on
small and stable workload. However, even after Balsa’s model is
comprehensively trained on this small JOB workload, it still performs worse
than Bao+ and Lero.

##  7\. Related Work

Learning to Optimize Queries. Recently, there is a flurry of research to apply
machine learning in query optimization (Zhu et al., 2022). The majority of
them focus on learned cardinality estimation, using either query-driven or
data-driven approaches. Query-driven methods (Kipf et al., 2019; Dutt et al.,
2019; Liu et al., 2021) apply learned models to map featurized query to its
cardinality. Data-driven methods (Yang et al., 2019, 2021; Tzoumas et al.,
2011; Wu and Shaikhha, 2020; Hilprecht et al., 2020; Zhu et al., 2021) use
different generative models to directly learn the underlying data
distribution. Their superiority and limitations have been evaluated (Wang et
al., 2021; Han et al., 2021). Others focus on refining traditional cost models
and plan enumeration algorithms. For learned cost models, (Sun and Li, 2019)
and (Zhou et al., 2020; Zhi Kang et al., 2021) utilize TreeLSTM and
convolution models to learn cost of single and concurrent queries,
respectively. Plan enumeration is often modelled as a reinforcement learning
problem on deciding the best join order of tables. (Hester et al., 2018;
Krishnan et al., 2018) and (Yu et al., 2020) use simple neural networks and
TreeLSTM model as value networks for join order selection, respectively.
(Trummer et al., 2019) considers how to adjust the join order on the fly.
These works only optimize an individual component in query optimizer, which
does not necessarily improve the overall performance.

Besides them, recent works (Marcus et al., 2019; Yang et al., 2022) provide
end-to-end learned solutions for query optimization, and (Marcus et al., 2021)
learns to steer a native query optimizer using hint set tuning. However, as
analyzed in Section 1.1, they suffer from lots of deficiencies arising from
predicting the cost or latency. Based on plan exploration and pairwise plan
comparison, Lero learns the difference between plan pairs and learns to
improve the end-to-end quality of query optimization.

Learning-to-Rank Paradigm. Lero follows a learning-to-rank paradigm, which is
a class of learning techniques to train models for ranking tasks (Karatzoglou
et al., 2013; Vargas and Castells, 2011; Liu, 2009). It has been widely
applied for, e.g., document retrieval, collaborative filtering, and
recommendation systems. Based on how ranking is generated, the learning-to-
rank techniques could be classified into pointwise (Fuhr, 1989; Li et al.,
2007), pairwise (Freund et al., 2003; Liu et al., 2020) and listwise (Pang et
al., 2020; Swezey et al., 2021) approaches. Among them, pairwise approach
learns a classifier on a pair of items to identify which one is better. To our
best knowledge, we are the first to apply a pairwise learning-to-rank paradigm
to develop a learned query optimizer.

Learning to Tune Indexes. The task of indexing tuning is to find the set of
indexes that fits in a given storage budget and results in the lowest
execution cost for a given workload of queries. A traditional index tuner
(Chaudhuri and Narasayya, 1997; Valentin et al., 2000; Agrawal et al., 2004)
first searches for the optimal index configuration for each query (query-level
search), and then enumerates different sets of those index configurations to
find the optimal index set for the workload under the budget (workload-level
search). Both phases need to compare the execution costs of two plans of the
same query given different index configurations. Traditional index tuners rely
on optimizer’s estimates for such comparisons, while (Ding et al., 2019)
trains a classifier to this end with higher accuracy.

While the query-level search in (Ding et al., 2019) can be regarded as an
application of learning-to-rank in index tuning, it has two fundamental
differences in comparison to Lero. First, the index tuner in (Ding et al.,
2019) is similar to traditional tuners (Chaudhuri and Narasayya, 1997;
Valentin et al., 2000; Agrawal et al., 2004), except that the classifier, as a
pairwise comparator model, is invoked during search procedures to determine
whether the plan of a query under a new index configuration is improved in
comparison to the one under the initial one; for a completely different task,
query optimization, Lero is equipped with two carefully designed components,
plan explorer and plan comparator model, which work together to explore the
plan space. Second, the comparator models in (Ding et al., 2019) and Lero both
compare the performance of two plans; however, with different goals in the two
tasks, the ways how features are encoded and the model architectures in the
two comparators are different. Appendix C compares the two models
experimentally.

##  8\. Conclusions

We propose Lero, a learning-to-rank query optimizer. First, Lero applies
learning-to-rank machine learning techniques to query optimization. We argue
that it is an overkill to develop machine models to predict the exact
execution latency or cardinalities in terms of query optimization. Instead,
Lero adopts a pairwise approach to train a binary classifier to compare any
two plans, which is proven to be more efficient and effective. Second, Lero
takes advantage of decades of wisdom of database research and jointly works
with the native query optimizer to improve optimization quality. Third, Lero
is equipped with a plan exploration strategy, which enables Lero to explore
new optimization opportunities more effectively. Finally, an extensive
evaluation on our implementation on top of PostgreSQL demonstrates Lero’s
superiority in query performance and its ability to adapt to changing data and
workload.

## References

  * (1)
  * Bal (2022) 2022\.  Balsa Implementation.  https://github.com/balsa-project/balsa.
  * Ler (2022) 2022\.  Lero on PostgreSQL.  https://github.com/Blondig/Lero-on-PostgreSQL.
  * Agrawal et al. (2004) Sanjay Agrawal, Surajit Chaudhuri, Lubor Kollár, Arunprasad P. Marathe, Vivek R. Narasayya, and Manoj Syamala. 2004\.  Database Tuning Advisor for Microsoft SQL Server 2005\. In _VLDB_. 1110–1121.
  * Chaiken et al. (2008) Ronnie Chaiken, Bob Jenkins, Per-Åke Larson, Bill Ramsey, Darren Shakib, Simon Weaver, and Jingren Zhou. 2008.  Scope: easy and efficient parallel processing of massive data sets.  _PVLDB_ 1, 2 (2008), 1265–1276.
  * Chaudhuri and Narasayya (1997) Surajit Chaudhuri and Vivek R. Narasayya. 1997.  An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server. In _VLDB_. 146–155.
  * Chen et al. (2016) Jianmin Chen, Xinghao Pan, Rajat Monga, Samy Bengio, and Rafal Jozefowicz. 2016.  Revisiting distributed synchronous SGD.  _arXiv:1604.00981_ (2016).
  * Council(TPC) (2021a) Transaction Processing Performance Council(TPC). 2021a.  TPC-DS Vesion 2 and Version 3.  http://www.tpc.org/tpcds/.
  * Council(TPC) (2021b) Transaction Processing Performance Council(TPC). 2021b.  TPC-H Vesion 2 and Version 3.  http://www.tpc.org/tpch/.
  * Dey et al. (2008) Atreyee Dey, Sourjya Bhaumik, Harish Doraiswamy, and Jayant R. Haritsa. 2008.  Efficiently approximating query optimizer plan diagrams.  _Proc. VLDB Endow._ 1, 2 (2008), 1325–1336.
  * Ding et al. (2019) Bailu Ding, Sudipto Das, Ryan Marcus, Wentao Wu, Surajit Chaudhuri, and Vivek R Narasayya. 2019.  Ai meets ai: Leveraging query executions to improve index recommendations. In _SIGMOD_. 1241–1258.
  * Doraiswamy et al. (2008) Harish Doraiswamy, Pooja N. Darera, and Jayant R. Haritsa. 2008.  Identifying robust plans through plan diagram reduction.  _Proc. VLDB Endow._ 1, 1 (2008), 1124–1140.
  * Dutt et al. (2019) Anshuman Dutt, Chi Wang, Azade Nazi, Srikanth Kandula, Vivek Narasayya, and Surajit Chaudhuri. 2019.  Selectivity estimation for range predicates using lightweight models.  _PVLDB_ 12, 9 (2019), 1044–1057.
  * Freund et al. (2003) Yoav Freund, Raj Iyer, Robert E Schapire, and Yoram Singer. 2003\.  An efficient boosting algorithm for combining preferences.  _Journal of machine learning research_ 4, Nov (2003), 933–969.
  * Fuhr (1989) Norbert Fuhr. 1989\.  Optimum polynomial retrieval functions based on the probability ranking principle.  _ACM Transactions on Information Systems_ 7, 3 (1989), 183–204.
  * Han (2021) Yuxing Han. 2021\.  Github repository: STATS End-to-End CardEst Benchmark.  https://github.com/Nathaniel-Han/End-to-End-CardEst-Benchmark.
  * Han et al. (2021) Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Tan Wei Liang, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, Zhengping Qian, Jingren Zhou, Jiangneng Li, and Bin Cui. 2021\.  Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation.  _PVLDB_ 15, 4 (2021), 752–765.
  * Hester et al. (2018) Todd Hester, Matej Vecerik, Olivier Pietquin, Marc Lanctot, Tom Schaul, Bilal Piot, Dan Horgan, John Quan, Andrew Sendonaris, Ian Osband, et al. 2018\.  Deep q-learning from demonstrations. In _AAAI_. 3223–3230.
  * Hilprecht et al. (2020) Benjamin Hilprecht, Andreas Schmidt, Moritz Kulessa, Alejandro Molina, Kristian Kersting, and Carsten Binnig. 2020.  DeepDB: learn from data, not from queries!  _PVLDB_ 13, 7, 992–1005.
  * Johannes and Eyke (2011) Fürnkranz Johannes and Hüllermeier Eyke. 2011.  _Preference Learning_.  Preference Learning.
  * Kanet and Sridharan (2000) John J Kanet and V Sridharan. 2000.  Scheduling with inserted idle time: problem taxonomy and literature review.  _Operations Research_ 48, 1 (2000), 99–110.
  * Karatzoglou et al. (2013) Alexandros Karatzoglou, Linas Baltrunas, and Yue Shi. 2013\.  Learning to rank for recommender systems. In _RecSys_. ACM, 493–494.
  * Kipf et al. (2019) Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. 2019\.  Learned cardinalities: Estimating correlated joins with deep learning. In _CIDR_.
  * Krishnan et al. (2018) Sanjay Krishnan, Zongheng Yang, Ken Goldberg, Joseph Hellerstein, and Ion Stoica. 2018.  Learning to optimize join queries with deep reinforcement learning.  _arXiv:1808.03196_ (2018).
  * Leis et al. (2015) Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2015\.  How good are query optimizers, really?  _PVLDB_ 9, 3 (2015), 204–215.
  * Li et al. (2012) Jiexing Li, Arnd Christian König, Vivek Narasayya, and Surajit Chaudhuri. 2012.  Robust estimation of resource consumption for sql queries using statistical techniques.  _arXiv:1208.0278_ (2012).
  * Li et al. (2007) Ping Li, Qiang Wu, and Christopher Burges. 2007.  Mcrank: Learning to rank using multiple classification and gradient boosting.  _Advances in neural information processing systems_ 20 (2007).
  * Liu et al. (2021) Jie Liu, Wenqian Dong, Qingqing Zhou, and Dong Li. 2021\.  Fauce: fast and accurate deep ensembles with uncertainty for cardinality estimation.  _PVLDB_ 14, 11 (2021), 1950–1963.
  * Liu (2009) Tie-Yan Liu. 2009\.  Learning to Rank for Information Retrieval.  _Foundations and Trends in Information Retrieval_ 3, 3 (2009), 225–331.
  * Liu et al. (2020) Weiwen Liu, Qing Liu, Ruiming Tang, Junyang Chen, Xiuqiang He, and Pheng Ann Heng. 2020\.  Personalized Re-ranking with Item Relationships for E-commerce. In _CIKM_. 925–934.
  * Marcus (2020a) Ryan Marcus. 2020a.  Bao appendix.  https://rmarcus.info/appendix.html.
  * Marcus (2020b) Ryan Marcus. 2020b.  Github repository: Bao for PostgreSQL.  https://github.com/learnedsystems/BaoForPostgreSQL.
  * Marcus et al. (2021) Ryan Marcus, Parimarjan Negi, Hongzi Mao, Nesime Tatbul, Mohammad Alizadeh, and Tim Kraska. 2021\.  Bao: Making learned query optimization practical. In _SIGMOD_. 1275–1288.
  * Marcus et al. (2019) Ryan Marcus, Parimarjan Negi, Hongzi Mao, Chi Zhang, Mohammad Alizadeh, Tim Kraska, Olga Papaemmanouil, and Nesime Tatbul. 2019\.  Neo: A Learned Query Optimizer.  _PVLDB_ 12, 11 (2019), 1705–1718.
  * Marcus and Papaemmanouil (2019) Ryan Marcus and Olga Papaemmanouil. 2019.  Plan-structured deep neural network models for query performance prediction.  _PVLDB_ 12, 11 (2019), 1733–1746.
  * Moerkotte et al. (2009) Guido Moerkotte, Thomas Neumann, and Gabriele Steidl. 2009\.  Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors.  _VLDB_ 2, 1 (2009), 982–993.
  * Mou et al. (2016) Lili Mou, Ge Li, Lu Zhang, Tao Wang, and Zhi Jin. 2016.  Convolutional neural networks over tree structures for programming language processing. In _AAAI_. 1287–1293.
  * Negi et al. (2021) Parimarjan Negi, Matteo Interlandi, Ryan Marcus, Mohammad Alizadeh, Tim Kraska, Marc Friedman, and Alekh Jindal. 2021.  Steering Query Optimizers: A Practical Take on Big Data Workloads. In _SIGMOD_. 2557–2569.
  * Pang et al. (2020) Liang Pang, Jun Xu, Qingyao Ai, Yanyan Lan, Xueqi Cheng, and Jirong Wen. 2020\.  Setrank: Learning a permutation-invariant ranking model for information retrieval. In _SIGIR_. 499–508.
  * Reddy and Haritsa (2005) Naveen Reddy and Jayant R. Haritsa. 2005.  Analyzing Plan Diagrams of Database Query Optimizers. In _VLDB_. 1228–1240.
  * Selinger et al. (1989) P Griffiths Selinger, Morton M Astrahan, Donald D Chamberlin, Raymond A Lorie, and Thomas G Price. 1989\.  Access path selection in a relational database management system.  In _Readings in Artificial Intelligence and Databases_. Elsevier, 511–522.
  * Sun and Li (2019) Ji Sun and Guoliang Li. 2019.  An end-to-end learning-based cost estimator.  _PLDB_ 13, 3 (2019), 307–319.
  * Swezey et al. (2021) Robin Swezey, Aditya Grover, Bruno Charron, and Stefano Ermon. 2021.  Pirank: Scalable learning to rank via differentiable sorting.  _Advances in Neural Information Processing Systems_ 34 (2021), 21644–21654.
  * Thompson (1933) William R Thompson. 1933\.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ 25, 3-4 (1933), 285–294.
  * Trummer et al. (2019) Immanuel Trummer, Junxiong Wang, Deepak Maram, Samuel Moseley, Saehan Jo, and Joseph Antonakakis. 2019\.  Skinnerdb: Regret-bounded query evaluation via reinforcement learning. In _SIGMOD_. 1153–1170.
  * Tzoumas et al. (2011) Kostas Tzoumas, Amol Deshpande, and Christian S Jensen. 2011\.  Lightweight graphical models for selectivity estimation without independence assumptions.  _PVLDB_ 4, 11 (2011), 852–863.
  * Valentin et al. (2000) Gary Valentin, Michael Zuliani, Daniel C. Zilio, Guy M. Lohman, and Alan Skelley. 2000.  DB2 Advisor: An Optimizer Smart Enough to Recommend Its Own Indexes. In _ICDE_. 101–110.
  * Vargas and Castells (2011) Saúl Vargas and Pablo Castells. 2011.  Rank and relevance in novelty and diversity metrics for recommender systems. In _Proceedings of the fifth ACM conference on Recommender systems_. 109–116.
  * Wang et al. (2021) Xiaoying Wang, Changbo Qu, Weiyuan Wu, Jiannan Wang, and Qingqing Zhou. 2021.  Are We Ready For Learned Cardinality Estimation?  _PVLDB_ 14, 9 (2021), 1640–1654.
  * Wu et al. (2013) Wentao Wu, Yun Chi, Shenghuo Zhu, Junichi Tatemura, Hakan Hacigümüs, and Jeffrey F Naughton. 2013.  Predicting query execution time: Are optimizer cost models really unusable?. In _ICDE_. 1081–1092.
  * Wu and Shaikhha (2020) Ziniu Wu and Amir Shaikhha. 2020.  BayesCard: A Unified Bayesian Framework for Cardinality Estimation.  _arXiv:2012.14743_ (2020).
  * Yang et al. (2022) Zongheng Yang, Wei-Lin Chiang, Sifei Luan, Gautam Mittal, Michael Luo, and Ion Stoica. 2022\.  Balsa: Learning a Query Optimizer Without Expert Demonstrations.  _SIGMOD_ (2022), 931–944.
  * Yang et al. (2021) Zongheng Yang, Amog Kamsetty, Sifei Luan, Eric Liang, Yan Duan, Xi Chen, and Ion Stoica. 2021.  NeuroCard: One Cardinality Estimator for All Tables.  _PVLDB_ 14, 1 (2021), 61–73.
  * Yang et al. (2019) Zongheng Yang, Eric Liang, Amog Kamsetty, Chenggang Wu, Yan Duan, Xi Chen, Pieter Abbeel, Joseph M Hellerstein, Sanjay Krishnan, and Ion Stoica. 2019\.  Deep unsupervised cardinality estimation.  _PVLDB_ 13, 3 (2019), 279–292.
  * Yu et al. (2020) Xiang Yu, Guoliang Li, Chengliang Chai, and Nan Tang. 2020\.  Reinforcement learning with tree-lstm for join order selection. In _ICDE_. 1297–1308.
  * Zhi Kang et al. (2021) Johan Kok Zhi Kang, Sien Yi Tan, Feng Cheng, Shixuan Sun, and Bingsheng He. 2021\.  Efficient Deep Learning Pipelines for Accurate Cost Estimations Over Large Scale Query Workload. In _SIGMOD_. 1014–1022.
  * Zhou (2015) Li Zhou. 2015.  A survey on contextual multi-armed bandits.  _arXiv:1508.03326_ (2015).
  * Zhou et al. (2020) Xuanhe Zhou, Ji Sun, Guoliang Li, and Jianhua Feng. 2020\.  Query performance prediction for concurrent queries using graph embedding.  _PVLDB_ 13, 9 (2020), 1416–1428.
  * Zhu et al. (2022) Rong Zhu, Ziniu Wu, Chengliang Chai, Andreas Pfadler, Bolin Ding, Guoliang Li, and Jingren Zhou. 2022.  Learned Query Optimizer: At the Forefront of AI-Driven Databases.. In _EDBT_. 1–4.
  * Zhu et al. (2021) Rong Zhu, Ziniu Wu, Yuxing Han, Kai Zeng, Andreas Pfadler, Zhengping Qian, Jingren Zhou, and Bin Cui. 2021\.  FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation.  _PVLDB_ 14, 9 (2021), 1489–1502.

## Appendix

##  Appendix A Comparator with $d$-$dim$ Embedding

Our plan comparator model ${\sf CmpPlan}$ (described in Section 3.1) could be
easily extended from 1-$dim$ plan embedding to use $d$-$dim$ ($d>1$) plan
embedding. We use the same way on encoding plans and slightly modify the plan
comparator model (shown in Figure 2) as follows:

  1. (1)

In the plan embedding layers, we change the output dimension of last embedding
layer to $d$ so that the plan embedding ${\sf PlanEmb}(P)$ becomes a $d$-$dim$
vector for any plan $P$.

  2. (2)

We change the comparison layer to a learnable linear layer. It takes two
$d$-$dim$ vectors ${\sf PlanEmb}(P_{1})$ and ${\sf PlanEmb}(P_{2})$ as inputs,
and outputs $0$ ($P_{1}$ is better) or $1$ ($P_{2}$ is better).

Next, we discuss how to select the best plan under $d$-$dim$ embedding (in
A.1) and the performance of plan comparator w.r.t. the dimensions of plan
embedding (in A.2).

###  A.1. Selecting the Best Plan using Comparators

Recall that the plan comparator ${\sf CmpPlan}(P_{1},P_{2})$ is an oracle
comparing any two plans $P_{1}$ and $P_{2}$ of a query. Given a list of
candidate plans $P_{1},P_{2},\dots,P_{n}$ of a query, for $d$-$dim$
embeddings, let

(7) ${\rm Wins}(P_{i})=|\\{P_{j}\mid{\sf CmpPlan}(P_{i},P_{j})=0,j\neq i\\}|,$

be the number of plans whose latencies are worse than $P_{i}$. ${\rm
Wins}(P_{i})$ defines a full order of all candidate plans. Obviously, the best
candidate plan $P^{*}$ has ${\rm Wins}(P^{*})=n-1$.

A comparator with $d$-$dim$ plan embeddings can be trained in a pairwise way
similar to the one introduced in Section 3.2 (without pre-training though).
After the comparator is fully trained, we can use it to pick the best plan
among candidates $P_{1},\ldots,P_{n}$ of a possibly unseen query $Q$. In the
general design where we have $d\geq 1$ for the plan embeddings, we do not
require a fully trained ${\sf CmpPlan}$ to preserve transitivity, i.e.,
$P_{1}$ is better than $P_{2}$ and $P_{2}$ is better than $P_{3}$ imply that
$P_{1}$ is better than $P_{3}$. In order to pick the best plan among
candidates $P_{1},\ldots,P_{n}$, we can invoke ${\sf CmpPlan}$ $n(n-1)$ times
to compare all pairs of candidates. In general, the output ${\sf
CmpPlan}(P_{i},P_{j})\in(0,1)$ gives a soft prediction (i.e., the predicted
probability of whether $P_{i}$ or $P_{j}$ is better). We use the algorithm
$\mathcal{A}$ in Eq. (3) to pick the better one, and define randomized wins as

${\rm RandomWins}(P_{i})=|\\{P_{j}\mid\mathcal{A}(P_{i},P_{j})=P_{i},j\neq
i\\}|.\vspace{-0.3em}$

Accordingly, in the $d$-$dim$ setting, we choose the best plan as

$P^{*}=\operatorname*{arg\,max}_{P_{i}\in\\{P_{1},\ldots,P_{n}\\}}{\rm
RandomWins}(P_{i})\vspace{-0.3em}$

with the most randomized wins–ties are broken arbitrarily.

In the more practical design of ${\sf CmpPlan}$ with $1$-$dim$ plan embedding
(Section 3.1), we do not need to derive ${\rm RandomWins}(P_{i})$ as above.
Instead, the output of the sub-model ${\sf PlanEmb}$ defines a total order on
all candidate plans. For any pair of plans $(P_{i},P_{j})$, if ${\sf
PlanEmb}(P_{i})>{\sf PlanEmb}(P_{j})$, we always have ${\sf
CmpPlan}(P_{i},P_{j})>0.5$, i.e., $P_{j}$ is more preferable than $P_{i}$ with
higher probability than vice versa. Therefore, we could select
$P^{*}=\operatorname*{arg\,min}_{P_{i}}{\sf PlanEmb}(P_{i})$ in the $1$-$dim$
setting as the best plan for execution.

We can show that, $P^{*}$ chosen in this way is indeed the one with the most
randomized wins in expectation (thus, the choice is equivalent to the one for
the general design, in expectation).

###### Proposition 0.

$P^{*}=\operatorname*{arg\,min}_{P_{i}}{\sf PlanEmb}(P_{i})$ chosen with the
lowest $1$-$dim$ embedding also wins the most: it satisfies

$P^{*}=\operatorname*{arg\,max}_{P_{i}\in\\{P_{1},\ldots,P_{n}\\}}\mathbb{E}\left[{\rm
RandomWins}(P_{i})\right].\vspace{-0.3em}$

###### Proof.

By the model construction, for each $P_{i}$, we have

$\displaystyle\mathbb{E}\left[{\rm
RandomWins}(P_{i})\right]=\sum_{j\in[n],j\neq
i}\operatorname*{Pr}\left[\mathcal{A}(P_{i},P_{j})=P_{i}\right]$
$\displaystyle=$ $\displaystyle\sum_{j\in[n],j\neq i}\\!\\!\\!\\!\\!\\!(1-{\sf
CmpPlan}(P_{i},P_{j}))=\\!\\!\\!\\!\\!\\!\sum_{j\in[n],j\neq
i}\\!\\!\\!\\!\\!\\!{\sf CmpPlan}(P_{j},P_{i})$ (8) $\displaystyle=$
$\displaystyle\left(\sum_{j\in[n]}\\!\\!\phi({\sf PlanEmb}(P_{j})-{\sf
PlanEmb}(P_{i}))\right)-\phi(0).$

From Eq. (8), it is straightforward that $P^{*}\in\\{P_{1},\ldots,P_{n}\\}$
with the lowest ${\sf PlanEmb}(\cdot)$ would maximize $\mathbb{E}\left[{\rm
RandomWins}(\cdot)\right]$. ∎

###  A.2. Performance of Comparator with Different Dimension of Plan Embedding

We test the performance of Lero with different dimensions of plan embedding.
We set $d=\\{1,2,4,8,16\\}$, train Lero on the training workload and then test
its performance on the test workload. Table 5 reports the execution time of
Lero with different dimensions of plan embedding on IMDB and STATS benchmarks.
Similar results are also observed on TPC-H and TPC-DS benchmarks.

Time (in hour) | IMDB | STATS
---|---|---
PostgreSQL | 1.15 | 20.19
Lero ($d=1$) | 0.35 | 11.32
Lero ($d=2$) | 0.77 | 20.74
Lero ($d=4$) | 0.69 | 21.2
Lero ($d=8$) | 0.49 | 21.38
Lero ($d=16$) | 0.59 | 21.19

Table 5. Performance of Lero with different dimensions of plan embedding.

Interestingly, we observe that the performance of Lero does not necessarily
increase with higher dimensional embeddings. On the contrary, Lero with
complex embedding ($d>1$) has much worse performance than using the simplest
1-$dim$ plan embedding. Specifically, on IMDB, the the execution time of Lero
with a larger $d\in\\{2,4,8,16\\}$ is $1.4$ times to $2.2$ times as long as
the case with $d=1$. On STATS, the execution time of Lero with $d>1$ is around
$1.8$ times longer than $d=1$, even longer than the execution time of the
native PostgreSQL. The reason could be that, with $d>1$, the embedding model
${\sf PlanEmb}$ tries to summarize more sophisticated information in plan
embeddings, but also requires larger training dataset and more training time
to obtain more accurate embeddings and to converge. Therefore, the training
workload may be not enough to comprehensively capture enough information for
plan comparison, so the selected plan may be not the best one.

In our experiments, Lero using 1-$dim$ plan embedding already attains
significant performance improvement in comparison to the native query
optimizer. Moreover, when $d>1$, it is not as convenient to select the best
plan as when $d=1$ (although Proposition A.1 says that there is an equivalent
way for plan selection), since ${\sf PlanEmb}(P)$ cannnot define a total order
on all plans $P$ when $d>1$. Thus, we use the simplest 1-$dim$ plan embeddings
in Lero.

##  Appendix B Exploration Heuristic based on Plan Diagram

Errors in estimating predicate selectivities can be propagated from bottom to
top during the plan search, and incur a wrong join order and sub-optimal
choices of join types. A plan diagram (Doraiswamy et al., 2008; Dey et al.,
2008) can be constructed by varying values of parameters in one or more
predicates of the query $Q$, so that the optimizer generates a set of
different plans. For example, for a query with a parameterized predicate
“${\sf@lower}$ $\leq$ ${\sf Age}$ $\leq$ ${\sf@upper}$”, the optimizer may
generate different plans by setting $({\sf@lower},{\sf@upper})$ as $(20,30)$
or $(10,40)$. These plans form a diagram of different regions on the 2D space
$({\sf@lower},{\sf@upper})$: within each region, the optimizer outputs the
same plan.

It is shown in (Doraiswamy et al., 2008; Dey et al., 2008) that replacing
selectivity error-sensitive plan choices with alternatives in the plan diagram
provides potentially better performance. Therefore, we can use plans in the
plan diagram as the list of candidates to explore the uncertainty from
estimating predicates’ selectivities in the native optimizer.

The drawbacks of this strategy are obvious. It is not affordable to generate a
plan diagram by varying parameters on more than two tables, as the number of
candidate plans would be too large (Dey et al., 2008). If we tune parameters
on two tables, the candidates may not be diversified enough to include plans
with quality sufficiently higher than the plan generated by the native
optimizer. In our evaluation on the STATS benchmark (Han et al., 2021), even
the best candidate in a plan diagram does not have significant performance
improvement. Specifically, the average performance improvement of the best
candidate is less than $3\%$, and the best candidates of only less than $5\%$
of queries are faster than those generated by PostgreSQL’s optimizer.

##  Appendix C Additional Experiments

###  C.1. Rank-Specific Analysis

For a query optimizer, what we care about is whether the selected plan $P^{*}$
is truly the best one; if not, whether it is among the top-$k$ best plans. To
this end, let $\mathcal{P}_{k}$ be the set of top-$k$ fastest plans generated
by exhaustively search for each query (in terms of execution time). For
different benchmarks, we record the ratio of queries for which $P^{*}$ falls
into $\mathcal{P}_{k}$. Table 6 lists results for each query optimizer for
$\mathcal{P}_{1}$ and $\mathcal{P}_{5}$. The percentage of plans selected by
Lero falling into $\mathcal{P}_{1}$ and $\mathcal{P}_{5}$ is much higher than
that by other query optimizers. This verifies that Lero could find plans
having higher quality in terms of the rank-specific metrics.

Query | Plans in $\mathcal{P}_{1}$ | Plans in $\mathcal{P}_{5}$
---|---|---
Optimizer | STATS | IMDB | TPC-H | STATS | IMDB | TPC-H
PostgreSQL | 0.137 | 0.000 | 0.167 | 0.459 | 0.336 | 0.867
Bao | 0.144 | 0.159 | 0.000 | 0.226 | 0.230 | 0.167
Bao+ | 0.096 | 0.221 | 0.833 | 0.171 | 0.319 | 1.000
Lero | 0.425 | 0.442 | 0.733 | 0.925 | 0.708 | 1.000

Table 6. Rank-specific metrics for different query optimizers.

Figure 11. Performance curves of Lero with different comparator models.

###  C.2. Effects of Comparator Model

To verify the effectiveness of our comparator model in Lero, we conduct an
experiment to replace Lero’s plan encoding approach and comparator model with
the ones in (Ding et al., 2019), and compare their performance. The results on
IMDB and TPC-H are reported in Figure 11. Lero with the comparator model from
(Ding et al., 2019) performs much worse than ours, which is not surprising as
the model from (Ding et al., 2019) does not consider the structural
information in the plan.

Specifically, the goal of (Ding et al., 2019) is index selection, what really
matters is the amount of work done in the plan by the each type of operators,
with or without indexes. Thus, a plan is flattened as a vector encoding the
total estimated costs and amount of data processed by each type of operator.
In Lero, the goal is plan selection, and thus we need finer-grained
information on each node (e.g., operator type, estimates, tables involved)
unfolded and use the tree convolution operation to capture more structural
information and correlation between tables.