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

概要

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

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

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

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

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

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

先來看個索引對ORDER BY起作用的例子：

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

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

SQL的流水線處理

資料庫以流水線的方式處理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的表，動态規劃不同的順序和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是否對排序有效而決定是否需要排序節點，進而選擇成本更低的路徑。