上一篇文章介绍了SQL引擎源解析中“6.1 概述”及“6.2 SQL解析”的精彩内容，本篇我们开启“6.3 查询优化”及“6.4 小结”的相关内容的介绍。

6.3 查询优化

openGauss数据库的查询优化过程功能比较明晰，从源代码组织的角度来看，相关代码分布在不同的目录下，如表6-6所示。

表6-6 查询优化模块说明

6.3.1 查询重写

SQL语言是丰富多样的，非常的灵活，不同的开发人员依据经验的不同，手写的SQL语句也是各式各样，另外还可以通过工具自动生成。SQL语言是一种描述性语言，数据库的使用者只是描述了想要的结果，而不关心数据的具体获取方式，输入数据库的SQL语言很难做到是以最优形式表示的，往往隐含了一些冗余信息，这些信息可以被挖掘用来生成更加高效的SQL语句。查询重写就是把用户输入的SQL语句转换为更高效的等价SQL，查询重写遵循两个基本原则。
（1） 等价性：原语句和重写后的语句，输出结果相同。
（2） 高效性：重写后的语句，比原语句在执行时间和资源使用上更高效。
查询重写主要是基于关系代数式的等价变换，关系代数的变换通常满足交换律、结合律、分配率、串接率等，如表6-7所示。

表6-7 关系代数等价变换

查询重写优化既可以基于关系代数的理论进行优化，例如谓词下推、子查询优化等，也可以基于启发式规则进行优化，例如Outer Join消除、表连接消除等。另外还有一些基于特定的优化规则和实际执行过程相关的优化，例如在并行扫描的基础上，可以考虑对Aggregation算子分阶段进行，通过将Aggregation划分成不同的阶段，可以提升执行的效率。
从另一个角度来看，查询重写是基于优化规则的等价变换，属于逻辑优化，也可以称为基于规则的优化，那么怎么衡量对一个SQL语句进行查询重写之后，它的性能一定是提升的呢？这时基于代价对查询重写进行评估就非常重要了，因此查询重写不只是基于经验的查询重写，还可以是基于代价的查询重写。
以谓词传递闭包和谓词下推为例，谓词的下推能够极大的降低上层算子的计算量，从而达到优化的效果，如果谓词条件有存在等值操作，那么还可以借助等值操作的特性来实现等价推理，从而获得新的选择条件。
例如，假设有两个表t1、t2分别包含[1,2,3,…100]共100行数据，那么查询语句SELECT t1.c1, t2.c1 FROM t1 JOIN t2 ON t1.c1=t2.c1 WHERE t1.c1=1则可以通过选择下推和等价推理进行优化，如图6-6所示。

图6-6 查询重写前后对比图

如图6-6-（1）所示，t1、t2表都需要全表扫描100行数据，然后再做join，生成100行数据的中间结果，最后再做选择操作，最终结果只有1行数据。如果利用等价推理，可以得到{t1.c1, t2.c1, 1}的是互相等价的，从而推导出新的t2.c1=1的选择条件，并把这个条件下推到t2上，从而得到图6-6-（4）重写之后的逻辑计划。可以看到，重写之后的逻辑计划，只需要从基表上面获取1条数据即可，join时内、外表的数据也只有1条，同时省去了在最终结果上的过滤条件，性能大幅提升。
在代码层面，查询重写的架构大致如图6-7所示。

图6-7 查询重写的架构

（1） 提升子查询：子查询出现在RangeTableEntry中，它存储的是一个子查询树，若子查询不被提升，则经过查询优化之后形成一个子执行计划，上层执行计划和子查询计划做嵌套循环得到最终结果。在该过程中，查询优化模块对这个子查询所能做的优化选择较少。若该子查询被提升，转换成与上层的join，由查询优化模块常数替换等式：由于常数引用速度更快，故将可以求值的变量求出来，并用求得的常数替换它，实现函数为preprocess_const_params。
（2） 子查询替换CTE：理论上CTE（common table expression，通用表达式）与子查询性能相同，但对子查询可以进行进一步的提升重写优化，故尝试用子查询替换CTE，实现函数为substitute_ctes_with_subqueries。
（3） multi count(distinct)替换为多条子查询：如果出现该类查询，则将多个count(distinct)查询分别替换为多条子查询，其中每条子查询中包含一个count(distinct)表达式，实现函数为convert_multi_count_distinct。
（4） 提升子链接：子链接出现在WHERE/ON等约束条件中，通常伴随着ANY/ALL/IN/EXISTS/SOME等谓词同时出现。虽然子链接从语句的逻辑层次上是清晰的，但是效率有高有低，比如相关子链接，其执行结果和父查询相关，即父查询的每一条元组都对应着子链接的重新求值，此情况下可通过提升子链接提高效率。在该部分数据库主要针对ANY和EXISTS两种类型的子链接尝试进行提升，提升为Semi Join或者Anti-SemiJoin，实现函数为pull_up_sublinks。
（5） 减少ORDER BY：由于在父查询中可能需要对数据库的记录进行重新排序，故减少子查询中的ORDER BY语句以进行链接可提高效率，实现函数为reduce_orderby。
（6） 删除NotNullTest：即删除相关的非NULL Test以提高效率，实现函数为removeNotNullTest。
（7） Lazy Agg重写：顾名思义，即“懒聚集”，目的在于减少聚集次数，实现函数为lazyagg_main。
（8） 对连接操作的优化做了很多工作，可能获得更好的执行计划，实现函数为pull_up_subqueries。
（9） UNION ALL优化：对顶层的UNION ALL进行处理，目的是将UNION ALL这种集合操作的形式转换为AppendRelInfo的形式，实现函数为flatten_simple_union_all。
（10） 展开继承表：如果在查询语句执行的过程中使用了继承表，那么继承表是以父表的形式存在的，需要将父表展开成为多个继承表，实现函数为expand_inherited_tables。，实现函数为expand_inherited_tables。
（11）预处理表达式：该模块是对查询树中的表达式进行规范整理的过程，包括对链接产生的别名Var进行替换、对常量表达式求值、对约束条件进行拉平、为子链接生成执行计划等，实现函数为preprocess_expression。
（12） 处理HAVING子句：在Having子句中，有些约束条件是可以转变为过滤条件的（对应WHERE），这里对Having子句中的约束条件进行拆分，以提高效率。
（13） 外连接消除：目的在于将外连接转换为内连接，以简化查询优化过程，实现函数为reduce_outer_join函数。
（14） 全连接full join重写：对全连接函数进行重写，以完善其功能。比如对于语句SELECT * FROM t1 FULL JOIN t2 ON TRUE可以将其转换为： SELECT * FROM t1 LEFT JOIN t2 ON TRUE UNION ALL (SELECT * FROM t1 RIGHT ANTI FULL JOIN t2 ON TRUE)，实现函数为reduce_inequality_fulljoins。
下面以子链接提升为例，介绍openGauss中一种最重要的子查询优化。所谓子链接（SubLink）是子查询的一种特殊情况，由于子链接出现在WHERE/ON等约束条件中，因此经常伴随ANY/EXISTS/ALL/IN/SOME等谓词出现，openGauss数据库为不同的谓词设置了不同的SUBLINK类型。代码如下：

