PostgreSQL统计信息和代价估算
内容来源：《PostgreSQL技术内幕：查询优化深度探索》，电子工业出版社，作者：张树杰。
优化器进行物理优化需要计算各种物理路径的代价，而代价估算严重依赖统计信息。统计信息是否能准确地描述表中的数据分布情况是决定代价的准确性的重要条件之一。
通过统计信息，代价估算时就可以了解一个表有多少行数据、用了多少个数据页面、某个值出现的频率等，然后根据这些信息计算出一个约束条件能够过滤掉多少数据，这种约束条件过滤出的数据占总数据量的比例成为“选择率”。
选择率 = 约束条件过滤后的元组数/约束条件过滤前的总元组数。
统计信息
PostgreSQL支持多种形式的统计信息，包括单列的统计信息和多列（扩展）的统计信息，单列的统计信息是指对每个表的每一个属性（列）都在PG_STATISTIC系统表中产生一个对应的统计信息元组，这个元组负责从多个角度描绘这个属性中的数据分布。
| 类型 | 说明 |
|---|---|
| STATISTIC_KIND_MCV | 高频值，在一个列中出现最频繁的值，按照出现的频率进行排序，并且生成一个一一对应的频率数组。 |
| STATISTIC_KIND_HISTOGRAM | 直方图，使用等频直方图来描述一个列中的数据的分布，高频值不会出现在直方图中。 |
| STATISTIC_KIND_CORRELATION | 相关系数，记录的是当前列未排序的数据分布和排序后的数据分布的相关性，这个值通常在索引扫描时用来估算代价。假设一个列未排序和排序之后的相关性是0，也就是完全不相关，那么索引扫描的代价就会高一些。 |
| STATISTIC_KIND_MCELEM | 类型高频值，用于数组类型或者一些其它类型，系统提供了ts_typanalyze函数来负责这种类型的统计信息。 |
| STATISTIC_KIND_DECHIST | 数组类型直方图，用于给数组类型生成直方图，系统提供了array_typanalyze函数来负责这种类型的统计信息。 |
| STATISTIC_KIND_RANGE_LENGTH_HISTOGRAM | 为Range类型生成一个基于长度的直方图统计西南西，用户可以自定义Range类型，系统提供了range_typanalyze函数负责生成这种类型的统计信息。 |
| STATISTIC_KIND_BOUNDS_HISTOGRAM | 为Range类型生成一个基于边界的直方图，这种类型的直方图也通过range_typanalyze函数进行统计。 |
STATISTIC_KIND_MCV、STATISTIC_KIND_HISTOGRAM、STATISTIC_KIND_CORRELATION是统计模块常用的三种统计方式。
使用基于单列的统计信息来对基于单个列的约束条件（例如a=1）进行选择率的估计，误差范围是可控的，但是对于引用了多个列的约束条件（例如a=1 or b=2 and c=3），如果还使用单列的统计信息进行估算，就需要将这个约束条件拆分成多个独立的子约束条件，对每个字约束条件信息选择率估算，并且假设这些子约束条件的选择率是独立的，然后基于概率的方法对总的选择率进行估算。由于实际应用中并不能保证它们是独立的，因此可能估算的误差较大，PostgreSQL对统计信息进行了扩展，支持多列的统计信息用来计算各个列之间的依赖度。
| 类型 | 说明 |
|---|---|
| STATS_EXT_NDISTINCT | 和单列统计信息中的stadistinct类似，stadistinct中记录的是单列中去掉NULL值和去重之后的数据量或者比例，STATS_EXT_NDISTINCT类型的统计信息记录的是基于多列的去重之后的数据量。 |
| STATS_EXT_DEPENDENCIES | 计算各个列之间的函数依赖度，通过函数依赖度计算各个列之间的依赖关系，从而得到准确的统计信息。 |
获得了统计信息之后，在代价估算的时候就可以利用这些统计信息进行计算。
PG_STATISTIC系统表
PG_CLASS系统表会保存两个统计信息：relpages和reltuples。relpages记录了当前表用了多少个页面，reltuples记录了当前表共有多少条元组。PG_STATISTIC系统表保存单列的统计信息，如果用户要给某个表生成统计信息，则可以使用ANALYZE语句对一个表进行统计分析，这样就能给这个表生成统计信息并且保存在PG_STATISTIC系统表中。
-
starelid：对应表的OID
-
staattnum：对应列的编号
-
stanullfrac：NULL值的比例
-
stawidth：该列的平均宽度
-
stadistinct：该列去重之后的数据的个数或比例
- =0，代表未知或者未计算的情况
- >0，代表消除重复值之后的个数
- <0，其绝对值是去重之后的个数占总个数的比例
-
stakind：统计信息的形式
#define STATISTIC_KIND_MCV 1 #define STATISTIC_KIND_HISTOGRAM 2 #define STATISTIC_KIND_CORRELATION 3 #define STATISTIC_KIND_MCELEM 4 #define STATISTIC_KIND_DECHIST 5 #define STATISTIC_KIND_RANGE_LENGTH_HISTOGRAM 6 #define STATISTIC_KIND_BOUNDS_HISTOGRAM 7 -
staop：统计过程中涉及的操作符
-
stanumbers：存在统计信息的高频值数组或者存放相关系数
-
stavalues：统计值的数组
PG_STATISTIC_EXT系统表
PG_STATISTIC_EXT系统表保存的是多列的统计信息，用户需要显式地使用CREATE STATISTICS语句对一个表创建多列统计信息。
| 属性 | 类型 | 说明 |
|---|---|---|
| stxrelid | Oid | 统计信息属于哪个表 |
| stxname | NameData | 统计信息的名字 |
| stxnamespace | Oid | 统计信息的namespace |
| stxowner | Oid | 统计信息的创建者 |
| stxkeys | int2vector | 统计哪些列 |
| stxkind | char | 多列统计的类型，目前支持两种类型：STATS_EXT_NDISTINCT('d')、STATS_EXT_DEPENDENCIES('f') |
| stxndistinct | pg_ndistinct | STATS_EXT_NDISTINCT类型的统计信息 |
| stxdependencies | pg_dependencies | STATS_EXT_DEPENDENCIES类型的统计信息 |
单列统计信息生成
统计信息的生成主要在analyze_rel函数->do_analyze_rel函数中。统计信息的生成过程主要分成两部分：数据采样和数据统计。
采样
两阶段采样算法：第一个阶段使用S算法对表中的页面进行随机采样，第二个阶段使用Z算法（Vitter）算法在第一阶段采样出来的页面的基础上对元组进行采样。
实现代码在acquire_sample_rows函数中。
统计方法
通过两阶段采样获得样本之后，就要对这些样本进行统计，对表的列属性分别进行统计，如果表上有索引，还会对索引进行单独的统计。
目前PostgreSQL的统计方法有7种，但是PG_STATISTIC表中的槽只有5个。PostgreSQL根据列属性的类型以及该类型可以使用的方法来决定采用的统计方法。选择统计方法的代码在std_typanalyze函数中实现。
多列统计信息生成
如果用户创建了多列统计信息项，那么在对一个表做单列统计信息时，也会尝试同时调用BuildRelationExtStatistics函数创建多列统计信息。
统计信息模块会根据用户指定的统计类型来生成统计信息，如果用户没有指定具体的统计类型，则统计模块会默认对STATS_EXT_NDISTINCT类型和STATS_EXT_DEPENDENCIES类型都进行统计。
STATS_EXT_NDISTINCT
与单列统计信息中的stadistinct类似，记录的是基于多列的去重之后的数据量。
STATS_EXT_DEPENDENCIES
函数依赖：两个属性之间满足函数依赖的值占总体数量的比例，也可以扩展到多个属性。
选择率
选择率的估算需要借助于统计信息（包括直方图、高频值、NULL值率等）。
例如，执行SQL语句SELECT * FROM STUDENT WHERE sname='ww' AND (ssex IS NOT NULL OR sno>5)，其中sname='ww' AND (ssex IS NOT NULL OR sno>5)是由3个约束条件拼接起来的一个完整的约束条件，对于这个约束会分别计算sname='ww'、(ssex IS NOT NULL)和(sno>5)三个子约束条件的选择率，然后根据其中的AND运算符和OR运算符再计算总的选择率。
其中sname='ww'的选择率的计算过程如下：
- 获得sname列对应的stanullfrac=0.142857。
- 获得高频值数组[0.285714,0.285714]，计算高频值的总比例=0.285714+0.285714=0.571428。
- 因为
sname='ww'既不是高频值，也不是NULL值，所有的元组的总比例是1，因此可以先去除NULL值和高频值，计算其余的元组所占的比例=1-0.142857-0.571428=0.285714。 - 计算除了NULL值和高频值，剩下还有几个值：其中元组数量=7，stadistinct=-0.571429，可以获得去除NULL值并去重之后，还剩7×0.571429=4个元组，这4个元组中还有两个高频值，从4个元组中去除两个高频值，也就是说还有两个值。
- 假设两个值平均分配选择率，可以获得
sname='ww'的选择率是0.285714/2=0.142857。
其中(ssex IS NOT NULL)的选择率的计算过程如下：
- 获得ssex列对应的stanullfrac=0.142857，这些对应的是NULL值的选择率。
- 非NULL值的选择率为1-stanullfrac=1-0.142857=0.857142。
其中(sno>5)的选择率计算过程如下：
- 根据sno属性的直方图[1,2,3,4,5,6,7]计算sno<=5的选择率，因为直方图是左闭右开区间，即[1,2)，[2,3)...因此sno<5共占了4个桶，共有6个桶，所以选择率是0.66666666，虽然sno=5则位于[5,6)这个桶内，但由于5是边界值，所以这部分选择率没有被计算入内。
- 根据sno<=5的选择率计算sno>5的选择率=1-0.66666666=0.33333333。
在计算了每个子约束条件独立的选择率之后，就可以根据AND运算符和OR运算符计算它们的综合的选择率。AND和OR运算符的选择率计算是基于概率的，已知基于独立事件的概率的加法和乘法的公式为：
P(A+B) = P(A) + P(B) - P(AB)
P(AB) = P(A) × P(B)
可以首先获得约束条件(ssex IS NOT NULL OR sno>5)的选择率为：
P(ssex IS NOT NULL OR sno>5)
= P(ssex IS NOT NULL) + P(sno>5) - P(ssex IS NOT NULL AND sno>5)
= P(ssex IS NOT NULL) + P(sno>5) - P(ssex IS NOT NULL) × P(sno>5)
= 0.857142 + 0.333333 - 0.857142 × 0.333333
= 0.90476
然后可以获得sname='ww' AND (ssex IS NOT NULL OR sno>5)的总的选择率为：
P(`sname='ww' AND (ssex IS NOT NULL OR sno>5))
= P(sname='ww') × P(ssex IS NOT NULL OR sno>5)
= 0.142857 × 0.90476
= 0.129252
统计信息并不能覆盖计算选择率计算的所有情况，并不是所有的约束条件都能使用统计信息进行选择率的计算。PostgreSQL设定了大量的选择率的默认值，部分选择率的默认值如下表：
| 变量名 | 值 | 说明 |
|---|---|---|
| DEFAULT_EQ_SEL | 0.005 | 等值约束条件的默认选择率，例如A=b |
| DEFAULT_INEQ_SEL | 0.33333333 | 不等值约束条件的默认选择率，例如A<b |
| DEFAULT_RANGE_INEQ_SEL | 0.005 | 涉及同一个属性的范围约束条件的默认选择率，例如A>b AND A<c |
| DEFAULT_MATCH_SEL | 0.005 | 基于模式匹配的约束条件的默认选择率，例如LIKE |
| DEFAULT_NUM_DISTINCT | 200 | 对一个属性去重之后的值中有多少个元素，通常和DEFAULT_EQ_SEL互为倒数 |
| DEFAULT_UNK_SEL | 0.005 | 对BoolTest或NullText这种约束条件的默认选择率，例如IS TRUE或IS NULL |
| DEFAULT_NOT_UNK_SEL | (1.0 - DEFAULT_UNK_SEL) | 对BoolTest或NullText这种约束条件的默认选择率，例如IS TRUE或IS NULL |
实际计算中，计算过程会比实例中更复杂。选择率的计算函数为clauselist_selectivity。
clauselist_selectivity主要考虑了三种情况：
- 使用函数依赖计算选择率
- 子约束条件的选择率
- 基于范围的约束条件的选择率修正
OpExpr的选择率
OpExpr这种类型的约束条件是比较常用的约束条件，treat_as_join_clause函数对这种约束条件进行了分类，分成了连接条件和过滤条件。
- 如果varRelid有值，有可能是一个参数化路径，这是认为OpExpr是过滤条件
- 如果sjinfo==NULL，可能是生成扫描路径，这时认为OpExpr是过滤条件
- 其它情况：如果OpExpr中只引用了一个表，按照过滤条件的方法来获得选择率，如果OpEXpr中引用了多个表，则按照连接条件来获取选择率。
如果是过滤条件就调用restriction_selectivity函数来获得OpExpr表达式的选择率，如果是连接条件则调用join_selectivity函数来获得选择率。
在PostgreSQL中，操作符保存在PG_OPERATOR系统表中，PG_OPERATOR系统表有两个属性：
- oprrest：这个属性指定一个函数，把OpExpr当作过滤条件，求取它的选择率。
- oprjoin：这个属性指定一个函数，把OpExpr当作连接条件，求取它的选择率。
代价
知道了约束条件的选择率，也就是知道了通过扫描路径要扫描出来的结果所占的比例或者通过连接操作所获得的元组所占的比例，通过这个比例就可以推算出中间结果和最终结果的数量，进而使用这些数量来计算代价。
代价基准单位
在实际应用中，数据库用户的硬件环境千差万别，如CPU频率、内存的大小和磁盘的IO速率等因素都会影响执行计划的实际执行效率，因此在代价估算的过程中，我们无法获得绝对真实的代价。
在代价估算的过程中，我们只是想从多个路径中找到一个代价最小的路径，只要这些路径的代价是可以相互比较的就可以了。因此，可以设定一个相对的代价作为单位1，同一个查询中所有的物理路径都基于这个相对的单位来计算代价，这样计算出来的代价就是可以比较的，也就能用来对路径进行挑选了。
基于页面的IO基准代价
PostgreSQL采用顺序读写一个页面的IO代价作为单位1，用DEFAULT_SEQ_PAGE_COST来表示。
#define DEFAULT_SEQ_PAGE_COST 1.0
#define DEFAULT_RANDOM_PAGE_COST 4.0
顺序IO和随机IO是相对应的，基准代价相差4倍。造成这种差距主要的原因：
- 机械硬盘的寻道时间
- 磁盘本身的缓存
可以通过GUC参数自己配置这些值：
double seq_page_cost = DEFAULT_SEQ_PAGE_COST;
double random_page_cost = DEFAULT_RANDOM_PAGE_COST;
由于不同的数据文件可以存储在不同的磁盘介质上，PostgreSQL允许用户在创建表空间的时候指定顺序IO和随机IO的基准代价。
基于元组的CPU基准代价
读取页面并不是查询的最终目标，查询的最终目标是将元组以要求的形式展示出来，因此就产生了从页面读取元组以及对元组处理的代价，这部分代价不同于读取页面的IO代价，这是页面已经在主存中了，从主存中的页面获取元组不会产生磁盘IO，它的代价主要产生在CPU的计算上。
PostgreSQL定义了DEFAULT_CPU_TUPLE_COST来表示处理元组的代价，使用DEFAULT_CPU_INDEX_TUPLE_COST来表示处理一条索引元组的代价。
#define DEFAULT_CPU_TUPLE_COST 0.01
#define DEFAULT_CPU_INDEX_TUPLE_COST 0.005
可以通过GUC参数调整这两个基准代价：
double cpu_tuple_cost = DEFAULT_CPU_TUPLE_COST;
double cpu_index_tuple_cost = DEFAULT_CPU_INDEX_TUPLE_COST;
基于表达式的CPU基准代价
在执行计划的过程中，不止处理元组需要消耗CPU资源，在投影、约束条件中包含大量的表达式，对这些表达式求值同样需要消耗CPU资源，因此PostgreSQL把表达式的求值代价独立出来。使用DEFAULT_CPU_OPERATOR_COST来作为计算表达式的基准代价。
#define DEFAULT_CPU_OPERATOR_COST 0.0025
double cpu_operator_cost = DEFAULT_CPU_OPERATOR_COST;
并行查询产生的基准代价
Gather进程和Worker进程在并行查询的过程中需要通信，因此需要考虑进程间通信所需的初始化代价，以及Worker进程向Gather进程投递元组的代价。
#define DEFAULT_PARALLEL_TUPLE_COST 0.1
#define DEFAULT_PARALLEL_SETUP_COST 1000.0
double parallel_tuple_cost = DEFAULT_PARALLEL_TUPLE_COST;
double parallel_setup_cost = DEFAULT_PARALLEL_SETUP_COST;
缓存对代价的影响
数据库本身有缓存系统，磁盘也有缓存，当读取一个缓存的数据页面时是不会产生磁盘IO的，因此如果对每个页面都计算磁盘IO的代价，代价的计算结果就会失真，所以我们还需要对缓存中的页面数量有一个估计，目前PostgreSQL用effective_cache_size参数来表示。
#define DEFAULT_EFFECTIVE_CACHE_SIZE 524288 /* measured in pages */
int effective_cache_size = DEFAULT_EFFECTIVE_CACHE_SIZE;
启动代价和整体代价
PostgreSQL将代价分成了两个部分：启动代价(Startup Cost)和执行代价(Run cost)，两者的总和是整体代价(Total Cost)。
Total Cost = Startup Cost + Run Cost
在Path结构体中用startup_cost和total_cost两个变量来表示启动代价和整体代价，startup_cost是值从语句开始执行到查询引擎返回第一条元组的代价（准备好获取第一条元组的代价），total_cost是SQL语句从开始执行到结束的所有代价。
表达式代价的计算
表达式的代价基准是cpu_operator_cost，不同的表达式需要辅以基准单位进行计算，表达式代价主要包括以下方面：
- 对投影列的表达式进行计算产生的代价
- 对约束条件中的表达式进行计算产生的代价
- 对函数参数中的表达式进行计算产生的代价
- 对聚集函数中的表达式进行计算产生的代价
- 子计划等执行计算产生的代价
表达式代价的计算是通过cost_qual_eval函数（针对表达式列表）或cost_qual_eval_node函数（针对单个表达式）来计算的。cost_qual_eval函数和cost_qual_eval_node函数都调用了递归函数cost_qual_eval_walker。cost_qual_eval_node函数递归处理表达式并且将表达式的估算代价逐层累加到QualCost数据结构中。
