上一篇文章介紹了SQL引擎源解析中“6.1 概述”及“6.2 SQL解析”的精彩内容，本篇我們開啟“6.3 查詢優化”及“6.4 小結”的相關内容的介紹。
6.3 查詢優化
openGauss資料庫的查詢優化過程功能比較明晰，從源代碼組織的角度來看，相關代碼分布在不同的目錄下，如表6-6所示。
表6-6 查詢優化子產品說明
| 子產品 | 目錄 | 說明 |
|---|---|---|
| 查詢重寫 | src/gausskernel/optimizer/prep | 主要包括子查詢優化、謂詞化簡及正則化、謂詞傳遞閉包等查詢重寫優化技術 |
| 統計資訊 | src/gausskernel/optimizer/commands/analyze.cpp | 生成各種類型的統計資訊，供選擇率估算、行數估算、代價估算使用 |
| 代價估算 | src/common/backend/utils/adt/selfuncs.cpp src/gausskernel/optimizer/path/costsize.cpp | 進行選擇率估算、行數估算、代價估算 |
| 實體路徑 | src/gausskernel/optimizer/path | 生成實體路徑 |
| 動态規劃 | src/gausskernel/optimizer/plan | 通過動态規劃方法對實體路徑進行搜尋 |
| 遺傳算法 | src/gausskernel/optimizer/geqo | 通過遺傳算法對實體路徑進行搜尋 |
6.3.1 查詢重寫
SQL語言是豐富多樣的，非常的靈活，不同的開發人員依據經驗的不同，手寫的SQL語句也是各式各樣，另外還可以通過工具自動生成。SQL語言是一種描述性語言，資料庫的使用者隻是描述了想要的結果，而不關心資料的具體擷取方式，輸入資料庫的SQL語言很難做到是以最優形式表示的，往往隐含了一些備援資訊，這些資訊可以被挖掘用來生成更加高效的SQL語句。查詢重寫就是把使用者輸入的SQL語句轉換為更高效的等價SQL，查詢重寫遵循兩個基本原則。
（1） 等價性：原語句和重寫後的語句，輸出結果相同。
（2） 高效性：重寫後的語句，比原語句在執行時間和資源使用上更高效。
查詢重寫主要是基于關系代數式的等價變換，關系代數的變換通常滿足交換律、結合律、配置設定率、串接率等，如表6-7所示。
表6-7 關系代數等價變換
| 等價變換 | 内容 |
| 交換律 | A × B == B × A A ⨝B == B ⨝ A A ⨝F B == B ⨝F A ……其中F是連接配接條件 Π p(σF (B)) == σF (Π p(B)) ……其中F∈p |
| 結合律 | (A × B) × C==A × (B × C) (A ⨝ B) ⨝ C==A ⨝ (B ⨝ C) (A ⨝F1 B) ⨝F2 C==A ⨝F1 (B ⨝F2 C) …… F1和F2是連接配接條件 |
| 配置設定律 | σF(A × B) == σF(A) × B …… 其中F ∈ A σF(A × B) == σF1(A) × σF2(B) …… 其中F = F1 ∪ F2，F1∈A, F2 ∈B σF(A × B) == σFX (σF1(A) × σF2(B)) …… 其中F = F1∪F2∪FX，F1∈A, F2 ∈B Π p,q(A × B) == Π p(A) × Π q(B) …… 其中p∈A，q∈B σF(A × B) == σFx (σF1(A) × σF2(B)) …… 其中F = F1∪F2∪Fx，F1∈A, F2 ∈B |
| 串接律 | Π P=p1,p2,…pn(Π Q=q1,q2,…qn(A)) == Π P=p1,p2,…pn(A)……其中P ⊆ Q σF1(σF2(A)) == σF1∧F2(A) |
查詢重寫優化既可以基于關系代數的理論進行優化，例如謂詞下推、子查詢優化等，也可以基于啟發式規則進行優化，例如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 函數輸入參數說明
| 參數名 | 參數類型 | |
| root | PlannerInfo* | 輸入參數，查詢優化子產品的上下文資訊 |
| jnode | Node* | 輸入參數，需要遞歸處理的節點，可能是RangeTblRef、FromExpr或JoinExpr |
| relids | Relids* | 輸出參數，jnode參數中涉及的表的集合 |
| 傳回值 | 經過子連結提升處理之後的node節點 |
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. 資料分布的存儲
資料集合D的分布由D上不同取值的頻次構成。設D為表6-9在Grade列上的投影資料，該列有3個不同取值Grade = 1, 2, 3，其頻次分布見表6-10。這裡，将Grade取值的個數簡稱為NDV（Number of Distinct Values，不同值的數量）。
表6-9 Grade屬性分布
| Sno | Name | Gender | Grade |
| 001 | 小張 | 男 | |
| 002 | 小李 | ||
| 003 | 小王 | ||
| 004 | 小周 | 女 | |
| 005 | 小陳 |
表6-10 Grade頻次分布
| 頻次 |
D可以涉及多個屬性，将多個屬性的分布稱為聯合分布。聯合分布的取值空間可能十分龐大，從性能的角度考慮，資料庫不會儲存 D的聯合分布，而是将 D中的屬性分布分開儲存，比如，資料庫儲存{ Gender=’男’}、{ Grade=’1’}的頻次，而并不儲存{ Gender=’男’, Grade=’1’}的頻次。這種做法損失了 D上分布的很多資訊。在随後的選擇率與資料分布小節的内容将看到，在系統需要的時候，openGauss将采取預測技術對聯合分布進行推測。雖然在某些情況下，這種推測的結果可能與實際出入較大。
資料分布的資料結構對于了解資料庫如何存儲該資訊尤為關鍵。一般來說，KV（key-value）鍵值對是描述分布最常用的結構，其中key表示取值，value表示頻次。但在NDV很大的情況下，key值的膨脹使得KV的存儲與讀取性能都不高。為提高效率，openGauss實際采用“KV向量+直方圖”的混合方式表示屬性分布。
資料分布的邏輯結構：高頻值頻次采用KV存儲，存儲結構被稱為最常見值；除高頻值以外的頻次采用等高直方圖（equal-bin-count histogram，EH）描述。實作中，openGauss會将頻次最高的 k(k=100)個key值放入MCV，其餘放入直方圖表示。
值得注意的是，等高直方圖會将多個值的頻次合并存放，在顯著提升存取效率的同時，也會使得分布模糊化。但在後續章節可以看到，相對于低頻值，高頻值對計劃代價的估算更為關鍵。是以，采取這種以損失低頻值準确性為代價，換取高性能的混合政策，無疑是一種相當劃算的做法。
資料分布的存放位置：在openGauss中，MCV、直方圖等資訊實際是放在系統表PG_STATISTIC中的，表定義如表6-11所示。
表6-11 系統表PG\_STATISTIC定義
| starelid | staattnum | stanullfrac | stakind1 | stanumbers1 | stavalues1 | Stakind2 | …… |
| {0.2851, 0.1345} | {1, 2} | ||||||
| {0.1955, 0.1741} | {數學, 國文} |
表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說明
| 類型 | |
| STATISTIC_KIND_MCV | 高頻值（常見值），在一個列裡出現最頻繁的值，按照出現的頻率進行排序，并且生成一個一一對應的頻率數組，這樣就能知道一個列中有哪些高頻值，這些高頻值的頻率是多少 |
| STATISTIC_KIND_HISTOGRAM | 直方圖，openGauss資料庫用等頻直方圖來描述一個列中資料的分布，高頻值不會出現在直方圖中，這就保證了資料的分布是相對平坦的 |
| STATISTIC_KIND_CORRELATION | 相關系數，相關系數記錄的是目前列未排序的資料分布和排序後的資料分布的相關性，這個值通常在索引掃描時用來估計代價，假設一個列未排序和排序之後的相關性是0，也就是完全不相關，那麼索引掃描的代價就會高一些 |
| STATISTIC_KIND_MCELEM | 類型高頻值（常見值），用于數組類型或者一些其他類型，openGauss資料庫提供了ts_typanalyze系統函數來負責生成這種類型的統計資訊 |
| STATISTIC_KIND_DECHIST | 數組類型直方圖，用于給數組類型生成直方圖，openGauss資料庫提供了array_typanalyze系統函數來負責生成這種類型的統計資訊 |
注意，資料分布和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（ C可為資料表或任何中間結果集合）和限制表達式x，x相對 C的選擇率定義為
其中，表示 ∣ C ∣ 的總記錄數，表示 ∣ C x ∣上滿足x限制的記錄數。如表6-13所示，在 x為“grade = 1”時， selec(x∣C)=3/5。
表6-13 資料集C選擇率結果
記 C 的資料分布為 π。從定義可知， selec(x∣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 | SELECT * FROM PRODUCT WHERE ISSOLD; |
| Const | SELECT * FROM PRODUCT WHERE TRUE; |
| Param | SELECT * FROM PRODUCT WHERE $1; |
| OpExpr | SELECT * FROM PRODUCT WHERE PRIZE = ‘100’; |
| AND | SELECT * FROM PRODUCT WHERE PRIZE = ‘100’ AND TYPE = ‘HAT’; |
| OR | SELECT * FROM PRODUCT WHERE PRIZE = ‘100’ OR TYPE = ‘HAT’; |
| NOT | SELECT * FROM PRODUCT WHERE NOT EXIST TYPE = ‘HAT’; |
| 其他 |
{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中滿足條件值的占比。該過程的具體代碼實作在ineq_histogram_selectivity函數中。最終，restriction_selectivity函數傳回的選擇率值為selec =selec_mcv + selec_histogram，其中，selec_mcv是MCV中滿足條件的占比。
（2） SET類型選擇率。
對于SET類型限制，clause_selectivity函數遞歸計算其包含的基本限制選擇率。然後根據SET類型的語義，通過表6-15所列方式傳回最終選擇率。
表6-15 SET類型選擇率說明
| SET類型 | |
| NOT運算符 | selec(B) = 1 –selec(A) {B = NOT A} |
| AND運算符 | selec(AB) = selec(A)×selec(B) {A AND B} |
| OR運算符 | selec(A+B) = selec(A)+selec(B)-selec(AB) {A OR B} |
回顧資料分布的存儲部分的内容，openGauss并沒有儲存多屬性聯合分布。而從表6-15可以看出，openGauss是在不同列取值互相獨立的假設下對聯合分布進行推算的。在列不獨立的場景下，這種預測常常存在偏差。例如：對于學生表來說，性别和專業存在相關性。是以，不能通過男同學占比×計算機系人數去推測該系的人數。但在一般情況下，使用獨立的假設往往也能獲得較準确的結果。
（3） 選擇率預設參數。
在資料分布未知的情況下，不能通過正常方法對選擇率進行估算。例如：未對資料表進行analyze操作，或者過濾條件本身就是一個不确定的參數。為給優化器一個合理的參考值，openGauss給出了一系列選擇率的經驗參數，如表6-16所示。
表6-16 選擇率參數說明
| 變量名 | 值 | |
| DEFAULT_EQ_SEL | 0.005 | 為等值限制條件的預設選擇率，例如A = b |
| DEFAULT_INEQ_SEL | 0.3333333333333333 | 為不等值限制條件的預設選擇率，例如A < b |
| DEFAULT_RANGE_INEQ_SEL | 為涉及同一個屬性（列）的範圍限制條件的預設選額率，例如A > b AND A < c | |
| DEFAULT_MATCH_SEL | 為基于模式比對的限制條件的預設選擇率，例如LIKE | |
| DEFAULT_NUM_DISTINCT | 200 | 為對一個屬性消重（distinct）之後的值域中有多少個元素，通常和DEFAULT_EQ_SEL互為倒數 |
| DEFAULT_UNK_SEL | 為對BoolTest或NullText這種限制條件的預設選擇率，例如IS TRUE或IS NULL | |
| DEFAULT_NOT_UNK_SEL | (1.0 - DEFAULT_UNK_SEL) | 為對BoolTest或NullText這種限制條件的預設選擇率，例如IS NOT TRUE或IS NOT NULL |
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 重複子問題的最優解
例如，圖6-9中兩個連接配接樹中A×B的連接配接操作就屬于重複子問題，因為無論是生成A×B×C×D還是A×B×C連接配接路徑的時候都需要先生成A×B連接配接路徑，對于多表連接配接生成的路徑即很多層堆積的情況下可能有上百種連接配接的方法，這些連接配接樹的重複子問題數量會比較多，是以連接配接樹具有重複子問題，可以一次求解多次使用，也就是對于連接配接A×B隻需要一次生成最優解即可。
多表連接配接動态規劃算法代碼主要是從make_rel_from_joinlist函數開始的，如圖6-10所示。
圖6-10 多表連接配接動态規劃算法
1） make_rel_from_joinlist函數
動态規劃的實作代碼主入口是從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);
}
2） standard_join_search函數
動态規劃方法在累積表的過程中，每一層都會增加一個表，當所有的表都增加完畢的時候，最後的連接配接樹也就生成了。是以累積的層數也就是表的數量，如果存在N個表，那麼在此就要堆積N次，具體每一層堆積的過程在函數join_search_one_level中進行介紹，那麼這個函數中主要做的還是為累積連接配接進行準備工作，包括配置設定每一層RelOptInfo所占用的記憶體空間以及每累積一層RelOptInfo後保留部分資訊等工作。
建立一個“連接配接的數組”，類似于[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;
做好了初始化工作之後，就可以開始嘗試建構每一層的RelOptInfo。代碼如下：
for (lev = 2; lev <= levels_needed; lev++) {
ListCell* lc = NULL;
//在join_search_one_level函數中生成對應的lev層的所有RelOptInfo
join_search_one_level(root, lev);
……
}
3） join_search_one_level函數
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作為外表形成了右深樹。
圖6-12 左深樹和右深樹示意圖
具體代碼如下：
//對目前層的上一層進行周遊，也就是說如果要生成第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. 路徑生成
前面已經介紹了路徑生成中使用的動态規劃方法，并且介紹了在累積過程中如何生成目前層的RelOptInfo。對于生成目前層的RelOptInfo會面臨幾個問題：一是需要判斷兩個RelOptInfo是否可以進行連接配接，二是生成實體連接配接路徑。目前實體連接配接路徑主要有三種實作，分别是NestLoopJoin、HashJoin和MergeJoin，建立連接配接路徑的過程就是不斷地嘗試生成這三種路徑的過程。
1） 檢查
在動态規劃方法中需要将N-1層的每個RelOptInfo和第1層的每個RelOptInfo嘗試做連接配接，然後将新連接配接的RelOptInfo儲存在目前第N層，算法的時間複雜度在O(M×N)左右，如果發生第N-1層和第1層中RelOptInfo都比較多的情況下，搜尋空間會膨脹得比較大。但有些RelOptInfo在做連接配接的時候是可以避免掉的，這也是我們需要及時檢查的目的，提前檢測出并且跳過兩個RelOptInfo之間的連結，會節省不必要的開銷，提升優化器生成優化的效率。
（1） 初步檢查
下面幾個條件是初步檢查主要進行衡量的因素。
一是RelOptinfo中joininfo不為NULL。那就說明這個RelOptInfo和其他的RelOptInfo存在相關的限制條件，換言之就是說目前這個RelOptInfo可能和其他表存在關聯。
二是RelOptInfo中has_eclass_joins為true，表明在等價類的記錄中目前RelOptInfo和其他RelOptInfo可能存在等值連接配接條件。
三是has_join_restriction函數的傳回值為true，說明目前的RelOptInfo和其他的RelOptInfo有連接配接順序的限制。
初步檢查就是利用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;
}
（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） 建立連接配接路徑
至此已經篩選出兩個滿足條件的RelOptInfo，那麼下一步就是要對他們中的路徑建立實體連接配接關系。通常的實體連接配接路徑有NestLoop、Merge Join和Hash Join三種，這裡主要是借由sort_inner_and_outer、match_unsorted_outer和hash_inner_and_outer函數實作的。
像sort_inner_and_outer函數主要是生成MergeJoin路徑，其特點是假設内表和外表的路徑都是無序的，是以必須要對其進行顯示排序，内外表隻要選擇總代價最低的路徑即可。而matvh_unsorted_outer函數則是代表外表已經有序，這時候隻需要對内表進行顯示排序就可以生成MergeJoin路徑或者生成NestLoop以及參數化路徑。最後的選擇就是對兩表連接配接建立HashJoin路徑，也就是要建立哈希表。
為了友善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);
}
（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，否則無法建立哈希表。
3） 路徑篩選
至此為止已經生成了實體連接配接路徑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;
}
6.3.5 遺傳算法
遺傳算法（genetic algorithm，GA）作為進化算法的一種，借鑒了達爾文生物進化論中的自然選擇以及遺傳學機理。通過模拟大自然中“物競天擇，适者生存”這種進化過程來生成最優的個體。
當生成一定數量的原始個體後，可以通過基因的排列組合産生新的染色體，再通過染色體的雜交和變異獲得下一代染色體。為了篩選出優秀的染色體，需要通過建立适應度函數計算出适應度的值，進而将适應度低的染色體淘汰。如此，通過個體間不斷的遺傳、突變，逐漸進化出最優秀的個體。将這個過程代入解決問題，個體即為問題的解。通過遺傳算法，可以通過此類代際遺傳來使得問題的解收斂于最優解。
差別于動态規劃将問題分解成若幹獨立子問題求解的方法，遺傳算法是一個選擇的過程，它通過将染色體雜交建構新染色體的方法增大解空間，并在解空間中随時通過适應度函數進行篩選，推舉良好基因，淘汰掉不良的基因。這就使得遺傳算法獲得的解不會像動态規劃一樣，一定是全局最優解，但可以通過改進雜交和變異的方式，來争取盡量的靠近全局最優解。
得益于在多表連接配接中的效率優勢，在openGauss資料庫中，遺傳算法是動态規劃方法的有益補充。隻有在Enable_geqo參數打開，并且待連接配接的RelOptInfo的數量超過Geqo_threshold（預設12個）的情況下，才會使用遺傳算法。
遺傳算法的實作有下面5個步驟。
（1） 種群初始化：對基因進行編碼，并通過對基因進行随機的排列組合，生成多個染色體，這些染色體構成一個新的種群。另外，在生成染色體的過程中同時計算染色體的适應度。
（2） 選擇染色體：通過随機選擇（實際上通過基于機率的随機數生成算法，這樣能傾向于選擇出優秀的染色體），選擇出用于交叉和變異的染色體。
（3） 交叉操作：染色體進行交叉，産生新的染色體并加入種群。
（4） 變異操作：對染色體進行變異操作，産生新的染色體并加入種群。
（5） 适應度計算：對不良的染色體進行淘汰。
舉個例子，如果用遺傳算法解決貨郎問題（TSP），則可以将城市作為基因，走遍各個城市的路徑作為染色體，路徑的總長度作為适應度，适應度函數負責篩選掉比較長的路徑，保留較短的路徑。算法的步驟如下。
（1） 種群初始化：對各個城市進行編号，将各個城市根據編号進行排列組合，生成多條新的路徑（染色體），然後根據各城市間的距離計算整體路徑長度（适應度），多條新路徑構成一個種群。
（2） 選擇染色體：選擇兩個路徑進行交叉（需要注意交叉生成新染色體中不能重複出現同一個城市），對交叉操作産生的新路徑計算路徑長度。
（3） 變異操作：随機選擇染色體進行變異（通常方法是交換城市在路徑中的位置），對變異操作後的新路徑計算路徑長度。
（4） 适應度計算：對種群中所有路徑進行基于路徑長度由小到大排序，淘汰掉排名靠後的路徑。
openGauss資料庫的遺傳算法正是模拟了解決貨郎問題的方法，将RelOptInfo作為基因、最終生成的連接配接樹作為染色體、連接配接樹的總代價作為适應度，适應度函數則是基于路徑的代價進行篩選，但是openGauss資料庫的連接配接路徑的搜尋和貨郎問題的路徑搜尋略有不同，貨郎問題不存在路徑不通的問題，兩個城市之間是相通的，可以計算任何兩個城市之間的距離，而資料庫中由于連接配接條件的限制，可能兩個表無法正常連接配接，或者整個連接配接樹都無法生成。另外，需要注意的是，openGauss資料庫的基因算法實作方式和通常的遺傳算法略有不同，在于其沒有變異的過程，隻通過交叉産生新的染色體。
openGauss資料庫遺傳算法的總入口是geqo函數，輸入參數為root（查詢優化的上下文資訊）、number_of_rels（要進行連接配接的RelOptInfo的數量）、initial_rels（所有的基表）。
1. 檔案結構
遺傳算法作為相對獨立的優化器子產品，擁有自己的一套檔案目錄結構，見表6-17。
表6-17 優化器檔案目錄結構說明
| 檔案名稱 | 功能說明 |
| geqo_copy.cpp | 複制基因函數，即gepo_copy函數 |
| geqo_cx.cpp | 循環交叉（CYCLE CROSSOVER）算法函數，即cx函數 |
| geqo_erx.cpp | 基于邊重組交叉(EGDE RECOMBINATION CROSSOVER）實作，提供調用gimme_edge_table函數 |
| geqo_eval.cpp | 主要進行适應度計算，調用make_one_rel函數生成連接配接關系 |
| geqo_main.cpp | 遺傳算法入口，即主函數geqo函數 |
| geqo_misc.cpp | 遺傳算法資訊列印函數，輔助功能 |
| geqo_mutation.cpp | 基因變異函數，在循環交叉cx函數失敗時調用，即geqo_mutation函數 |
| geqo_ox1.cpp | 順序交叉（ORDER CROSSOVER）算法方式一函數，即ox1函數 |
| geqo_ox2.cpp | 順序交叉（ORDER CROSSOVER）算法方式二函數，即ox2函數 |
| geqo_pmx.cpp | 部分比對交叉(PARTIALLY MATCHED CROSSOVER)算法函數，即pmx函數 |
| geqo_pool.cpp | 處理遺傳算法的基因池，基因池是表示所有個體（包括染色體和多表連接配接後得到的新的染色體）的集合 |
| geqo_px.cpp | 位置交叉（POSITION CROSSOVER）算法函數，即px函數 |
| geqo_random.cpp | 遺傳算法的随機算法函數，用來随機生成變異内容 |
| geqo_recombination.cpp | 遺傳算法初始化群體函數，即init_tour函數 |
| geqo_selection.cpp | 遺傳算法随機選擇個體函數，即geqo_selection函數 |
這些檔案作為優化器遺傳算法的各個子產品都在src/gausskernel/optimizer/gepo下。接下來的幾個單元會着重根據這些檔案中的代碼進行解讀。
2. 種群初始化
在使用遺傳算法前，可以利用參數Gepo_threshold的數值來調整觸發的條件。為了友善代碼解讀，将這個邊界條件降低至4（即RelOptInfo數量或者說基表數量為4的時候就嘗試使用遺傳算法）。下面在解讀代碼的過程中，以t1，t2，t3，t4四個表為例進行說明。
RelOptInfo作為遺傳算法的基因，首先需要進行基因編碼，openGauss資料庫采用實數編碼的方式，也就是用{1,2,3,4}分别代表t1，t2，t3，t4這4個表。
然後通過gimme_pool_size函數來獲得種群的大小，種群的大小受Geqo_pool_size和Geqo_effort兩個參數的影響，種群用Pool結構體進行表示，染色體用Chromosome結構體來表示。代碼如下：
/* 染色體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;
另外通過gimme_number_generations函數來擷取染色體交叉的次數，交叉的次數越多則産生的新染色體也就越多，也就更可能找到更好的解，但是交叉次數多也影響性能，使用者可以通過Geqo_generations參數來調整交叉的次數。
在結構體中确定的變量如下。
（1） 通過gimme_pool_size确定的染色體的數量（Pool.size）。
（2） 每個染色體中基因的數量（Pool.string_length），和基表的數量相同。
然後就可以開始生成染色體，染色體的生成采用的是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--;
}
表6-18是生成一條染色體的流程，假設4次的随機結果為{1,1,1,0}。
表6-18 生成染色體的流程
| 基因備選集 Tmp | 結果集 tour | 随機數 範圍 | ||
| 1 2 3 4 | 0~3 | 随機數為1，結果集的第一個基因為tmp[1]，值為2，更新備選集tmp，将未被選中的末尾值放在前面被選中的位置上 | ||
| 1 4 3 | 2 4 | 0~2 | 随機數為1，結果集的第二個基因為4，再次更新備選集tmp | |
| 1 3 | 2 4 3 | 0~1 | 随機數為1，結果集的第三個基因為3，由于末尾值被選，無須更新備選集 | |
| 2 4 3 1 | 0~0 | 最後一個基因為1 |
在多次随機生成染色體後，得到一個種群，假設Pool種群中共有4條染色體，用圖來描述其結構，如圖6-13所示。
圖6-13 染色體結構
然後對每條染色體計算适應度（worth），計算适應度的過程實際上就是根據染色體的基因編碼順序産生連接配接樹，并對連接配接樹求代價的過程。
在openGauss資料庫中，每個染色體都預設使用的是左深樹，是以每個染色體的基因編碼确定後，它的連接配接樹也就随之确定了，比如針對{2, 4, 3, 1}這樣一條染色體，它對應的連接配接樹就是（（（t2，t4），t3）， t1），如圖6-14所示。
圖6-14 染色體連接配接樹
openGauss資料庫通過geqo_eval函數來生成計算适應度，它首先根據染色體的基因編碼生成一棵連接配接樹，然後計算這棵連接配接樹的代價。
遺傳算法使用gimme_tree函數來生成連接配接樹，函數内部遞歸調用了merge_clump函數。merge_clump函數将能夠進行連接配接的表盡量連接配接并且生成連接配接子樹，同時記錄每個連接配接子樹中節點的個數。再将連接配接子樹按照節點個數從高到低的順序記錄到clumps連結清單。代碼如下：>
/* 循環周遊所有的表，盡量将能連接配接的表連接配接起來 */
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);
}
以之前生成的{2, 4, 3, 1}這樣一條染色體為例，并假定。
（1） 2和4不能連接配接。
（2） 4和3能夠連接配接。
（3） 2和1能夠連接配接。
在這些條件下，連接配接樹生成的過程見表6-19。
表6-19 連接配接樹生成過程
| 輪數 relcount | 連接配接結果集 clumps | |
| 初始 | NULL | 建立基因為2的節點cur_clump，cur_clump.size = 1 |
| {2} | 因為clumps == NULL，cur_clump沒有連接配接表，将cur_clump直接加入clumps | |
| {2}，{4} | 建立基因為4的節點cur_clump，cur_clump.size = 1，将基因為4的cur_clump和clumps連結清單的裡的節點嘗試連接配接，因為2和4不能連接配接，節點4也被加入clumps | |
| 建立基因為3的節點cur_clump，cur_clump.size = 1，周遊clumps連結清單，分别嘗試和2、4進行連接配接，發現和4能進行連接配接，建立基于3和4的連接配接的新old_clumps節點，ols_clumps.size = 2，在clumps連結清單中删除節點4 | ||
| {3, 4} {2} | 用2和4連接配接生成的新的old_clumps作為參數遞歸調用merge_clump，用old_clumps和clumps連結清單裡的節點再嘗試連接配接，發現不能連接配接（即{3,4}和{2}不能連接配接），那麼将old_clumps加入clumps，因為old_clumps.size目前最大，插入clumps最前面 | |
| {3, 4} | 建立基因為1的節點cur_clump，cur_clump.size = 1 周遊clumps連結清單，分别嘗試和{3,4}、{2}進行連接配接，發現和2能進行連接配接，建立基于1和2的新old_clumps節點，ols_clumps.size = 2，在clumps連結清單中删除節點2 | |
| {3, 4} {1, 2} | 用1和2連接配接生成的新的old_clumps作為參數遞歸調用merge_clump，用old_clumps和clumps連結清單裡的節點嘗試連接配接，發現不能連接配接，将old_clumps加入clumps，因為old_clumps.size = 2，插入clumps最後 |
結合例子中的步驟，可以看出merge_clumps函數的流程就是不斷的嘗試生成更大的clump。
/* 如果能夠生成連接配接，則通過遞歸嘗試生成節點數更多的連接配接 */
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連結清單中有兩個節點，分别是兩棵連接配接子樹，然後将force設定成true後，再次嘗試連接配接這兩個節點。
/* 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;
}
3. 選擇算子
在種群生成之後，就可以進行代際遺傳優化，從種群中随機選擇兩個染色做交叉操作，這樣就能産生一個新的染色體。
由于種群中的染色體已經按照适應度排序了，對來說适應度越低（代價越低）的染色體越好，因為希望将更好的染色體遺傳下去，是以需要在選擇父染色體和母染色體的時候更傾向于選擇适應度低的染色體。在選擇過程中會涉及傾向（bias）的概念，它在算子中是一個固定的值。當然，bias的值可以通過參數Geqo_selection_bias進行調整（預設值為2.0）。
/* 父染色體和母染色體通過linear_rand函數選擇 */
first = linear_rand(root, pool->size, bias);
second = linear_rand(root, pool->size, bias);
要生成基于某種機率分布的随機數（x），需要首先知道機率分布函數或機率密度函數，openGauss資料庫采用的機率密度函數（probability density function，PDF） fx(x)為：
通過機率密度函數獲得累計分布函數（cumulative distribution function，CDF） Fx(x)：
：然後通過機率分布函數根據逆函數法可以獲得符合機率分布的随機數。對于函數。
求逆函數。
這和源代碼中linear_rand函數的實作是一緻的。
/* 先求的值 */
double sqrtval;
sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(root);
if (sqrtval > 0.0)
sqrtval = sqrt(sqrtval);
/* 然後計算的值，其為基于機率分布随機數且符合[0,1]分布 */
/* max是種群中染色體的數量 */
/* index就是滿足機率分布的随機數，且随機數的值域在[0, max] */
index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
把基于機率的随機數生成算法的代碼提取出來單獨進行計算驗證，看一下它生成随機數的特點。設bias = 2.0，然後利用機率密度函數計算各個區間的理論機率值進行分析，比如對于0.6~0.7的區間，計算其理論機率如下。
各個區間的理論機率值如圖6-15所示。
圖6-15 随機數生成理論機率值
從圖6-15可以看出各個區間的理論機率值的數值是依次下降的，也就是說在選擇父母染色體的時候是更傾向于選擇适應度更低（代價更低）的染色體。
4. 交叉算子
通過選擇算子選擇出父母染色體之後，則可以對選出的父母染色體進行交叉操作，生成新的子代染色體。
openGauss提供了多種交叉方法，包括有基于邊的重組交叉方法（edge combination crossover）、部分比對交叉方法(partially matched crossover)、循環交叉（cycle crossover）、位置交叉（position crossover）、順序交叉（order crossover）等。在源代碼分析的過程中，以位置交叉方法為例進行說明。
假如選擇父染色體的基因編碼為{1, 3, 2, 4}，适應度為100，母染色體的基因編碼為{2, 3, 1, 4}，适應度為200，在子染色體還沒有生成，處于未初始化狀态時，這些染色體的狀态如圖6-16所示。
圖6-16 染色體狀态
交叉操作需要生成一個随機數num_positions，這個随機數的位置介于基因總數的1/3~2/3區間的位置，這個随機數代表了有多少父染色體的基因要按位置遺傳給子染色體。具體代碼如下：
/* 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;
}
假設父染色體需要遺傳2個基因給子染色體，分别傳遞第1号基因和第2号基因，那麼子染色體目前的狀态如圖6-17所示。
圖6-17 目前染色體狀态
目前子染色體已經有了3和2兩個基因，則母染色體排除這兩個基因後，還剩下1和4兩個基因，将這兩個基因按照母染色體中的順序寫入子染色體，新的子染色體就生成了，如圖6-18所示。
圖6-18 新的染色體裝狀态
5. 适應度計算
當得到了新生成的子染色體後，需要通過geqo_eval函數來計算适應度，随後使用spread_chromo函數将染色體加入到種群中。
/* 适應度分析*/
kid->worth = geqo_eval(root, kid->string, pool->string_length);
/* 基于适應度将染色體擴散*/
spread_chromo(root, kid, pool);
由于種群中的染色體始終應保持有序的狀态，spread_chromo函數可以使用二分法周遊種群來比較種群中的染色體和新染色體的适應度大小并根據适應度大小來查找新染色體的插入位置，排在它後面的染色體自動退後一格，最後一個染色體被淘汰，如果新染色體的适應度最大，那麼直接會被淘汰。具體代碼如下：
/* 二分法周遊種群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);
}
}
6.4 小結