Typedef enum SubLinkType {
    EXISTS_SUBLINK,
    ALL_SUBLINK,
    ANY_SUBLINK,
    ROWCOMPARE_SUBLINK,
    EXPR_SUBLINK,
    ARRAY_SUBLINK,
    CTE_SUBLINK
} SubLinkType;

openGauss数据库为子链接定义了单独的结构体——SubLink结构体，其中主要描述了子链接的类型、子链接的操作符等信息。代码如下：

Typedef struct SubLink {
    Expr xpr;
    SubLinkType subLinkType;
    Node* testexpr;
    List* operName;
    Node* subselect;
    Int location;
} SubLink;

子链接提升相关接口函数如图6-8所示。

图6-8 子链接相关接口函数

子链接提升的主要过程是在pull_up_sublinks函数中实现，pull_up_sublinks函数又调用pull_up_sublinks_jointree_recurse递归处理Query->jointree中的节点，函数输入参数如表6-8所示。

表6-8 函数输入参数说明

jnode分为三种类型：RangeTblRef、FromExpr、JoinExpr。针对这三种类型pull_up_sublinks_jointree_recurse函数分别进行了处理。

1）RangeTblRef

RangeTblRef是Query->jointree的叶子节点，所以是该函数递归结束的条件，程序走到该分支，一般有两种情况。
（1） 当前语句是单表查询而且不存在连接操作，这种情况递归处理直到结束后，再去查看子链接是否满足其他提升条件。
（2） 查询语句存在连接关系，在对From->fromlist、JoinExpr->larg或者JoinExpr->rarg递归处理的过程中，当遍历到了RangeTblRef叶子节点时，需要把RangeTblRef节点的relids（表的集合）返回给上一层。主要用于判断该子链接是否能提升。

2） FromExpr

（1） 递归遍历From->fromlist中的节点，之后对每个节点递归调用pull_up_sublinks_jointree_recurse函数，直到处理到叶子节点RangeTblRef才结束。
（2） 调用pull_up_sublinks_qual_recurse函数处理From->qual，对其中可能出现的ANY_SUBLINK或EXISTS_SUBLINK进行处理。
3） JoinExpr

（1） 调用pull_up_sublinks_jointree_recurse函数递归处理JoinExpr->larg和JoinExpr->rarg，直到处理到叶子节点RangeTblRef才结束。另外还需要根据连接操作的类型区分子链接是否能够被提升。
（2） 调用pull_up_sublinks_qual_recurse函数处理JoinExpr->quals，对其中可能出现的ANY_SUBLINK或EXISTS_SUBLINK做处理。如果连接类型不同，pull_up_sublinks_qual_recurse函数的available_rels1参数的输入值是不同的。
pull_up_sublinks_qual_recurse函数除了对ANY_SUBLINK和EXISTS_SUBLINK做处理，还对OR子句和EXPR类型子链接做了查询重写优化。其中Expr类型的子链接提升代码逻辑如下。
（1） 通过safe_convert_EXPR函数判断sublink是否可以提升。代码如下：

    //判断当前SQL语句是否满足sublink提升条件
    if (subQuery->cteList ||
        subQuery->hasWindowFuncs ||
        subQuery->hasModifyingCTE ||
        subQuery->havingQual ||
        subQuery->groupingSets ||
        subQuery->groupClause ||
        subQuery->limitOffset ||
        subQuery->rowMarks ||
        subQuery->distinctClause ||
        subQuery->windowClause) {
        ereport(DEBUG2,
            (errmodule(MOD_OPT_REWRITE),
                (errmsg("[Expr sublink pull up failure reason]: Subquery includes cte, windowFun, havingQual, group, "
                        "limitoffset, distinct or rowMark."))));
        return false;
}

（2） 通过push_down_qual函数提取子链接中相关条件。代码如下：

Static Node* push_down_qual(PlannerInfo* root, Node* all_quals, List* pullUpEqualExpr)
{
    If (all_quals== NULL) {
        Return NULL;
    }

    List* pullUpExprList = (List*)copyObject(pullUpEqualExpr);
    Node* all_quals_list = (Node*)copyObject(all_quals);

    set_varno_attno(root->parse, (Node*)pullUpExprList, true);
    set_varno_attno(root->parse, (Node*)all_quals_list, false);

    Relids varnos = pull_varnos((Node*)pullUpExprList, 1);
    push_qual_context qual_list;
    SubLink* any_sublink = NULL;
    Node* push_quals = NULL;
    Int attnum = 0;

    While ((attnum = bms_first_member(varnos)) >= 0) {
        RangeTblEntry* r_table = (RangeTblEntry*)rt_fetch(attnum, root->parse->rtable);

        //这张表必须是基表，否则不能处理
        If (r_table->rtekind == RTE_RELATION) {
        qual_list.varno = attnum;
        qual_list.qual_list = NIL;

        //获得包含特殊varno的条件
                get_varnode_qual(all_quals_list, &qual_list);

If (qual_list.qual_list != NIL && !contain_volatile_functions((Node*)qual_list.qual_list)) {
            any_sublink = build_any_sublink(root, qual_list.qual_list, attnum,pullUpExprList);
            push_quals = make_and_qual(push_quals, (Node*)any_sublink);
        }

        list_free_ext(qual_list.qual_list);
        }
   }

    list_free_deep(pullUpExprList);
    pfree_ext(all_quals_list);

    return push_quals;
}

