ICDM’23 BICE论文解读

0 导读

本文《Efficient Cardinality and Cost Estimation with Bidirectional Compressor-based Ensemble Learning》是由华为云数据库创新Lab联合电子科技大学数据与智能实验室发表在顶会ICDM’23的长文。ICDM是数据挖掘领域顶级学术会议之一。本届会议共收到投稿1003篇，其中录用长文94篇，长文录取率约为9.37%，总体录取率约为19.94%。

摘要

查询优化器在数据库管理系统中有着非常重要的作用，而基数和代价估计是查询优化器能否输出高质量执行计划的基础。为增强基数和代价估计，我们提出了一种基于双向LSTM和集成学习的模型框架，名为BICE。具体地，我们设计了4个自编码器组成特征提取器对查询计划中不同种类的丰富信息进行提取与编码。我们通过图嵌入算法学习表与表之间的关联，并作为连接条件编码的依据。之后，我们建立了双向LSTM对物理计划进行学习。此外，我们通过基于贝叶斯神经网络结合主动学习抽取不同的数据样本集合，以此来提高模型在复杂查询上的下性能表现。最后，我们在公开数据集上进行了大量的实验以论证BICE的有效性。

问题描述

一条查询语句$q$中包含若干个连接条件$J=\{J_{1},J_{2},...,J_{m}\}$和若干个谓词过滤条件$F=\{F_{1},F_{2},...,F_{m}\}$。通过DBMS的查询优化器，我们可以获取查询语句$q$对应的查询计划$p$。本文要解决的问题是：给定一条查询语句$q$，将其查询计划$p$输入到训练过的函数$f$中，得到其基数与执行时间，即$f(q)=(C(q),T(q))$。$C(q)$和$T(q)$分别表示基数与执行时间。

特征编码

首先，本文通过深度优先搜索（DFS）得到查询计划对应的节点序列。之后，本文设计了特征编码器用以抽取查询计划中蕴含的丰富信息，其由四个子编码器组成，分别是连接编码器、类型编码器、谓词编码器和信息编码器。下面，本文对各个子编码器的细节进行介绍。

连接编码器

连接编码器学习并编码查询语句中的若干连接条件$J$。先前的模型（如MSCN等）大多基于one-hot编码方法对连接条件进行规则编码。这种方法的最大缺陷在于，无法表示表和列之间的结构关系。因此，本文首先应用图嵌入算法学习数据库中的列关系。具体来讲，本文采用node2vec算法：$e_i=node2vec(c_i)$。$c_i$表示数据库中的列，$e_i$表示其对应的嵌入向量。之后，本文将连接条件中对应的两个列进行拼接得到连接条件对应的编码。特别地，本文全局地定义了列的顺序，以保证连接条件集合不会收到次序的影响。

类型编码器

类型编码器对查询计划中的节点类型进行编码。与上文介绍的连接条件不同，节点类型的数量在数据库管理系统中通常是有限的。因此，本文对于节点类型的编码方法和先前的许多模型（MSCN、QPPNet和TPool等）相同，即采用one-hot编码方法处理节点类型。

谓词编码器

谓词是查询中最为复杂的信息之一，其直接影响着许多操作（如顺序扫描等）的基数大小，进而导致查询代价的不同。为增强对谓词信息的学习，本文基于查询范围嵌入和并行深度神经网络设计了谓词编码器，下面对二者分别进行介绍。

对于查询范围嵌入，本文采用两个向量$[V_{1}^{max},V_{2}^{max},...,V_{n_{c}}^{max}]$和$[V_{1}^{min},V_{2}^{min},...,V_{n_{c}}^{min}]$用以进行范围表示，其中$n_c$表示列的数量。具体规则定义如下：

• 若$c_i > value$，则将$V_{i}^{min}$的值设置为$value$。
• 若$c_i < value$，则将$V_{i}^{max}$的值设置为$value$。
• 若$c_i = value$，则将$V_{i}^{min}$和$V_{i}^{max}$的值设置为$value$。

其中，$c_i$为谓词中的列，$value$为对应的参数值。通过应用上述规则，我们能够得到查询对应的最大范围向量$V^{max}$和最小范围向量$V^{min}$。之后，本文建立了两个并行的神经网络学习$V^{max}$和$V^{min}$，将学习得到的嵌入向量进行拼接得到谓词对应的编码，并作为谓词编码器的输出。

