开放科学（资源服务）标志码（OSID）：

0 概述

查询优化是许多关系型数据库管理系统以及其他数据库（如图数据库）领域的一个重要课题^[1-3]。查询是用户对数据库信息发起的请求，可以是简单快速的查询，也可以是复杂耗时的查询。查询结果是通过访问相关数据库数据并对其进行操作从而产生的用户所需要的信息。由于数据库结构复杂，对于复杂的查询，其执行时间可能根据处理查询方式的不同而存在较大的差异，从几分之一秒到几小时不等。查询优化是一个自动化的过程，其目的是找到通过最少时间来处理给定查询的方式。不同的查询处理策略对应不同的执行时间，为提高查询效率，进行查询优化具有一定的现实意义^[4-6]。

在众多数据库查询操作中，连接（JOIN）操作最为费时，其往往涉及多个表之间大量的数据读取，因此，许多查询优化是针对JOIN展开的^[7-8]。基数估计是对数据表统计信息进行估计，并将其用于后续优化步骤。对原始数据进行基数估计在大多情况下比较费时，而在样本数据上做基数估计，对查询涉及的数据本身进行抽样，使得原本在大规模数据上进行的基数估计计算变为在较小但足够精确的样本数据上进行基数估计，并通过样本数据上的基数估计结果近似估计出原数据集上的基数，从而大幅减少计算时间。

近年来，许多在单表上的抽样算法相继被提出^[9-11]，同时，学者们也对一些评估抽样结果优劣的方法与标准进行了研究^{[9, 12]}，这些工作大都聚焦在单表数据分布或是与其他表的主外键关系上，针对每一个单表进行最佳抽样率计算^[13-14]。但是，假设数据库含有多个数据表，且对于众多数据表的样本临时数据表存在存储限制，即不能对每个数据表做过多抽样，样本总容量有预算上限，那么如何分配每个数据表的抽样大小就成为一个需要解决的问题。此时，需要找到一个合理的样本分配方案，使得在此样本数据上做基数估计的准确率能够在一定标准下以及一定误差范围内尽可能达到最高。

将多个表的抽样率整体看作一个待分配比例的组合，寻找一个最佳抽样率的分配就成了一个连续空间搜索问题，此时擅长连续空间搜索的贝叶斯优化算法可以发挥优势。本文将贝叶斯优化算法应用到数据库抽样中，提出一种面向多表JOIN查询优化的基数估计方法。在多表关系型数据库对样本临时表有整体存储限制时，利用贝叶斯优化算法可以快速搜索出不同表之间抽样样本大小的分配比例，且抽样结果可以达到最优，从而实现查询优化的目的。具体地，如果有一组查询负载涉及多个表之间的JOIN操作，需要将这组查询涉及的所有表进行一定比例的抽样，但抽样样本的总体大小受到限制。此时，将每个表的抽样比例看作一个参数，则整个数据库中所有表的抽样比例形成一个参数组合，所有不超过样本总大小限制的参数组合总体构成参数空间。在一个参数组合对应的抽样方案下，参考文献[12]进行二层抽样做基数估计，得到一个多表整体基数估计准确率。利用贝叶斯优化^[15]快速地在参数空间搜索对应基数估计准确率最高的参数组合，即在抽样样本总大小受限的条件下，利用贝叶斯优化算法快速确定对应基数估计准确率最高的多表抽样比例分配方案。

1 问题定义 1.1 多表JOIN查询优化

在关系型数据库中，最耗时的一类查询往往涉及许多JOIN操作。不同表之间不同类型（如BroadcastHashJoin、SortMergeJoin）、不同顺序的JOIN往往数据量大不相同，操作代价也存在很大差异。因此，合理地执行计划（如合理的JOIN类型、合理的JOIN顺序）能够大幅优化查询过程，提高查询效率。在查询计划优化器中有一类基于代价的优化器，其根据数据库中数据表上数据统计和代价模型的代价进行估计，计算不同执行计划对应的代价，从而选择最小代价的计划来执行。因此，数据统计结果的精确度会影响基于代价的优化器对执行计划的选择，从而影响查询优化结果。多表JOIN查询优化表示当查询语句中的JOIN操作涉及3张以上的数据表时，数据库管理系统或数据库优化工具根据数据统计信息对JOIN顺序、JOIN方式进行合理规划，从而达到缩减查询开销的目标。

