基于PostgreSQL解析器模塊的底層研究與分析

曹 陽，張 冰

(1.同濟大學 電子信息與工程學院，上海 201804；2.煤炭科學研究總院經濟與信息研究分院，北京 100013)

PostgreSQL[1]始自于美國加州大學伯克利分校的數據庫研究計劃“Ingres項目”，最早被命名為 Postgres。歷經多年的改善和發展，于2006年成立了EnterpriseDB公司，其目的為了讓PostgreSQL能更好更方便地為企業級用戶服務。現在，PostgreSQL數據庫已經成為當今世界上特色最鮮明、功能最強大、內容最豐富和開發人員最多的開源數據庫系統之一，是一種復雜的關系型數據庫管理系統(ORDBMS)。它的很多特性正是當今許多商業數據庫的前身。

PostgreSQL數據庫支持多版本并發控制，可以支持所有廣為使用的SQL結構，并且兼容時下最流行的計算機開發語言，如 C、C++、Java、Perl等。與其他主流數據庫一樣，PostgreSQL擁有諸多現代數據庫特征，其特征特性涵蓋了SQL-2/SQL-92和SQL-3/SQL-99。作為一款開源軟件，PostgreSQL數據庫不斷被完善，擁有如下諸多優勢：

(1)事務支持更徹底。對擁有海量存儲的數據庫，若一個查詢請求長時間運行無果，就很可能會導致阻礙表的更新。MySQL對于無事務的MyISAM表所采取的處理方式為“表鎖定”，而PostgreSQL則根本不存在這類問題。

(2)完美支持存儲過程。通過存儲過程，PostgreSQL便能輕松完成商業邏輯封裝，極大減少了服務器的運轉負荷。獨有的內在機制會自行優化設計原存儲過程，最大限度地避免傳輸大量原始查詢語句，從而提高運行效率。

(3)支持子查詢和觸發器。使用子查詢語句使得PostgreSQL在高效運行的同時，擁有更高的程序可讀性；而觸發器則更有利于其商業邏輯封裝，可減少應用程序對同一商業邏輯的重復控制，從而保證數據的完整性。

(4)支持多種特殊數據類型和自定義擴展需求。一般來說，特殊行業的數據會比商業數據更為復雜多變，而PostgreSQL將多維數據的集合體描述成一個對象類型，并作為屬性存儲在表中。這樣能保證用戶自定義數據類型與原有操作符運算規則一致，并兼容現有數據類型。

盡管PostgreSQL有著無可比擬的優勢，但仍不可避免地存在缺點。如其穩定性和效能上有待提高；欠缺一些高端數據庫管理系統所需要的特性 (如聯機熱備份、數據庫集群等)。

1 PostgreSQL開源數據庫的體系架構

就架構技術而言，PostgreSQL數據庫采用了經典的客戶端/服務器(Client/Server)模型，其客戶端進程與服務器端進程一一對應。很多工作經由客戶端處理后再提交給服務器，極大地提高了客戶端的響應速度，從而充分發揮客戶端的處理能力。

PostgreSQL查詢語句的執行流程如圖1所示。當出現查詢連接請求時，主進程(Main)派生一個服務器監聽進程 (Postmaster)，以等待從TCP/IP端口送入的連接請求。客戶應用端通過調用庫函數(Libpq)發出連接請求，并把用戶請求反饋給Postmaster，后者派生出后臺服務進程(Postgres)，使其與客戶端進程直接對接(Libpq僅支持一個客戶端進程對接多個后臺服務進程)。隨后，客戶端進程和后臺服務進程不通過Postmaster而直接通信。Postmaster和Postgres運行在數據庫服務器中，而客戶端應用則可運行在任何機器上。服務器進程之間利用信號標志和共享內存進行通信，確保并發數據訪問過程的數據完整性。一個查詢請求經歷的完整過程可分為5個階段：

(1)連接階段：客戶端向服務器發出查詢請求，通過Postmaster與Postgres建立通信對接。

