智能关键技术三：智能优化器

贝叶斯网络模型原理贝叶斯网络是一种概率图模型，拓扑结构通常为一个有向无环图。

贝叶斯网络的优势在于能够利用条件独立假设对多变量数据进行建模，并且自适应变量之间的相关性，具体是指每个变量的概率分布只和与它直接连接的父亲节点有关。使用这种方法能够比基于简单的独立性假设的模型获得更高的建模准确率，也能够比完整的联合分布建模获得更高的执行效率。在关系数据表中，每一列数据都可以成为一个变量，比如下表中包含A,B,C三列数据：

分别使用基于独立性假设的单列建模和基于条件独立假设的贝叶斯网络计算查询 SELECT * FROM table WHERE A=A1 AND B=B1 AND C=C1的选择率：单列建模：P(A=A1, B=B1, C=C1)=P(A1)P(B1)P(C1)=0.5 * 0.67 * 0.67=0.22贝叶斯网络：P(A=A1, B=B1, C=C1)= P(A1)P(B1|A1)P(C1|B1)=0.51.01.0=0.5可以看出贝叶斯网络在列相关性强的场景下能够更加准确地估计出多列查询选择率（和基数）。

贝叶斯网络结构搜索贝叶斯网络的拓扑结构决定于变量之间的互相关性，直观上看，将互相关性强的变量进行连接并计算条件概率有助于提高分布建模准确性。假设有两列数据A和B，互相关性定义如下：

遍历上述临时表，对每一行求得互相关性，然后求和之后就是A和B列的整体相关性。

贝叶斯网络对于每个节点父亲节点的数量是没有要求的，但是父亲节点越多，条件概率建模的难度也越大，消耗的空间和时间代价也会相应变大。

所以在本子系统中，我们只采用树型的网络拓扑结构。这种结构中每个节点只有一个父亲节点，所以只需要保存本节点可以另一个父亲节点的条件概率即可，示例如下：

在有了树型限制之后，结构搜索空间就少了很多，现在的目标就是找到一颗总互相关性最大的生成树，这里本系统采用chow-liu算法，也是一种加权最大生成树算法，算法流程如下：

根据搜索出的贝叶斯网络结构，构造出包含所有边的字符串，比如”a,b,a,c”或者”a,b,b,c”传入贝叶斯网络算子进行模型创建。

贝叶斯网络训练

贝叶斯网络训练过程中，算子首先会遍历一遍样本数据，获得每列数据不同值统计；然后对于每列数据，根据是否是连续数据类型进行数据分桶或者高频值抽取以减小存储和计算代价；对数据分桶采用等高分桶，尽量使每个桶内的频度是相似的，每个桶中范围值下界被存储在数据列表中，NULL值单独作为一个值放在列表最后；连续值高频值抽取会将频度最高的K各元素放置在数据列表中，除此之外的其他元素都被表示为一个通配符号放在列表最后；为了减少查找匹配代价，字符串类型数据会存储一个额外的哈希值；列表中每个元素表示结构如下所示：

typedef struct ValueInTuple {    Datum data;    Oid type;    bool isnull;    uint32_t hashval;} ValueInTuple;

概率建模过程中，针对形如P(离散值|离散值)的条件概率使用概率表记录每种值的概率；针对P(离散值|连续值)，将连续值通过范围分桶当做离散值处理；针对P(连续值|离散值)，使用高斯分布对连续值分布进行建模；针对P(连续值|连续值)，使用高斯分布对条件连续值进行离散化分桶处理，对目标连续值进行高斯分布建模。训练完成之后，将模型序列化成一个二进制字符串。

贝叶斯网络模型推理

贝叶斯网络从第一个位置开始获得一个未访问节点，如果该节点存在未访问父亲节点，那么就递归访问父亲节点；如果父亲节点都已经被访问，那么利用条件独立性假设，利用概率表或者是高斯函数局部计算出当前节点的条件概率并且和父亲节点的概率相乘作为联合概率。

然后判断当前节点是否是叶子节点，如果是叶子节点则将联合概率和选择率相乘，否则继续寻找下一个未被访问过的节点。

最后返回选择率。

模型参数缓存策略

在基数估计的时候需要获得相应的模型参数，这个过程需要从磁盘读取以及反序列化两种操作，涉及到磁盘访问以及内存申请操作，效率较低，所以在模型数量不多的情况下可以利用全局共享缓存将其存在内存中，下次访问效率就会变高，但是在模型数量变多之后就需要缓存替换策略以保证内存使用是可控的。

本子系统采用的是异步批量替换策略，在模型访问亲和性高的场景下，当前一段时间所需要的模型都放置在内存中，不会带来额外的性能损失，访问申请的也都是共享锁支持高并发；当负载偏移之后，新的模型会被访问，从磁盘中被加载到内存，内存中的数量就会超过阈值，这种情况下系统按照每个模型的最近访问时间归一化之后的概率选择1/3的旧模型替换出内存。这种一次性替换多个模型的方法可以避免每次读操作都要申请互斥锁维护链表并且降低替换操作触发的次数。并发analyze场景通过互斥锁进行共享缓存访问控制。