openGauss 内核分析（五）：统计信息与行数估计

SQL 引擎执行查询主要经历了词法语法解析、查询重写、查询规划和计划执行等步骤。其中，在查询规划过程中，为了生成可执行的最优计划，首先要生成路径，而由于路径存在多样性，因此需要对路径进行淘汰选择。目前优化器进行路径的选择主要是基于估算的代价，因此这种优化器也被称为基于代价的优化器（Cost Based Optimization， CBO）。相对于逻辑优化，这种优化方法是物理优化：根据数据的分布（统计信息）情况来对查询执行路径进行评估，从可选的路径中选择一个执行代价最小的路径进行执行，例如是否选择索引 SeqScan vs. IndexScan，选择哪个索引，两表关联选择什么样的连接顺序，选择怎样的具体算法等。

在代价估算时，需要使用基表或连接表的行数，而在很多时候，优化器无法获得准确的行数值，因此需要对行数进行估算（Cardinality Estimation），然后再计算代价。

统计信息

统计信息是物理优化的依据，来源于表信息的统计。其中描述基表数据的特征包括唯一值、MCV（Most Common Value）值等，用于行数估算。

Table-Level 表级别统计信息，存储在系统表 pg_class。

relptuples 总元组数：描述表对应的元组数。

relpages 总页面数：描述表对应的磁盘页数。

Column-Level 列级别统计信息，存储在系统表 pg_statistics，也可以使用视图 pg_stats 查看数据。

Starelid：表的 oid。

Staattnum：表属性编号。

stadistinct：用于描述字段里唯一的非 NULL 数据值的数目，一般用于估算集合分组之后的大小，Join 结果集大小。

stanullfrac：用于描述当前列中 NULL 值在总数中的占比。

属性组{stakind1, stanumbers1, stavalues1}构成 PG_STATISTIC 表的一个卡槽，在 PG_STATISTIC 表中有 5 个卡槽。一般情况下，第一个卡槽存储 MCV（Most Common Value）信息：描述出现频率大于一定百分比的值的集合，按照出现的频率进行排序，通常用于表征哪些值上出现了倾斜。第二个卡槽存储 Histogram 直方图信息,描述除了 NULL 值、MCV 值以外的值的分布情况，一般用于估算选择率。

以 MCV 卡槽为例属性“stakind1”标识卡槽类型为 MCV，其中“1”为“STATISTIC_KIND_MCV”的枚举值；属性 stanumbers1 与属性 stavalues1 记录 MCV 的具体内容，其中 stavalues1 记录 key 值，stanumbers1 记录 key 对应的频次。

系统表 pg_statistics 的定义在文件 pg_statistic.h 中。

#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

统计信息通过 analyze 命令获得。

表 tt 的 oid 为 40960，有 10000 行数据占用 345 个 pages 页。第 1 列 unique1 的分布情况可以从直方图信息获取，直方图有 100 个区间，并且没有空值和 MCV。第 16 列 string4 的分布情况可以通过 MCV 信息获取，这一列有 4 个 distinct 值”AAAAxx” ,”HHHHxx” , “OOOOxx” , “VVVVxx” ，4 个值的分布频次都有 0.25。

行数估计

行数估算是代价估算的基础，来源于基表统计信息的推算，估算基表 baserel、Join 中间结果集 joinrel、Aggregation 中结果集大小，为代价估算做准备。

SQL 查询常常带有 where 约束（过滤条件），比如 SELECT * FROM tt WHERE string4 = 'AAAAxx'。知道了约束条件的选择率，也就是知道了通过扫描路径要扫描出来的结果所占的比例或者通过连接操作所获得的元组所占的比例，通过这个比例就可以推算出中间结果和最终结果的数量，进而使用这些数量来计算代价。

这里重点分析基表的简单查询——基于 OpExpr 类型的选择率计算，处理函数在 clause_selectivity。如果是过滤条件就调用 restriction_selectivity 函数来获得 OpExpr 表达式的选择率，如果是连接条件则调用 join_selectivity 函数来获得选择率。

SELECT * FROM tt WHERE string4 = 'AAAAxx'为过滤条件，调用 restriction_selectivity 进行选择率估算。

restriction_selectivity 函数识别出 string4 = 'AAAAxx'是形如 Var = Const 的等值约束，操作符的约束选择性计算函数存储在系统表 PG_OPERATOR，opno = 93 对应的选择率计算函数为 eqsel，通过 eqsel 函数调用 var_eq_const 函数进行选择率估算。在该过程中，var_eq_const 函数会读取 PG_STATISTIC 表中 string4 列分布信息，并利用 MCV 信息直接返回选择率为 0.25。

函数 set_baserel_size_estimates 计算估计行数。

函数调用关系：standard_planner-> subquery_planner-> grouping_planner-> query_planner-> make_one_rel-> set_base_rel_sizes-> set_rel_size-> set_plain_rel_size-> set_baserel_size_estimates-> clauselist_selectivity-> clause_selectivity-> restriction_selectivity-> OidFunctionCall4Coll-> eqsel->var_eq_const