openGauss数据库源码解析系列文章——SQL引擎源码解析（二）

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

查询重写主要是基于关系代数式的等价变换，关系代数的变换通常满足交换律、结合律、分配率、串接率等，如表2所示。

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

Typedef struct SubLink {
    Expr xpr;
    SubLinkType subLinkType;
    Node* testexpr;
    List* operName;
    Node* subselect;
    Int location;
} 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;
}

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;
}

//为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);

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

//生成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);

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;
}

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

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;

动态规划的实现代码主入口是从make_rel_from_joinlist函数开始的，它的输入参数是deconstruct_jointree函数拉平之后的RangeTableRef链表，每个RangeTableRef代表一个表，然后就可以根据这个链表来查找基表的RelOptInfo结构体，用查找到的RelOptInfo去构建动态规划连接算法一层中的基表RelOptInfo，后续再继续在这第1层RelOotInfo进行“累积”。代码如下：

//遍历拉平之后的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);

创建一个“连接的数组”，类似于[LIST1, LIST2, LIST3]的结构，其中数组中的链表就用来保存动态规划方法中一层所有的RelOptInfo，例如数组中的第一个链表存放的就是有关所有基表路径的链表。代码如下：

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

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所示。如果要生成第N层的RelOptInfo主要有三种方式：一是尝试生成左深树和右深树，二是尝试生成浓密树，三是尝试生成笛卡儿积的连接路径（俗称遍历尝试）。

具体代码如下：

//对当前层的上一层进行遍历，也就是说如果要生成第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]));
  }
}

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);
        }
      }
    }
  }
}

初步检查就是利用RelOptInfo的信息进行一种“可能性”的判断，主要是检测是否有连接条件和连接顺序的约束。

static bool has_join_restriction(PlannerInfo* root, RelOptInfo* rel)
{
    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;
}

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;
}

对于合法连接，主要代码在join_is_legal中，它主要就是判断两个RelOptInfo可不可以进行连接生成物理路径，入参就是两个RelOpInfo。对于两个待选的RelptInfo，仍不清楚他们之间的逻辑连接关系，有可能是Inner Join、LeftJoin、SemiJoin，或者压根不存在合法的逻辑连接关系，故这时候就需要确定他们的连接关系，主要分成两个步骤。

为了方便MergeJoin的建立，首先需要对约束条件进行处理，故把适用于MergeJoin的约束条件从中筛选出来（select_mergejoin_clauses函数），这样在sort_inner_and_outer和match_unsorted_outer函数中都可以利用这个Mergejoinable连接条件。代码如下：

//提取可以进行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);
}

//对外表和内表中的每一条路径进行连接尝试遍历
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++;
}

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;
}

得益于在多表连接中的效率优势，在openGauss数据库中，遗传算法是动态规划方法的有益补充。只有在Enable_geqo参数打开，并且待连接的RelOptInfo的数量超过Geqo_threshold（默认12个）的情况下，才会使用遗传算法。

openGauss数据库的遗传算法正是模拟了解决货郎问题的方法，将RelOptInfo作为基因、最终生成的连接树作为染色体、连接树的总代价作为适应度，适应度函数则是基于路径的代价进行筛选，但是openGauss数据库的连接路径的搜索和货郎问题的路径搜索略有不同，货郎问题不存在路径不通的问题，两个城市之间是相通的，可以计算任何两个城市之间的距离，而数据库中由于连接条件的限制，可能两个表无法正常连接，或者整个连接树都无法生成。另外，需要注意的是，openGauss数据库的基因算法实现方式和通常的遗传算法略有不同，在于其没有变异的过程，只通过交叉产生新的染色体。

遗传算法作为相对独立的优化器模块，拥有自己的一套文件目录结构，见表12。

/* 染色体Chromosome结构体 */
typedef struct Chromosome {
    /* string实际是一个整型数组，它代表基因的一种排序方式，也就对应一棵连接树 */
    /* 例如{1,2,3,4}对应的就是t1 JOIN t2 JOIN t3 JOIN t4 */
    /* 例如{2,3,1,4}对应的就是t2 JOIN t3 JOIN t1 JOIN t4 */
  Gene*    string; 
  Cost worth;      /* 染色体的适应度，实际上就是路径代价 */
} Chromosome;


/*  种群Pool结构体 */
typedef struct Pool {
  Chromosome *data;  /* 染色体数组，数组中每个元组都是一个连接树 */
  int size;  /* 染色体的数量，即data中连接树的数量，由gimme_pool_size生成 */
  int string_length;  /* 每个染色体中的基因数量，和基表的数量相同 */
} Pool;

然后就可以开始生成染色体，染色体的生成采用的是Fisher-Yates洗牌算法，最终生成Pool.size条染色体。具体的算法实现如下：

