PgSQL · 源碼分析 · PG 優化器中的pathkey與索引在排序時的使用

sql在postgresql中的處理，是類似于流水線方式的處理，先後由：

詞法、文法解析，生成解析樹後，将其交給語義解析

語義解析，生成查詢樹，将其交給planner

planner根據查詢樹，生成執行計劃，交給執行器

執行器執行完成後傳回結果

資料庫優化器在生成執行計劃的時候，優化器會考慮是否需要使用索引，而使用了索引之後，則會考慮如何利用索引已經排過序的特點，來優化相關的排序，比如order by / group by等。

先來看個索引對order by起作用的例子：

由此可見，通過索引進行查詢後，是可以直接利用已經索引的有序需不需要再次進行排序。

本文将介紹優化器如何在已有索引的基礎上，優化排序的。

資料庫以流水線的方式處理sql請求，當一個sql到來後：

以sql中select語句的基本表達形式為例：

為了表示一個select的語句，語義解析之前是selectstmt結構，其中包括targetlist、from 子句、where子句、group by子句等。

在語義解析之後，會引入一個query結構，該query結構隻表示目前語句中的内容，并不直接包括需要遞歸的子句，比如子查詢(子查詢用rangetblentry描述，存放在query->rtable清單中)等。在query之後，優化器根據其中的内容生成reloptinfo，作為整個執行計劃的入口。

query 結構如下，此處我們着重關注rtable和jointree：

在query中，此次最關注的是由$tables_or_sub_queries解析得來的query->rtable。query->rtable是一個rangetblentry的清單，用于表示$tables_or_sub_queries中的以下幾種類型：

表

子查詢，表示出另外一個子句，但不包含子句中的query，而是由rangetblentry中的subquery來描述其對應的query

join，除了将join相關的表添加到query->rtable外，還會加入一個rangetblentry表示join表達式用于後面的執行計劃

函數

同時也會添加到相應的parsestate->p_joinlist，後轉換為fromexpr作為query->jointree。後面的執行計劃生成階段主要依賴query->jointree和query->rtable用于處理pathkey相關的資訊。

在sql的操作中，幾乎所有的操作（比如查詢）最終都會落在實際的表上，那麼在執行計劃中表的表示就比較重要。postgresql用reloptinfo結構體來表示，如下：

事實上，reloptinfo是執行計劃路徑生成的主要資料結構，同樣用于表述表、子查詢、函數等。

在sql查詢中，join是最為耗時，執行計劃的生成首先考慮join。是以，整個執行計劃路徑的入口即為一個join類型的reloptinfo。當隻是單表的查詢時，則執行計劃入口為這張表的reloptinfo。

執行計劃的生成過程，就是從下往上處理到最上層的reloptinfo->pathlist的過程，選擇有成本較優先節點、删除無用節點，最後得到一個成本最優的執行計劃。

在整個過程中，大約分為以下幾步：

擷取表資訊

建立表reloptinfo，将所有該表的掃瞄路徑加入到該表的reloptinfo->pathlist

建立join的reloptinfo，将所有可能的join順序和方式以path結構體添加到reloptinfo->pathlist

針對join的reloptinfo，添加group by、order by等節點

執行計劃一開始，即首先将擷取所有的表資訊，并以reloptinfo（baserel）存放在plannerinfo結構體中的simple_rel_array中，如reloptinfo中的indexlist用于表示這張表的索引資訊，用于判斷是否可以用上索引。

為每張表建立掃瞄路徑，一般有順序掃瞄和索引掃瞄兩種。掃瞄路徑用path結構體來表示，并存放在該表對應的reloptinfo->pathlist中。path結構體如下：

在添加表的掃瞄路徑時，會首先添加順序掃瞄（seqscan）到這張表的reloptinfo->pathlist，保證表資料的擷取。而後考慮indexscan掃瞄節點等其他方式。

當reloptinfo->indexlist滿足reloptinfo->baserestrictinfo中的過濾條件，或滿足reloptinfo->joininfo等條件時，則認為index是有效的。然後根據統計資訊（如過濾性等）計算成本後，建立index掃瞄節點。

