（论文阅读-优化器）Selectivity Estimation using Probabilistic Models，基于概率模型的优化器选择性估算研究

摘要：本文研究了使用概率模型进行选择性估计的问题。文章介绍了优化器在机器学习模型训练中的重要性，并详细阐述了如何通过概率模型来估计和优化选择性的过程。文章通过理论分析并结合实验验证，展示了概率模型在提高选择性估计准确性和优化器性能方面的潜力。

目录

摘要

一、简介

二、单表估计

2.1 条件独立Condition Independence

2.2 贝叶斯网络Bayesian Networks

2.3 查询评估中的贝叶斯网络

三、Join选择性估计

3.1 两表Join

3.2 概率关系模型

3.3 使用PRMs的选择性估计

四、PRM构建

4.1 评分标准

4.2 参数估计

4.3 结构选择

4.3.1 评分审视

4.3.2 模型空间

4.3.3 搜索算法

五、实验结果

六、总结

摘要

对于涉及多个属性选择和多个关系连接的复杂查询，其结果大小的估计是数据库查询处理中一项困难而又基本的任务。它出现在基于成本的查询优化、查询分析和近似查询回答中。在本文中，我们展示了如何有效地使用概率图形模型作为跨多个关系的多个属性联合频率分布的精确和紧凑的逼近来完成这项任务。概率关系模型(Probabilistic Relational Models, PRMs)是最近的一项发展，它将图形统计模型(如贝叶斯网络)扩展到关系领域。它们表示表中属性之间以及跨外键连接的属性之间的统计依赖关系。我们提供了一种从数据库构建PRM的有效算法，并展示了如何使用PRM对广泛的查询类计算选择性估计。这项工作的主要贡献之一是为涉及选择和外键连接操作的查询的时间确定提供了统一的框架。此外，我们的方法并不局限于回答一小部分预先确定的查询;可以使用单个模型有效地估计跨多个表的大量潜在查询集合的大小。我们在几个真实的数据库上展示了我们的方法的结果。对于单表多属性查询和一般的select-join查询，我们的方法使用可对比的空间和时间，比标准的选择性估计方法产生更准确的估计。

一、简介

概率图模型是一类用图形模式表达基于概率相关关系的模型的总称。概率图模型结合概率论与图论的知识，利用图来表示与模型有关的变量的联合概率分布。近10年它已成为不确定性推理的研究热点，在人工智能、机器学习和计算机视觉等领域有广阔的应用前景。 [1]

基本的概率图模型包括贝叶斯网络、马尔可夫网络和隐马尔可夫网络。

基本的Graphical Model 可以大致分为两个类别：贝叶斯网络(Bayesian Network)和马尔可夫随机场(Markov Random Field)。它们的主要区别在于采用不同类型的图来表达变量之间的关系：贝叶斯网络采用有向无环图(Directed Acyclic Graph)来表达因果关系，马尔可夫随机场则采用无向图(Undirected Graph)来表达变量间的相互作用。这种结构上的区别导致了它们在建模和推断方面的一系列微妙的差异。一般来说，贝叶斯网络中每一个节点都对应于一个先验概率分布或者条件概率分布，因此整体的联合分布可以直接分解为所有单个节点所对应的分布的乘积。而对于马尔可夫场，由于变量之间没有明确的因果关系，它的联合概率分布通常会表达为一系列势函数（potential function）的乘积。通常情况下，这些乘积的积分并不等于1，因此，还要对其进行归一化才能形成一个有效的概率分布——这一点往往在实际应用中给参数估计造成非常大的困难。

概率图模型有很多好的性质：它提供了一种简单的可视化概率模型的方法，有利于设计和开发新模型；用于表示复杂的推理和学习运算，可以简化数学表达。 [3]

准确估计查询结果的大小对于数据库管理系统(DBMS)的几个查询处理组件来说是至关重要的。基于成本的查询优化器使用中间结果大小估计来选择最优的查询执行计划。查询分析器在查询设计阶段通过预测资源消耗和查询结果的分布向DBMS用户提供反馈。精确的选择性估计还允许在多处理器系统上实现高效的并行连接负载平衡。选择性估计还可用于近似地回答计数(聚合)查询。

对多个属性的选择查询的结果大小由这些属性值的联合频率分布决定。联合分布对所有属性值组合的频率进行编码，因此随着属性和值的增加，精确地表示它的方案变得不可行。大多数商业系统通过采用几个关键假设来近似联合分布;这些假设允许快速计算选择性估计，但是，正如许多人注意到的，估计可能是非常不准确的。

