Classic case

优化器技术演进：统计信息feedback

本文将讲述数据库优化器中，统计信息的feedback机制。对数据库统计信息的概念有基本了解的同学，可以直接跳到第三章进行阅读。

统计信息（statistics）是数据库优化器领域中经久不衰的话题，几乎每年的数据库顶级会议中都会有多篇涉及到统计信息的论文。

在现代数据库中，对于用户传来的SQL，优化器首先为其枚举出不同的执行计划，形成一个搜索空间；然后将收集得到的统计信息（如表的行数、谓词的选择率等）作为输入，在代价模型（cost model）中为不同的执行计划计算出相应的代价。最小代价的计划会被优化器选中，成为最终的执行计划，在数据库执行器中运行。

常见的统计信息指标包括但不限于：

表的行数（row count），对于关系R，行数可以表示为 $row\\_count=|R|$
某一列中ndv的数量（number of distinct value），即去重之后元素的数量。
选择率（selectivity），对于某一个过滤条件，被过滤的行的比例。对于关系R上的过滤条件（谓词）p，其选择率可以表示为 $sel(p)=\\frac{|\\sigma_p R|}{|R|}$ .
基数（cardinality），狭义上的基数是指Join / Agg等算子输出的行数。基数估计(cardinality estimation)是数据科学家们研究最多的统计信息问题，几乎成为统计信息的代名词，对于条件为p的Join算子 $R\\bowtie_p S$ ，基数估计常常转化为 $card(R\\bowtie_p S)=card(\\sigma_p(R\ imes S))$ 的形式来处理。

而为了表示统计信息，数据库科学家们研究出了丰富的表示形式。在数据库学术领域，统计信息的表示形式统称为数据摘要（Synopses），推荐阅读这篇雄文 Synopses for Massive Data:Samples,Histograms, Wavelets, Sketches。

本文关注的统计信息表示形式是最古老、最实用的直方图(histogram)，即柱形图。只表示一列统计信息的直方图，称为一维直方图。一维直方图可以分为以下几种：

频率直方图，用于表示某一列中各个数值出现的频率，其中横轴是一个个按序排列好的区间，每个区间上的柱形称为一个桶（bucket），其高度代表该区间内数据出现的次数（频率）。所有桶的高度之和便是表的行数。频率直方图有等宽、等高之分，

等宽直方图，区间大小一致，桶高度不同:

等高直方图，桶高度一致，区间大小不同：

2. TOP-K直方图，在直方图上为列中频率最高的前K个数值，存储相应的频率 $f_k$ ，而其他不频繁出现的数值频率被视为 $f_{rare}=\\frac{|R|-\\sum f_k}{ndv-K}$

与一维直方图不同，多维直方图可以表示多个列的频率信息。对于含有d列的高维直方图，原先的一维区间 $[l,u]$ ，成为了新的高维空间 $[l_1,u_1]\ imes[l_2,u_2]\ imes...\ imes[l_d,u_d]$ ，每个桶表示该高维空间内一个区间上的频率值。

从1979年的优化器奠基之作 Access Path Selection in a Relational Database Management System 开始，数据库统计信息的构建一般都遵循着以下几个假设：

时效性假设，即假定过去一段时间内表的数据是不变的，旧的统计信息能准确反映现在时段的数据分布情况。

独立性假设，即假设不同谓词之间概率分布相互独立，互不干预，对于谓词 $p_1\\wedge p_2$ ，其选择度满足 $sel(p_1\\wedge p_2)=sel(p_1) * sel(p_2)$ 。

均匀假设，即假定柱状直方图的每个柱形内部，数据是均匀分布的。例如，表R中A列的真实分布情况如下，其中柱状直方图的横坐标代表distinct value，柱形桶的高度代表该distinct value在表中的数量：

现在我们为A列收集统计信息，其建立如下的等宽直方图，每个桶宽度相同，都覆盖4个distinct value；当我们需要计算满足A=5的行数，首先我们找到区间在[5, 8]的桶，然后根据独立性假设，认为桶内数据是均匀分布的，从而计算出行数 $|\\sigma_{A=5}(R)|=19/4\\approx5$ ，与实际结果1有较大误差。

而如果为A列建立如下的等高直方图，每个桶的高度一致。当我们需要计算满足 $A > 5 \\ and \\ A <=16$ 的行数，假设桶内数据均匀分布，则计算方式为 $|\\sigma_{A>5 \\ and\\ A<=16}(R)|=16+16+16+2/7*16\\approx53$ ，与真实数据 $|\\sigma_{A>5 \\ and\\ A<=16}(R)|=59$ 同样存在误差。