1.2 基数估计

本文主要关注基于代价的优化器中的数据统计部分，这一部分通常称作基数估计，其通过数据统计和对数据分布、列的相关性以及连接关系的一些假设，来得到一些中间操作的元组条目数，这些数字会用于代价模型以决定查询计划。理论上讲，只要基数估计准确、后续代价模型估计准确，优化器就能在有限时间内获得全局最优的查询执行计划。

在数据库查询场景下，基数估计指的是对一个操作符产生的结果元组条目数进行估计，这个估计的条目数会用于代价模型预测这一个操作符的操作代价开销，根据操作代价开销的不同，对查询作出不同的物理执行计划，从而达到查询优化的目的。文献[15]指出，在现有的代价模型下，微小的基数估计误差可能会带来最多30%的代价预测误差。文献[16]对多表JOIN复杂查询下传统查询优化器的物理执行计划进行研究，其得到了与文献[15]类似的结论。因此，基数估计结果的准确率会严重影响查询优化的效果。

在数据库查询中，最费时的一类查询往往涉及多个JOIN操作，因此，本文主要关注这一类涉及多表JOIN的查询优化中所需进行的基数估计。多表JOIN涉及多张表之间多个列上的基数估计。在实际的数据库优化中，基数估计包括复杂的计算，本文将对基数估计的计算过程进行简化。基数估计的关键步骤是计算结果表中元组的分类计数，本文将基数估计过程转化为一个GROUP BY+COUNT的查询，以一组特殊设计的查询语句来近似替代单表基数估计进行计算。

定义1（多表基数估计近似查询）   对于一个给定的涉及JOIN的查询（如$ R $ JOIN $ P $），记这个JOIN结果为J，令$ S $为J的一个列组合（如$ \{R.{a}_{1}\}, \{R.{a}_{1}, P.{b}_{2}\} $等），$ S $在一种特殊情况下为空，即$ S=\mathrm{\varnothing } $，则对于如下查询结果的估计即为对涉及JOIN查询的多表基数估计：

SELECT S，COUNT（*）

FROM J

GROUP BY S

对查询结果的估计，包括了结果条目数的估计以及每一条结果中对COUNT（*）结果的估计。需要注意的是，单表基数估计近似查询是JOIN查询基数估计近似查询的一个特例。因此，本文讨论涉及JOIN查询的多表基数估计近似查询。

1.3 基于抽样的多表JOIN查询基数估计

图 1所示为基于抽样并面向多表JOIN查询的基数估计问题定义。上文定义的面向多表JOIN查询的基数估计由于要计算连接后的结果表元组条目数，因此当原始数据表规模很大时计算量巨大。为解决该问题，常用的一个策略是对原始数据表进行一定比例的抽样，在抽样数据表上进行基数估计近似查询，然后根据抽样比例再估算原始数据表上做多表JOIN查询的基数估计结果。对于多表JOIN查询，各表上不同的抽样比例会导致JOIN查询在抽样表上做出的基数估计结果准确率不同。因此，对于一组确定的多表JOIN查询，本文目标是确定一组使得基数估计准确率最高的抽样方案。

当限定一个数据库中可以额外存储临时表的空间，即限制数据表可产生的抽样样本表的样本空间时，则必须将有限的样本空间分配给数据库中的每一张需要抽样的数据表，使得每张数据表以一定的抽样率进行样本抽样且样本总和不超过限制的空间大小。在这个空间有限制的总体样本上，本文针对给定的查询负载做基数估计。本文目标是在给定样本空间限制的条件下，找到一种样本抽样在不同数据表上的分配方案，使得查询负载在样本上做出的基数估计准确率最高，即数据库中所有数据表的样本基数估计结果准确率的平均值最大。

2 贝叶斯优化与二层抽样 2.1 贝叶斯优化

