這篇文章主要介紹PostgreSQL優(yōu)化器的示例分析，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

創(chuàng)新互聯(lián)建站專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務，包含不限于成都網(wǎng)站建設、成都做網(wǎng)站、調(diào)兵山網(wǎng)絡推廣、重慶小程序開發(fā)、調(diào)兵山網(wǎng)絡營銷、調(diào)兵山企業(yè)策劃、調(diào)兵山品牌公關、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運營等，從售前售中售后，我們都將竭誠為您服務，您的肯定，是我們最大的嘉獎；創(chuàng)新互聯(lián)建站為所有大學生創(chuàng)業(yè)者提供調(diào)兵山建站搭建服務，24小時服務熱線：028-86922220，官方網(wǎng)址：www.cdcxhl.com

簡介

PostgreSQL 的開發(fā)源自上世紀80年代，它最初是 Michael Stonebraker 等人在美國國防部支持下創(chuàng)建的POSTGRE項目。上世紀末，Andrew Yu 等人在它上面搭建了第一個SQL Parser，這個版本稱為Postgre95，也是加州大學伯克利分校版本的PostgreSQL的基石[1]。

我們今天看到的 PostgreSQL 的優(yōu)化器代碼主要是 Tom Lane 在過去的20年間貢獻的，令人驚訝的是這20年的改動都是持續(xù)一以貫之的，Tom Lane 本人也無愧于“開源軟件十大杰出貢獻者”的稱號。

但是從今天的視角，PostgreSQL 優(yōu)化器不是一個好的實現(xiàn)，它用C語言實現(xiàn)，所以擴展性不好；它不是 Volcano 優(yōu)化模型的[2]，所以靈活性不好；它的很多優(yōu)化復雜度很高（例如Join重排是System R[3]風格的動態(tài)規(guī)劃算法），所以性能不好。

無論如何，PostgreSQL 是優(yōu)化器的優(yōu)秀實現(xiàn)和創(chuàng)新源頭（想象 Greenplum 和 ORCA 等一系列項目），它的一些優(yōu)化手段和代碼結構在今天仍然是值得借鑒的，包括：

1. 參數(shù)化路徑，作用于indexed lookup join

2. 分區(qū)裁剪和并行優(yōu)化

3. 強一致的cardinality estimation保證

本文嘗試快速地瀏覽一遍 PostgreSQL 優(yōu)化器的代碼，和現(xiàn)代優(yōu)化器比較優(yōu)缺點。大部分的 PostgreSQL 優(yōu)化器代碼來自于 https://github.com/postgres/postgres/tree/master/src/backend/optimizer 。 我們提到現(xiàn)代優(yōu)化器主要指的是 Apache Calcite 和 ORCA。

術語解釋

1. Datum

2. Qual

3. Path

關鍵數(shù)據(jù)結構

查詢

1. __Query__: Parse Tree，優(yōu)化器的輸入

2. __RangeTblEntry__: Parse Tree的一個節(jié)點，它描述了一個數(shù)據(jù)集的視圖，這個數(shù)據(jù)集可能來源于某個子查詢、Join、Values或任何一個簡單關系代數(shù)表達式。Join實現(xiàn)需要把它的輸入都表達為 RangeTblEntry （以下簡稱RTE）。

執(zhí)行計劃

1. __PlannedStmt__: 執(zhí)行計劃的頂層節(jié)點

2. __PlannerInfo__: 優(yōu)化器的上下文信息。它是一個樹形結構，用parent_root變量指向父節(jié)點。一個Query包含一個或多個PlannerInfo，每次Join切分一次樹節(jié)點。它包含RelOptInfo的指針。

3. __RelOptInfo__: 優(yōu)化器的核心數(shù)據(jù)結構，包含一個子查詢的Path集合等信息。這個概念對應于ORCA的Group或Calcite中的Set。

4. __Path__: 區(qū)別于Parser稱Relational Expression為Node，Optimizer稱優(yōu)化時的關系代數(shù)為Path。Path是物理計劃，它包含優(yōu)化器對于單個關系代數(shù)的理解，包括并行度、PathKey和cost。

5. __PathKey__: 排序?qū)傩浴＿@個概念相當于Volcano中的Physical Property或Calcite中的Trait。因為 PostgreSQL 是單機數(shù)據(jù)庫，僅用排序?qū)傩跃涂梢员磉_所有算法的需求和實現(xiàn)特性。對于分布式數(shù)據(jù)庫，通常還需要分布屬性。

主流程

子查詢上拉

因為優(yōu)化的單元（RelOptInfo）是子查詢，合并子查詢可以簡化優(yōu)化流程。關聯(lián)的過程包括：

1. __pull_up_sublinks__: 將可轉(zhuǎn)換的 ANY/EXISTS 子句轉(zhuǎn)換為 (anti-)semi-join 。一些優(yōu)化器稱這個過程為de-correlation。