第一个常见的假设是属性值独立假设（attribute value independence assumption），在该假设下，单个属性的分布是相互独立的，联合分布是单属性分布的产物。然而，真实的数据往往包含违背这一假设的属性之间的强相关性，导致非常不准确的近似。例如，一个普查数据库可能包含高度相关的属性，如Income和Home-owner。属性值独立性假设会导致对请求低收入房主的查询结果大小的高估。

第二个常见的假设是连接一致性假设（join uniformity assumption），它表示来自一个关系的元组与来自第二个关系的任何元组连接的可能性相等。同样，在许多情况下，这一假设是违反的。例如，假设我们的人口普查数据库有一个用于在线购买的第二个表。高收入人群通常会比平均水平网购更多。因此，购买表中的元组更有可能与高收入个人的元组连接，从而违反了连接一致性假设。如果我们考虑一个针对高收入个人购买的查询，使用连接一致性假设的估计过程很可能会大大低估查询的大小。

为了放宽这些假设，我们需要一种更精细的方法，考虑多个属性的联合分布，而不是单独考虑属性的分布。最近提出了几种联合分布近似的方法，也称为数据约简;请参阅[2]以获得该领域的优秀摘要。这些工作的大部分集中在评估单个表中选择操作的选择性的任务上。一种简单的近似查询大小的方法是通过随机抽样。在这里，生成一组样本，然后通过计算相对于采样数据的实际查询结果大小来估计查询结果大小。然而，精确估计所需的数据量可能相当大。最近，提出了几种方法，试图更直接地获取属性的联合分布。其中最早的是Poosala和Ioannidis的多维直方图方法[23,25]。它们为构造多维直方图的方法分类提供了广泛的探索，并研究了不同技术的有效性。文中还提出了一种基于奇异值分解的方法，该方法仅适用于二维场景。一种新的方法是使用小波wavelets来逼近潜在的联合分布[21,27,6]。

在估计连接的选择性方面所做的工作要少得多。商业DBMS通常做出统一连接的假设。建议的一种方法是基于随机抽样:对两个表进行随机抽样，并计算它们的连接。这种方法在几个方面有缺陷，一些工作致力于以更有针对性的方式生成样本的替代方法[20]。最近另一种替代方法是Acharya等人[1]关于连接概要的工作，它维护一些不同连接的统计信息。据我们所知，目前还没有对现实世界中同时包含select和join操作的查询支持选择性估计的方法进行研究。

在本文中，我们基于概率图模型领域的技术[17,24]，提出了一种选择性估计问题的替代方法。正如我们将展示的，我们的方法有几个重要的优点。首先，它为选择选择估计和外键连接选择估计提供了统一的框架，并引入了一种系统的方法来估计这两种操作符的查询大小。其次，我们的方法不局限于回答一小部分预先确定的查询;可以使用单个统计模型对数据库中任何一组表和属性有效地估计任何查询(选择外键连接)的大小。

概率图形模型是一种用于紧表示高维空间中复杂联合分布的语言。它们基于图形表示法，对分布中属性之间的条件独立性进行编码。当两个属性是相关的，但相互作用是通过一个或多个其他变量中介时，就会出现条件独立性。例如，在人口普查数据库中，教育程度与收入相关，有房者身份与收入相关。因此，教育与有房者地位相关，但仅通过收入水平间接相关。这种类型的交互在实际领域中非常常见。概率图形模型利用了存在于域中的条件依赖关系，从而允许我们紧凑地指定高维空间上的联合分布。

在本文中，我们提供了一个使用概率图模型估计关系数据库中查询选择性的框架。正如我们所展示的，贝叶斯网络(bn)可以用来表示单个表中属性之间的交互，提供table中的属性上的联合分布的高质量估计。概率关系模型[18]（PRMs）将贝叶斯网络扩展到关系设置。正如我们所展示的，PRM允许我们表示表之间连接概率的倾斜，以及通过外键连接的元组属性之间的相关性。因此，它们允许我们评估涉及多个表上的选择和连接的查询的选择性。

与大多数选择性估计算法一样，我们的算法由两个阶段组成。脱机阶段offline phase，在脱机阶段中，从数据库构建PRM。这个过程是自动的，完全基于数据和分配给统计模型的空间。第二个阶段(在线阶段online phase)是对特定查询的选择性估计。选择性估计器selectivity estimator接收一个查询和一个PRM作为输入，并输出查询结果大小的估计。注意，同样的PRM用于估计数据库中任何属性子集的查询的大小；我们不需要事先获得关于查询工作负载的信息。

