[ 永遠的UNIX > PostgreSQL7.0手冊-開發者手冊 -61. PostgreSQL 內部概貌 ]

[ 永遠的UNIX::UNIX技術資料的寶庫 ] GB | BIG5

首頁 > 數據庫 > 其它 > 正文

PostgreSQL7.0手冊-開發者手冊 -61. PostgreSQL 內部概貌

編譯：何偉平 laser@zhengmai.com.cn (2001-04-21 23:33:31)

第六十一章.　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　（標識）用指代查詢裡出現的關系。所有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　的列表包含關聯接屬性的信息。　mergeclauses　列表裡（還有　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　指針，表示我們已經處理完畢時為止。

--------------------------------------------------------------------------------

(http://www.fanqiang.com) 進入【UNIX論壇】

相關文章

===更多相關===

★ 樊強制作歡迎分享 ★