2. __pull_up_subqueries__: 將可上拉的子查詢上拉到當前查詢，刪除原來的子查詢。如果子查詢是一個 Join ，這個操作相當于打平 binary join 到 multi join。

EquivalenceClass解析

Equivalence Class（EC）是 qual 的術語，它指代的是 expression 的等價性。例如，expression

a = b AND b = c

則稱 {a, b, c} 是一個EC。特別地，在 PostgreSQL 中，expression

a = b AND b = 5

只生成簡化的EC：{a = 5} {b = 5}

EC是很關鍵的數(shù)據(jù)結構，它的應用場景包括：

1. 在 Join 時，EC用來決定 Join Key，它決定了 Outer Join 簡化和PathKey設定

2. 在 Join 時決定 qual 穿越

3. 決定參數(shù)化路徑的參數(shù)列表

4. 匹配主-外鍵約束，以便優(yōu)化（Join的）cardinality estimation

EC是一個樹形結構，每個節(jié)點是一個EC，并鏈接到它合并的父節(jié)點上。考慮a = b AND b = c的例子，最后的EC tree表達為

{a, b, c}
|- {a, b}
|- {b, c}

其中，每個EC內(nèi)部的expression稱為EquivalenceMember（EM）。

生成 EC 的入口是 generate_base_implied_equalities ，它從 query_planner 調(diào)入。也就是說，EC是在規(guī)劃Join的前一刻生成的，這個階段解析EC的代價最小，但是也決定了EC只能應用于Join優(yōu)化。

Join重排

（有關Join重排的背景知識可以參考我之前的文章 SQL優(yōu)化器原理 - Join重排）

make_rel_from_joinlist是Join重排的入口，當前版本的 PostgreSQL 有三種算法：

1. 你可以插入一個自定義的Join重排算法

2. GEQO： Genetic Optimization （基因算法，或遺傳算法[4]），是一種非窮舉的最優(yōu)化算法實現(xiàn)

3. Standard：一個略微剪枝的動態(tài)規(guī)劃算法。

默認在12路及以上的復雜Join中會打開GEQO。可以在postgresql.conf中修改參數(shù)

geqo = on
geqo_threshold = 12

控制GEQO設定。

現(xiàn)在讓我們檢查 Standard 算法。它的主入口在 join_search_one_level ，每次在已生成的局部計劃的基礎上：

1. 按EC檢查未加入的Join input，加入到生成的局部計劃，這個操作僅產(chǎn)生 Left-deep-tree

2. 從未加入局部計劃的Join input里找到有EC的兩個input，生成額外的局部計劃，用于生成Bushy-tree

3. 如果當前層找不到任何EC關聯(lián)，生成笛卡爾積。

上述描述已經(jīng)足夠復雜，讓我們總結一下 Standard 算法：

1. Standard 算法仍然是一個窮舉的動態(tài)規(guī)劃算法

2. 它對 a-b/b-a 鏡像去重，同時當EC存在時不考慮笛卡爾積，這些工程上的降級有效降低了搜索復雜度

路徑生成和動態(tài)規(guī)劃

如上所述，優(yōu)化過程集中在對子查詢（RelOptInfo）的重建過程，這可以理解為邏輯優(yōu)化過程，這通常是跨關系代數(shù)操作符的、比較復雜的優(yōu)化。事實上 PostgreSQL 也同步在做物理優(yōu)化。

物理優(yōu)化就是將 Path 加入 RelOptInfo。考慮Join，物理優(yōu)化的入口在 populate_joinrel_with_paths。對每個JoinRel（Join RelOptInfo），考慮：

1. sort_inner_and_outer：兩邊排序的MergeJoin路徑

2. match_unsorted_outer：Null-generating side不排序路徑，包括 MergeJoin 和 NestedLoopJoin 。

3. hash_inner_and_outer：兩邊哈希的HashJoin路徑。

有趣的點是HashJoin路徑（hash_inner_and_outer），顧名思義，它要求Join兩邊都計算哈希值。在生成Path過程中，需要計算兩邊的參數(shù)信息。例如A join B on A.x = B.y，對于A來說，x是參數(shù)，對于B是y。如果選定A作為Probe side，一旦B上有y的索引，每次x的probe將以參數(shù)的形式傳遞給y的索引。通過調(diào)用 get_joinrel_parampathinfo 來產(chǎn)生參數(shù)信息。

路徑生成的入口是add_path，每次生成路徑，需要更新RelOptInfo的最佳路徑和最小代價以便后續(xù)動態(tài)規(guī)劃選擇全局最優(yōu)。

流程圖

