PostgreSQL優(yōu)化器的示例分析

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

簡(jiǎn)介

PostgreSQL 的開發(fā)源自上世紀(jì)80年代，它最初是 Michael Stonebraker 等人在美國國防部支持下創(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語言實(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)在今天仍然是值得借鑒的，包括：

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

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

3. 強(qiáng)一致的cardinality estimation保證

本文嘗試快速地瀏覽一遍 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ù)語解釋

1. Datum

2. Qual

3. Path

關(guān)鍵數(shù)據(jù)結(jié)構(gòu)

查詢

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

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

執(zhí)行計(jì)劃

1. __PlannedStmt__: 執(zhí)行計(jì)劃的頂層節(jié)點(diǎn)

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

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

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

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

主流程

子查詢上拉

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

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

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

EquivalenceClass解析

Equivalence Class（EC）是 qual 的術(shù)語，它指代的是 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)景包括：

1. 在 Join 時(shí)，EC用來決定 Join Key，它決定了 Outer Join 簡(jiǎn)化和PathKey設(shè)定

2. 在 Join 時(shí)決定 qual 穿越

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

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

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 有三種算法：

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

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

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

默認(rèn)在12路及以上的復(fù)雜Join中會(huì)打開GEQO?？梢栽趐ostgresql.conf中修改參數(shù)

geqo = on
geqo_threshold = 12

控制GEQO設(shè)定。

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

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

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

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

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

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

2. 它對(duì) a-b/b-a 鏡像去重，同時(shí)當(dāng)EC存在時(shí)不考慮笛卡爾積，這些工程上的降級(jí)有效降低了搜索復(fù)雜度

路徑生成和動(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），考慮：

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

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

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

有趣的點(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àn)镃語言本身不容易擴(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)帶來的?，F(xiàn)代的優(yōu)化器基本都是Volcano Model[2]的（例如SQL Server和Oracle，就像他們聲稱的那樣），而 PostgreSQL 沒有實(shí)現(xiàn)為 Volcano Model 這種 Generic purpose，pluggable 的形式。影響包括：

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

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

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

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

1. 可定制的Join重排算法

2. 可定制的PathKey生成算法

3. 定制的Join Path生成算法

等等。

性能

雖然沒有實(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)景。

以上是“PostgreSQL優(yōu)化器的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！