（3） 通过transform_equal_expr函数构造需要提升的SubQuery（增加GROUP BY子句，删除相关条件）。代码如下：

    //为SubQuery增加GROUP BY和windowClasues
    if (isLimit) {
       append_target_and_windowClause(root,subQuery,(Node*)copyObject(node), false);
    } else {
        append_target_and_group(root, subQuery, (Node*)copyObject(node));
}
//删除相关条件
subQuery->jointree = (FromExpr*)replace_node_clause((Node*)subQuery->jointree,
         (Node*)pullUpEqualExpr,
         (Node*)constList,
         RNC_RECURSE_AGGREF | RNC_COPY_NON_LEAF_NODES);

（4） 构造需要提升的条件。代码如下：

//构造需要提升的条件
joinQual = make_and_qual((Node*)joinQual, (Node*)pullUpExpr);
…
Return joinQual;

（5） 生成join表达式。代码如下：

//生成join表达式
if (IsA(*currJoinLink, JoinExpr)) {
        ((JoinExpr*)*currJoinLink)->quals = replace_node_clause(((JoinExpr*)*currJoinLink)->quals, 
                                tmpExprQual, 
                                makeBoolConst(true, false),
                                RNC_RECURSE_AGGREF | RNC_COPY_NON_LEAF_NODES);
        
    } else if (IsA(*currJoinLink, FromExpr)) {
        ((FromExpr*)*currJoinLink)->quals = replace_node_clause(((FromExpr*)*currJoinLink)->quals, 
                                tmpExprQual, 
                                makeBoolConst(true, false),
                                RNC_RECURSE_AGGREF | RNC_COPY_NON_LEAF_NODES);
    }

    rtr = (RangeTblRef *) makeNode(RangeTblRef);
    rtr->rtindex = list_length(root->parse->rtable);
    
    // 构造左连接的JoinExpr
    JoinExpr *result = NULL;
    result = (JoinExpr *) makeNode(JoinExpr);
    result->jointype = JOIN_LEFT;
    result->quals = joinQual;
    result->larg = *currJoinLink;
    result->rarg = (Node *) rtr;

// 在rangetableentry中添加JoinExpr。在后续处理中，左外连接可转换为内连接
rte = addRangeTableEntryForJoin(NULL,
                                    NIL,
                                    result->jointype,
                                    NIL,
                                    result->alias,
                                    true);
    root->parse->rtable = lappend(root->parse->rtable, rte);

6.3.2 统计信息和代价估算

在不同数据分布下，相同查询计划的执行效率可能显著不同。因此，在选择计划时还应充分考虑数据分布对计划的影响。与通用逻辑优化不同，物理优化将计划的优化建立在数据之上，并通过最小化数据操作代价来提升性能。从功能上来看，openGauss的物理优化主要有以下3个关键步骤。
（1） 数据分布生成——从数据表中挖掘数据分布并存储。
（2） 计划代价评估——基于数据分布，建立代价模型评估计划的实际执行时间。
（3） 最优计划选择——基于代价估计，从候选计划中搜寻代价最小的计划。
首选，介绍数据分布的相关概念及其数据库内部的存储方式。

1. 数据分布的存储

表6-9 Grade属性分布

表6-10 Grade频次分布

D可以涉及多个属性，将多个属性的分布称为联合分布。联合分布的取值空间可能十分庞大，从性能的角度考虑，数据库不会保存D DD的联合分布，而是将D DD中的属性分布分开保存，比如，数据库保存{ Gender=’男’}、{ Grade=’1’}的频次，而并不保存{ Gender=’男’, Grade=’1’}的频次。这种做法损失了D DD上分布的很多信息。在随后的选择率与数据分布小节的内容将看到，在系统需要的时候，openGauss将采取预测技术对联合分布进行推测。虽然在某些情况下，这种推测的结果可能与实际出入较大。
数据分布的数据结构对于理解数据库如何存储该信息尤为关键。一般来说，KV（key-value）键值对是描述分布最常用的结构，其中key表示取值，value表示频次。但在NDV很大的情况下，key值的膨胀使得KV的存储与读取性能都不高。为提高效率，openGauss实际采用“KV向量+直方图”的混合方式表示属性分布。
数据分布的逻辑结构：高频值频次采用KV存储，存储结构被称为最常见值；除高频值以外的频次采用等高直方图（equal-bin-count histogram，EH）描述。实现中，openGauss会将频次最高的k ( k = 100 ) k( k=100 )k(k=100)个key值放入MCV，其余放入直方图表示。
值得注意的是，等高直方图会将多个值的频次合并存放，在显著提升存取效率的同时，也会使得分布模糊化。但在后续章节可以看到，相对于低频值，高频值对计划代价的估算更为关键。因此，采取这种以损失低频值准确性为代价，换取高性能的混合策略，无疑是一种相当划算的做法。
数据分布的存放位置：在openGauss中，MCV、直方图等信息实际是放在系统表PG_STATISTIC中的，表定义如表6-11所示。

表6-11 系统表PG\_STATISTIC定义

表6-11中的一条元组存储了一条属性的统计信息。下分别对元组的属性意义进行解读。
（1） 属性starelid/staattnum表示的表OID和属性编号。
（2） 属性stanullfrac表示属性中为NULL的比例（为0表示该列没有NULL值）。
（3） 属性组{ stakind1, stanumbers1, stavalues1}构成PG_STATISTIC表的一个卡槽，存放表6-12中的一种数据结构类型的信息。在PG_STATISTIC表中有5个卡槽。一般情况下，第一个卡槽存储MCV信息，第二个卡槽存储直方图信息。以MCV卡槽为例：属性“stakind1”标识卡槽类型为MCV，其中“1”为“STATISTIC_KIND_MCV”的枚举值；属性stanumbers1与属性stavalues1记录MCV的具体内容，其中stavalues1记录key值，stanumbers1记录key对应的频次。上例中取值“1”的频次比例为0.2851，“2”的频次比例为0.1345。

