PostgreSQL7.0手冊-開發者手冊 -61. PostgreSQL 內部概貌
2019-09-08 23:34:07
供稿：網友
第六十一章. PostgreSQL 內部概貌
內容
查詢的過程
聯接是如何建立起來的
分析器階段
Postgres 規則系統
規劃器/優化器
執行器
作者：本章最初是做為 Simkovics, 1998 的一部分出現的，它是 Stefan Simkovics 在 維也納理工大學準備的碩士論文，是由 O.Univ.Prof.Dr. Georg Gottlob 和 Univ.Ass. Mag. Katrin Seyr 指導的。
本章給出了 Postgres 后端服務器的內部情況的一個概貌。在閱讀完畢下面的章節后，你應該對如何處理查詢有一個概念了。不過別指望我們在這里有詳細的描述（我想，要對Postgres 里面所有的數據結構和函數都做這樣的詳細描述可能要超過 1000 頁的內容?。?。本章只是試圖幫助我們了解在后端里面從受到查詢到發出結果之間的通常的控制和數據的流動?！?
查詢的過程
下面是一個簡短的描述一個查詢從開始到得到結果要經過的階段。
首先必須先建立起從應用程序到 Postgres 服務器的聯接。應用程序想服務器發送查詢然后接收從服務器收到的結果?！?
分析階段（parser stage）檢查從應用程序（客戶端）發送過來的查詢，核對語法并創建一個查詢樹（query tree）。
重寫系統（rewrite system）接收分析階段來的查詢樹并且搜索任意應用到查詢樹上的規則（rules）（存儲在系統表里）并根據給出的規則體（rule bodies）進行轉換。重寫系統的一個應用在視圖（views）的實現里給出了?！?
當一個查詢訪問一個視圖時（也就是說，一個虛擬表（virtual table）），重寫系統改寫用戶的查詢，使之成為一個訪問帶有視圖定義（view definition）的基本表（base tables）的查詢。
規劃器/優化器（planner/optimizer）接收（改寫的）查詢樹然后創建一個查詢規劃（queryplan），這個查詢規劃是執行器（executor）的輸入。
它（規劃器/優化器）首先創建所有得出相同結果的可能的 路徑（paths）。例如，如果待掃描的關系上有一個索引，那么掃描的路徑就有兩個。一個可能是簡單的順序查找，而另一個可能就是使用索引的那個。下一步是計算出每個索引執行的開銷，并且選擇和返回開銷最少的那個?！?
執行器遞歸地走過規劃樹（plan tree）并且在這個過程中檢索規劃所代表的記錄。執行器在對關系進行掃描時使用存儲系統（storage system），進行排序（sorts）和聯接（joins），計算條件（qualifications）并且最終交回生成的記錄。
在隨后的章節里，我們將對上面的每一個步驟進行更詳細的討論，以便讓我們對Postgres 的內部控制和數據結構有一個更準確的理解。
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
聯接是如何建立起來的
Postgres 是用一個簡單的"每用戶一進程"的client/server 模型實現的。在這種模式里一個客戶端進程只是與一個服務器進程聯接。因為我們不知道具體要建立多少個聯接，所以我們不得不利用一個主進程 在每次聯接請求時派生出一個新的服務器進程來。這個主進程叫做 postmaster，它監聽著一個特定的 TCP/IP 端口等待進來的聯接。每當檢測到一個聯接請求時，postmaster 進程派生出一個新的叫 postgres 的服務器進程。服務器任務（postgres 進程）相互之間使用信號燈和共享內存進行通訊，以確保在并行的數據訪問過程中的數據完整性。圖 /ref{connection} 顯示了主進程 postmaster，服務器進程 postgres 和客戶端應用之間的相互關系?！?
客戶端進程要么是 psql 前端（用于交互的 SQL 查詢）或者是任意用 libpg 庫實現的用戶應用。請注意用 ecpg（Postgres 用于 C 的嵌入 SQL 預處理器）實現的應用同樣也使用這個庫?！?
一旦建立起來一個聯接，客戶端進程就可以向后端服務器進程發送查詢了。查詢是通過純文本傳輸的，也就是說在前端（客戶端）不做任何分析處理。服務器分析查詢，創建執行規劃，執行該規劃并且通過已經建立起來的聯接把檢索出來的記錄返回給客戶端。
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
分析器階段
分析器階段（ parser stage?。┌瑑蓚€部分：
在 gram.y 和 scan.l 里定義的分析器是使用 Unix 工具 yacc 和 lex 制作的?！?
轉換處理對分析器返回的數據結構進行修改和增補。
分析器
分析器必須檢查（以純 ASCII 文本方式到來的）查詢字串的語法。如果語法正確，則創建一個分析樹并將之傳回，否則，返回一個錯誤。在這個實現里我們使用了著名的 Unix 工具 lex 和 yacc?！?
lexer?。ㄔ~法）在文件 scan.l 里定義，負責識別標識符，SQL 關鍵字等。對于發現的每個關鍵字或者標識符都會生成一個記號并且傳遞給分析器?！?
分析器在文件 gram.y 里定義并且包含一套語法規則和觸發規則時執行的動作。動作代碼（實際上是 C 代碼）用語建立分析樹?！?
文件 scan.l 用 lex 轉換成 C 源文件而 gram.y 用 yacc 轉換成 gram.c。在完成這些轉換后，一個通用的 C 編譯器可以用于創建分析器。千萬不要對生成的 C 源文件做修改，因為下一次調用 lex 或 yacc 會把它們覆蓋?！?
注意：上面提到的轉換和編譯是使用跟隨Postgres 發布的 makefiles 自動完成的。
對 yacc 或者 gram.y 里的語法規則的詳細描述超出本文的范圍。有很多關于lex 和 yacc 的書籍和文檔。你在開始研究 gram.y 里給出的語法之前，你應該對 yacc 很熟悉，否則你是看不懂那里面的內容，理解不了發生了什么事情的。
為了更好地理解處理一個查詢時 Postgres 里使用的數據結構，我們用一個簡單的例子演示在每個階段數據結構所做的改變?！?
例 54-1. 一個簡單的選擇（Select）
這個例子包含下面的簡單的查詢，這個例子將會在本章剩余各節的所有描述和圖示里出現。該查詢假設在Supplier Database 數據庫里的表已經定義了。
select s.sname, se.pno
from supplier s, sells se
where s.sno > 2 and s.sno = se.sno;
圖 /ref{parsetree} 顯示了 gram.y 里的語法規則和動作為查詢 一個簡單的 Select 這個例子包含下面的簡單查詢，該查詢將被用于隨后各個階段的各種描述和圖片．這個查詢假設在供應商數據庫里的表已經定義了． select s.sname, se.pno from supplier s, sells se where s.sno > 2 and s.sno = se.sno; 構建的分析樹（不帶用于 where 子句的操作符樹，它在圖/ref{where_clause}里顯示，因為在一幅圖里沒有足夠的位置把兩部分的數據結構都放進去）?！?
樹的頂端節點是 SelectStmt 節點。對每個在 SQL 查詢的 from子句里出現的元素創建一個 RangeVar 節點，存放 alias（別名）的名稱和一個指向一個存放關系名稱的RelExpr 節點的指針。所有 RangeVar 節點都收集到一個列表里，然后附加到 SelectStmt 節點的 fromClause 字段上?！?
對于 SQL 查詢里面的 select列表 里出現的每個元素都創建一個 ResTarget 節點，存放一個指向 Attr 節點的指針。Attr 節點存放元素的關系名稱和一個指向存放著字段名稱的 Value 節點的指針。所有 ResTarget 節點都收集到一個列表里，然后鏈接到 SelectStmt 節點的 targetList 字段里?！?
圖 /ref{where_clause} 顯示了為例子 select s.sname, se.pno from supplier s, sells se where s.sno > 2 and s.sno = se.sno; 里 SQL 查詢的 where 子句構建的操作符樹，這個操作符樹附加到了 SelectStmt 節點的字段 qual 上。操作符樹的頂端節點是一個代表 AND 操作的 A_Expr 節點。這個節點有兩個后繼節點， lexpr 和 rexpr 分別指向兩個子樹。附加到 lexpr 的子樹代表條件 s.sno > 2 而附加到 rexpr 的子樹代表 s.sno = se.sno。為每個字段創建一個 Attr 節點，存放關系名和一個指向存放著字段名的 Value 節點的指針。為在查詢里出現的常量條款創建一個 Const 節點，存放常量值。
轉換處理
轉換處理把分析器傳遞過來的分析樹作為輸入，然后遞歸地處理它。如果碰到一個 SelectStmt 節點，就把它轉換成一個 Query 節點，這個節點將是新數據結構的最頂端節點。圖 /ref{transformed} 顯示了轉換過后的數據結構（轉換過后的 where 子句在圖 /ref{transformed_where} 里給出，因為一幅圖里放不下所有的部分）?！?
現在進行一個檢查，看看 FROM 子句里面的關系名是否被系統所知。為每個系統表里面出現的關系名創建一個RTE 節點，該節點包含關系名，別名和關系 id。從現在開始，關系 id?。俗R）用于指代查詢里出現的關系。所有RTE 節點都收集到范圍表項目列表（range table entry list）里，然后該列表在鏈接到 Query 節點的 rtable 字段上。如果查詢里面有一個不為系統所知的關系被檢測到，那么將返回一個錯誤然后查詢處理將退出?！?
下一步是檢查所用的字段名是否包含在查詢給出的關系里。為找到的每個字段創建一個TLE 節點，保存一個指向 Resdom 節點的（該節點里保存列名稱）的指針和一個指向 VAR 節點的指針。在 VAR 節點里有兩個重要的數字。數據域 varno 包含當前字段的關系在上面創建的范圍表項目列表里面的位置。數據域 varattno 給出該字段在關系里的位置。如果無法找到一個字段的名稱，則返回一個錯誤而且這個正在處理的查詢將退出。
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
Postgres 規則系統
Postgres 維持一個強大的規則系統，用以闡述視圖和不明確的視圖更新。最初Postgres規則系統包含兩個實現：
第一個能用的規則系統采用記錄級別處理，是在執行器深層實現的。每次訪問一條獨立的記錄時都調用規則系統。這個實現在1995年被刪除了，那時Postgres 項目的最后一個官方版本正轉換成 Postgres95?！?
第二個規則系統的實現從技術角度來說叫查詢重寫。重寫系統是一個存在于分析器階段和規劃器/優化器之間的一個模塊。這個技術實現仍然存在。
要獲取關于 Postgres 系統里規則的創建和語法的信息，請參考 PostgreSQL 用戶手冊?！?
重寫系統
重寫系統是一個存在于分析器階段和規劃器/優化器之間的一個模塊。它處理分析器階段傳回的分析樹（該分析樹代表用戶查詢），如果存在一條必須應用的規則的話，這個模塊把分析樹重寫成一個變化了的形式?！?
實現視圖的技巧
現在我們勾畫一下查詢重寫系統的算法。為了更好的說明問題，我們把用規則系統實現視圖作為一個例子?！?
先給出下面規則：
create rule view_rule
as on select
to test_view
do instead
select s.sname, p.pname
from supplier s, sells se, part p
where s.sno = se.sno and
p.pno = se.pno;
當檢測到對關系 test_view 的 select 時，就會觸發上面給出的規則。這時這句選擇語句將執行規則里的動作部分，而不是從 test_view 里選擇記錄?！?
給出下面的用戶對 test_view 的查詢：
select sname
from test_view
where sname <> 'Smith';
這里是當一個用戶查詢作用于 test_view 時，查詢重寫系統執行的一系列步驟。（下面的列表只是一個非常不正式的關于查詢重寫的算法的描述，只是用于了解基礎。更多的詳細描述請參考 Stonebraker et al, 1989）?！?
test_view 重寫
獲取在規則的動作部分給出的查詢。
調整其目標列表以便與用戶查詢給出的字段的數目和順序相匹配?！?
把用戶查詢的 where 子句里的條件部分追加到規則動作部分的查詢的條件上。
給出上面定義的規則后，用戶查詢將被重寫為下面的形式（請注意：重寫動作是對從分析器階段傳回的用戶查詢的內部形式操作的，不過所產生的新的數據結構將代表下面的查詢）：
select s.sname
from supplier s, sells se, part p
where s.sno = se.sno and
p.pno = se.pno and
s.sname <> 'Smith';
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
規劃器/優化器
規劃器/優化器的任務是創建一個優化了的執行規劃。它首先合并所有對出現在查詢里的關系的掃描和聯合的方法。這樣創建的所有的路徑都導致相同的結果，而優化器的任務就是計算每個路徑的開銷并且找出開銷最小的那條路徑。
生成可能的規劃
規劃器/優化器以查詢里出現的關系上定義的索引的類型為基礎，判斷應該生成哪些規劃。對一個關系總是可以進行一次順序查找，所以總是會創建只使用順序查找的規劃。假設一個關系上定義著一個索引（例如 B-tree 索引），并且一條查詢包含約束 relation.attribute OPR constant。如果 relation.attribute 碰巧匹配 B-tree 索引的關鍵字并且 OPR 又不是 '<>'，則將會創建另一個使用 B-tree 索引掃描該關系的規劃。如果還有別的索引，而且查詢里面的約束又和那個索引的關鍵字匹配，則還會生成更多的規劃?！?
在找完掃描一個關系的所有可能的規劃后，接著創建聯接各個關系的規劃。規劃器/優化器認為只有在每兩個關系之間存在聯接，對應地在 where 條件里存在一條 join 子句（也就是說，存在象 where rel1.attr1=rel2.attr2 這樣的約束）。規劃器/優化器為它們認為可能的所有的聯接關系對生成一個規劃。有三種可能的聯接策略：
嵌套的反復聯接（nested iteration join）：對左邊的關系里面找到的每條記錄都對右邊關系進行一次掃描。這個策略容易實現，但是可能會很耗費時間?！?
融合排序聯接（merge sort join）：在聯接開始之前，每個關系都對聯接字段進行排序。然后兩個關系融合到一起，認為兩個關系都對聯接字段進行了排序。這種聯合更有吸引力，因為每個關系都只用掃描一次?！?
哈希聯接（hash join）：右邊的關系首先對它的聯接字段進行哈希運算。然后掃描左邊的關系，并將找到的每條記錄的合適的值作為哈希鍵字用以定位右邊關系里的記錄。
規劃的數據結構
我們在這里對規劃里出現的節點做一些簡單描述。圖 /ref{plan} 顯示了為例子 /ref{simple_select} 里的查詢生成的規劃?！?
規劃的頂端節點是一個 MergeJoin 節點，它有兩個下級節點，一個附加在域 lefttree 上，而另一個附加在域 righttree 上。每個子節點代表一個聯接的關系。如上面所述，一個融合聯接要求每個關系先被排序。這就是為什么我們在每個子規劃里有一個 Sort 節點的原因。查詢里附加的條件（s.sno > 2）被盡可能地向下推，并且附加在對應的子規劃的葉節點 SeqScan 的 qpqual 域上?！?
附加在節點 MergeJoin 的域 mergeclauses 的列表包含關于聯接屬性的信息?！ergeclauses 列表里（還有 targetlist 里）出現的 VAR 節點的數據域 varno 的值 65000 和 65001 意味著不考慮當前節點的記錄，而是使用下一"更深"節點（也就是說，子規劃的頂端節點）的記錄?！?
請注意圖 /ref{plan} 里的每個 Sort 和 SeqScan 節點都有一個 targetlist，但因為空間不夠，只有 MergeJoin 節點的畫出來了?！?
規劃器/優化器執行的另一個任務是填補 Expr 和 Oper 節點里的操作符id。如上所述，Postgres 支持廣范圍的不同的數據類型，甚至可以使用用戶定義類型。為了能夠維護這些數目巨大的函數和操作符，有必要把它們存放在系統表里。每個函數和操作符有一個唯一的操作符 id。根據在資格條件等地方使用的字段的類型，必須選用合適的操作符 id。
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
執行器
執行器接收由規劃器/優化器傳遞過來的規劃，然后開始處理頂端節點。在我們給出的例子里面（在例子 /ref{simple_select} 里給出的查詢），頂端節點是一個 MergeJoin 節點。
在進行任何融合之前，首先要抓取兩條記錄（從每個子規劃里抓一條）。所以執行器遞歸地調用它自己以處理子規劃（它從附加在 lefttree 上的子規劃開始）。新的頂端節點（左邊子規劃的頂端節點）是一個 SeqScan 節點，同樣必須先抓取一條記錄然后才能處理節點本身。執行器再次遞歸地調用自身，處理附加在 lefttree 的 SeqScan 節點上的子規劃。
現在新的頂端節點是一個 Sort 節點。因此，要對整個關系進行排序。當第一次訪問 Sort 節點時，執行器開始從 Sort 節點的子查詢里抓取記錄并把它們在一個臨時關系里面（在內存或文件中）排序。（對 Sort 節點的進一步檢查將總是從排好序的臨時關系里返回一條記錄。）
每當處理 Sort 節點需要新的記錄時，都會為作為子規劃附加上來的 SeqScan 節點遞歸地調用執行器。然后對該關系（在內部通過數據域 scanrelid 給出的值引用）進行掃描，檢索下一條記錄。如果記錄滿足附加在 qpqual 上的條件樹則將其返回，否則抓取下一條記錄知道條件被滿足。如果處理到了關系的最后一條記錄，則返回一個 NULL 指針。
在 MergeJoin 的 lefttree 返回一條記錄后，用同樣方法處理 righttree。如果兩條記錄都存在了，執行器就處理 MergeJoin 節點。每當有一個子規劃需要一條新的記錄時，都進行一次執行器的遞歸調用以獲取記錄。如果可以創建一條聯合的記錄，那么就把這條記錄返回并且完成一次完整的規劃樹的處理。
現在，上面描述的步驟對每條記錄執行一次，直到對 MergeJoin 節點的處理返回一個 NULL 指針，表示我們已經處理完畢時為止。
------------------------------------------------------------------------------
