本文是相似源码浏览的一篇文章，初步对 PostgreSQL 统计信息模块进行了一些简略的介绍。这里抉择 PostgreSQL 而不是其余数据库的起因是在各种论文中看到一些设计估算的比拟时，PostgreSQL 总是会在论文中有一个不错的体现。
PG 中收集的统计信息
在 PostgreSQL 中，收集的统计信息分为三类：为一张表收集的统计信息，为一个列收集的统计信息，以及为了一组列收集的统计信息。
为表收集的统计信息
为表收集的统计信息次要是记录了这个表有多少行、有多少页（disk pages）。这两个信息也会为每个索引进行保护，同一个表的索引它的行数尽管一样，然而页数显然会不同。
为单列收集的统计信息
为单列收集的统计信息会大抵形容这个列的数据分布以及数据大小。在 PostgreSQL 中，它为每个列收集了如下的信息：
- Histogram：直方图，这个数据结构用来形容数据的散布，在 TiDB 源码浏览 统计信息（上）中也对这个数据结构做了比拟具体的形容，有趣味的同学能够在这篇文章中看到更具体的介绍。
- Most common values: 呈现次数最多的一组值。将它们踢出直方图能够缩小极其值造成的估算误差。
- Distinct Number: 即这一列一共有多少个不同的值。值得注意的是 PostgreSQL 并没有为直方图的每个 bucket 保护一个 bucket 自身的不同的值。
- NULL values: 有多少行的值为 NULL。因为 NULL 是一个十分非凡的值，所以也会将 NULL 独自拿进去进行保护
- Average value width in bytes: 列均匀长度，记录这个值能够用来对 SQL 应用的内存大小进行估算，以及对 IO 开销进行更粗疏的估算。
- Correlation: 索引和主键（或者说 row id）之间的程序相干水平。比方一个工夫索引总是插入最新一天的数据，那么它和主键的相干程序就会很高。失去了程序相干水平之后，咱们就能够估算一次索引回表读会造成多少 random IO。并且对于
where index col = xxx order by primary_key limit y这样的查问咱们也能够更精确的决策是抉择读索引还是抉择间接读表。
为多列收集的统计信息
PostgreSQL 没有间接为索引收集统计信息，而是须要通过语句来为某几个列收集统计信息。这里它收集了 Functional Dependency 和 Multivariate N-Distinct Counts。上面咱们别离介绍一下两种统计信息。
Functional Dependency
在数据库课程中咱们学到过当列 A 取某个值时，列 B 总是会取一个雷同的值，则存在列 B 对列 A 的函数依赖。在理论的数据库中，咱们很难找到十分严格的函数依赖，因而 PostgreSQL 这里也是记录了函数依赖的水平。在保护这个值之后，PG 就能够缩小依赖列之间因为独立不相干假如造成的估算误差。
如 where zip_code = … and province = ... 这里邮编和省份显然并不是齐全独立的，这时如果咱们保护了函数依赖的信息，那么咱们就能够在做估算时不必假如邮编和省份是独立不相干的了。
PostgreSQL 中对于给定的 n 列，应用的是如下的简略算法保护 n 列跟前 n-1 列之间的依赖性：
- 基于采样数据计算函数依赖，因为两头会进行屡次排序等操作，全量数据会过于耗时；
- 首先枚举所有可能列之间的排列；
- 对每组排列，咱们都依照对应的程序进行排序；
- 排序之后，咱们依照前 (n-1) 列进行分组；
- 对于每一组，咱们查看最初一列是不是只有一种值存在。如果是，那么 successfulSize += currentGroupSize；
- 最初函数依赖的水平为 successfulSize / totalRows。
Multivariate N-Distinct Counts（MCV）
PostgreSQL 保护的这个信息大抵上能够认为是多列上的 Most Common Values。因为比直方图来说构造上更加涣散，因而能够用来预计
- (a = 1) and (b = 2)
- (a < 1) and (b >= 2)
- (a is null) or (b is not null)
- (a < 1) or (b >= 2)
等各式各样的谓词的过滤率，而不须要总是在前缀列总是等值条件的状况下才能够估算下一列。
PostgreSQL 计算 MCV 的形式也和函数依赖比拟类似。比拟非凡的是，它并不只是简略的记录了最常呈现的那些值的 frequency（呈现次数 / 总行数），还记录了如果这些列之间是齐全不相干时的 frequency。这里的逻辑比较复杂，本文不对这里进行具体的解释。
PG 如何应用统计信息对单表进行估算
clauselist_selectivity
PostgreSQL 对统计信息的入口是函数 clauselist_selectivity
这个函数会承受 CNF 模式的谓词数组（由 AND 连贯数组中的各个谓词）。首先它会尝试应用 extended statistics（即多列统计信息）对谓词进行估算，而后对残余的谓词应用单列统计信息进行估算，两个入口别离是 statext_clauselist_selectivity 和 clauselist_selectivity_simple。
statext_clauselist_selectivity
在 statext_clauselist_selectivity 中首先会应用 MCV 进行估算，这里 PostgreSQL 只会应用一个它认为最优的 MCV 进行估算，而不是应用多个 MCV 再依据独立不相干假如进行估算。在判断哪个 MCV 最优时，它是应用了一个简略的贪婪算法，即看这个 MCV 笼罩了多少谓词。无关 MCV 的逻辑，在函数 statext_mcv_clauselist_selectivity 中。
dependencies_clauselist_selectivity
在应用了 MCV 解决后，它会开始应用函数依赖对谓词进行进一步的过滤，对于两列的函数依赖 P(a, b) = P(a) (f + (1-f) P(b)) 这里 f 即是 (a, b) 之间的函数依赖水平。对于多列的函数依赖，通过 P(a, b, c) = P(a, b) (f + (1-f) P(c)) 来归化成 P(a, b) 与 P(c) 之间的计算。这部分逻辑在函数 dependencies_clauselist_selectivity 中。
在应用完两种多列统计信息后，便是应用残余的单列统计信息在基于各列 / 谓词之间独立不相干假如进行的估算。
clauselist_selectivity_simple
函数 clauselist_selectivity_simple 是一个简略的 wrapper，次要是对单列上的范畴谓词做了解决，避免独立假如造成的误差。即对于 a > 100 and a < 1000 它会为 a 保护一个区间信息，当所有谓词都解决完之后，再依据区间信息对这个列进行估算。对于不须要保护区间信息的其余谓词，它会间接应用函数 clause_selectivity 进行估算。
clause_selectivity
在 clause_selectivity 中，则是应用各种假如进行的最粗犷的估算：
- 对于一个 DNF（由 OR 连贯各个谓词），应用 s = s1 + s2 – s1*s2 进行估算
- 对于 NOT 表达式，应用 s = 1 – s1 进行估算
- 对于一个 CNF，跳回下层应用 clauselist_selectivity 进行估算
- ….
能够看到这里就是应用独立散布的假如进行估算了。
PG stats 总结
下图示意 PG 整个估算过程：
与 TiDB 的异同
TiDB 目前短少 PostgreSQL 中领有的多列统计信息（MCV 和 函数依赖），然而有多列直方图。PostgreSQL 以后并没有为多列保护直方图。PostgreSQL 以后的做法将统计信息和索引进行理解耦这样就能够间接对并不是索引的列组合建设须要的统计信息，某种程度也不便统计信息的保护和治理。
TiDB 目前并没有应用 s = s1 + s2 – s1*s2 来为 DNF 进行估算，而是简略的是用一个 magic number(0.8) 来示意 DNF 的选择率。
其余的流程上，TiDB 和 PostgreSQL 大体上是雷同的。
PG 如何应用统计信息对多表进行估算
这里咱们次要介绍一下 PostgreSQL 如何对 inner join 进行估算。
PostgreSQL 次要是应用 Most Common Values 对 join 的后果集进行估算。它首先计算如下几局部：
- match_prod_freq：左右表只应用 MCV 失去的选择率，即两边 MCV 中都呈现的值的选择率之和；
- match_freq1：MCV 1 中多少值在 MCV 2 中被匹配到了；
- match_freq2：同理；
- unmatch_freq1：MCV 1 中有多少值在 MCV 2 中没有被匹配到；
- unmatch_freq2：同理；
- other_freq1：表 1 中有多少值是没在 MCV 中呈现的。
那么残缺的选择率便是，MCV 之间计算失去的选择率 + 没有在 MCV 1 中呈现的值和 MCV 2 进行匹配的选择率 + 没有在 MCV 2 中呈现的值和 MCV 1 进行匹配的选择率 + 没有在 MCV 1 中呈现的值和没有在 MCV 2 中呈现的值进行匹配的选择率：
上述式子只有基于表 1 的视角进行计算的后果，再镜像失去一份表 2 视角的选择率便是残缺的计算结果。
上述逻辑在函数 eqjoinsel_inner 能够找到。
比拟奇怪的是，这里仿佛并没有为 join key 是多列的状况进行解决（t1 join t2 where t1.a = t2.a and t1.b=t2.b），失常来说如果齐全应用独立不相干假如，估算容易呈现较大的偏差，可能这里有一些逻辑被我漠视了，在之后还会思考应用理论数据对 PostgreSQL 进行 debug 来进一步了解它的估算逻辑。
总结
本文对 PostgreSQL 所保护的统计信息以及进行的估算的框架通过追随代码进行了简略的介绍，还没有涉及其更细节的估算逻辑，之后还会持续对 PostgreSQL 的估算框架进行更粗疏的考查，看有没有值得借鉴的中央。