交叉列统计信息

此页面概述了实施跨列统计信息的尝试，即为了增强优化器而做出的一项努力，以便它能在表中的列不独立的情况下表现得更好。您可以在此找到失败案例的示例、关于解决方案如何奏效的想法、有关此主题的论文链接，等等。

此处罗列的大多数信息来自邮件列表上的讨论（尤其是 此线程，其中包括 后续内容），但主题一旦变得有些庞大，就很难继续跟进。因此，从这个角度来看，此页面只是一款易于阅读的摘要。

可能的路线图

简言之，没有明确的路线图，而是一个可能会突然改变的总体方向。目前的目的是构建一组概念证明，尝试构建各种可能性，然后可能构建利用 contrib 模块来估算 COUNT(*) 结果（这对分页非常有用）。然后，如果一切正常，最终可以在内核中使用该模块。

属性值独立性假设

属性值独立性假设是问题的根源 - 它相当于列的 统计独立性。根据这一假设，联合分布等于各个列的概率分布相乘。

当列在统计学上不独立时，这通常会导致对行数的严重低估。而在现实中，列几乎从未独立过。问题在于这种依赖性到底有多强。

我们来看一个真实的例子。

示例

一个典型的失败案例是一个包含邮政编码和城市名称的表。这两列高度依赖，因为邮政编码通常决定了一个城市。

假设有 100 个城市，每个城市有 100 个邮政编码。这意味着有 100 个城市和 10,000 个邮政编码。在估算满足条件的行数时

WHERE zip_code = '12345' AND city = 'cityname'

优化器当前执行以下操作

1. 估算“zip_code = '12345'”的选择性（假设分布均匀，选择性为 1/10,000 = 0.01%）
2. 估算“city = 'cityname'”的选择性（假设分布均匀，选择性为 1/100 = 1%）
3. 将选择性相乘，得到选择性 0.0001%

问题在于实际选择性是 0.01%，因为邮政编码暗示了城市。因此，获得的估计值将被低估 100 倍。并且通过合并更多条件，这甚至可能导致更差的估计值。这可能是一个严重的问题，因为计划人员可能决定在这种情况中使用索引扫描而不是顺序扫描。对于复杂查询，有时很难预测效果。

这一切都是由于“属性值独立性”，它基本上与概率论中的“统计独立性”相同。

如果您需要真实的样本数据进行操作，请尝试 1999 年美国邮政服务邮政编码（或直接 ZIP）。它并不是非常新鲜，但足够好。它采用 DBF 格式，因此您需要使用一些工具来提取数据（如 PgDBF）。

假设、假设、假设...

收集统计信息并使用它们来估计行数时，总是有一些假设表明：“如果这个成立，那么估计值与实际值不应该相差太远。”问题在于，实际数据集几乎永远无法完美地满足这些假设。

这样的假设有一个示例，即属性值独立性假设 (AVI)，如上文所述以及失败案例。但还有其他几个假设，有些用于不同的地方，有些可能是 AVI 假设的可能替代方案。这是一个非常简短的列表

• 直方图箱内均匀分布——优化器假设在直方图箱内，值呈均匀分布
• 均匀相关——假设不是独立的，而是P(A=a|B=b)=c（常数），因此P(A=a,B=b)=P(A=a|B=b)*P(B=b)=c*P(B=b)
• 条件独立——这有点复杂，例如请参阅论文使用概率模型进行选择性估计 [4]

其原理是用一个非常弱的假设（如均匀相关或条件独立）来替换一个非常强有力的假设（如 AVI）。打破一个较弱的假设通常会导致估计误差小得多。

问题的实例

正如我在这篇文章中所解释的那样，我认为这个问题有四个截然不同的实例。也许有一个“统一理论”可以处理所有这些问题，但我并不知道。那么有哪些情况呢？

首先，有两种完全不同的变量（列）——数值和离散。离散并非意味着整数，而是充当标签的值 - 姓名（城市、人名）就是一个很好的示例。离散列实际上可以编码为数字，例如邮政编码。乍一看，这些类型似乎相等，但事实并非如此 - 您可以使用数值执行许多操作，而这些操作要么无法使用离散值执行，要么结果没有多大意义。例如，对邮政编码进行减法、计算城市名称的平均值等。

其次，有两种类型的条件 - 等式和不等式（范围）条件。这两种类型的条件通常需要不同类型的统计，所以我们分别处理它们。

因此最终有问题的四个不同实例

	等式条件	不等式条件
离散值	A	D
数值	C	B

A) 离散值和等式条件