贝叶斯优化的目标是一个计算代价昂贵的黑盒函数$ f $ ^[17-19]，$ f $的具体函数形式不得而知，但对于一个特定的自变量输入值$ x $，其对应的函数值$ f\left(x\right) $是可以获取的。虽然$ f\left(x\right) $的值可以获取，但是计算时间会很长，因此，要求得函数$ f $在定义域$ \mathcal{X} $上的最大值或最小值，就不能进行穷尽枚举^[17]。贝叶斯优化可以在有限步的尝试内，近似搜索到函数$ f $的最大值或最小值，从而大幅缩短函数优化时间^[20]。

贝叶斯优化算法是一个迭代执行的过程，$ x $它在每一步迭代时选取一个函数的合法输入值$ x\in \mathcal{X} $并评估$ y= $ $ f $（x）。在算法的初始阶段，需要随机选取几个输入值$ x $。在迭代过程中，假设函数的一个输入和输出的键值对序列已经在之前的$ t $-$ 1 $轮迭代中被选中并评估过，记已评测过的采样点集合为$ {D}_{t-1}=\left\{\right({x}_{i}，{y}_{i}{\left)\right\}}_{i=0}^{t-1} $。贝叶斯优化在迭代时使用一个采集函数（acq）来挑选$ {x}_{t} $，从而近似估计$ {x}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $并交由高斯过程（GP）^{[18, 21]}去拟合待优化的函数，那么$ {x}_{t} $和相应的输出（即模型性能）$ {y}_{t}=f\left({x}_{t}\right) $将被加到已评测过的采样点集合$ {D}_{t}={D}_{t-1}\bigcup \left\{\right({x}_{t}, {y}_{t}\left)\right\}\mathrm{中} $。在实践中，这个过程不会停止，直到模型性能收敛，或者迭代过程已经执行了一个预设好且数值较大的最大迭代轮数$ T $。

2.2 二层抽样

二层抽样是文献[12]在总结目前用于查询优化中数据表JOIN结果基数估计的抽样方法后，提出的一种用以估计两表间查询JOIN结果大小的抽样方法。该文分析了简单独立伯努利抽样（即随机抽样）、关联抽样、端偏抽样（End-biased sampling）的特点与弊端，在此基础上提出了二层抽样方法。

假设需要JOIN的2个表分别为A和B，且在列A.a和B.a上做条件JOIN，$ v $为A.a或B.a上的某一属性值，在A.a中的频数为$ av $，在B.a中的频数为b$ v $。$ {K}_{A} $和$ {K}_{B} $为2个人工设定的系数，则令$ p\left(v\right)=\mathrm{m}\mathrm{i}\mathrm{n}\left(av/{K}_{A}, bv/{K}_{B}, 1\right) $，二层抽样的步骤如下：

1）第一层抽样。确定JOIN的属性列，并利用一个哈希函数$ h $将属性列上的属性值$ v $映射到$ h\left(v\right)\in $[0, 1]的区间。若$ h\left(v\right)\le p\left(v\right) $，则属性$ v $对应的表中元组将在第一层抽样中被全部抽取；反之，则不抽取。

2）第二层抽样。对于第一层抽样中抽取的属性值，以概率$ q $进行均匀抽样，同时保证每一类属性值对应的元组中至少有一条被保留。

二层抽样方法考虑了原始数据的分布与连接关系，避免了需要JOIN的两表间数据属性值匹配不均而带来的基数估计误差。二层抽样方法易于操作，仅需遍历一遍数据即可完成，且可以根据人工参数进行调整，使得在不同抽样样本量条件下样本尽可能地保留连接属性值。

3 算法实现

本文通过形式化的定义，将多表JOIN查询基数估计问题转化为等价SQL语句的近似查询问题。基于这一转化，本文提出一种面向多表JOIN查询基数估计的最佳数据抽样方案搜索算法。

3.1 数据抽样与基数估计