/* 初始化基因序列至{1,2,3,4} */
for (i = 0; i < num_gene; i++)
        tmp[i] = (Gene)(i + 1);


    remainder = num_gene - 1;  /* 定义剩余基因数 */


/* 洗牌方法实现，多次随机挑选出基因，作为基因编码的一部分 */
    for (i = 0; i < num_gene; i++) {
        /* choose value between 0 and remainder inclusive */
        next = geqo_randint(root, remainder, 0);
        /* output that element of the tmp array */
        tour[i] = tmp[next];  /* 基因编码 */
        /* and delete it */
        tmp[next] = tmp[remainder];   /* 将剩余基因序列更新 */
        remainder--;
    }

/* 循环遍历所有的表，尽量将能连接的表连接起来 */
For (rel_count = 0; rel_count < num_gene; rel_count++) {
  int cur_rel_index;
  RelOptInfo* cur_rel = NULL;
  Clump* *cur_clump = NULL;


  /* tour 代表一条染色体，这里是获取染色体里的一个基因，也就是一个基表 */
  cur_rel_index = (int) tour[rel_count];
  cur_rel = (RelOptInfo *) list_nth(private->initial_rels, cur_rel_index - 1);


  /* 给这个基表生成一个Clump，size=1代表了当前Clump中只有一个基表*/
  cur_clump = (Clump*)palloc(sizeof(Clump));
  cur_clump->joinrel = cur_rel;
  cur_clump->size = 1;


  /* 开始尝试连接，递归操作，并负责记录Clump到clumps链表 */
  clumps = merge_clump(root, clumps, cur_clump, false);
}

/* 如果能够生成连接，则通过递归尝试生成节点数更多的连接 */
if (joinrel != NULL) {
…………
/* 生成新的连接节点，连接的节点数增加 */
    old_clump->size += new_clump->size;
    pfree_ext(new_clump);
  
    /* 把参与了连接的节点从clumps连表里删除 */
    clumps = list_delete_cell(clumps, lc, prev);
    /* 以clumps和新生成的连接节点（old_clump）为参数，继续尝试生成连接 */
return merge_clump(root, clumps, old_clump, force);
}

/* clumps中有多个节点，证明连接树没有生成成功 */
if (list_length(clumps) > 1) {
    ……
   foreach(lc, clumps) {
      Clump* clump = (Clump*)lfirst(lc);
        /* 设置force参数为true，尝试无条件连接 */
      fclumps = merge_clump(root, fclumps, clump, true);
   }
   clumps = fclumps;

在种群生成之后，就可以进行代际遗传优化，从种群中随机选择两个染色做交叉操作，这样就能产生一个新的染色体。

各个区间的理论概率值如图10所示。

从图6-15可以看出各个区间的理论概率值的数值是依次下降的，也就是说在选择父母染色体的时候是更倾向于选择适应度更低（代价更低）的染色体。

 /* num_positions决定了父染色体遗传多少基因给子染色体 */
  num_positions = geqo_randint(root, 2 * num_gene / 3, num_gene / 3);


  /* 选择随机位置*/
  for (i = 0; i < num_positions; i++)
{
        /* 随机生成位置，将父染色体这个位置的基因遗传给子染色体 */
    pos = geqo_randint(root, num_gene - 1, 0);


    offspring[pos] = tour1[pos];
         /* 标记这个基因已经使用，母染色体不能再遗传相同的基因给子染色体 */
    city_table[(int) tour1[pos]].used = 1;
}

当得到了新生成的子染色体后，需要通过geqo_eval函数来计算适应度，随后使用spread_chromo函数将染色体加入到种群中。

/* 适应度分析*/
kid->worth = geqo_eval(root, kid->string, pool->string_length);


/* 基于适应度将染色体扩散*/
spread_chromo(root, kid, pool);

/* 二分法遍历种群Pool中的染色体 */
top = 0;
mid = pool->size / 2;
bot = pool->size - 1;
index = -1;


/* 染色体筛选 */
while (index == -1) {
    /* 下面4种情况需要进行移动*/
    if (chromo->worth <= pool->data[top].worth) {
        index = top;
    } else if (chromo->worth - pool->data[mid].worth == 0) {
        index = mid;
    } else if (chromo->worth - pool->data[bot].worth == 0) {
        index = bot;
    } else if (bot - top <= 1) {
        index = bot;
    } else if (chromo->worth < pool->data[mid].worth) {
    /*
     * 下面这两种情况单独处理，因为他们的新位置还没有被找到
     */
        bot = mid;
        mid = top + ((bot - top) / 2);
    } else { /* (chromo->worth > pool->data[mid].worth) */
        top = mid;
        mid = top + ((bot - top) / 2);
    }
}

四、 小结