其中一篇论文（一种通过联结谓词评估选择性的贝叶斯方法）提供了一个非常有趣的解决方案，我已发布一篇关于如何将它们应用于邮政编码/城市名称问题的描述 - 参见这篇文章和随后的讨论。

这基本上用单一的相关性假设取代了 AVI 假设，后者要弱得多。它有一些优点（轻松扩展到两列以上，只需保留少量数据），以及一些与估计不同值数量（针对单个列和查询中使用的组合）相关尚未解决的问题。当前的（基于采样的）估计器存在已知的问题，尤其在组合的情况下 - 文档此处描述了改进估计器的举措。

B) 数值和不等式条件

大多数针对此问题提出的论文都基于离散化和多维直方图来近似联合分布。所以我猜我的最初提议（参见第一个 PoC）并非完全无稽之谈，因为它基于此方法。一旦我们有了一个基于直方图的解决方案，我们就可以着手提高精度和效率（存储直方图需要多少空间、计算一个估计需要多长时间等）。根据这些论文，有两种方法可以做到这一点（如果您知道其他解决方案，请告知我们）。

首先，有一些文章提出各种增强型多维直方图（GenHist、SGRID、VMHIST 等）。当然，每篇文章都声明他们描述的直方图实际上是最好的（效率最高的、最精确的等），这有点可疑。无论如何，有构建更好的多维直方图的一些有希望的方法。

其次，文章“使用概率模型进行选择性估计”描述了一种完全不同的基于贝叶斯网络的解决方案。这似乎是一个非常有趣的替代方案（它实际上也涉及连接选择性估计）。

因此，尽管初始实现可能效率低下且不精确，但我非常有信心我们能够显著改进它。使用高级直方图或使用贝叶斯网络。

C) 数字值和相等条件

我不确定如何处理这种情况。但针对数字查询的查询在大部分情况下都是范围查询，所以也许这并不是什么大问题。

D) 离散值和不等式条件

从本质上讲，离散化后这可以像数字值一样处理，即使用直方图。但就像前一个情况一样，这不是一个非常常见的情况。例如，你运行此类操作的频率是多少

SELECT * FROM foo WHERE (zip_code BETWEEN '12899' AND '23890') AND (city_name BETWEEN 'Boston' AND 'Chicago')

可能不是非常频繁。

离散/数字列的组合

我现在不确定如何处理这个问题。显然，可以构建多维直方图，并估算尽可能多的查询。

概念证明

到目前为止，我构建了两个概念证明 - 第一个解决了情况 B（带有范围条件的数字数据），第二个解决了情况 A（带有相等条件的离散数据）。

数字数据和范围查询

此概念证明在初始提案中进行了描述。它基于多维的（相当原始的）。

离散数据和相等查询

此概念证明在这篇文章中得到了详细描述。它基于文章使用贝叶斯方法估计合取谓词的选择性 [2]。

可能的功能

本部分讨论解决方案可能具备的各种功能，这些功能的优点/缺点等。

可选与自动

不太可能自动收集统计信息，请参阅下一部分。

收集有关列所有组合的数据

我绝认为我们不应该为表中列的每个组合收集统计信息。收集跨列统计信息可能会消耗大量资源（时间、CPU、内存、I/O，...），所以收集信息每个组合并非高效率。该计划允许 DBA 仅在实际需要时（即满足这些条件时）启用跨列统计信息（使用 ALTER TABLE、PL/pgSQL 程序等）。

• 这些列是相关性的
• 这些列经常一起（频繁）使用在查询中
• 目前的估算值严重不准确，导致选择低效的查询计划

不太可能自动为列的每个组合收集统计信息。

为多列索引收集统计信息

唯一可能自动收集跨列统计信息的情况是存在多列索引。这通常表示列经常一起使用，而且极有可能使用此索引更有效地构建直方图。但有一些反驳意见

• 多列索引并不意味着这些列具有相关性（会产生无效的估计值）
• 许多开发人员通常将多列索引替换为简单索引的集合（并让数据库使用位图索引扫描来处理它）

独立性测试

对于或然表，有一个独立性检验（例如，Pearson 的卡方检验），因此可以轻松找出这些列是否独立。如果该检验显示这些列是独立的，我们可以直接丢弃跨列统计信息，并根据属性值的独立性使用简单的估算。

识别经常一起使用的列

我注意到有需求收集有关在单个 WHERE 条件同时频繁使用的列的数据。这可能是一个有趣的功能（尤其是当估计值与实际值严重不同时），但这不属于此任务（当前任务）的一部分。