假设有一组（若干条）JOIN查询，需要对这若干条JOIN查询都做出基数估计，本文将对若干条JOIN查询做出的基数估计问题称为基数估计查询负载（下文简称为负载）。在实际应用中，数据库中的数据表条目数通常达百万条之多，若是负载中的查询覆盖到数据库中所有的数据表，那么在原数据上做JOIN查询会是一个数据量巨大的工作。为解决该问题，可以对原数据表进行合理地抽样，然后将负载在抽样后的样本上执行查询，依据结果做基数估计，并用样本上的基数估计来近似原数据表上的基数估计。由于执行的数据表经过了抽样，因此在抽样样本上原始负载的近似基数估计结果也有误差。在不同的抽样率下，基数估计结果也必然不同。因此，需要定义对于确定的负载在抽样样本上做基数统计的结果准确率，具体方法是将样本上做出的基数估计查询结果与实际原始数据上做出的基数估计查询结果进行比较并得出误差。

假设$ {C}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}} $是基数估计查询在真实数据集（未抽样前的原始数据集）上得出的结果表，$ {C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}} $是基数估计查询在将语句中的数据表替换为样本数据表后在样本数据表上得出的结果表。有如下结论：

命题1   对于$ \forall s\in S $，如果$ (s, r) $出现在$ {C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}} $中，则$ \exists r\text{'} $，使得$ (s, r\text{'}) $出现在$ {C}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}} $中，且$ r\text{'} $唯一；反之，不一定成立。

证明   不妨设某一基数估计查询涉及2张表$ R $和$ P $的JOIN：

$ J=R\ \mathrm{J}\mathrm{O}\mathrm{I}\mathrm{N}{}_{\mathrm{j}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}}P $

那么JOIN结果$ J $可以用关系代数改写成如下形式：

$ J={\sigma }_{\mathrm{j}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}}(R\times P) $

(1)