planner
|- subquery_planner 迭代的子查詢優(yōu)化
    |- pull_up_sublinks de-correlation
    |- pull_up_subqueries 子查詢上拉
    |- preprocess_expression Query/PlannerInfo 結構解析，常量折疊
    |- remove_useless_groupby_columns
    |- reduce_outer_joins Outer Join退化
    |- grouping_planner
        |- plan_set_operations SetOp優(yōu)化
        |- query_planner 子查詢優(yōu)化主入口
            |- generate_base_implied_equalities 生成/合并EC
            |- make_one_rel Join優(yōu)化入口
                |- set_base_rel_pathlists 生成Join RelOptInfo列表
                |- make_rel_from_joinlist Join重排和規(guī)劃
                    |- standard_join_search 標準Join重排算法
                        |- join_search_one_level
                            |- make_join_rel 生成JoinRel和對應的Path
        |- create_XXX_paths Grouping、window等其他expression優(yōu)化

討論

擴展性和靈活性

首先，PostgreSQL 的優(yōu)化器代碼可以說非常復雜，這已經(jīng)極大限制了它的擴展性和靈活性。如果看一眼這部分代碼的更新日志，會發(fā)現(xiàn)里面的作者已經(jīng)只有少數(shù)幾個人。

一部分擴展性限制是由編程語言帶來的，因為C語言本身不容易擴展，這意味著大部分時候想要添加一個新的Node或Path變得很不容易，你需要定義一系列的數(shù)據(jù)結構、Cardinality Estimation邏輯、并行邏輯和Path解釋邏輯。并沒有類似interface這樣的抽象指導你該怎么做。雖然，PostgreSQL 的代碼已經(jīng)寫得非常工整，而且也有很多的文章告訴你該怎么做（比如 Introduction to Hacking PostgreSQL 和 The Internals of PostgreSQL）。

另一部分擴展性限制是優(yōu)化器本身的結構帶來的。現(xiàn)代的優(yōu)化器基本都是Volcano Model[2]的（例如SQL Server和Oracle，就像他們聲稱的那樣），而 PostgreSQL 沒有實現(xiàn)為 Volcano Model 這種 Generic purpose，pluggable 的形式。影響包括：

1. 無法做邏輯和物理優(yōu)化的互操作。例如前文說到的，一個Join產(chǎn)生的EC必須和它緊跟的 RTE 結合才能產(chǎn)生 IndexedLookupJoin，而不像其他優(yōu)化器可以把這個 EC （它在某種意義上已經(jīng)是物理計劃）下推到合適的邏輯計劃上，指導它做物理計劃轉(zhuǎn)換。

2. 不容易定制優(yōu)化規(guī)則。

3. 開發(fā)者關注的切片太大，開發(fā)一個優(yōu)化規(guī)則除了關注優(yōu)化本身，不得不學習其他優(yōu)化規(guī)則的數(shù)據(jù)結構、動態(tài)規(guī)劃更新、RelOptInfo新建和清理，甚至內(nèi)存分配本身。

PostgreSQL 仍然提供了部分手寫的 Plugin Point，包括：

1. 可定制的Join重排算法

2. 可定制的PathKey生成算法

3. 定制的Join Path生成算法

等等。

性能

雖然沒有實驗，但是 PostgreSQL 在優(yōu)化上的性能可以想像是比較好的，這很大程度是用靈活性交換來的。

首先，不像 Volcano Optimizer ，PostgreSQL 優(yōu)化器不需要不斷生成中間節(jié)點，它的 RelOptInfo 的數(shù)量是相對穩(wěn)定的（約等于Join的數(shù)量）。它的最優(yōu)計劃搜索以 RelOptInfo 為單位，如果 Join 重排不產(chǎn)生大量 RelOptInfo ，搜索寬度很低。

其次，RelOptInfo 簡化了大量跨 Relational Expression 優(yōu)化的細節(jié)，比起 Calcite 這種按 Relational Expression 來組織等價路徑集合的方案， 它的搜索寬度進一步降低了。從等價集合的數(shù)量看， PostgreSQL 的搜索寬度大概比 Calcite 要低一個數(shù)量級，當然，如上所述，這是用更多優(yōu)化可能性作為交換的。

最后，PostgreSQL 在優(yōu)化階段糅合了很多業(yè)務邏輯，在提高代碼閱讀的難度同時，也相應加快的優(yōu)化效率。在優(yōu)化過程中，PostgreSQL會不間斷地做常量折疊、PathKey去重、Union打平、子查詢打平……這些操作不會應用在memo里。

對比 Calcite/Orca ，PostgreSQL 的優(yōu)化更快，更適合事務性場景。不過我無法判斷 Calcite/Orca 在做了適當?shù)募糁蛢?yōu)化規(guī)則糅合后，是否也能支持事務場景。

以上是“PostgreSQL優(yōu)化器的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關知識，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道！