包含性原则。对于条件为p的Join算子 $R.a\\bowtie_pS.b$ ，其选择率往往被粗暴定义为 $\\frac{1}{max\\{ ndv(R.a),ndv(S.b)\\}}$ ，这里隐含一个假设，即对于ndv较小的列而言，每一个列元素都能在ndv较大的列中匹配到相同元素。如果用贝叶斯定理来理解的话，设A事件为R.a列元素发生匹配，B事件为S.b列元素发生匹配，则有 $P(A|B)=1\\ or\\ P(B|A)=1$ 。

在优化器实际运行时，当这些假设出现不成立的情况，统计信息就会出现较大的偏差，给代价估算带来错误结果，进而影响到计划的选取，得到次优的执行计划，给整个数据库的处理性能带来不利。在著名文章 How Good Are Query Optimizers, Really？中提到，底层算子上统计信息估算时的偏差，会在算子间指数级地放大和传递，让最终求得的执行代价差之千里。

为了应对这一问题，统计信息feedback，即在运行时收集统计信息误差，并及时对统计信息进行修正，成为Oracle、Db2等主流数据库厂商采纳的方案。本文将梳理统计信息feedback的发展脉络。

DB2在2001发表文章 LEO – DB2’s LEarning Optimizer，引入了一个完整的、商用的feedback方案"Leo"，整体架构如下：

对于用户SQL：

SELECT * FROM X, Y, Z
 
WHERE X.Price >=100 AND Z.City=‘Denver’ 
AND Y.Month=‘Dec’ AND X.ID=Y.ID 
AND Y.NR=Z.NR 

GROUP BY A

Leo优化器处理得到一个执行计划QEP(query execution plan)，称为"skeleton"。相比于一般的执行计划，skeleton可以对每个算子的输入输出行数、执行时间都进行实时监控，并与统计信息估算值进行对比。上述SQL经处理得到的skeleton如下：

根据收集到的skeleton监控信息，与优化器统计信息估计值对比如下：

接下来，LEO优化器通过监控分析程序，为出现错误估计的算子，求出一个adjustment数值，来调整算子的选择率，从而修正统计信息带来的误差。

这里需要先引入几个基本概念：

old_est: 优化器对于选择率的估计值
old_adj: 优化器用于修正选择率的旧adjustment
stats：调整前的选择率，old_est /old_adj
act: 真实的选择率

监控分析程序计算adjustment的过程如下：

首先，监控分析程序后续遍历整个skeleton树，找到最早出现估算错误的算子节点。判断估算错误的依据是， $error: |old\\_est-act|/act>0.05$ ，即当选择率估计值和真实值差距在5%以上时，认为发生错误。
接着，对于算子（TBSCAN, IXSCAN, FETCH, FILTER, GROUP BY, NLJOIN, HSJOIN等）对比选择度的估计值和真实值，求出一个adjustment数值： $adj=\\frac{act}{stats}=act/(old\\_est/old\\_adj)=act*\\frac{old\\_adj}{old\\_est}$
将求得的adjustment数值存入系统表，作为优化器的输入，在优化时对统计信息进行修正。

上述监控分析程序可以离线，也可以实时执行。实时执行的监控分析，对query响应更快、更灵敏，但是很难保证工程上的准确性。为了不影响程序执行，监控分析由一个优先级很低的线程来处理，仅在数据库负载 $act sel=1 - 0.8335 * (1 - 0.1595)=0.2994$ 较低时触发，并且可以随时被高优先级的线程终止。

adjustment机制有以下几个优点：

可以灵活地关闭和打开feedback功能，（简单地忽略统计信息）
可以将adjustment存入系统表，并通过查阅系统表，得知现有的adjustment的情况，知道哪些谓词、选择度已经被调整过，避免重复调整，或者给予正确的再调整（re-adjustment）
可以对系统表建立一个访问机制，对于adjustment进行人工调优。

Leo优化器规定：用谓词 $p(col<X)$ col < X的adjustment值，来修正 $p(col >=X)$ 的选择率：

$sel(col >=X)=1 - sel(col < X)$

$=1 - adj(col < X) * est(col < X)$

$=1 - adj(col < X) * (1 - est(col >=X))$