对R和P分别进行抽样，得到样本数据表$ R\text{'} $和$ P\text{'} $，那么$ {C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}} $是在抽样样本结果表$ J\text{'} $上做查询的结果：

$ J\text{'}={\sigma }_{\mathrm{j}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}}(R\text{'}\times P\text{'}) $

(2)

因为$ R\text{'} $和$ P\text{'} $分别是数据表$ R $和$ P $的抽样结果，所以有：

$ R\text{'}\subseteq R, P\text{'}\subseteq P\Rightarrow R\text{'}\times P\text{'}\subseteq R\times P $

(3)

因为$ J $和$ J\text{'} $分别是对$ R\times P $和$ R\text{'}\times P\text{'} $在同一条件下的选择结果，所以根据式（1）、式（2）有：

$ J\text{'}\subseteq J $

(4)

则对于$ \forall s $在$ J\text{'} $中，有如下结论：

$ \forall s\mathrm{在}J\text{'}\mathrm{中}\Rightarrow s\mathrm{在}J\mathrm{中} $

(5)

由于基数估计查询结果是GROUP BY后的COUNT（*）结果，因此$ s $和$ r $在结果集中一一对应，即：

$ s\mathrm{在}J\text{'}\mathrm{中}\iff (s, r)\in {C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}} $

$ s\mathrm{在}J\mathrm{中}\iff (s, r\text{'})\in {C}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}} $

(6)

在式（6）中，$ r $和$ r\text{'} $是唯一的。由式（5）、式（6）得到：

$ \forall s\in S，\mathrm{如}\mathrm{果}\left(s, r\right)\in {C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}}\Rightarrow $

$ \exists \mathrm{唯}\mathrm{一}\mathrm{的}r\text{'}, \mathrm{使}\mathrm{得}(s, r\text{'})\in {C}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}} $

上述是2张表做JOIN时的情形，同理，可以推广到任意数量的表JOIN时的情形，即当一个JOIN操作是由$ {R}_{1}, {R}_{2}, \cdots , {R}_{k} $的JOIN而成时，令$ {R}_{1}^{\mathrm{\text{'}}}, {R}_{2}^{\mathrm{\text{'}}}, \cdots , $ $ {R}_{\mathrm{k}}^{\mathrm{\text{'}}} $为抽样后的样本数据表，那么式（1）、式（2）可改写为如下形式：

$ {J}_{\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}}={\sigma }_{\mathrm{j}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}}({R}_{1}\times {R}_{2}\times \cdots \times {R}_{k}) $

$ {J}_{\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}}^{\mathrm{\text{'}}}={\sigma }_{\mathrm{j}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}}({R}_{1}^{\mathrm{\text{'}}}\times {R}_{2}^{\mathrm{\text{'}}}\times \cdots \times {R}_{{k}}^{\mathrm{\text{'}}}) $

同理，$ {J}_{\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}} $和$ {J}_{\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}}^{\mathrm{\text{'}}} $之间的包含关系也如上可证，结论成立。

证毕。

由命题1可知：$ \exists (s, {r}_{0}) $，使得$ (s, {r}_{0})\in {C}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}} $，而对$ \forall r\in {\mathbb{N}}^{+} $，均有$ (s, r)\notin {C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}} $。由于下文需要定义基数估计查询结果准确率，因此本文将$ {C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}} $进行如下扩增以得到$ {C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}}^{\mathrm{\text{'}}} $：对于使得$ (s, {r}_{0})\in {C}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}} $，而对$ \forall r\in {\mathbb{N}}^{+} $，均有$ (s, r)\notin {C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}} $，对这样的$ s $，将$ (s, 0) $加入$ {C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}} $中，最终获得$ {C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}}^{\mathrm{\text{'}}} $，即：

$ {C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}}^{\mathrm{\text{'}}}={C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}}\bigcup \left\{\left(s, 0\right)\right\}, \mathrm{ }\exists {r}_{0}\in {\mathbb{N}}^{+}, \left(s, {r}_{0}\right)\in {C}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}} $

$ \mathrm{且}\forall r\in {\mathbb{N}}^{+}, (s, r)\notin {C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}} $

(7)

定义2（以样本进行基数估计的准确率）  给定一个JOIN基数估计查询，设原始基数估计查询在原数据表上的结果为$ {C}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}} $，将原数据表的每张表按抽样率$ p $抽样后，在样本数据表上做基数估计查询的结果为$ {C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}} $，将$ {C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}} $按式（7）做扩增，得到$ {C}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}}^{\mathrm{\text{'}}} $。记$ {C}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}} $的条目数为$ \left|{C}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}}\right| $，则使用样本的基数估计准确率$ \rho $定义为：

$ \rho =\sum\limits _{(s, r)\in {C}_{{\rm{sample}}}\mathrm{且}(s, r\text{'})\in {C}_{{\rm{real}}}}\frac{1-\frac{|r/p-r\text{'}|}{r\text{'}}}{\left|{C}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}}\right|} $

3.2 数据抽样的空间限制

2.1节所提抽样方法都是在单表下讨论的，在真实场景中，查询往往包括JOIN操作，这就涉及一个查询语句需要在2张甚至多张数据表上进行查询计算，因此，需要对涉及的2张甚至多张表都进行抽样，而这些表上的抽样肯定相关联，能够用以准确进行基数估计的样本结果不会是相互独立的。因此，对于某一个特定的查询问句，需要对其涉及的所有表都进行一次联合抽样，以实现最准确的基数估计。

定义3（数据表的最佳抽样率）   设数据库中拥有$ n $张数据表，记为$ {R}_{1}, {R}_{2}, \cdots , {R}_{i}, \cdots , {R}_{n} $。设拥有若干条（m条）查询，记为$ {Q}_{1}, {Q}_{2}, \cdots , {Q}_{j}, \cdots , {Q}_{m} $。假设在处理查询$ {Q}_{j} $的过程中需要对表$ {R}_{i} $进行抽样率为$ {p}_{ij} $的随机抽样，能够达到最准确的基数估计（即样本基数估计结果准确率$ \rho $的值最大，注意，这里可能查询$ {Q}_{j} $并不涉及表$ {R}_{i} $，在这种情况下$ {p}_{ij} $= 0），那么针对由m条查询构成的查询集合，表$ {R}_{i} $的最佳抽样率为：

$ {p}_{i}^{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}=\frac{\sum\limits _{j=1}^{m}{p}_{ij}}{\sum\limits _{j=1}^{m}{1}_{{p}_{ij}\ne 0}} $

通过定义3可以得知，假设在随机抽样策略下要达到最准确的基数估计，则整个数据库所有数据表的抽样样本存储大小之和为$ {H}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $，如果数据库本身已经存储了大量数据，所剩存储空间不多，已经不足以存放$ {H}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $大小的抽样样本，就出现了问题。由于整体可产生的抽样样本所占存储空间受到限制，那么针对特定的查询集合，势必无法使得每张表的样本都进行最准确的基数估计，即本文所讨论的情况是在$ H\le {H}_{\mathrm{b}\mathrm{u}\mathrm{d}\mathrm{g}\mathrm{e}\mathrm{t}} < {H}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $的条件下寻找使得整体基数估计准确率最大的抽样率组合$ \boldsymbol{p} $。因此，需要合理地动态分配（这里的动态指针对不同的查询）存储空间给每张表产生的样本，以在存储空间受限的条件下使得数据库中数据表的基数估计准确率平均值最大。

定义4（数据库的整体样本基数估计结果准确率）   设数据库中有$ n $张表$ {R}_{1}, {R}_{2}, \cdots , {R}_{n} $，每张表的抽样率为$ {p}_{i} $，并且在给定的抽样率条件下，针对给定的查询负载，其样本基数估计结果准确率分别为$ {\rho }_{1}, {\rho }_{2}, \cdots , {\rho }_{n} $，则数据库的样本基数估计准确率$ {\rho }_{db} $定义为：

$ {\rho }_{db}=\sum\limits _{i=1}^{n}\frac{{\rho }_{i}}{n} $

(8)

由定义4可知，当给定一组抽样率$ {p}_{1}, {p}_{2}, \cdots , {p}_{n} $且满足$ H=\sum\limits _{i=1}^{n}\left(\right|{R}_{i}|\mathrm{ }\cdot {p}_{i})\le {H}_{\mathrm{b}\mathrm{u}\mathrm{d}\mathrm{g}\mathrm{e}\mathrm{t}} $ $ （{H}_{\mathrm{b}\mathrm{u}\mathrm{d}\mathrm{g}\mathrm{e}\mathrm{t}} $事先给定）时，可以得到给定查询负载下整体基数估计结果准确率$ {\rho }_{db} $，误差率为$ 1-{\rho }_{db} $。

3.3 贝叶斯优化与空间有限数据抽样

由定义3可知，当查询负载和抽样样本给定时，数据表的样本基数估计结果准确率容易计算。因此，如果将一组在限定空间大小之内的数据表样本抽样分配方案作为自变量，将此时对于给定的查询负载在样本上的整体基数估计准确率作为应变量，在这2个变量间建立映射关系，那么上述寻找最佳样本抽样分配方案的问题，就可转化为函数最优化搜索问题，则可以引入贝叶斯优化算法进行解决。本文在给定样本总空间大小条件下，将数据库中所有数据表合法的抽样样本组合（即样本总和不超过给定大小的上限）组成整个自变量搜索空间，空间中每一个自变量对应一种合法样本组合$ {\boldsymbol{R}}_{1}^{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}}, {\boldsymbol{R}}_{2}^{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}}, \cdots , {\boldsymbol{R}}_{n}^{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}} $（设数据库中有n张表），然后通过贝叶斯优化算法在搜索空间中搜索，以给定查询负载下数据库样本基数估计结果准确率$ {\rho }_{db} $作为目标函数值，从而优化这一映射关系函数，最终搜索出最高的数据库样本基数估计结果准确率，以及使得数据库样本基数估计结果准确率最高的样本组合，就可求出每张表对应的抽样率。为计算方便，本文将搜索空间适当修改，将合法的样本组合一一对应成合法的抽样率组合，即贝叶斯优化算法需要搜索的搜索空间变为由所有合法的抽样率组合$ \mathcal{X}=({\boldsymbol{p}}_{1}, {\boldsymbol{p}}_{2}, \cdots , {\boldsymbol{p}}_{n}) $（设数据库中有$ n $张表）构成的空间。具体算法描述如算法1所示。

算法1    搜索最佳样本组合方案的贝叶斯优化算法

输入

T：算法最大执行迭代轮数

$ {H}_{\mathrm{b}\mathrm{u}\mathrm{d}\mathrm{g}\mathrm{e}\mathrm{t}} $：允许产生的最大样本总数

$ {D}_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{p}\mathrm{s}} $：初始化随机样本抽样率组合x及对应的数据库样本基数估计结果准确率$ {\rho }_{db} $的键值对集合

$ \boldsymbol{X} $：待优化函数的定义域，即由所有合法抽样率组合构成的空间

输出

$ {x}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $：最大的数据库样本基数估计结果准确率对应的抽样率组合

$ {y}_{\mathrm{m}\mathrm{a}\mathrm{x}} $：最大的数据库样本基数估计结果准确率

1.$ \mathrm{f}\mathrm{o}\mathrm{r}\mathrm{ }\mathrm{t}=\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{p}\mathrm{s}+1\mathrm{ }\mathrm{t}\mathrm{o}\mathrm{ }\mathrm{T} $

2.     $ {\mathrm{x}}_{\mathrm{t}}=\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}{\mathrm{x}}_{\mathrm{x}\in \mathrm{X}}\mathrm{a}\mathrm{c}{\mathrm{q}}_{{{{\mathtt{ρ}} }}_{\mathrm{d}\mathrm{b}}}\left(\mathrm{x}\right) $

3.     $ {\mathrm{y}}_{\mathrm{t}}={{{\mathtt{ρ}} }}_{\mathrm{d}\mathrm{b}}\left({\mathrm{x}}_{\mathrm{t}}\right) $

4.     $ \mathrm{u}\mathrm{p}\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{e}{\mathrm{D}}_{\mathrm{t}}\leftarrow {\mathrm{D}}_{\mathrm{t}-1}\bigcup \left\{\right({\mathrm{x}}_{\mathrm{t}}, {{{\mathtt{ρ}} }}_{\mathrm{d}\mathrm{b}}\left({\mathrm{x}}_{\mathrm{t}}\right)\left)\right\} $

5.$ \mathrm{e}\mathrm{n}\mathrm{d}\mathrm{ }\mathrm{f}\mathrm{o}\mathrm{r} $

6. $ \mathrm{r}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{n} $ $ {\mathrm{x}}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}，({\mathrm{x}}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}, {\mathrm{y}}_{\mathrm{m}\mathrm{a}\mathrm{x}})\in {\mathrm{D}}_{\mathrm{T}}, {\mathrm{y}}_{\mathrm{m}\mathrm{a}\mathrm{x}}=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\mathrm{y}\right|(\mathrm{x}, \mathrm{y})\in {\mathrm{D}}_{\mathrm{T}}\} $