在建立index掃瞄節點時，根據索引建立時的情況（排序順序、比較操作符等），建立pathkeys的清單（可能多個字段），存放在indexpath->path->pathkeys中。pathkeys的結構體如下：

事實上，pathkeys可以用于所有已排過序的reloptinfo中，用于表示這個表、函數、子查詢、join等是有序的，作為上層判斷選擇path的依據之一。

在建立除seqscan之外的其他節點時，會與pathlist中已有的每個節點根據啟動成本和總體成本做對比（相差在一定比值，預設1%），則分為四種情況：

建立節點和已有節點，其中一方啟動成本和總成本都更優，且其pathkeys也更優，那麼删除另外一個

建立節點和所有已有節點的啟動成本和總成本兩方面的對比不一緻（如總成本高但啟動成本較低，或反過來），且建立節點總成本較低，則會全部保留并添加到reloptinfo->pathlist中。

新節點和已有節點，其中一方啟動成和總成本都更優，但其pathkeys不夠，則兩者都保留，由上層path節點來判斷

當建立節點和已有節點成本相同時，則對比兩者的pathkeys，選擇保留更優pathkeys的節點

此時，即完成一張表所有的path的生成，儲存在該表的reloptinfo->pathlist中，并從中選擇一條成本最低的path，作為reloptinfo->cheapest_total_path。索引掃瞄節點的pathkeys将會被上層路徑在與排序相關節點中用到，如order by、group by、merge join等。

join節點生成的算法較為複雜，簡單來說，會針對所有參與join的表，動态規劃不同的順序和join方式，然後生成不同的path加到這個join的reloptinfo->pathlist中。

在完成join的各個路徑判斷後，針對各路徑選擇成本最低的path（表的join順序和join方式）作為最優路徑，并依據這個路徑上的pathkeys處理order by、group by等其他子句的計劃，進而完成最終的執行計劃。

在前面的介紹中，每張表的reloptinfo->pathlist中的indexscan的path都帶有pathkeys資訊，即表明這個節點執行完之後的結果是按pathkeys來排序的。那麼在以下幾個地方則可以用到該特性：

merge join

在建立join節點時，會有多種join方式可以選擇，如nestloop、merge join等。當建立了merge join節點之後，一般是需要對兩張表進行排序。但當某張表的掃瞄節點傳回的是有序的，且該順序與查詢所需完全一緻，則會去除這個排序節點，進而在成本上占據優勢。

order by

當最終的reloptinfo節點建立完成後，會拿表reloptinfo->pathlist中成本最低的path，與帶有pathkeys的path做成本上的對比，選擇成本更低的路徑。如果最終是pathkeys的路徑，那麼該reloptinfo的pathkeys會保留。

若該sql語句中帶order by，則可以判斷該reloptinfo的pathkeys是否對order by（字段和排列順序一緻），則不必再建立order by節點。如果pathkeys沒有幫助，則會建立排序節點

group by

group by有多種方式。如果reloptinfo中的pathkeys與在解析階段産生的group by的pathkeys一緻，則從成本上對reloptinfo結果集的pathkeys對該group by是否有效，進而可以考慮選用sort加agg的方式。這種方式，因為pathkeys的存在，則不必再建sort 節點。然後再對比與其他方式的成本，擇優采用。

子查詢

如果join中包含子查詢，那麼則在join的reloptinfo->pathlist中添加一個subquery類型的path，并把子查詢中的排序的結果指定為pathkeys放在該path中。進而上層節點，可以用上面同樣的方法，選用該reloptinfo中最優的path，并根據pathkeys決定是否需要排序。

通過以上表述，可以說明一條sql語句的執行計劃入口是一個reloptinfo結構，其中成員pathlist則标示所有不同的查找路徑，在這些路徑中最終會落在表的reloptinfo->pathlist中最優的path中。如果該path帶有pathkeys，那麼上層在處理ort相關的操作時，可以根據pathkeys是否對排序有效而決定是否需要排序節點，進而選擇成本更低的路徑。