例如，对于skeleton图中的算子TBSCAN X，首先计算谓词price<=100的adjustment $adj(Price<100)$ ：

$adj(TBSCAN X)=7632/7200=1.06$ $est sel=1149 / 7200=0.1595$ $act sel=2282 / 7632=0.2994$ $adjustment(Price <=100)=(1-0.2994) / (1-0.1595)=0.8335$

接着可以修正得到Price > 100 的真实选择率：

$sel(Price > 100)=1 - 0.8335 * (1 - 0.1595)=0.2994$

对于join算子 $R\\bowtie_pS$ ，Leo将其转为 $\\sigma_p(R\ imes S)$ ，其基数表示为 $|R|*|S|*sel(p)$ 。这样，adjustment对于谓词选择率的修正，也可以自然地应用到join算子上了。

在统计信息feedback修正方案里，不同于DB2 Leo优化器直接修正选择率，update statistics代表了一种更长期、更直接的修正，即根据算子上监控得出的反馈信息，对直方图进行更新，从而给优化器提供更准确的统计信息参考。

update statistics 可以简单地理解为，通过监控得到某个范围内或某个单点的基数信息，如 $|\\sigma_{a<=p<=b}R|$ 或 $|\\sigma_{p=x}R|$ ，将此信息作为feedback，根据修正算法来直接修正和更新原有的直方图。

首先来明确几个概念。记col=v的频率：f(col=v)=fv，

原先的频率值 $fv_1, fv_2, ... fv_n$
从feedback中收集得到的新频率数值信息 $cfv_1, cfv_2, ... cfv_m$
排在topk之外的普通低频数据： $f_{rare}$

直接综合1，2，3中的数据，更新得到一个新的序列 $f_1, f_2 ... f_{m+n}$ 。那么更新后的低频数据值： $f_{rare}'=(C-\\sum_{j=0}^{K}f_j)/(ndv-K)$ ，其中n<=K<=(m+n)。

随着时间的推移，feedback数据的增加，m+n可能会越来越大，因此需要限制top-K中K值的大小。由于feedback只提供了K范围内的准确数据，第K ~ m+n 之间的数值频率估计是存在误差的。总的误差值可以写为：

$error(K)=\\sum_{i=K+1}^{m+n}|f_i-f_{rare}'| + (d-(m+n))|f_{rare}-f_{rare}'|$

其中， $\\sum_{i=K+1}^{m+n}|f_i-f_{rare}'|$ 是区间（K+1, m+n）内的误差， $(d-(m+n))|f_{rare}-f_{rare}'|$ 是区间 $(m+n+1, \\infty)$ 内的误差。从中我们可以得到这样一个trade-off的关系：K值越小，总的误差越高；K值越大，则feedback需要监控的top-k信息越多、开销越高。因此，我们应当尽可能地提升K值，并保证error(K)下降到一个可接受的范围。

问题定义：对于一个直方图，设第x个桶为 $b_x$ ，原高度为 $H_{b_x}$ ，根据feedback更新后的高度为 $h_{b_x}$ 。现在我们得到一组feedback信息，将要更新N条数据到直方图中，每个桶x被更新的机会均等，其更新概率 $p_x$ 满足概率分布： $h_{b_x}\\sim$ $Bin(N,p_x)$ . 如果是范围更新，则概率分布是连续的，满足 $h_{b_x}\\sim N(H_{b_x},\\sigma_{b_x})$ 。

现在我们得到了一组feedback，形式为：对于范围谓词 $\\sigma_{col<=x}R$ ，监控得到其基数，设为为 $h_R$ ；R与每个桶 $b_i$ 的交集为 $R_{b_i}$ ，其高度为 $h_{R_{b_i}}$ 。那么可以得到R整体与每个交集 $R_{b_i}$ 的对应关系： $R=\\sum^{MaxBuckets}_{i=1}{R_{bi}}$ ， $h_R=\\sum^{MaxBuckets}_{i=1}h_{R_{bi}}$

在图上形象表示下：