在本文中，我们做了两个重要的假设。首先，外键遵守引用完整性。这个关于数据库的假设在构建PRM时是必需的。其次，所有连接都是外键和主键之间的相等连接。做这个假设纯粹是为了便于表示。虽然外键连接的查询从我们提出的概率模型中获益最大，但我们的方法并不局限于处理这些查询，我们在第6节中描述了如何将我们的方法扩展到更广泛的连接类。

本文其余部分的结构如下。在第2节中，我们考虑在单个表上选择操作的选择性估计。我们定义了贝叶斯网络，并展示了如何使用它们来近似表中所有属性集合上的联合分布。在第3节中，我们将讨论对多个表进行查询的更复杂的情况。我们介绍了PRM框架，它将贝叶斯网络推广到关系情况，并展示了我们如何使用PRM在单个框架中完成选择和连接选择估计。在第4节中，我们提出了一个从关系数据库自动构造PRM的算法。在第5节中，我们提供了我们的方法的经验验证，并将其与一些最常见的现有方法进行比较。我们展示了在几个真实世界领域的实验，表明我们的方法提供了比以前的方法更高的准确性(在给定的空间量)，在非常合理的计算成本，包括离线和在线。

二、单表估计

我们首先考虑对单个关系上的选择查询的结果大小进行估计。对于本节的大部分内容，我们将注意力限制在每个属性的值数量相对较少(最多50个)的域，以及使用attribute = value形式的相等谓词的查询。这些限制都不是我们方法的根本限制;在本节的最后，我们将讨论如何将我们的方法应用于具有较大属性值空间的域和范围查询。

让R来代表一些table；我们使用R.*来表示表示R中属性A1, ..., An的值（非key）。我们将A1, ..., An的联合频率分布表示为FD(A1, ..., An)。它便于处理归一化频率分布PD(A1, ..., An)：

这样的转换允许我们将PD(A1, ..., Ak)作为一个概率分布处理。我们同样可以将这个联合分布看作是一个虚构的过程产生的，在这个过程中，我们从一个R中采样出一个元组r，然后选择r A1，…，an的值作为r中A1，…，r.An的值（请注意，我们并不是建议在实践中执行用于定义PD的取样过程。我们只是用它来作为一种定义PD的方法）。

现在，我们来考虑一个基于一组属性A1,...,Ak⊆R.*之上的查询Q，它是一组格式为Ai=vi的选择的组合。假设IQ是为Q中对r能使等式成立的事件。显然query Q的结果大小为：

其中FD(Q)是满足Q的元组数量，PD(IQ)是概率，相对于D，事件Q。为了简化符号，我们经常会简单地使用PD(Q)。由于relation的大小是一直的，联合概率分布包含了查询大小估计所需要的全部信息。因此，我们重点关注联合概率分布。

不幸的是,这种联合分布的条目数量随着属性数量呈指数级增长，因此明确表示这个联合分布几乎总是棘手的。有人提出了几种方法，通过使用更紧凑的结构来逼近联合分布(或联合分布的投影)来绕过这个问题[25,21]。我们也建议使用统计模型来近似完全联合分布。但是为了以紧凑的方式表示分布，我们探索了经常会在真实世界数据中的联合分布中具备的条件独立condition independence。通过将联合分布的表示法分解成能捕获域中独立性的因子，我们得到了该分布的一个紧凑表示法。

2.1 条件独立Condition Independence

考虑在一个简单relation R中的三个值属性，其每个值域都展示在括号中：Education(hight-school, college, advancd-degree)、Income(low, medium, hight)和Home-owner(false, true)。为了方便，我们使用每个名称的首字母来代表它，对属性使用大写字母，对于属性的特定值使用小写字母。我们使用P(A)来代表属性A可能的值的概率分布，P(a)代表事件A=a的概率。

假设在一个数据库中的属性值的联合概率分布如Fig.1(a)所示。使用这个联合分布，我们可以计算出来基于E，I和H上的的任意查询的选择率selectivity。为了方便，我们使用Qeih来代表一个格式为E=e, I=i, H=h的选择查询。然后会得到sizeQeih[D] = |R| * PD(e,i,h)。然而，为了精确表示这个联合分布，我们需要存储18个数值，其中每一个代表属性值可能的组合。（实际上，我们可以只使用17个数值，因我们我们知道联合分布中的和一定为1）。