(2)解析階段：解析器分析查詢請求，核對語法無誤后創建一個查詢樹。

(3)重寫階段：在系統目錄(pg_rewrite)中匹配重寫規則，重寫系統根據規則體進行重寫轉換，隨后創建解析樹作為結果輸出。

(4)優化階段：優化器根據解析樹創建查詢規劃。首先確定同一查詢結果的所有查詢路徑，然后計算不同查詢路徑的執行成本并選擇最優路徑，最后將其拓展為完整查詢規劃樹。

(5)執行階段：執行器對查詢規劃樹進行遞歸掃描，按其指定的執行方式檢索數據記錄。在掃描關系時，使用存儲系統執行排序和連接操作，計算條件后反饋最終查詢結果[2]。

2 PostgreSQL解析器模塊的內部結構

PostgreSQL數據庫的解析器模塊由解析器和轉換處理器組成。解析器又分為詞法分析器和語法分析器兩部分，分別由 lex和 yacc創建，定義在 scan.l和 gram.y中。解析器生成原始解析樹(即為一種數據結構)后，轉換處理器再對其進行修正和增補，最終生成查尋樹。

詞法分析器(yylex())的主要功能是做查詢語句詞法檢測，用來識別其中的標識符、SQL關鍵字等。它對每個關鍵字或標識符都會生成一個標記符號并將該標記結果反饋至語法分析器。語法分析器(yyparse())主要功能是對查詢語句做語法檢測。它由一套語法規則和觸發規則組成，當任意一條規則被觸發時，兩者將被執行。

圖1 PostgreSQL查詢語句的執行流程

所謂語法語義解析，即將來自庫函數的SQL查詢請求轉化為解析樹，供優化器/執行器或指令集使用。在解析階段，當以ASCII碼組成的查詢字符串到達解析器后，首先對其執行詞法分析，將其轉換為解析器所能識別的關鍵字、標識符和常量；再執行語法分析，檢查該查詢字符串的語法的有效性，并生成命令形式的查詢結構(即解析樹)。若語法正確，解析器將會反饋生成的解析樹；若語法錯誤，則返回一個錯誤標志或空值；隨后，解析樹被分離、檢查和傳送到指令集中的處理函數，或轉換為結點鏈表供優化器/執行器處理。

在解析器階段，解析器只依據與SQL語法結構相關的固定規則創建解析樹。由于自身不會自動查詢任何系統目錄，因此就不能理解查詢語句的詳細語義。故查詢語句被轉換為解析樹后，轉換處理器將對其做進一步處理，分析查詢語句所引用的表、函數和操作符的語義，然后生成查詢樹 (Query Tree)，用來表示解析樹具體信息的數據結構。把原始解析(僅包含查詢語句的原始信息)和語義分析分成兩個過程是因為系統目錄查詢操作只能在一個事務中執行，并且無法在接收到查詢字符串后就立即發起一個事務。服務器一旦確認正在處理一個查詢操作，那么就可以發起一個事務。此時，轉換處理器才能被順利調用。

從數據結構來說，轉換處理器生成的查詢樹與原始解析樹十分類似，但是結構細節上仍有差異。例如：在一個解析樹中，一個FuncCall節點可能在語句構成上被理解為函數調用功能，也可能根據引用名是普通函數還是聚合函數被轉換成FuncExpr節點或Aggref節點。類似地，查尋樹也可能添加了具體數據類型的信息(如相關字段或表達式)。本文以transformFuncCall調用為例：

(1)對每一個參數調用transformExpr；

(2)調用 ParseFuncOrColumn：

①調用ParseComplexProjection辨別Column Projection函數：關系型參數和復合類型參數。

②調用 func_get_detail(普通函數)：

·調用 FuncnameGetCandidates，在 Cache PROCNAMEARGSNSP中找到符合查詢條件的候選函數列表FuncCandidateList；

·返回無需做參數類型轉換的項；

·若只有一個參數，則嘗試對系統未定義的類型轉換型函數做二進制兼容的強制轉換；