表6-12 系统表PG\_STATISTIC说明

注意，数据分布和PG_STATISTIC表中的内容不是在创建表的时候自动生成的，其生成的触发条件是用户对表进行了analyze操作。

2. 数据分布抽取方法

数据分布的存储给出了数据分布在openGauss的逻辑结构和存储方式。那么上面介绍的数据分布信息是如何从数据中获得呢？针对该问题，下面将简要介绍openGauss抽取分布的主要过程。为加深对方法的理解，先分析该问题面临的挑战。
获取分布最直接的办法是遍历所有数据，并通过计数直接生成MCV和直方图信息。但现实中的数据可能是海量的，遍历的I/O代价往往不可接受。比如，银行的账单数据涉及上千亿条记录，需要TB级的存储。除I/O代价外，计数过程的内存消耗也可能超过上限，这也使得算法实现变得尤为困难。因此，更现实的做法是降低数据分析的规模，采用小样本分析估算整体数据分布。那么，样本选择的好坏就显得尤为重要。
目前，openGauss数据库的样本生成过程在acquire_sample_rows函数实现，它采用了两阶段采样的算法对数据分布进行估算。第一阶段使用S算法对物理页进行随机采样，生成样本S1；第二阶段使用Z（Vitter）算法对S1包含的元组进行蓄水池采样，最终生成一个包含3000元组的样本S2。两阶段算法可以保证S2是原数据的一个无偏样本。因此，可以通过分析S2推断原数据分布，并将分布信息记录在PG_STATISTIC表的对应元组中。
openGauss将样本的生成划分成两个步骤，主要是为了提高采样效率。该方法的理论依据依赖于以下现实条件：数据所占据的物理页数量M可以准确获得，而每个物理页包含的元组数n未知。由于M已知，S算法可以用1/M的概率对页进行均匀抽样，可以生成原数据的小样本S1。一般认为，某元组属于任一物理页是等概率事件，这就保证了S1是一个无偏样本；而由于S1包含的元组远少于原数据，在S1的基础上进行二次抽样代价将大大减少。第二阶段没有继续使用S算法的主要原因是：S1的元组总数N未知（因为n未知），该算法无法获得采样概率——1/N。而Z（Vitter）的算法是一种蓄水池抽样算法，这类算法可以在数据总量未知条件下保证采样的均匀。蓄水池抽样算法原理不是本书的重点，读者可以自行查阅资料。

3. 选择率与数据分布

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

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

其中，表示∣ C ∣ |C|∣C∣的总记录数，表示∣ C x ∣上满足x约束的记录数。如表6-13所示，在x xx为“grade = 1”时，s e l e c ( x ∣ C )=3/5。

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

记C CC的数据分布为π ππ。从定义可知，s e l e c ( x ∣ C ) selec(x|C)selec(x∣C)其实是对π ππ按照语义x xx的一种描述。从这里可看到数据分布的关键用处：数据分布可以辅助选择率的计算、而使得计算过程不必遍历原数据。在代价估算部分中，将看到选择率对计划代价估算的巨大作用。
根据该思路，介绍openGauss计算选择率的基本过程。注意，由于简单约束下的选择率计算具有代表性，本部分将主要围绕着该进行问题进行讲解。简单约束的定义为：仅涉及基表单个属性的非范围约束。
涉及非简单约束选择率的计算方法，读者可以参照本章自行阅读源码。

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

假设x xx为简单约束，且x xx所涉及的属性分布信息已存在于PG_STATISTIC表元组r rr中（参见数据分布的存储部分内容）。openGauss通过调用clause_selectivity函数将元组r rr按x xx要求转换为选择率。
clause_selectivity的第二个参数clause为约束语句x xx。面对不同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中数值的总频次(Fb)。为解决该问题，openGauss假设桶中元素频次相等，并采用公式（B 中 小 于 100 值 的 个 数 B 所 有 取 值 个 数/B所有取值个数） ∗ F b 估算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 选择率参数说明

4. 代价估算

查询执行的代价分为I/O代价和CPU代价。这两种代价都与查询过程中所处理的元组数量正相关。因此，通过选择率对查询计划的总代价进行评估是较为准确的。但由于硬件环境的差别，openGauss的代价模型输出的“代价”只是一种度量计划好坏的通用指标，而不是指执行时间。为描述度量的过程，下面将从代价模型参数的介绍为切入点，逐一展开I/O和CPU的代价评估方法。
（1） I/O代价评估

在磁盘上，元组是按数据页的方式进行组织的。页的存取方式主要有：顺序读和随机读。受制于存储介质的性能，顺序读的效率明显高于随机读。比如：机械硬盘面临大量随机访问时，磁头寻道的时间占据了数据读取的大部分时间。在openGauss中，不同存取方式I/O代价如下所示：

DEFAULT_SEQ_PAGE_COST  1.0
DEFAULT_RANDOM_PAGE_COST  4.0

默认参数将数据页“顺序读”和“随机读”的开销设置为了1:4。
设置对于机械磁盘来说是比较合理的。但对于寻址能力出众的SSD盘来说，该参数就需要根据具体情况进行调整了。此外，现实中的数据库部署十分复杂，一个系统中可能同时存在多种不同的存储介质。为使得代价模型能同时应对不同存储介质的I/O性能，openGauss给用户提供了设定文件I/O单位代价的方法。

CREATE TABLESPACE TEST_SPC LOCATION '...' WITH (SEQ_PAGE_COST=2, RANDOM_PAGE_COST=3);