假设从feedback中，我们监测到了card(R)的真实值S： $\\sum^{MaxBuckets}_{i=1}h_{R_{bi}}=S$ . 在这一条件下，某个桶x被R范围囊括，其更新后的高度，概率分布为 $p(h_{b_x}|\\sum^{MaxBuckets}_{i=1}h_{R_{bi}}=S)$ 。利用贝叶斯公式推得： $p(h_{b_x}|\\sum^{MaxBuckets}_{i=1}h_{R_{bi}}=S)\\propto p(\\sum^{MaxBuckets}_{i=1}h_{R_{bi}}=S|\\ h_{b_x})\\cdot p(h_{b_x})$ 。消除关联，得到： $p(h_{b_x}|\\sum^{MaxBuckets}_{i=1}h_{R_{bi}}=S)\\propto p(\\sum^{MaxBuckets}_{i=1}h_{R_{bi}}=S-h_{b_x})\\cdot p(h_{b_x})$

其中，对于两概率相乘，由于左边符合概率分布 $N(\\sum_{i\\in AllBuckets,i \ eq x}H_{bi}, \\sqrt{\\sum_{i\\in AllBuckets,i \ eq x}\\sigma^2_{bi}})$ ，右边符合概率分布 $h_{b_x}\\sim N(H_{b_x},\\sigma_{b_x})$ ，两边相乘可以得到新的正态分布，均值为： $H_{bx}\\cdot \\frac{(\\sum_{i\\in AllBuckets,i \ eq x}\\sigma^2_{bi})}{\\sum_{i\\in AllBuckets}\\sigma^2_{bi}}+\\frac{(S-\\sum_{i\\in AllBuckets,i \ eq x}H_{bi})\\cdot \\sigma^2_{bi}}{\\sum_{i\\in AllBuckets}\\sigma^2_{bi}}$

方差为 $\\frac{\\sigma_{bx}\\sqrt{\\sum_{i\\in AllBuckets,i \ eq x}\\sigma^2_{bi}}}{\\sqrt{\\sum_{i\\in AllBuckets}\\sigma^2_{bi}}}$

至此，我们得到了每个桶在确切的feedback监控信息下，更新高度的概率分布 $p(h_{b_x}|S)$ ；据此可以依次对每个桶的高度进行更新，得到新的直方图。

多维直方图是用来表示多个关联列的直方图。我们给出问题定义：假设有d列，每列的最小值 $l_i$ ，最大值 $u_i$ ，多维直方图代表着空间 $\\varphi=[l_1,u_1]\ imes[l_2,u_2]\ imes...\ imes[l_d,u_d]$ ；直方图上的每个桶 $b_i$ 占据了空间中的一部分，这部分空间范围表示为 $C_{b_i}$ 。

现在，假设我们从feedback中得到了一组谓词，和监测到的基数 $(q_1,N(q_1)),(q_2,N(q_2))...(q_m,N(q_m)),$ 其中每一个谓词q，代表着d个列上的谓词以and连词的形式结合到一起： $(x_1<=C_1<=y_1)\\wedge...\\wedge(x_{d'}<=C_{d'}<=y_{d'})$ 。举个形象的例子，对于Car表上的两个过滤谓词color='white'和make='Honda'，监控收集得到的反馈如下：

其中Car表总共100行，make 列包含’honda’, ‘bwm’两种值，可以映射为0, 1；color列包含’black’, ‘white’两种值，同样可以映射为0,1；不久，又从feedback监测到N(color=‘white’)=30。于是我们可以得到三个等式：

$n(b_1)+n(b_2)+n(b_3)+n(b_4)=100$

$n(b_2)+n(b_4)=80$

$n(b_3)+n(b_4)=30$

最开始我们假设直方图均匀分布。根据feedback逐步更新，我们得到：

会发现，根据feedback直接强行更新，会得到直方图上数据不一致的情况。需要设计一种算法，同时保证：

一致性：不违背表行数、feedback信息的一致性
均匀性：更新后的多维直方图保持均匀

我们来量化这一问题。根据Maximum-Entropy Principle，无约束情况下尽量保持数据分布均匀 (p代表概率分布)，其最大熵可以表示为 $H(p)=-\\sum ^n_{i=1}p_iln(p_i)$ ，当数据连续时， $H(p)=\\int _{\\varphi}p_uln(p_u)du$ 。

假设：谓词q，在多维直方图中覆盖的范围为R(q)，多维直方图的某个桶 $b_i$ ，其覆盖的空间范围是 $C_{b_i}$ ，桶内数据总量为 $n_{b_i}$ ，vol代表某个空间的几何大小。从直方图中可以估算出谓词q的基数： $\\hat{N}(q)=\\sum_{i=1}^kn(b_i)\\frac{vol(R(q)\\cap C(b_i))}{vol(C(b_i))}$