PostgreSQL 优化器代码概览
簡(jiǎn)介
PostgreSQL 的開發(fā)源自上世紀(jì)80年代，它最初是 Michael Stonebraker 等人在美國(guó)國(guó)防部支持下創(chuàng)建的POSTGRE項(xiàng)目。上世紀(jì)末，Andrew Yu 等人在它上面搭建了第一個(gè)SQL Parser，這個(gè)版本稱為Postgre95，也是加州大學(xué)伯克利分校版本的PostgreSQL的基石[1]。
我們今天看到的 PostgreSQL 的優(yōu)化器代碼主要是 Tom Lane 在過去的20年間貢獻(xiàn)的，令人驚訝的是這20年的改動(dòng)都是持續(xù)一以貫之的，Tom Lane 本人也無愧于“開源軟件十大杰出貢獻(xiàn)者”的稱號(hào)。
但是從今天的視角，PostgreSQL 優(yōu)化器不是一個(gè)好的實(shí)現(xiàn)，它用C語(yǔ)言實(shí)現(xiàn)，所以擴(kuò)展性不好；它不是 Volcano 優(yōu)化模型的[2]，所以靈活性不好；它的很多優(yōu)化復(fù)雜度很高（例如Join重排是System R[3]風(fēng)格的動(dòng)態(tài)規(guī)劃算法），所以性能不好。
無論如何，PostgreSQL 是優(yōu)化器的優(yōu)秀實(shí)現(xiàn)和創(chuàng)新源頭（想象 Greenplum 和 ORCA 等一系列項(xiàng)目），它的一些優(yōu)化手段和代碼結(jié)構(gòu)在今天仍然是值得借鑒的，包括：
本文嘗試快速地瀏覽一遍 PostgreSQL 優(yōu)化器的代碼，和現(xiàn)代優(yōu)化器比較優(yōu)缺點(diǎn)。大部分的 PostgreSQL 優(yōu)化器代碼來自于?https://github.com/postgres/postgres/tree/master/src/backend/optimizer。 我們提到現(xiàn)代優(yōu)化器主要指的是 Apache Calcite 和 ORCA。
術(shù)語(yǔ)解釋
關(guān)鍵數(shù)據(jù)結(jié)構(gòu)
查詢
執(zhí)行計(jì)劃
主流程
子查詢上拉
因?yàn)閮?yōu)化的單元（RelOptInfo）是子查詢，合并子查詢可以簡(jiǎn)化優(yōu)化流程。關(guān)聯(lián)的過程包括：
EquivalenceClass解析
Equivalence Class（EC）是 qual 的術(shù)語(yǔ)，它指代的是 expression 的等價(jià)性。例如，expression
a = b AND b = c則稱 {a, b, c} 是一個(gè)EC。特別地，在 PostgreSQL 中，expression
a = b AND b = 5只生成簡(jiǎn)化的EC：{a = 5} {b = 5}
EC是很關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)，它的應(yīng)用場(chǎng)景包括：
EC是一個(gè)樹形結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)是一個(gè)EC，并鏈接到它合并的父節(jié)點(diǎn)上。考慮a = b AND b = c的例子，最后的EC tree表達(dá)為
{a, b, c} |- {a, b} |- {b, c}其中，每個(gè)EC內(nèi)部的expression稱為EquivalenceMember（EM）。
生成 EC 的入口是 generate_base_implied_equalities ，它從 query_planner 調(diào)入。也就是說，EC是在規(guī)劃Join的前一刻生成的，這個(gè)階段解析EC的代價(jià)最小，但是也決定了EC只能應(yīng)用于Join優(yōu)化。
Join重排
（有關(guān)Join重排的背景知識(shí)可以參考我之前的文章?SQL優(yōu)化器原理 - Join重排）
make_rel_from_joinlist是Join重排的入口，當(dāng)前版本的 PostgreSQL 有三種算法：
默認(rèn)在12路及以上的復(fù)雜Join中會(huì)打開GEQO。可以在postgresql.conf中修改參數(shù)
geqo = on geqo_threshold = 12控制GEQO設(shè)定。
現(xiàn)在讓我們檢查 Standard 算法。它的主入口在 join_search_one_level ，每次在已生成的局部計(jì)劃的基礎(chǔ)上：
上述描述已經(jīng)足夠復(fù)雜，讓我們總結(jié)一下 Standard 算法：
路徑生成和動(dòng)態(tài)規(guī)劃
如上所述，優(yōu)化過程集中在對(duì)子查詢（RelOptInfo）的重建過程，這可以理解為邏輯優(yōu)化過程，這通常是跨關(guān)系代數(shù)操作符的、比較復(fù)雜的優(yōu)化。事實(shí)上 PostgreSQL 也同步在做物理優(yōu)化。
物理優(yōu)化就是將 Path 加入 RelOptInfo。考慮Join，物理優(yōu)化的入口在 populate_joinrel_with_paths。對(duì)每個(gè)JoinRel（Join RelOptInfo），考慮：
有趣的點(diǎn)是HashJoin路徑（hash_inner_and_outer），顧名思義，它要求Join兩邊都計(jì)算哈希值。在生成Path過程中，需要計(jì)算兩邊的參數(shù)信息。例如A join B on A.x = B.y，對(duì)于A來說，x是參數(shù)，對(duì)于B是y。如果選定A作為Probe side，一旦B上有y的索引，每次x的probe將以參數(shù)的形式傳遞給y的索引。通過調(diào)用 get_joinrel_parampathinfo 來產(chǎn)生參數(shù)信息。
路徑生成的入口是add_path，每次生成路徑，需要更新RelOptInfo的最佳路徑和最小代價(jià)以便后續(xù)動(dòng)態(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和對(duì)應(yīng)的Path|- create_XXX_paths Grouping、window等其他expression優(yōu)化討論
擴(kuò)展性和靈活性
首先，PostgreSQL 的優(yōu)化器代碼可以說非常復(fù)雜，這已經(jīng)極大限制了它的擴(kuò)展性和靈活性。如果看一眼這部分代碼的更新日志，會(huì)發(fā)現(xiàn)里面的作者已經(jīng)只有少數(shù)幾個(gè)人。
一部分?jǐn)U展性限制是由編程語(yǔ)言帶來的，因?yàn)镃語(yǔ)言本身不容易擴(kuò)展，這意味著大部分時(shí)候想要添加一個(gè)新的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 沒有實(shí)現(xiàn)為 Volcano Model 這種 Generic purpose，pluggable 的形式。影響包括：
PostgreSQL 仍然提供了部分手寫的 Plugin Point，包括：
等等。
性能
雖然沒有實(shí)驗(yàn)，但是 PostgreSQL 在優(yōu)化上的性能可以想像是比較好的，這很大程度是用靈活性交換來的。
首先，不像 Volcano Optimizer ，PostgreSQL 優(yōu)化器不需要不斷生成中間節(jié)點(diǎn)，它的 RelOptInfo 的數(shù)量是相對(duì)穩(wěn)定的（約等于Join的數(shù)量）。它的最優(yōu)計(jì)劃搜索以 RelOptInfo 為單位，如果 Join 重排不產(chǎn)生大量 RelOptInfo ，搜索寬度很低。
其次，RelOptInfo 簡(jiǎn)化了大量跨 Relational Expression 優(yōu)化的細(xì)節(jié)，比起 Calcite 這種按 Relational Expression 來組織等價(jià)路徑集合的方案， 它的搜索寬度進(jìn)一步降低了。從等價(jià)集合的數(shù)量看， PostgreSQL 的搜索寬度大概比 Calcite 要低一個(gè)數(shù)量級(jí)，當(dāng)然，如上所述，這是用更多優(yōu)化可能性作為交換的。
最后，PostgreSQL 在優(yōu)化階段糅合了很多業(yè)務(wù)邏輯，在提高代碼閱讀的難度同時(shí)，也相應(yīng)加快的優(yōu)化效率。在優(yōu)化過程中，PostgreSQL會(huì)不間斷地做常量折疊、PathKey去重、Union打平、子查詢打平……這些操作不會(huì)應(yīng)用在memo里。
對(duì)比 Calcite/Orca ，PostgreSQL 的優(yōu)化更快，更適合事務(wù)性場(chǎng)景。不過我無法判斷 Calcite/Orca 在做了適當(dāng)?shù)募糁蛢?yōu)化規(guī)則糅合后，是否也能支持事務(wù)場(chǎng)景。
原文鏈接
本文為云棲社區(qū)原創(chuàng)內(nèi)容，未經(jīng)允許不得轉(zhuǎn)載。
總結(jié)
以上是生活随笔為你收集整理的PostgreSQL 优化器代码概览的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 浅谈 Spark 的多语言支持
- 下一篇： AutoML数据增广