在上述贝叶斯优化搜索的每一步，当假设了每张数据表的抽样率之后，采用二层抽样方法来抽取样本以用于最终的基数估计。在每一轮迭代中，在贝叶斯优化算法推荐的抽样比例下做二层抽样以估算基数估计结果，并按式（8）计算基数估计准确率，将其与历史最优记录进行比较，若该抽样比例方案下基数估计准确率有所提高，则更新历史最优记录。整体算法流程如图 2所示。

3.4 时间复杂度分析

原始贝叶斯优化算法在一次迭代中用高斯过程搜索黑盒函数最值点的时间复杂度为$ {\rm O}\left({n}^{2}\right) $，其中，$ n $为观测点数目^[22-23]。而在一次迭代中，本文优化算法除了利用高斯过程计算一组推荐抽样率方案之外，还需要根据计算出的抽样率方案对查询负载中的$ m $条多表JOIN查询计算基数估计准确率，因此，一次迭代的总时间开销为$ {\rm O}({n}^{2}+m) $。根据贝叶斯优化算法的特点，算法在进行第n轮迭代时的观测点数目为n，因此，本文算法前n轮的总时间复杂度为$ {\rm O}({n}^{3}+nm) $。

4 实验评估 4.1 实验设置

在本次实验中，采用TPC-H生成了1 GB的数据集，并选取22个官方查询模板查询语句中的12个查询模板语句（这12个模板均含有多表JOIN查询，符合本文讨论的范畴），构建查询负载并进行优化。其中，问句均涉及2张及2张以上的表的JOIN，并且查询返回时以某一列或某几列做分组（GROUP BY）后的计数（COUNT）作为结果呈现。所有12个查询问句共涉及数据库中的8张数据表，以这种类型的查询问句来模拟数据库的查询优化器在分析用户真实查询问句后得出问句涉及具体哪些数据表（对应实验中查询问句的JOIN部分），以及获取到下一步执行计划优化所需基数估计的列（对应实验中查询问句的GROUP BY部分）。因此，实验中的查询负载事实上是模拟了真实场景中查询优化器分析需要做何种基数估计的这一步骤。