根据I/O代价参数和选择率，可以很容易对候选计划的I/O开销进行评估。下面将以顺序扫描（SeqScan）和索引扫描（IndexScan）为例，讲解代价评估的具体过程。
① SeqScan：对表的数据进行从头至尾的遍历，属于顺序读。因此，SeqScan的IO代价为：表数据页总数×DEFAULT_SEQ_PAGE_COST。
② IndexScan：通过索引查找满足约束的表数据，属于随机读。因此，IndexScan的I/O代价为：P * DEFAULT_RANDOM_PAGE_COST。
其中，P（满足数据页数量）与R（满足约束的元组数量）正相关，且R = 表元组总量×选择率；openGauss计算出R后，将调用index_pages_fetched(R, …)函数估算P。该函数在costsize.c文件中实现，具体细节请参考Mackert L F和Lohman G M的论文Index scans using a finite LRU buffer: A validated I/O model。
通过观察代价模型可以发现当选择率超过一定阈值时，P会相对较大，而使得IndexScan的代价超过SeqScan。因此说明，IndexScan的效率并不总高于SeqScan。

（2） CPU代价评估

数据库在数据寻址和数据加工阶段都需要消耗CPU资源，比如：元组投影选择、索引查找等。显然，针对不同的操作，CPU花费的代价都是不相同的。openGauss将CPU代价细分为：元组处理代价和数据操作代价。
① 元组处理代价：将一条磁盘数据转换成元组形式的代价；针对普通表数据和索引数据，代价参数分别如下：

#define DEFAULT_CPU_TUPLE_COST 0.01
#define DEFAULT_CPU_INDEX_TUPLE_COST 0.005

默认参数中，索引代价更低。这是因为索引数据所涉及的列一般少于表数据，所需的CPU资源相对较小。
② 数据操作代价：对元组进行投影，或根据约束表达式判断元组是否满足条件的代价。代价参数如下：

#define DEFAULT_CPU_OPERATOR_COST  0.0025

给定以上参数，CPU的代价估算与问题的计算规模成正比，而问题的计算规模取决于选择率。这种关系类似于算法例复杂度与n的关系。限于篇幅，本节不做具体介绍。

6.3.3 物理路径

在数据库中，路径使用path结构体来表示，path结构体“派生”自Node结构体，path结构体同时也是一个“基”结构体，类似于C++中的基类，每个具体路径都从path结构体中“派生”，例如索引扫描路径使用的IndexPath结构体就是从path结构体中“派生”的。

typedef struct Path
{
     NodeTag    type;
     NodeTag    pathtype;          /* 路径的类型，可以是T_IndexPath、T_NestPath等 */
     RelOptInfo *parent;        /* 当前路径执行后产生的中间结果 */
     PathTarget *pathtarget;        /* 路径的投影，也会保存表达式代价*/
                                 /* 需要注意表达式索引的情况*/
     ParamPathInfo *param_info;        /* 执行期使用参数，在执行器中，子查询或者一些特殊*/
                                 /* 类型的连接需要实时的获得另一个表的当前值 */
     Bool    parallel_aware;     /* 并行参数，区分并行还是非并行 */
     bool    parallel_safe;        /* 并行参数，由set_rel_consider_parallel函数决定 */
     int    parallel_workers;        /* 并行参数，并行线程的数量 */
     double    rows;        /* 当前路径执行产生的中间结果估计有多少数据 */
     Cost    startup_cost;      /* 启动代价，从语句执行到获得第一条结果的代价 */
     Cost    total_cost;          /* 当前路径的整体执行代价 */
     List   *pathkeys;       /* 当前路径产生的中间结果的排序键值，如果无序则为NULL */
} Path;

6.3.4 动态规划

目前openGauss已经完成了基于规则的查询重写优化和逻辑分解优化，并且已经生成各个基表的物理路径。基表的物理路径仅仅是优化器规划中很小的一部分，现在openGauss将进入优化器优化的另一个重要的工作，即生成Join连接路径。openGauss采用的是自底向上的优化方式，对于多表连接路径主要采用的是动态规划和遗传算法两种方式。这里主要介绍动态规划的方式，但如果表数量有很多，就需要用遗传算法。遗传算法可以避免在表数量过多情况下带来的连接路径搜索空间膨胀的问题。对于一般场景采用动态规划的方式即可，这也是openGauss默认采用的优化方式。
经过逻辑分解优化后，语句中的表已经被拉平，即从原来的树状结构变成了扁平的数组结构。各个表之间的连接关系也被记录到了root目录下的SpecialJoinInfo结构体中，这些也是对连接做动态规划的基础。

1. 动态规划方法

图6-9 重复子问题的最优解

//遍历拉平之后的joinlist，这个链表是RangeTableRef的链表
foreach(jl, joinlist)
{
Node   *jlnode = (Node *) lfirst(jl);
RelOptInfo *thisrel;
    
    //多数情况下都是RangeTableRef链表，根据RangeTableRef链表中存放的下标值（rtindex）
    //查找对应的RelOptInfo
if (IsA(jlnode, RangeTblRef))
{
int varno = ((RangeTblRef *) jlnode)->rtindex;
thisrel = find_base_rel(root, varno);
}
    //受到from_collapse_limit参数和join_collapse_limit参数的影响，也存在没有拉平的节点，这里递归调用make_rel_from_joinlist函数
else if (IsA(jlnode, List))
thisrel = make_rel_from_joinlist(root, (List *) jlnode);
else
ereport (……);

    //这里就生成了第一个初始链表，也就是基表的链表，这个链表是
    //动态规划方法的基础
initial_rels = lappend(initial_rels, thisrel);
}

2） standard_join_search函数

//分配“累积”过程中所有层的RelOptInfo链表
root->join_rel_level = (List**)palloc0((levels_needed + 1) * sizeof(List*));
//初始化第1层所有基表RelOptInfo
root->join_rel_level[1] = initial_rels;

做好了初始化工作之后，就可以开始尝试构建每一层的RelOptInfo。代码如下：

for (lev = 2; lev <= levels_needed; lev++) {
    ListCell* lc = NULL;
//在join_search_one_level函数中生成对应的lev层的所有RelOptInfo
    join_search_one_level(root, lev);

……
}

join_search_one_level函数主要用于生成一层中的所有RelOptInfo，如图6-11所示。如果要生成第N层的RelOptInfo主要有三种方式：一是尝试生成左深树和右深树，二是尝试生成浓密树，三是尝试生成笛卡儿积的连接路径（俗称遍历尝试）。

图6-11 生成第N层的RelOptInfo方式

（1） 左深树和右深树

