![](https://csdnimg.cn/release/download_crawler_static/89216132/bg4.jpg)
Aggregated execution stats
Application requests
Cross-database
offline model
Deploy
model
Execution History
Query
Optimizer
DBMS Engine
Query
Execution
Metadata
Index Tuner
Classifier
Search Algorithm
Query-level
Workload-
level
Q, C
H
<P
1
, P
2
>
Regress,
Improve
Cloud Database Service
P
H
“what-if” API
Figure 2: Overview of an architecture leveraging the
classier trained on aggregated execution data from
multiple databases in a cloud database service.
2.3 Architecture
Figure 2 illustrates the end-to-end architecture of an in-
dex tuner leveraging aggregated execution data in a cloud
platform, such as Azure SQL Database. Databases emit ag-
gregated query plan execution statistics through telemetry.
These statistics include the featurized plans (see Section 3.2)
from dierent index congurations, which happen naturally
as indexes are changed by human administrators or auto-
mated services [
24
,
52
]. Plans of the same query are identied
with a unique query hash generated by Azure SQL Database
from the abstract syntax tree. Using dierent plans for the
same query, we construct the pairs that provide the nal fea-
ture vectors (see Section 3.3) and use plans’ execution cost
to assign the class label. We train a classier by aggregating
this data across databases, which corresponds to the oine
model (Section 4.1). This oine model is then deployed for
the index tuner to use during its search for index cong-
urations (Section 5). The application’s queries execute in
parallel to the index tuner implementing its indexes, similar
to the auto-indexing service in Azure SQL Database [
24
].
These new congurations result in additional execution data
collected local to each database. We adapt the model to each
database (Section 4.3) by retraining the adaptive model on
these additional data at each invocation of the index tuner.
3 FEATURIZING QUERY PLAN PAIRS
3.1 Rationale
The input to the classication task is a pair of query plans,
where each query plan is a tree of operators. O-the-shelf
ML techniques rely on feature vectors of xed dimensions.
Hence, we need to convert the pair of query plans into fea-
ture vectors. Several approaches exist to convert graphical or
tree-structured data into vectors [
33
,
71
]. While being more
general purpose, such approaches do not leverage informa-
tion specic to database semantics and critical for execution
cost that query plans encode, e.g., operator type, parallelism,
execution mode, etc. To better leverage such information, we
develop a featurization, inspired by other approaches used
for DB applications (e.g.,[
5
,
31
]), that is ecient and results
in models with high accuracy. While some featurization as-
pects leverage the details of SQL Server, we expect the key
ideas are applicable to other database engines.
We use the following guiding principles to encode the
semantics of the query plans and other factors that contribute
to execution cost in our featurization:
• Learn across queries and databases:
Be schema agnos-
tic to allow cross-database learning, leveraging execution
data from millions of databases in a cloud platform.
• Learn from the optimizer:
Leverage the valuable infor-
mation presented in query plans generated by industrial-
strength query optimizers.
• Learn from information in estimated query plans:
The index tuner can search for congurations that have
never been implemented. Thus, execution statistics, such
as true cardinalities, are rarely available at inference time.
Featurization should not use such information.
In addition to the above principles, the feature vectors should
encode the following key types of information that provide
a way for the model to learn the classication task:
• Measure of work done:
The query optimizer’s estimate
for an operator’s cost or the number of rows processed by
an operator are example features for this measure.
• Structural information:
Join orders or the position of
an operator in the plan is often useful, especially when
comparing two plans for the same query.
• Physical operator details:
Physical operators in a plan
play a crucial role in the cost. For instance, a nested loop
join will have very dierent cost compared to a merge join
even if they correspond to the same logical join operator.
We assume all execution data is collected on similar hard-
ware; extensions to heterogeneous hardware is future work.
3.2 Featurizing a Plan
Guided by our principle of being able to learn across plans,
queries, and databases and our goal of capturing physical
operator details, we use the physical operators supported
by SQL Server as our feature dimensions or attributes.
SQL Server supports a set of physical operators (such as
Index Scan, Table Scan, Hash Join, etc.) which are known in
advance and also do not change very frequently. A query
plan is a tree of these physical operators. Two additional
properties of physical operators are relevant to execution
cost:
(a)
parallelism: whether the operator is single-threaded
(serial) or multi-threaded (parallel); and
(b)
execution mode:
whether the operator processes one row at a time (row
mode) or a batch of data items in a vectorized manner
(batch mode). Each operator is assigned a
key
of the form