信息编码器

查询计划树中不仅包括了原始查询语句的相关信息，同时还包括了查询优化器估计的若干信息，包括基数和代价等。虽然这些估计的信息在多数情况下是存在误差的，但是学习这种估计信息的错误分布是一种十分高效且有效的方法。因此本文设计了信息编码器，其将查询优化器估计的基数和代价经过归一化处理后作为特征编码的一部分。

最后，特征编码器整合上述四个子编码器的输出，得到查询计划对应的特征编码。

基于集成学习的估计模型

压缩器

压缩器学习特征编码器输出的特征向量，其输出一个固定长度的嵌入向量作为后续估计模型的输入。为了更好地学习特征编码中蕴含的丰富信息，本文建立了双向的LSTM模型处理特征编码。其具体的训练方法需结合估计模型，在本文下节中进行介绍。

贝叶斯神经网络

多数深度学习模型采用最大似然估计（MLE）基于当前观察到的数据得到最优的模型参数，这种方法假定了观察到的数据分布与全部的数据分布是相同或相似的。而贝叶斯神经网络则与此不同，其基于最大后验概率（MAP）的思想，通过引入不确定性来衡量模型对样本的置信程度。在基数和代价估计中，复杂的查询是频繁出现的。但是现有的基于方法大多基于MLE思想进行学习，无法在得到真实标签之前衡量模型在这些复杂查询上的表现。并且单一的模型难以学习全部查询的数据分布。因此，本文引入贝叶斯神经网络来衡量模型对各类样本的置信度。具体来讲，BICE采用MC_Dropout的思想建立了包括3层线性神经网络的贝叶斯模型以进行初步训练。定义如下：

$Loss=qerror(C_r(q),1/n_B \sum_{i=1}^{n_B} f_B(q|W_B))$

基于上述的损失函数定义，我们同时更新压缩器中的模型参数，至此完成了BICE的初步训练。

主动学习

完成初步训练后，为解决上文提到的单一模型难以适应复杂多样的工作负载的问题，本文采用主动学习的思想训练得到集成学习模型。具体来讲，本文共设计了四种数据抽样策略构成主动学习。分别是：（1）基于贝叶斯神经神经网络的置信度。（2）基于置信度和最大置信上界。（3）基于多样性与置信度。（4）基于多样新与最大置信上界。 本文采用贝叶斯神经网络在数据样本上输出的方差来衡量其置信度。用最大的$qerror$表示最大置信上界。此外，本文通过对数据样本进行聚类，之后在每个类别中进行样本抽取，以此来表示数据的多样性。在完成上述数据抽样后，本文建立了4个对应的估计模型进行学习。值得注意的时，在这一阶段的训练中，压缩器的参数并不会更新。因此对于各个数据样本，我们仅需利用上一阶段压缩器输出的样本的嵌入向量即可。仅训练估计模型（由3层线性神经网络组成）的过程是高效的。

实验

本文基于IMDB和TPC-H数据集进行了相关实验，其中IMDB数据集还包括了三个公开的测试负载：（1）JOB-light；（2）Scale和（3）Synthesis。

实验结果 我们在各个数据集上与相关的方法进行了对比，包括基数估计和代价估计，总体效果如下表所示。

实验表明BICE在绝大多数情况下均取得了最优表现。之后，本文将BICE与其他模型嵌入到查询优化器中，替代查询优化器所估计的基数，以进行端到端的测试，实验结果如下表所示。

实验表明，BICE在端到端测试中也有着最优的表现。此外，我们还进行了针对BICE的消融实验以论证各个组件的有效性，如下图所示。

上述消融实验表明，BICE的各个组件均能够有效地提升模型的表现。

结论

本文建立了一个基于双向LSTM和集成学习的模型框架，BICE。其能够进行有效的基数估计和代价估计。通过运用贝叶斯神经网络和主动学习，我们建立了表现更加优异的集成学习模型，其能够适应更加复杂多样的工作负载类型。实验研究表明，BICE在大量公开数据集上均有着更加优异的表现。