4.2 误差率对比实验

本文设定允许产生的样本总大小为原始数据大小的0.01%~5%不等，利用贝叶斯优化算法搜索20步，记录搜索到的8张表上的最佳抽样率组合以及对应的数据库抽样基数估计误差率的最小值。对于选定的抽样率，以随机抽样或二层抽样的方法重复10次实验并取最佳结果，同样地，利用随机搜索算法搜索20步，记录8张表上的最佳抽样率组合以及对应的数据库抽样基数估计误差率的最小值。实验结果如图 3所示。

分析图 3可知，对于各表在抽样大小受限条件下的最优抽样率分配方案，采用二层抽样方法总是优于随机抽样方法，而在相同的抽样样本比例限定下（如0.1%），采用贝叶斯优化算法确定的最优样本分配方案在有限步骤内（或有限时间内）总是要比随机搜索确定的最优样本分配方案对应基数估计的误差率要小。在抽样率比例上限为0.01%和5%条件下，采用贝叶斯优化算法得到的基数估计误差率比随机搜索算法得到的基数估计误差率分别降低60.2%和54.8%。

4.3 搜索效率对比实验

本文设计实验来证明贝叶斯优化算法在解决面向多表JOIN查询优化基数估计问题上的高效性。通过TPC-H产生1 GB原始数据，并设置允许产生的各表样本总大小分别为原始数据的0.01%、0.05%、0.1%、0.5%和1%，分别使用随机搜索和贝叶斯优化算法来确定各表的最优抽样率比例分配方案，抽样方法均采用二层抽样，记录历史最低基数估计误差率，直到历史最低基数估计误差率在10步迭代内降低不超过1%，则可认为搜索到的最优抽样率比例分配收敛，记录随机搜索和贝叶斯优化算法的收敛时间，每一种抽样比例下进行20次实验取平均值，结果如图 4所示。

分析图 4可知，在不同的抽样数据规模下，利用贝叶斯优化算法搜索最优抽样分配方案时，收敛时间少于随机搜索算法。因此，贝叶斯优化算法在解决面向多表JOIN查询优化的基数估计问题时具有高效性。

5 结束语

本文提出一种面向多表JOIN查询优化的基数估计方法。对于一组给定的查询负载，需要在查询优化前对其进行基数估计，而对于庞大的原始数据，又需要在基数估计前进行样本总大小有限的多表联合抽样。本文利用贝叶斯优化算法快速搜索多张数据表之间可能的抽样样本比例分配组合，采用二层抽样方法在有限时间内确定多表联合抽样率分配方案，使得给定查询负载平均基数估计结果误差率最小，从而实现精准且快速的基数估计。实验结果表明，该方法能有效提升涉及多表JOIN复杂查询的基数估计计算效率，且误差率相比随机搜索算法大幅降低，实现了查询优化的效果。下一步考虑将元学习、强化学习等算法应用于查询优化与基数估计任务中，结合传统基于数据统计的计算方法与基于强化学习的模型，以提高数据查询效率并提升数据库优化的整体水平。