資料庫高手昇華必經道路：解析PostgreSQL原始程式碼

01 PostgreSQL概述
1.1 概述
1.2 查詢敘述最佳化
1.3 建立查詢計畫
1.4 小結

02 基表資料結構
2.1 概述
2.2 資料結構
2.3 小結
2.4 思考

03 查詢分析
3.1 概述
3.2 問題描述
3.3 詞法分析和語法分析（Lex&Yacc）
3.4 抽象查詢語法樹AST
3.5 查詢分析
3.6 查詢重寫
3.7 小結
3.8 思考

04 查詢邏輯最佳化
4.1 概述
4.2 前置處理
4.3 查詢最佳化中的資料結構
4.4 查詢最佳化分析

05 查詢實體最佳化
5.1 概述
5.2 所有可行查詢存取路徑組成函數make_one_rel
5.3 小結
5.4 思考

06 查詢計畫的產生
6.1 查詢計畫的產生
6.2 產生查詢計畫—create_plan/create_plan_recurse
6.3 查詢計畫的閱讀
6.4 小結
6.5 思考

07 其他函數與基礎知識
7.1 AND/OR規範化
7.2 常數運算式的處理—eval_const_expressions
7.3 Relids的相關函數
7.4 List 的相關函數
7.5 中繼資料表Meta Table
7.6 查詢引擎相關參數設定

前言

　　隨著行動使用者的高速發展，「資料」已成為當今最寶貴的資源；誰掌握了資料，誰就掌握了無盡的寶藏。而如何有效地管理這些巨量資料則成為擺在人們面前的首要問題。從電腦出現以來，人們便孜孜不倦地追求著高效管理資料的辦法，IBM的System R，U.C. Berkeley PostgreSQL以及OracleMySQL的誕生，無一不表明人們對於高效、快速的資料管理的不懈追求。

　　雖然Oracle、MySQL廣泛應用於國內外各大網際網路公司的基礎架構中，但作為另一款優秀的開放原始碼關聯式資料庫，PostgreSQL同樣也獲得了各大網際網路公司的持續關注；另外隨著大數據平台對SQL標準支援的日益豐富，SQL on Hadoop的各種解決方案如雨後春筍般湧現，例如Hadoop Hive、Facebook Presto、Cloudera Impala等，這些SQL on Hadoop解決方案無一例外地需要一個表現優異的SQL查詢引擎的支援。

　　作為資料庫的大腦，查詢引擎的優劣直接決定了資料庫管理系統的好壞。不同的查詢引擎對相同查詢敘述的處理策略可能截然不同，而其導致的執行效率也差別很大，少則相差數倍，多則數百倍。因此，認真地分析設計優秀的查詢引擎並學習其查詢最佳化方法可以使我們能夠以「巨人肩膀之上」的方式來提升我們自己資料庫產品的查詢效率。

　　PostgreSQL為優秀的開放原始碼關聯式資料庫管理系統，其來自U.C.Berkeley，帶有濃郁的學術氣息，資料庫相關理論貫穿於整個PostgreSQL的設計和實現中，尤以查詢引擎更甚。目前，無論中文或是英文資料，對PostgreSQL查詢引擎的介紹非常缺乏，僅有的相關資料不是限於整體架構性的介紹，就是粗淺的概述性描述。對PostgreSQL查詢引擎中較多的實現及其相對應的理論基礎並無較為深入的說明，這使得很多相關核心開發人員初次閱讀查詢引擎原始程式時存在許多的學習困難和疑點。舉例來說，查詢引擎在子連結處理時的理論依據；Lateral Join的處理方法；限制條件下推時需滿足的條件；選擇率對查詢計畫的影響等。而這也正是作者最初在閱讀PostgreSQL查詢引擎原始程式時所經歷過的迷惑和不解。

　　本書的寫作初衷正是為了加快資料庫開發人員對PostgreSQL查詢引擎的學習過程以及減少相關人員在原始程式學習中的迷惑，同時本書也為那些想一窺查詢引擎究竟的DBA們提供一個相互學習的機會和通道，無論你是MySQL DBA 或是Oracle DBA。

　　讀者定位

　　本書嘗試以一種全新的角度列出對PostgreSQL查詢引擎的分析，筆者作為一名資料庫核心開發人員，了解核心開發人員關注的重點是什麼。因此，本書以一位核心開發人員和架構師的角度來探討如何設計並完成一個資料庫查詢引擎；資料庫查詢引擎在設計和實現過程中需要考慮哪些問題，又透過什麼樣的途徑和方法來解決這些問題。舉例來說，如何以資料結構來表示一條SQL查詢敘述？如何將SQL查詢最佳化理論應用到查詢引擎的實現中？相信讀者在閱讀本書後，能產生同樣的思考。

　　本書主要針對的受眾：首先是資料庫核心開發人員。無論你是MySQL開發人員還是PostgreSQL開發人員，亦或是Infomix開發人員。一個優秀的查詢引擎總是值得你花費一定的時間和精力進行研究並學習其設計和實現中的精華。其次，資料庫DBA們同樣也值得花費一定的時間和精力來閱讀和研究查詢引擎原始程式，所謂知彼知己，百戰百勝。只有更進一步地了解核心中的理論基礎和實現機制，我們才可能管理好資料庫。最後，對於那些對資料庫核心實現有興趣的相關人員，無論您是經驗豐富的老手還是初出茅廬的新手，我想本書也能夠為想要了解PostgreSQL查詢引擎的實現內幕的您提供一絲幫助。同樣，對於高年級的大學生或是低年級的所究所學生，相信本書也可作為您學習資料庫理論的有益補充。