左深树和右深树生成的原理是一样的，只是在make_join_rel函数中对候选出的待连接的两个RelOptInfo进行位置互换，也就是每个RelOptInfo都有一次作为内表或作为外表的机会，这样其实创造出更多种连接的可能有助于生成最优路径。
如图6-12所示两个待选的RelOptInfo要进行连接生成A×B×C，左深树也就是对A×B和C进行了一下位置互换，A×B作为内表形成了左深树，A×B作为外表形成了右深树。

具体代码如下：

//对当前层的上一层进行遍历，也就是说如果要生成第4层的RelOptInfo
//就要取第3层的RelOptInfo和第1层的基表尝试做连接
foreach(r, joinrels[level - 1])
{
    RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
     //如果两个RelOptInfo之间有连接关系或者连接顺序的限制
     //优先给这两个RelOptInfo生成连接
     // has_join_restriction函数可能误判，不过后续还会有更精细的筛查
  if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
    has_join_restriction(root, old_rel))
  {
    ListCell   *other_rels;
         //要生成第N层的RelOptInfo，就需要第N-1层的RelOptInfo和1层的基表集合进行连接
         //即如果要生成第2层的RelOptInfo，那么就变成第1层的RelOptInfo和第1层的基表集合进行连接
         //因此，需要在生成第2层基表集合的时候做一下处理，防止自己和自己连接的情况
    if (level == 2)
      other_rels = lnext(r);
    else
      other_rels = list_head(joinrels[1]);
          //old_rel“可能”和其他表有连接约束条件或者连接顺序限制
         //other_rels中就是那些“可能”的表，make_rels_clause_joins函数会进行精确的判断
    make_rels_by_clause_joins(root,  old_rel,  other_rels);
  }
  else
  {
          //对没有连接关系的表或连接顺序限制的表也需要尝试生成连接路径
    make_rels_by_clauseless_joins(root,  old_rel,  list_head(joinrels[1]));
  }
}

（2） 浓密树

要生成第N层的RelOptInfo，左深树或者右深树是将N-1层的RelOptInfo和第1层的基表进行连接，不论是左深树，还是右深树本质上都是通过引用基表RelOptInfo去构筑当前层RelOptInfo。而生成浓密树抛开了基表，它是将各个层次的RelOptInfo尝试进行随意连接，例如将第N-2层RelOptInfo和第2层的RelOptInfo进行连接，依次可以类推出（2，N﹣2）、(3，N﹣3)、(4, N﹣4)等多种情况。浓密树的建立要满足两个条件：一是两个RelOptInfo要存在相关的约束条件或者存在连接顺序的限制，二是两个RelOptInfo中不能存在有交集的表。

for (k = 2;; k++)
{
  int other_level = level - k;
  foreach(r, joinrels[k])
  {
    //有连接条件或者连接顺序的限制
    if (old_rel->joininfo == NIL && !old_rel->has_eclass_joins &&
      !has_join_restriction(root, old_rel))
      continue;
    ……
    for_each_cell(r2, other_rels)
    {
      RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
             //不能有交集
    if (!bms_overlap(old_rel->relids, new_rel->relids))
    {
        //有相关的连接条件或者有连接顺序的限制
        if (have_relevant_joinclause(root, old_rel, new_rel) ||
        have_join_order_restriction(root, old_rel, new_rel))
    {
     (void) make_join_rel(root, old_rel, new_rel);
        }
      }
    }
  }
}

（3） 笛卡儿积

在尝试过左深树、右深树以及浓密树之后，如果还没有生成合法连接，那么就需要努力对第N﹣1层和第1层的RelOptInfo做最后的尝试，其实也就是将第N﹣1层中每一个RelOptInfo和第1层的RelOptInfo合法连接的尝试。

2. 路径生成

{
    ListCell* l = NULL;

//如果当前RelOptInfo涉及Lateral语义，那么就一定有连接顺序约束
    foreach(l, root->lateral_info_list)
    {
        LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(l);

        if (bms_is_member(ljinfo->lateral_rhs, rel->relids) ||
            bms_overlap(ljinfo->lateral_lhs, rel->relids))
            return true;
    }

//仅处理除内连接之外的条件
    foreach (l, root->join_info_list) {
        SpecialJoinInfo* sjinfo = (SpecialJoinInfo*)lfirst(l);

        //跳过全连接检查，会有其他机制保证其连接顺序
        if (sjinfo->jointype == JOIN_FULL)
            continue;

         //如果这个SpecialJoinInfo已经被RelOptInfo包含就跳过
        if (bms_is_subset(sjinfo->min_lefthand, rel->relids) && 
bms_is_subset(sjinfo->min_righthand, rel->relids))
            continue;

        //如果RelOptInfo结构体的relids变量和min_lefthand变量或min_righthand变量有交集，那么它就有可能有连接顺序的限制
        if (bms_overlap(sjinfo->min_lefthand, rel->relids) || 
bms_overlap(sjinfo->min_righthand, rel->relids))
            return true;
    }

    return false;
}

（1） 精确检查
在进行了初步检查之后，如果判断出两侧RelOptInfo不存在有连接条件或者连接顺序的限制，那么就进入make_rels_by_clauseless_joins函数中，将RelOptInfo中所有可能的路径和第1层RelOptInfo进行连接。如果当前RelOptInfo可能有连接条件或者连接顺序的限制，那么就会进入make_rel_by_clause_joins函数中，会逐步将当前的RelOptInfo和第1层其他RelOptInfo进一步检查以确定是否可以进行连接。
在have_join_order_restriction函数判断两个RelOptInfo是否具有连接顺序的限制，主要从两个方面判断是否具有连接顺序的限制：一是判断两个RelOptInfo之间是否具有Lateral语义的顺序的限制，二是判断SpecialJoinInfo中的min_lefthand和min_righthand是否对两个RelOptInfo具有连接顺序的限制。
对have_join_order_restriction部分源码分析如下：

