內容提要
PostgreSQL作為當今最先進的開源關係型資料庫，《PostgreSQL查詢引擎源碼技術探析》揭示PostgreSQL查詢引擎的運行原理和實現技術細節，其中包括：基礎數據結構；SQL詞法語法分析及查詢語法樹；查詢分析及查詢重寫；子連結及子查詢處理；查詢訪問路徑創建；查詢計畫生成，等等。以深入淺出的方式討論每個主題並結合基礎數據結構、圖表、源碼等對所討論的主題進行詳細分析，以使讀者對PostgreSQL查詢引擎的運行機制及實現細節能有全面且深入的認識。
《PostgreSQL查詢引擎源碼技術探析》適合從事資料庫領域相關研究人員、高等院校相關專業高年級本科生或研究生閱讀，也可作為高等院校的資料庫原理課程的有益補充，還可作為業界資料庫相關人員的案頭圖書。《PostgreSQL查詢引擎源碼技術探析》有助於讀者理解數據查詢引擎核心的技術內幕。
目錄
第1 章 PostgreSQL 概述 1
1.1 概述 1
1.2 查詢語句最佳化 3
1.2.1 工具類語句 4
1.2.2 查詢類語句的處理 5
1.3 創建查詢計畫 8
1.4 小結 8
第2 章 基表數據結構 10
2.1 概述 10
2.2 數據結構 10
2.2.1 查詢樹Query 11
2.2.2 Select 型查詢語句SelectStmt 13
2.2.3 目標列項TargetEntry 15
2.2.4 From…Where…語句FromExpr 16
2.2.5 範圍表項RangeTblEntry/RangeTblRef 16
2.2.6 Join 表達式JoinExpr 18
2.2.7 From 語句中的子查詢RangeSubSelect 19
2.2.8 子連結SubLink 20
2.2.9 子查詢計畫SubPlan 22
2.2 小結 23
2.3 思考 24
第3 章 查詢分析 25
3.1 概述 25
3.2 問題描述 25
3.3 詞法分析和語法分析（Lex&Yacc） 28
3.3.1 概述 28
3.3.2 詞法分析器Lex 28
3.3.3 語法分析器Yacc 30
3.3.4 小結 36
3.3.5 思考 36
3.4 抽象查詢語法樹AST 37
3.5 查詢分析 39
3.5.1 概述 39
3.5.2 查詢分析—parse_analyze 40
3.5.3 查詢語句分析—transformStmt 42
3.6 查詢重寫 54
3.6.1 概述 54
3.6.2 查詢重寫——pg_rewrite_query 54
3.7 小結 55
3.8 思考 56
第4 章 查詢邏輯最佳化 57
4.1 概述 57
4.2 預處理 57
4.2.1 xxx_xxx_walker/mutator 的前世今生 59
4.2.3 對xxx_xxx_walker/mutator 的思考 60
4.3 查詢最佳化中的數據結構 61
4.3.1 數據結構 62
4.3.2 小結 80
4.3.3 思考 81
4.4 查詢最佳化分析 81
4.4.1 邏輯最佳化——整體架構介紹 82
4.4.2 子查詢最佳化——subquery_planner 88
4.4.3 創建分組等語句查詢計畫—grouping_planner 142
4.4.4 創建查詢訪問路徑—query_planner 150
4.4.5 小結 195
4.4.6 思考 196
第5 章 查詢物理最佳化 198
5.1 概述 198
5.2 所有可行查詢訪問路徑構成函式make_one_rel 200
5.2.1 設定基表的物理參數 202
5.2.2 基表大小估計—set_rel_size 203
5.2.3 尋找查詢訪問路徑——set_base_rel_pathlists 214
5.2.4 添加查詢訪問路徑—add_path 247
5.2.5 求解Join 查詢路徑—make_rel_from_joinlist 255
5.2.6 構建兩個基表之間連線關係—make_join_rel 267
5.2.7 構建連線關係—build_join_rel 277
5.3 小結 291
5.4 思考 291
第6 章 查詢計畫的生成 293
6.1 查詢計畫的產生 293
6.2 生成查詢計畫—create_plan/create_plan_recurse 293
6.2.1 構建Scan 類型查詢計畫——create_scan_plan 295
6.2.2 構建Join 類型查詢計畫——create_join_plan 300
6.3 查詢計畫的閱讀 305
6.4 小結 308
6.5 思考 308
第7 章 其他函式與知識點 310
7.1 AND/OR 規範化 310
7.2 常量表達式的處理—eval_const_expressions 314
7.3 Relids 的相關函式 316
7.4 List 的相關函式 319
7.5 元數據表Meta Table 320
7.6 查詢引擎相關參數配置 324
結束語 328
前言
隨著移動互聯的飛速發展，“數據”已成為當今最寶貴的資源；誰掌握了數據，誰就掌握了無盡的寶藏。而如何有效地管理這些海量數據則成為擺在人們面前的首要問題。從計算機出現以來，人們便孜孜不倦地追求著高效管理數據的辦法，IBM的System R，U.C.Berkeley PostgreSQL以及Oracle MySQL的誕生，無一不表明人們對於高效、快捷的數據管理的不懈追求。
雖然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章主要分析我們在源碼閱讀過程中遇到的一些重要輔助函式。
致謝
本書在編寫過程中得到了許多朋友的關心和幫助。首先，感謝北大方正信息產業集團基礎軟體中心（上海）的小夥伴們：王博、王鑫、蔣燦、彭川、羅正海、黃誠一、劉慧娟、何奇、劉鈺，等等。正是他們的鼓勵和幫助，我才有完成本書的勇氣和動力。同時，還要感謝基礎軟體中心（上海）關健和陳敏敏兩位領導。
騰訊TDSQL技術專家趙偉、Oracle MySQL技術專家賴錚閱讀了本書的書稿並給出了許多具有洞察力的建議和意見，使得本書增色不少。同樣，兩位資料庫核心專家也為本書撰寫了精彩的評論，兩位對本書的謬讚讓我誠惶誠恐，唯恐書中的錯誤和不足讓兩位專家的鼓勵蒙羞。兩位專家作為我的好友，其毋庸置疑的技術能力和為人、做事一直是我前進路上的榜樣。在此，對二位的鼓勵表示真摯的感謝。
由書稿到鉛字出版，離不開本書的責任編輯博文視點陳曉猛編輯的辛勤工作。無論從本書主題、版式風格，到稿件的修改等諸多方面都體現了曉猛編輯出色的業務能力和辛勤的勞動。本書能夠順利出版離不開他的辛勞，在此表示衷心感謝。
同樣要對我成長路上的諸多師長和同學及友人表達最衷心的感謝，正是他們的諄諄教誨和陪伴，我才可以自由地追逐夢想。
李浩