　　當然，您在閱讀本書之前還需要有一些必要的知識：對SQL標準有必要的認識和了解；了解資料庫原理中的相關基本概念，例如查詢計畫、索引等；C/C++程式設計知識等。

　　章節編排

　　第1章以如何了解並執行查詢敘述為例，綜合性地描述PostgreSQL查詢引擎包含的相關模組以及各個模組的功能。

　　第2章從核心開發人員的角度出發重點介紹描述一條SQL查詢敘述需要的相關資料結構。

　　第3章主要討論對一條SQL查詢敘述的識別以及相關知識，並以此為基礎重點討論將該字串形式的SQL查詢敘述轉為查詢樹的過程。

　　第4章將以第3章中所獲得的查詢樹為基礎，討論如何對該查詢樹進行查詢邏輯最佳化。舉例來說，對SubLinks的最佳化處理，對SubQueries的處理，對運算式的最佳化，對限制條件的處理，對Lateral Join的處理，等等。

　　第5章以查詢中有關的基底資料表的物理參數為基礎，依據查詢代價來計算查詢敘述的最佳查詢存取路徑的方法，並對實體最佳化中使用的相關技術和理論基礎進行詳細的討論和分析。舉例來說，所有可行查詢存取路徑的求解策略，多表連接的處理策略，索引建立和選擇的策略，實體代價相關參數的分析，等等。

　　第6章以第5章中所獲得的最佳查詢存取路徑為基礎，重點討論如何依據該查詢存取路徑建置執行引擎所需的查詢計畫。舉例來說，順序掃描查詢計畫的建置，連接關係查詢計畫建置等。

　　第7章主要分析我們在原始程式閱讀過程中遇到的一些重要輔助函數。

　　錯誤說明

　　由於筆者水準有限，本書中可能存在一定的錯誤，例如筆誤、了解錯誤等，對於本書中出現的錯誤，讀者可以在www.leehao.org中查詢該錯誤的勘誤資訊，或發送郵件至hom.lee@hotmail.com與作者聯繫。筆者非常希望能夠與讀者共同進步，推動資料庫核心開發人員對PostgreSQL查詢引擎的認識。相比MySQL而言，PostgreSQL的相關資料非常少，而專門介紹PostgreSQL查詢引擎之類的資料則更加少，而這也是本書成書的原因。

　　學習資料

　　原始程式碼作為最好的學習資料，應該永遠值得我們認真對待和重視，本書所有分析均基於PostgreSQL 9.4.1版本。讀者可以在github.com/postgres/postgres中下載最新原始程式。當然，最新版本的原始程式可能與本書討論中列出的原始程式有所不同，但這並不影響我們對主題問題的討論。

　　為了解最新特性或想參與PostgreSQL核心開發，讀者可以訂閱PostgreSQL郵寄清單，其中包含開發人員郵寄清單、當地語系化相關郵寄清單、相關Bugs郵寄清單等。

　　■ www.postgresql.org/list/pgsql-cluster-hackers/叢集相關核心開發人員郵寄清單；
　　■ www.postgresql.org/list/pgsql-committers/核心commiters 郵寄清單，為核心日常技術問題討論，讀者可從中了解核心commiters的最新動態；
　　■ www.postgresql.org/list/pgsql-hackers/核心開發人員郵寄清單；
　　■ www.postgresql.org/list/pgsql-interfaces/相關介面討論郵寄清單，例如odbc、jdbc等；
　　■ www.postgresql.org/list/pgsql-docs/相關文件郵寄清單；
　　■ www.postgresql.org/list/pgsql-bugs/相關bugs郵寄清單。

　　相關郵寄清單並不限於上述幾種， 實際內容還請讀者參考www.postgresql.org/list/中列出的詳細資訊。

　　致謝

　　本書在撰寫過程中獲得了許多朋友的關心和幫助。首先，感謝北大方正資訊產業集團基礎軟體中心（上海）的同伴們：王博、王鑫、蔣燦、彭川、羅正海、黃誠一、劉慧娟、何奇、劉鈺，等等。正是他們的鼓勵和幫助，我才有完成本書的勇氣和動力。同時，還要感謝基礎軟體中心（上海）關健和陳敏敏兩位主管。

　　騰訊TDSQL技術專家趙偉、Oracle MySQL技術專家賴錚閱讀了本書的書稿並列出了許多具有洞察力的建議和意見。兩位專家作為我的好友，其毋庸置疑的技術能力和為人、做事一直是我前進路上的榜樣。在此，對二位的鼓勵表示真摯的感謝。

　　由書稿到鉛字出版，離不開本書的責任編輯博文視點陳曉猛編輯的辛勤工作。無論從本書主題、版式風格，到稿件的修改等諸多方面，在此表示衷心感謝。

　　同樣要對我成長路上的諸多師長和同學及友人表達最衷心的感謝，正是他們的諄諄教誨和陪伴，我才可以自由地追逐夢想。