bool have_join_order_restriction(PlannerInfo* root, RelOptInfo* rel1, RelOptInfo* rel2)
{
    bool result = false;
    ListCell* l = NULL;

//如果有Lateral语义的依赖关系，则一定具有连接顺序的限制
    foreach(l, root->lateral_info_list)
    {
        LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(l);

        if (bms_is_member(ljinfo->lateral_rhs, rel2->relids) &&
            bms_overlap(ljinfo->lateral_lhs, rel1->relids))
            return true;
        if (bms_is_member(ljinfo->lateral_rhs, rel1->relids) &&
            bms_overlap(ljinfo->lateral_lhs, rel2->relids))
            return true;
    }

//遍历root目录中所有SpecialJoinInfo，判断两个RelOptInfo是否具有连接限制
    foreach (l, root->join_info_list) {
        SpecialJoinInfo* sjinfo = (SpecialJoinInfo*)lfirst(l);

        if (sjinfo->jointype == JOIN_FULL)
            continue;

        //"最小集"分别是两个表的子集，两个表需要符合连接顺序
        if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) && 
bms_is_subset(sjinfo->min_righthand, rel2->relids)) {
            result = true;
            break;
        }
//反过来同上，"最小集"分别是两个表的子集，两个表需要符合连接顺序
        if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) && 
bms_is_subset(sjinfo->min_righthand, rel1->relids)) {
            result = true;
            break;
        }

//如果两个表都和最小集的一端有交集，那么这两个表应该在这一端下做连接
//故让他们先做连接
        if (bms_overlap(sjinfo->min_righthand, rel1->relids) && bms_overlap(sjinfo->min_righthand, rel2->relids)) {
            result = true;
            break;
        }
//反过来同上
        if (bms_overlap(sjinfo->min_lefthand, rel1->relids) && bms_overlap(sjinfo->min_lefthand, rel2->relids)) {
            result = true;
            break;
        }
    }

//如果两个表上和其他表有相对应的连接关系
//那么可以让他们先和具有连接关系的表进行连接
    if (result) {
        if (has_legal_joinclause(root, rel1) || has_legal_joinclause(root, rel2))
            result = false;
    }

    return result;
}

（2） 合法连接
由于RelOptInfo会导致搜索空间膨胀，如果上来就对两个RelOptInfo进行最终的合法连接检查会导致搜索时间过长，这也就是为什么要提前做初步检查和精确检查的原因，可以减少搜索时间其实达到了“剪枝”的效果。
对于合法连接，主要代码在join_is_legal中，它主要就是判断两个RelOptInfo可不可以进行连接生成物理路径，入参就是两个RelOpInfo。对于两个待选的RelptInfo，仍不清楚他们之间的逻辑连接关系，有可能是Inner Join、LeftJoin、SemiJoin，或者压根不存在合法的逻辑连接关系，故这时候就需要确定他们的连接关系，主要分成两个步骤。
步骤1：对root中join_info_list链表中的SpecialJoinInfo进行遍历，看是否可以找到一个“合法”的SpecialJoinInfo，因为除InnerJoin外的其他逻辑连接关系都会生成对应的一个SpecialJoinInfo，并在SpecialJoinInfo中还记录了合法的链接顺序。
步骤2：对RelOptInfo中的Lateral关系进行排查，查看找到的SpecialJoinInfo是否符合Lateral语义指定的连接顺序要求。

2） 建立连接路径

//提取可以进行Merge Join的条件
foreach (l, restrictlist) {
    RestrictInfo* restrictinfo = (RestrictInfo*)lfirst(l);

//如果当前是外连接并且是一个过滤条件，那么就忽略
    if (isouterjoin && restrictinfo->is_pushed_down)
        continue;

    //对连接条件是否可以做Merge Join进行一个初步的判断
//restrictinfo->can_join和restrictinfo->mergeopfamilies都是在distribute_qual_to_rels生成
    if (!restrictinfo->can_join || restrictinfo->mergeopfamilies == NIL) {
//忽略FULL JOIN ON FALSE情况
        if (!restrictinfo->clause || !IsA(restrictinfo->clause, Const))
            have_nonmergeable_joinclause = true;
        continue; /* not mergejoinable */
    }

//检查约束条件是否是outer op inner或者inner op outer的形式
    if (!clause_sides_match_join(restrictinfo, outerrel, innerrel)) {
        have_nonmergeable_joinclause = true;
        continue; /* no good for these input relations */
    }

//更新并使用最终的等价类
//"规范化"pathkeys，这样约束条件就能和pathkeys进行匹配
    update_mergeclause_eclasses(root, restrictinfo);

    if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) || EC_MUST_BE_REDUNDANT(restrictinfo->right_ec)) {
        have_nonmergeable_joinclause = true;
        continue; /* can't handle redundant eclasses */
    }

    result_list = lappend(result_list, restrictinfo);
}

（1） sort_inner_and_outer函数
sort_inner_and_outer函数主要用于生成MergeJoin路径，它需要显式地对两个字RelOptInfo进行排序，只考虑子RelOptInfo中的cheapest_total_path函数即可。通过MergeJoinable（能够用来生成Merge Join的）的连接条件来生成pathkeys，然后不断地调整pathkeys中pathke的顺序来获得不同的pathkeys集合，再根据不同顺序的pathkeys来决定内表的innerkeys和外表的outerkeys。代码如下：

