共計 5354 個字符，預計需要花費 14 分鐘才能閱讀完成。

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

簡介

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

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

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

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

參數化路徑，作用于 indexed lookup join

分區裁剪和并行優化

強一致的 cardinality estimation 保證

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

術語解釋

Datum

Qual

Path

關鍵數據結構查詢

__Query__: Parse Tree，優化器的輸入

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

執行計劃

__PlannedStmt__: 執行計劃的頂層節點

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

__RelOptInfo__: 優化器的核心數據結構，包含一個子查詢的 Path 集合等信息。這個概念對應于 ORCA 的 Group 或 Calcite 中的 Set。

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

__PathKey__: 排序屬性。這個概念相當于 Volcano 中的 Physical Property 或 Calcite 中的 Trait。因為 PostgreSQL 是單機數據庫，僅用排序屬性就可以表達所有算法的需求和實現特性。對于分布式數據庫，通常還需要分布屬性。

主流程

子查詢上拉

因為優化的單元（RelOptInfo）是子查詢，合并子查詢可以簡化優化流程。關聯的過程包括：

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

__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 是很關鍵的數據結構，它的應用場景包括：

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

在 Join 時決定 qual 穿越

決定參數化路徑的參數列表

匹配主 - 外鍵約束，以便優化（Join 的）cardinality estimation

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

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

其中，每個 EC 內部的 expression 稱為 EquivalenceMember（EM）。

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

Join 重排

（有關 Join 重排的背景知識可以參考我之前的文章 SQL 優化器原理 – Join 重排）

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

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

GEQO：Genetic Optimization（基因算法，或遺傳算法[4]），是一種非窮舉的最優化算法實現

Standard：一個略微剪枝的動態規劃算法。

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

geqo = on
geqo_threshold = 12

控制 GEQO 設定。

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

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

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

如果當前層找不到任何 EC 關聯，生成笛卡爾積。

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

Standard 算法仍然是一個窮舉的動態規劃算法

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

路徑生成和動態規劃

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

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

sort_inner_and_outer：兩邊排序的 MergeJoin 路徑

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

hash_inner_and_outer：兩邊哈希的 HashJoin 路徑。

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

路徑生成的入口是 add_path，每次生成路徑，需要更新 RelOptInfo 的最佳路徑和最小代價以便后續動態規劃選擇全局最優。

流程圖

planner
|- subquery_planner  迭代的子查詢優化
 |- 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 優化
 |- query_planner  子查詢優化主入口
 |- generate_base_implied_equalities  生成 / 合并 EC
 |- make_one_rel Join 優化入口
 |- set_base_rel_pathlists  生成 Join RelOptInfo 列表
 |- make_rel_from_joinlist Join 重排和規劃
 |- standard_join_search  標準 Join 重排算法
 |- join_search_one_level
 |- make_join_rel  生成 JoinRel 和對應的 Path
 |- create_XXX_paths Grouping、window 等其他 expression 優化

討論

擴展性和靈活性

首先，PostgreSQL 的優化器代碼可以說非常復雜，這已經極大限制了它的擴展性和靈活性。如果看一眼這部分代碼的更新日志，會發現里面的作者已經只有少數幾個人。

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

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

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

不容易定制優化規則。

開發者關注的切片太大，開發一個優化規則除了關注優化本身，不得不學習其他優化規則的數據結構、動態規劃更新、RelOptInfo 新建和清理，甚至內存分配本身。

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

可定制的 Join 重排算法

可定制的 PathKey 生成算法

定制的 Join Path 生成算法

等等。

性能

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

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

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

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

對比 Calcite/Orca，PostgreSQL 的優化更快，更適合事務性場景。不過我無法判斷 Calcite/Orca 在做了適當的剪枝和優化規則糅合后，是否也能支持事務場景。

以上是“PostgreSQL 優化器的示例分析”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注丸趣 TV 行業資訊頻道！