然而，在许多上场景下，我们的数据将会以一种特定的结构展示，来允许我们（近似地）使用一种更紧凑的格式来代表分布。直觉上，某些属性之间的关联可能是间接的，由其他属性推导。例如，教育对拥有住房的影响可能通过收入来调节:一个高中辍学生拥有一家成功的互联网创业公司，比一个受过高等教育的海滩流浪汉更有可能拥有住房——收入是主导因素，而不是教育。这一断言可以以这样的描述来格式化表示：基于给定Income，Home-owner条件独立于Education。即，对于每一个h,e,i的组合来说，我们可以获得：

这个假设适用于Fig.1中的分布。

条件独立假设允许我们以分解的形式来更紧凑地表示联合分布。我们会展示：Education的边缘分布 - P(E)；给定Education下的Income条件分布 - P(I|E)；和一个给定Income下Home-owner的条件分布 - P(H|I)，而不是直接展示P(E,I,H)。我们可以很容易证明，如果条件独立假设成立，这样的表示包含了原始联合分布中的所有信息：

最后一个等式是由和给定的条件独立性推导出来的。在我们的例子中，联合分布可以用Fig.1(b)所示的三个表来表示。很容易验证它们编码的联合分布与Fig.1(a)完全相同。

拆解后的存储要求好像和之前是一样的：3+9+6=18。实际上，如果我们考虑到有些参数是多余的，因为这些数字加起来必须等于1，我们将获得 2 + 6+ 3 = 11，对于与完全联合的17。虽然这种情况下的节省似乎不是特别令人印象深刻，但只要直接依赖项的数量保持有限，节省就会随着属性数量的增加呈指数增长。

注意,条件独立性假设是完全不同于标准属性独立性假设。在这种情况下，例如，三个属性的一维直方图(即边缘分布)如图1(c)所示。很容易看出，在这种情况下，我们从属性独立性假设中得到的联合分布与真正的潜在联合分布非常不同。同样重要的是要注意，我们的条件独立假设与在这个分布中存在的房屋所有者和教育之间的强相关性是相容的。因此，条件独立性是一个比标准(边际)独立性弱得多且更灵活的假设。

2.2 贝叶斯网络Bayesian Networks

贝叶斯网络是高维联合分布的紧凑图形表示。它探索了域的底层结构-事实上，只有域的几个少数方面会直接相互影响。我们将概率空间定义为relation R中的属性集合A1,...,An的集合的可能赋值集合。贝叶斯网络BNs可以通过利用可以捕获属性之间的条件独立的结构，来紧凑地表示在A1,...,An之上的联合分布，从而利用概率影响的“局部性”。

一个贝叶斯网络β由两个组件组成。第一个组件，G，是一个有向无环图，其节点对应于属性A1,...,An。图中的边表示一个属性Ai和它的父Parents(Ai)的直接依赖。这个图结构将一组条件独立假设进行编码：每个节点Ai条件地独立于其父节点的非后代节点。

Fig.2(a)显示了使用美国人口普查局的数据提取系统从1993年当前人口调查中获得的数据(自动)构建的贝叶斯网络。在这个场景中，table包含12个属性：Age, Worker-Class, Education, Marital-Status, Industry, Race, Sex, Child-Support, Earner,Children, Income, and Employment-Type. 这些属性的域大小分别为：18, 9, 17, 7, 24, 5, 2, 3, 3, 42, 和 4。我们可以看到，举例来说，Children属性（代表家庭中是否有children）只通过属性Income、Age和Marital-Status依赖其他的属性。因此，Children在给定的Income、Age和Marital-Status下条件独立于其他的属性。

贝叶斯网络的第二个组件是每个节点和它的parents节点之间的统计关系statistical relationship。它由一个每个属性的条件概率分布（conditional probability distribution，CPD）Pβ( Ai | Parents(Ai) )组成，这个条件概率分布指定了在其parents的任意可能的赋值条件下的Ai分布。这个CPD可能会有多种表示方式。它可以表示为一个表，就像我们前面的例子一样。或者，它可能会表示为一棵树，其中内部顶点代表Ai的某个父结点的分割，叶子节点包含Ai值的分布。在这个表达式中，我们发现在通过沿着树中合适的路径达到叶子节点的方式，在给定其parents特定值Ak1=a1, ..., Akl = al的情况下，Ai的条件分布：当我们在某个变量桑遇到split时，我们沿着对应值aj的分支往下走；然后使用存储在叶子节点上的分布。Fig.2(a)中网络中的Children属性的CPD tree展示在Fig.2(b)中。这个属性的可能值为N/A，Yes和No。我们可以看到，例如，基于给定条件Income≥17.5K，Age