//对外表和内表中的每一条路径进行连接尝试遍历
foreach (lc1, outerrel->cheapest_total_path) {
    Path* outer_path_orig = (Path*)lfirst(lc1);
    Path* outer_path = NULL;
    j = 0;
    foreach (lc2, innerrel->cheapest_total_path) {
        Path* inner_path = (Path*)lfirst(lc2);
        outer_path = outer_path_orig;

//参数化路径不可生成MergeJoin路径
        if (PATH_PARAM_BY_REL(outer_path, innerrel) ||
            PATH_PARAM_BY_REL(inner_path, outerrel))
            return;

        //必须满足外表和内表最低代价路径
        if (outer_path != linitial(outerrel->cheapest_total_path) &&
            inner_path != linitial(innerrel->cheapest_total_path)) {
            if (!join_used[(i - 1) * num_inner + j - 1]) {
                j++;
                continue;
            }
        }

//生成唯一化路径
        jointype = save_jointype;
        if (jointype == JOIN_UNIQUE_OUTER) {
            outer_path = (Path*)create_unique_path(root, outerrel, outer_path, sjinfo);
            jointype = JOIN_INNER;
        } else if (jointype == JOIN_UNIQUE_INNER) {
            inner_path = (Path*)create_unique_path(root, innerrel, inner_path, sjinfo);
            jointype = JOIN_INNER;
        }
//根据之前提取的条件确定可供MergeJoin路径生成的PathKeys集合
        all_pathkeys = select_outer_pathkeys_for_merge(root, mergeclause_list, joinrel);
//处理上面pathkeys集合中每一个Pathkey尝试生成MergeJoin路径
        foreach (l, all_pathkeys) {
……
            //生成内表的Pathkey
            innerkeys = make_inner_pathkeys_for_merge(root, cur_mergeclauses, outerkeys);

            //生成外表的Pathkey
            merge_pathkeys = build_join_pathkeys(root, joinrel, jointype, outerkeys);

//根据pathkey以及内外表路径生成MergeJoin路径
            try_mergejoin_path(root, ……,innerkeys);
        }
        j++;
    }
    i++;
}

（2） match_unsorted_outer函数
match_unsorted_outer函数大部分整体代码思路和sort_inner_and_outer一致，最主要的一点不同是sort_inner_and_outer是根据条件去推断出内外表的pathkey。而在match_unsorted_outer函数中，是假定外表路径是有序的，它是按照外表的pathkeys反过来排序连接条件的，也就是外表的pathkeys直接就可以作为outerkeys使用，查看连接条件中哪些是和当前的pathkeys匹配的并把匹配的连接条件筛选出来，最后再参照匹配出来的连接条件生成需要显示排序的innerkeys。
（3） hash_inner_and_outer函数
顾名思义，hash_inner_and_outer函数的主要作用就是建立HashJoin的路径，在distribute_restrictinfo_to_rels函数中已经判断过一个约束条件是否适用于Hashjoin。因为Hashjoin要建立哈希表，至少有一个适用于Hashjoin的连接条件存在才能使用HashJoin，否则无法创建哈希表。

至此为止已经生成了物理连接路径Hashjoin、NestLoop、MergeJoin，那么现在就是要根据他们生成过程中计算的代价去判断是否是一条值得保存的路径，因为在连接路径阶段会生成很多种路径，并会生成一些明显比较差的路径，这时候筛选可以帮助做一个基本的检查，能够节省生成计划的时间。因为如果生成计划的时间太长，即便选出了“很好”的执行计划，那么也是不能够接受的。
add_path为路径筛选主要函数。代码如下：

switch (costcmp) {
    case COSTS_EQUAL:
        outercmp = bms_subset_compare(PATH_REQ_OUTER(new_path), 
PATH_REQ_OUTER(old_path));
        if (keyscmp == PATHKEYS_BETTER1) {
            if ((outercmp == BMS_EQUAL || outercmp == BMS_SUBSET1) && 
  new_path->rows <= old_path->rows)
  //新路径代价和老路径相似，PathKeys要长，需要的参数更少
  //结果集行数少，故接受新路径放弃旧路径
                remove_old = true; /* new dominates old */
        } else if (keyscmp == PATHKEYS_BETTER2) {
            if ((outercmp == BMS_EQUAL || outercmp == BMS_SUBSET2) && 
  new_path->rows >= old_path->rows)
  //新路径代价和老路径相似，pathkeys要短，需要的参数更多
  //结果集行数更多，不接受新路径保留旧路径
                accept_new = false; /* old dominates new */
        } else {
            if (outercmp == BMS_EQUAL) {
  //到这里，新旧路径的代价、pathkeys、路径参数均相同或者相似
  //如果新路径返回的行数少，选择接受新路径，放弃旧路径
                if (new_path->rows < old_path->rows)
                    remove_old = true; /* new dominates old */
  //如果新路径返回行数多，选择不接受新路径，保留旧路径
                else if (new_path->rows > old_path->rows)
                    accept_new = false; /* old dominates new */
  //到这里，代价、pathkeys、路径参数、结果集行数均相似
  //那么就严格规定代价判断的范围，如果新路径好，则采用新路径，放弃旧路径
                else {
                    small_fuzzy_factor_is_used = true;
                    if (compare_path_costs_fuzzily(new_path, old_path, SMALL_FUZZY_FACTOR) ==
                        COSTS_BETTER1)
                        remove_old = true; /* new dominates old */
                    else
                        accept_new = false; /* old equals or
                                             * dominates new */
                }
   //如果代价和pathkeys相似，则比较行数和参数，好则采用，否则放弃
            } else if (outercmp == BMS_SUBSET1 && 
new_path->rows <= old_path->rows)
                remove_old = true; /* new dominates old */
            else if (outercmp == BMS_SUBSET2 && 
  new_path->rows >= old_path->rows)
                accept_new = false; /* old dominates new */
             /* else different parameterizations, keep both */
        }
        break;
    case COSTS_BETTER1:
//所有判断因为新路径均好于或者等于旧路径
//则接受新路径，放弃旧路径
        if (keyscmp != PATHKEYS_BETTER2) {
            outercmp = bms_subset_compare(PATH_REQ_OUTER(new_path), 
PATH_REQ_OUTER(old_path));
            if ((outercmp == BMS_EQUAL || outercmp == BMS_SUBSET1) && 
new_path->rows <= old_path->rows)
                remove_old = true; /* new dominates old */
        }
        break;
    case COSTS_BETTER2:
//所有判断因素旧路径均差于或者等于新路径
//则不接受新路径，保留旧路径
        if (keyscmp != PATHKEYS_BETTER1) {
            outercmp = bms_subset_compare(PATH_REQ_OUTER(new_path),
PATH_REQ_OUTER(old_path));
            if ((outercmp == BMS_EQUAL || outercmp == BMS_SUBSET2) && 
new_path->rows >= old_path->rows)
                accept_new = false; /* old dominates new */
        }
        break;
    default:

        /*
         * can't get here, but keep this case to keep compiler
         * quiet
         */
        break;
}

由于篇幅限制，下一篇继续讲解SQL引擎源解析之遗传算法。