历史与讨论

此内容是存档中讨论跨列统计信息的主题列表。这绝非详尽无遗的列表（例如，pgsql-performance 存档中包含大量讨论由错误估计值引起的问题的条目）

• 对规划器和索引的改进提出假想建议 - pgsql-performance，2003 年 5 月
• 跨列统计信息 - pgsql-hackers，2006 年 2 月
• 规划器提示的一个想法 - pgsql-hackers，2006 年 8 月
• 多列索引统计 - pgsql-hackers，2007 年 3 月
• 多维直方图 - pgsql-hackers，2009 年 6 月
• 对跨列统计的重新审视 - pgsql-hackers，2010 年 10 月
• 对跨列相关性的重新审视 - pgsql-hackers，2010 年 7 月
• 提议：跨列统计 - pgsql-hackers，2010 年 12 月

有趣的文件

有很多有关选择性估计的有趣文件。这是我最近阅读的文件列表，外加简短说明。如果您知道与此主题（选择性估计，特别是有关相关列）相关的其他有趣文件，只需在此处添加。该部分分为两部分 -“推荐文章”列出了真正有趣的文章（不被淘汰、对领域进行总体介绍或描述非常有趣的方法）。“其他文章”用于在将来可能有趣的文章、已被淘汰的文章或描述不直接适用于 PostgreSQL 的解决方案（例如涉及随机采样）的文章。

推荐的文件

1. 新泽西州数据归纳报告 citeseerx PDF
   • 发表于 1997 年，作者：丹尼尔·芭芭拉、威廉·杜蒙歇尔、克里斯托斯·法洛佐斯、彼得·J·哈斯、约瑟夫·M·赫勒斯坦、扬尼斯·约阿尼迪斯、H·V·贾加迪什、西奥多·约翰逊、雷蒙德·吴、维斯瓦纳特·波萨拉、肯尼斯·A·罗斯、肯尼斯·C·塞夫奇克
   • 对“数据归纳”，即用模型表示数据的非常彻底的介绍
   • 涵盖此处提到的所有可能性（直方图、SVD、采样）外加更多可能（对数线性模型）
   • 不涵盖概率模型
   • 无论如何，如果您需要有关此主题的介绍，这可能是最佳起点 - 它很彻底，写得很好，涵盖了大部分知识，等等。
2. 使用贝叶斯方法估计联接谓词的选择性 PDF
   • 发表于 2009 年，作者：马克斯·海梅尔、沃尔克·马克尔、凯沙瓦·穆尔蒂
   • 基于假设“一致相关性”，与属性值独立性相比，这是一个非常弱的假设
   • 可轻松扩展到两列以上
   • 为高度相关的列提供良好估计
   • 不需要多维直方图等复杂技术
   • 似乎是解决“ZIP 代码”失败案例的不错解决方案
   • 有一些弱点 - 最严重的一个是需要对离散值数量（各个列和用于查询的组合）进行良好估计
3. 在不使用属性值独立性假设的情况下估计选择性 citeseerx PDF
   • 1997 年发表，作者：Viswanath Poosala、Yannis E. Ioannidis
   • 没有革命性进展——它只是展示了构建多维直方图的另一种方式（以及基于 SVD 的完全不同的方法）
   • 这些直方图旨在提高效率和准确性，因此一旦我们获得有效（但不够精确）的解决方案，这可能会在未来成为一项非常有趣的改进
4. 使用概率模型估计选择性 citeseerx PDF
   • 发表时间为 2001 年，作者：Lise Getoor、Ben Taskar、Daphne Koller
   • 用较弱的“条件独立性”假设替换令人担忧的“属性值独立性”假设，然后用于构建贝叶斯网络 (BN)/概率关系模型 (PRM)
   • 显然，这可用于推断单表估计和联接估计
   • 我尚未深入研究 BN/PRM 构造，但它看起来相当容易处理（并且有一系列介绍此的文章）
   • BN/PRM 方法的主要作用是显著减少存储联合分布所需的数据量（不存储整个表，而只存储一些条件概率）
   • 这实际上可构建在多维直方图之上，因为我们需要以某种方式将值离散化（当然，除非数据已经是离散的）