·若為一般函數，則在候選函數中找最匹配函數func_match_argtypes；

·嘗試解決存在的沖突調用func_select_candidate；

·返回值。

③依據返回值采取相應措施；

④生成相應節點并返回：FuncExpr節點或Aggref節點[1]。

3 PostgresSQL解析器模塊的源碼剖析

PostgreSQL開源數據庫的源代碼相對路徑為Postgresqlsourcesrcackend，其代碼整體編譯流程大致如下：PostgresSQL在exec_simple_query函數中處理與用戶交互的簡單查詢請求，其查詢操作使用兩種協議：Simple query protocol和 Extended query protocol。 Extended query protocol包含 Parse、Bind、Execute三個步驟， 并定義了Prepared Statement和 Portal兩種重要數據結構。Prepared Statement用來表示詞法解析、查詢規劃等結果，Portal用來表示可以被執行或已部分執行完畢的語句。由于本文側重研究解析階段，故只對Simple query protocol協議進行具體分析，第三步生成物理查詢規劃和第四步執行物理規劃由于不是本文的側重點在此不贅述。

(1)編譯查詢

通過pg_parse_query函數返回一系列查詢解析樹，并生成列表文件parsetree_list。具體工作由raw_parse函數通過調用base_yyparse函數對查詢語句進行詞法分析完成。

(2)生成邏輯規劃與查詢重寫(QueryRewrite)

通過語義分析將已有解析樹轉化為所需查詢規劃，建立最優查詢規劃。具體由pg_analyze_and_rewrite函數調用parse_analyze函數轉換完成。部分代碼如下：

再執行parse_analyze函數中的query=transformStmt(pstate，parseTree)；最后， 通過調用語句 querytree_list=pg_rewrite_query(query)；完成查詢重寫。pg_rewrite_query函數通過調用查詢重寫器的入口函數QueryRewrite來完成操作，而查詢重寫的作用就是根據系統或用戶自定義規則來重寫規劃。

PostgreSQL解析器模塊所接受的查詢請求表現形式為查詢字符串，經過解析生成原始解析樹，并返回列表文件(parsetree_list)，其每一個節點都是一個完整的語法解析樹。一個原始解析樹由多個節點構成，一個節點表示一個類型(由NodeTag定義)。PostgreSQL解析器模塊內部函數調用關系如圖2所示。

圖2 PostgreSQL解析器模塊內部函數的調用模型

解析器模塊有3個主要函數，分別是：raw_parser()、free_parser()和 filtered_base_yylex()， 可 以 在.ParserParser.c文件中找到其定義。下面就其主要源碼進行剖析和理解：

輸入：為輸入的查詢字符串定義一個指向字符常數的指針。

功能：掃描查詢字符串并返回相應值。

返回值：若無語法錯誤，則建立解析樹(Parser Tree)，并將查詢語句存儲在該解析樹中；否則，向解析器返回空指針(NIL)。

輸入：為所給字符串定義一個指向字符常數的指針。

功能：獲取所給字符串的值。

返回值：base_yylval.str；

調用函數：scanner_init()； base_yylex()； scanner_finish()。

(3)filtered_base_yylex()filtered_base_yylex(void)

{

Int cur_token；

…

return cur_token；

}

輸入：無輸入值。

功能：作為解析器的中間件，對查詢語句執行優化處理，過濾部分累贅語句。例如：當查詢語句存在多個空字符時，該函數會自動將其合并。

返回值：無返回值。

調用函數：base_yylex()。

(4)free_parser(void)

輸入：無輸入值。

功能：釋放已生成的語法解析樹所占用的內存空間。

返回值：無返回值。

調用函數：pool_memory_delete()。

對查詢語句做轉換處理是為了把生成的解析樹都轉換成根為Query型節點的查尋樹。轉換處理工作在parse_analyze函數中進行：首先定義ParseState*pstate函數，用以記錄轉換處理過程中的狀態信息，然后調用transformStmt函數進行正式的轉換處理工作，它會根據解析樹不同類型的根節點調用相應的函數。部分代碼如下：

