簡介
PostgreSQL 的開發(fā)源自上世紀(jì)80年代，它最初是 Michael Stonebraker 等人在美國國防部支持下創(chuàng)建的POSTGRE項目。上世紀(jì)末，Andrew Yu 等人在它上面搭建了第一個SQL Parser，這個版本稱為Postgre95，也是加州大學(xué)伯克利分校版本的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)化復(fù)雜度很高（例如Join重排是System R[3]風(fēng)格的動態(tài)規(guī)劃算法），所以性能不好。

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

參數(shù)化路徑，作用于indexed lookup join
分區(qū)裁剪和并行優(yōu)化
強一致的cardinality estimation保證
本文嘗試快速地瀏覽一遍 PostgreSQL 優(yōu)化器的代碼，和現(xiàn)代優(yōu)化器比較優(yōu)缺點。大部分的 PostgreSQL 優(yōu)化器代碼來自于 https://github.com/postgres/p... 。 我們提到現(xiàn)代優(yōu)化器主要指的是 Apache Calcite 和 ORCA。

術(shù)語解釋
Datum
Qual
Path
關(guān)鍵數(shù)據(jù)結(jié)構(gòu)
查詢
__Query__: Parse Tree，優(yōu)化器的輸入
__RangeTblEntry__: Parse Tree的一個節(jié)點，它描述了一個數(shù)據(jù)集的視圖，這個數(shù)據(jù)集可能來源于某個子查詢、Join、Values或任何一個簡單關(guān)系代數(shù)表達式。Join實現(xiàn)需要把它的輸入都表達為 RangeTblEntry （以下簡稱RTE）。
執(zhí)行計劃
__PlannedStmt__: 執(zhí)行計劃的頂層節(jié)點
__PlannerInfo__: 優(yōu)化器的上下文信息。它是一個樹形結(jié)構(gòu)，用parent_root變量指向父節(jié)點。一個Query包含一個或多個PlannerInfo，每次Join切分一次樹節(jié)點。它包含RelOptInfo的指針。
__RelOptInfo__: 優(yōu)化器的核心數(shù)據(jù)結(jié)構(gòu)，包含一個子查詢的Path集合等信息。這個概念對應(yīng)于ORCA的Group或Calcite中的Set。
__Path__: 區(qū)別于Parser稱Relational Expression為Node，Optimizer稱優(yōu)化時的關(guān)系代數(shù)為Path。Path是物理計劃，它包含優(yōu)化器對于單個關(guān)系代數(shù)的理解，包括并行度、PathKey和cost。
__PathKey__: 排序?qū)傩浴＿@個概念相當(dāng)于Volcano中的Physical Property或Calcite中的Trait。因為 PostgreSQL 是單機數(shù)據(jù)庫，僅用排序?qū)傩跃涂梢员磉_所有算法的需求和實現(xiàn)特性。對于分布式數(shù)據(jù)庫，通常還需要分布屬性。
主流程
子查詢上拉

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

__pull_up_sublinks__: 將可轉(zhuǎn)換的 ANY/EXISTS 子句轉(zhuǎn)換為 (anti-)semi-join 。一些優(yōu)化器稱這個過程為de-correlation。
__pull_up_subqueries__: 將可上拉的子查詢上拉到當(dāng)前查詢，刪除原來的子查詢。如果子查詢是一個 Join ，這個操作相當(dāng)于打平 binary join 到 multi join。
EquivalenceClass解析

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

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

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

EC是很關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)，它的應(yīng)用場景包括：

在 Join 時，EC用來決定 Join Key，它決定了 Outer Join 簡化和PathKey設(shè)定
在 Join 時決定 qual 穿越
決定參數(shù)化路徑的參數(shù)列表
匹配主-外鍵約束，以便優(yōu)化（Join的）cardinality estimation
EC是一個樹形結(jié)構(gòu)，每個節(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只能應(yīng)用于Join優(yōu)化。

Join重排

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

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

你可以插入一個自定義的Join重排算法
GEQO： Genetic Optimization （基因算法，或遺傳算法[4]），是一種非窮舉的最優(yōu)化算法實現(xiàn)
Standard：一個略微剪枝的動態(tài)規(guī)劃算法。
默認(rèn)在12路及以上的復(fù)雜Join中會打開GEQO。可以在postgresql.conf中修改參數(shù)

geqo = on
geqo_threshold = 12
控制GEQO設(shè)定。

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

按EC檢查未加入的Join input，加入到生成的局部計劃，這個操作僅產(chǎn)生 Left-deep-tree
從未加入局部計劃的Join input里找到有EC的兩個input，生成額外的局部計劃，用于生成Bushy-tree
如果當(dāng)前層找不到任何EC關(guān)聯(lián)，生成笛卡爾積。
上述描述已經(jīng)足夠復(fù)雜，讓我們總結(jié)一下 Standard 算法：

Standard 算法仍然是一個窮舉的動態(tài)規(guī)劃算法
它對 a-b/b-a 鏡像去重，同時當(dāng)EC存在時不考慮笛卡爾積，這些工程上的降級有效降低了搜索復(fù)雜度
路徑生成和動態(tài)規(guī)劃

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

物理優(yōu)化就是將 Path 加入 RelOptInfo。考慮Join，物理優(yōu)化的入口在 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過程中，需要計算兩邊的參數(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 結(jié)構(gòu)解析，常量折疊 |- 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 標(biāo)準(zhǔn)Join重排算法|- join_search_one_level|- make_join_rel 生成JoinRel和對應(yīng)的Path|- create_XXX_paths Grouping、window等其他expression優(yōu)化

討論
擴展性和靈活性

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

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

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

無法做邏輯和物理優(yōu)化的互操作。例如前文說到的，一個Join產(chǎn)生的EC必須和它緊跟的 RTE 結(jié)合才能產(chǎn)生 IndexedLookupJoin，而不像其他優(yōu)化器可以把這個 EC （它在某種意義上已經(jīng)是物理計劃）下推到合適的邏輯計劃上，指導(dǎo)它做物理計劃轉(zhuǎn)換。
不容易定制優(yōu)化規(guī)則。
開發(fā)者關(guān)注的切片太大，開發(fā)一個優(yōu)化規(guī)則除了關(guān)注優(yōu)化本身，不得不學(xué)習(xí)其他優(yōu)化規(guī)則的數(shù)據(jù)結(jié)構(gòu)、動態(tài)規(guī)劃更新、RelOptInfo新建和清理，甚至內(nèi)存分配本身。
PostgreSQL 仍然提供了部分手寫的 Plugin Point，包括：

可定制的Join重排算法
可定制的PathKey生成算法
定制的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ù)量級，當(dāng)然，如上所述，這是用更多優(yōu)化可能性作為交換的。

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

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

本文作者：少杰

閱讀原文

本文為云棲社區(qū)原創(chuàng)內(nèi)容，未經(jīng)允許不得轉(zhuǎn)載。

總結(jié)

以上是生活随笔為你收集整理的PostgreSQL 优化器代码概览的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。