5. 真实属性的多维范围查询的选择性估计器 citeseerx PDF
   • 发表时间为 2005 年，作者：Dimitrios Gunopulos、George Kollios、Vassilis J. Tsotras、Carlotta Domeniconi
   • 很好地总结了与跨列统计信息相关的问题，以及可能的解决方案（直方图、SVD、DCT，...）
   • 总结了构建更高（超过 1D）维度的直方图时遇到的问题，即单元格数量呈指数增长（存储空间更大，查询交集更多）与较大（准确性更低）单元格之间的问题。
   • 提供了两个新估计器——GENHIST 和核估计器
   • GENHIST 是构建直方图的另一种方法，它允许相交单元格（与将空间分区为不相交区域的常用直方图相反）
   • 核估计器 是随机采样的增强版，具有非常有趣的速度/准确性和其他优点（不基于直方图），但我想这对我们来说并不是很有用，因为我们没有进行任何采样

其他论文

1. 查询优化 引文网 PDF
   • 作者：扬尼斯·埃·伊奥安尼迪斯，发表于 1996 年
   • 一篇非常棒的选择性估计理论导论，如果你对一般原理一无所知，值得一读
2. 用于范围谓词选择性估计的改进直方图 引文网 PDF
   • 作者：维斯瓦纳特·普萨拉、扬尼斯·埃·伊奥安尼迪斯、彼得·J·哈斯、尤金·J·希基塔，发表于 1996 年
   • 与“不带属性值独立假定的选择性估计”（两位作者于 1997 年撰写）大致相同
   • 未讨论某些备选方案（例如 SVD），且包含稍有不同的测试。
   • 有一章非常有意思的第 7 章，关于计算技术（分布、分位数、不同值、直方图构造成本、所需的样本量等）
3. STHoles：一个多维负载感知直方图 引文网 PDF
   • 作者：尼古拉斯·布鲁诺、苏拉吉特·乔杜里、路易斯·格拉瓦诺，发表于 2001 年
   • 另一种类型的直方图 - 这种情况下，它不是直接从数据集构建的，而是从查询结果构建的，而且这不是一个一次性过程，直方图会持续改进（在频繁查询的区域进行改进）。
   • 我没有读过全文，但尽管它看起来很有趣，但不太可能很快进入核心内容，而且没有类似内容（根据查询结果更新统计数据）
   • 所以这是一个有趣的话题，但目前不在讨论范围内。
4. 摘要网格：构建准确的多维直方图 引文网 PDF
   • 作者：佩德罗·富塔多、H·马德拉，发表于 1999 年
   • 描述了一种构建多维直方图的替代方法 - 传统算法（MHIST、PHASE）自上而下地工作，即把空间划分为越来越小且越同质的区域（存储区），这种新算法（称为 SGRID）自下而上地工作，即它不断地把同质的区域合并到更大的存储区中
   • 同样地，在开始时这并不是非常有趣，也许晚一点在改进解决方案时（使其更有效，占用更少空间等）会变得有趣
5. Vmhist：效率高且准确性更好的多维直方图 PDF
   • 作者：佩德罗·富塔多、亨里克·马德拉，发表于 2000 年
   • 对另一个直方图的描述，称为 VMHIST
   • 作者声称它比 MHIST（参见其他文章）效果更好，且可扩展性更好
   • 这篇文章比较粗糙，关于算法的细节并不多，而且比较也不够全面
6. 平衡直方图最优性和查询结果大小估计的实用性 PDF
   • 发表于 1995 年，作者：Yannis E. Ioannidis、Viswanath Poosala
   • 这似乎是一篇相当老的文章，并且大部分内容已经过时（例如，Ioannidis 发表的以下文章更有趣，因为里面展示了更高级的直方图）
   • 包含一些基本的定义、引理等
7. 快速且有效的直方图构建 WWW PDF
   • 发表于 2009 年，作者：Felix Halim、Panagiotis Karras、Roland H. C. Yap
   • 另一篇文章提出了构建直方图的新方法，与较旧的直方图等进行比较
8. HASE：联接谓词选择性估计的混合方法 PDF
   • 发表于 2006 年，作者：Xiaohui Yu1、Nick Koudas1、Calisto Zuzarte
   • 尝试将简介（预生成信息 - 例如，直方图）和随机抽样的估计值（在规划查询时执行）结合在一起
   • 目前这两种方法是分开使用的，他们尝试结合起来，消除缺点并获得两者的最佳部分
   • 现在这对我们来说毫无用处，因为我们根本没有使用随机抽样（也许将来这可能是一个有趣的改进）
9. 基于直方图的集合值查询答案近似 citeseerx PDF
   • 发表于 1999 年，作者：Yannis E. Ioannidis、Viswanath Poosala
   • 与其说是关于估计，不如说是关于近似返回行集的查询结果
   • 包含一些有趣的信息，但与估计无关