Select statement分為簡單型和復合型。復合型內含集合操作符，在這種語法樹中，Select語句都處于葉節點位置，而內部節點則表示集合操作符。簡單型也可分為兩類：一類有VALUES，一類無VALUES。

把原始解析樹轉換處理到查尋樹的目標就是為了從系統關系表中得到相關信息并據此進行相關節點的轉換和信息添加。得到了查尋樹后，它將被執行重寫、優化、執行等操作，至此完成了一次完整的查詢請求。

4 PostgreSQL子查詢調試

由于PostgreSQL是個開源數據庫，可以支持多種操作系統的編譯與執行。本文選用以Linux為內核的Ubuntu v11.04作為調試環境，其內核版本為2.6.38-8-generic。操作系統加載的PostgreSQL版本為v8.4.8。搭建系統中，所選用的調試工具為DDD，其版本號為v3.3.12。所選用編譯器為gcc，其版本為v4.4.5，庫版本為GNU libc v2.12。

執行子查詢調試步驟如下：

首先，在PostgreSQL數據庫中建立一張新表，表名為“film”，該表中存放電影相關信息字段：

然后，再在數據庫中建立第二張表，表名為“cinema”，該表中存放有某一部電影的放映信息：

在所建的兩張表中，同時建立了B-tree類型的索引。B-tree索引主要處理那些按照某種順序存儲的數據查詢，它能為索引的每個列(字段)聲明一個操作符表。PostgreSQL的create index語句一般都默認使用B-tree索引類型。

最后，再新建一張鏈接表，表名為“announcement”。該表通過建立外部關鍵字(foreign key)鏈接生成，主要用來顯示所需要查詢的某部電影的相關信息：

在更改好表 “announcement”中的相關字段屬性后，通過新建視圖表來完成所查詢請求，并顯示相關結果：

子查詢的結果如下：

該結果中，字段 fid即為表“film”中的 id字段，每一個id字段值對應唯一一部電影；字段cid即為表“cinema”中的id字段，每一個字段值所對應的電影都被標示著相應的放映信息。在本次查詢請求的建立表中，表 “cinema” 中的字段 id=1所對應的 cinema=Wanda，即表示所進行的查詢請求就是顯示所有在萬達影城播放的電影信息。更多具體電影和放映信息在表中略去，但通過增加字段來完整顯示即可。

PostgresSQL開源數據庫目前已被成功應用于包括醫療、電子商務等在內的廣闊領域中。經過二十多年的快速發展，PostgreSQL的內部結構和工作機制已經相當成熟，直到今天依然在全球眾多開源程序員的努力中不斷地被改進和優化。

本文主要對PostgreSQL開源數據庫的解析器做了底層研究并對該模塊的源碼做了一定分析，并通過一個子查詢調試實驗實現了一個基本的查詢請求。針對PostgreSQL開源數據庫的源碼分析在國內尚處起步階段，而源碼分析對深入理解PostgreSQL開源數據庫的開發思想有著里程碑的意義。

[1]PostgreSQL中文之家.[2010-05].http：//www.pgsqldb.org.

[2]The PostgreSQL GlobaldevelopmentGroup.PostgreSQL 8.4.8 documentation[S/OL].(2010-05-17)[2011-04-02].http：//www.postgresql.org/docs/8.4/static/index.html.

[3]陳景峰.PostgreSQL實用實例參考 [R/OL](2004-5-20).[2011-04-20].

[4]郭龍江，李金寶.PostgreSQL分析器的研究[J].黑龍江大學自然科學學報，2001，18(4)：49-52.

[5]DOUGLAS K， DOUGLAS S.PostgreSQL： the comprehensive guide to building， programming， and administering PostgreSQL databases， second edition[M].[S.l.]： Sams Publishing，2005.

[6]陳文星，付繼宗.Linux下數據庫PostgreSQL分析與應用[J].電腦開發與應用，2006，19(11)：56-57.