openGauss 选择率与数据分布

SQL查询常常带有where约束（过滤条件），比如：Select * from student where gender = ‘male’； Select * from student where grade > ‘1’。那么，约束对于查询结果的实际影响是什么呢？为度量约束的效能，首先引入选择率的概念。

选择率：给定查询数据集C（C可为数据表或任何中间结果集合）和约束表达式x，x相对C的选择率定义为

其中，表示C的总记录数，表示C上满足x约束的记录数。如表6-13所示，在x为“grade = 1”时，3/5。

表6-13 数据集C选择率结果

记C的数据分布为π。从定义可知，其实是对π按照语义x的一种描述。从这里可看到数据分布的关键用处：数据分布可以辅助选择率的计算、而使得计算过程不必遍历原数据。在代价估算部分中，将看到选择率对计划代价估算的巨大作用。

根据该思路，介绍openGauss计算选择率的基本过程。注意，由于简单约束下的选择率计算具有代表性，本部分将主要围绕着该进行问题进行讲解。简单约束的定义为：仅涉及基表单个属性的非范围约束。

涉及非简单约束选择率的计算方法，读者可以参照本章自行阅读源码。

1） 简单约束的选择率计算

假设x为简单约束，且x所涉及的属性分布信息已存在于PG_STATISTIC表元组r中（参见数据分布的存储部分内容）。openGauss通过调用clause_selectivity函数将元组r按x要求转换为选择率。

clause_selectivity的第二个参数clause为约束语句x。面对不同SQL查询，输入clause_selectivity的clause可能有多种类型，典型类型如表6-14所示。

表6-14 简单约束类型

{Var, Const, Param, OpExpr}属于基础约束类型，而包含{AND, OR, NOT}的约束都是建立约束基础上的集合运算，称为SET约束类型。进一步观察可以发现，约束{Var, Const, Param}可以看作OpExpr约束的一个特例。比如：“SELECT * FROM PRODUCT WHERE ISSOLD”与“SELECT * FROM PRODUCT WHERE ISSOLD = TRUE”等价。限于篇幅，这里将着重介绍基于OpExpr类型的选择率计算，并简要给出SET类型计算的关键逻辑。

（1） OpExpr类型选择率。

以查询语句SELECT * FROM PRODUCT WHERE PRIZE = ‘100’为例。clause_selectivity函数首先根据clause（PRIZE = ‘100’）类型找到OpExpr分支。然后调用treat_as_join_clause函数判断clause是否是一个join约束；结果为假，说明clause是过滤条件（OP），则调用restriction_selectivity函数对clause参数进行选择率估算。代码如下：

Selectivity

clause_selectivity(PlannerInfo *root,

Node *clause,

int varRelid,

JoinType jointype,

SpecialJoinInfo *sjinfo)

{

Selectivity s1 = 0.5;/* default for any unhandled clause type */

RestrictInfo *rinfo = NULL;

if (clause == NULL) /* can this still happen? */

return s1;

if (IsA(clause, Var))...

else if (IsA(clause, Const))...

else if (IsA(clause, Param))

// not子句处理分支

else if (not_clause(clause))

{

/* inverse of the selectivity of the underlying clause */

s1 = 1.0 - clause_selectivity(root,

(Node *) get_notclausearg((Expr *) clause),

varRelid,

jointype,

sjinfo);

}

// and子句处理分支

else if (and_clause(clause))

{

/* share code with clauselist_selectivity() */

s1 = clauselist_selectivity(root,

((BoolExpr *) clause)->args,

varRelid,

jointype,

sjinfo);

}

// or子句处理分支

else if (or_clause(clause))

{

ListCell *arg;

s1 = 0.0;

foreach(arg, ((BoolExpr *) clause)->args)

{

Selectivity s2 = clause_selectivity(root,

(Node *) lfirst(arg),

varRelid,

jointype,

sjinfo);

s1 = s1 + s2 - s1 * s2;

}

}

// join或op子句处理分支

else if (is_opclause(clause) || IsA(clause, DistinctExpr))

{

OpExpr *opclause = (OpExpr *) clause;

Oidopno = opclause->opno;

// join子句处理

if (treat_as_join_clause(clause, rinfo, varRelid, sjinfo))

{

/* Estimate selectivity for a join clause. */

s1 = join_selectivity(root, opno,

opclause->args,

opclause->inputcollid,

jointype,

sjinfo);

}

// op子句处理

else

{

/* Estimate selectivity for a restriction clause. */

s1 = restriction_selectivity(root, opno,

opclause->args,

opclause->inputcollid,

varRelid);

}

}

... ...

return s1;

}

restriction_selectivity函数识别出PRIZE = ‘100’是形如Var = Const的等值约束，它将通过eqsel函数间接调用var_eq_const函数进行选择率估算。在该过程中，var_eq_const函数会读取PG_STATISTIC表中PRIZE列分布信息，并尝试利用信息中MCV计算选择率。首选调用get_attstatsslot函数判断‘100’是否存在于MCV中，有以下几种情况。

• 情况1：存在，直接从MCV中返回‘100’的占比作为选择率。
• 情况2：不存在，则计算高频值的总比例sumcommon，并返回(1.0 – sumcommon – nullfrac) / otherdistinct作为选择率。其中，nullfrac是NULL的比例，otherdistinct是低频值的NDV。

加入查询的约束是PRIZE < ‘100’，restriction_selectivity函数，该约束将根据操作符类型调用scalargtsel函数并尝试利用PG_STATISTIC表中信息计算选择率。由于满足< ‘100’的值可能分别存在于MCV和直方图中，所以需要分别在两种结构中收集满足条件的值。相比于MCV来说，在直方图中收集满足条件值的过程较为复杂，因此下面重点介绍：借助于直方图key的有序性，openGauss采用二分查找快速搜寻满足条件的值，并对其总占比进行求和并记作selec_histogram。注意，等高直方图不会单独记录‘100’的频次，而是将‘100’和相邻值合并放入桶(记作B桶)中，并仅记录B中数值的总频次(F_b)。为解决该问题，openGauss假设桶中元素频次相等，并采用公式估算B中满足条件值的占比。该过程的具体代码实现在ineq_histogram_selectivity函数中。最终，restriction_selectivity函数返回的选择率值为selec =selec_mcv + selec_histogram，其中，selec_mcv是MCV中满足条件的占比。

（2） SET类型选择率。

对于SET类型约束，clause_selectivity函数递归计算其包含的基本约束选择率。然后根据SET类型的语义，通过表6-15所列方式返回最终选择率。

表6-15 SET类型选择率说明

回顾数据分布的存储部分的内容，openGauss并没有保存多属性联合分布。而从表6-15可以看出，openGauss是在不同列取值相互独立的假设下对联合分布进行推算的。在列不独立的场景下，这种预测常常存在偏差。例如：对于学生表来说，性别和专业存在相关性。因此，不能通过男同学占比×计算机系人数去推测该系的人数。但在一般情况下，使用独立的假设往往也能获得较准确的结果。

（3） 选择率默认参数。

在数据分布未知的情况下，不能通过常规方法对选择率进行估算。例如：未对数据表进行analyze操作，或者过滤条件本身就是一个不确定的参数。为给优化器一个合理的参考值，openGauss给出了一系列选择率的经验参数，如表6-16所示。

表6-16 选择率参数说明