第1章 概述 1
1.1 查询优化的简介 1
1.2 逻辑优化 3
1.2.1 关系模型 3
1.2.2 逻辑优化示例 8
1.3 物理优化 10
1.3.1 物理优化的4个“法宝” 12
1.3.2 物理路径的生成过程 14
1.4 文件介绍 17
1.5 示例的约定 18
1.6 小结 19
第2章 查询树 20
2.1 Node的结构 20<p>第1章 概述 1</p> <p>1.1 查询优化的简介 1</p> <p>1.2 逻辑优化 3</p> <p>1.2.1 关系模型 3</p> <p>1.2.2 逻辑优化示例 8</p> <p>1.3 物理优化 10</p> <p>1.3.1 物理优化的4个“法宝” 12</p> <p>1.3.2 物理路径的生成过程 14</p> <p>1.4 文件介绍 17</p> <p>1.5 示例的约定 18</p> <p>1.6 小结 19</p> <p> </p> <p>第2章 查询树 20</p> <p>2.1 Node的结构 20</p> <p>2.2 Var结构体 21</p> <p>2.3 RangeTblEntry结构体 23</p> <p>2.4 RangeTblRef结构体 25</p> <p>2.5 JoinExpr结构体 26</p> <p>2.6 FromExpr结构体 27</p> <p>2.7 Query结构体 27</p> <p>2.8 查询树的展示 31</p> <p>2.9 查询树的遍历 31</p> <p>2.10 执行计划的展示 32</p> <p>2.11 小结 33</p> <p> </p> <p>第3章 逻辑重写优化 34</p> <p>3.1 通用表达式 35</p> <p>3.2 子查询提升 36</p> <p>3.2.1 提升子连接 37</p> <p>3.2.2 提升子查询 51</p> <p>3.3 UNION ALL优化 68</p> <p>3.4 展开继承表 69</p> <p>3.5 预处理表达式 71</p> <p>3.5.1 连接Var的溯源 71</p> <p>3.5.2 常量化简 72</p> <p>3.5.3 谓词规范 73</p> <p>3.5.4 子连接处理 79</p> <p>3.6 处理HAVING子句 80</p> <p>3.7 Group By键值消除 81</p> <p>3.8 外连接消除 82</p> <p>3.9 grouping_planner的说明 91</p> <p>3.10 小结 92</p> <p> </p> <p>第4章 逻辑分解优化 93</p> <p>4.1 创建RelOptInfo 94</p> <p>4.1.1 RelOptInfo结构体 94</p> <p>4.1.2 IndexOptInfo结构体 97</p> <p>4.1.3 创建RelOptInfo 100</p> <p>4.2 初识等价类 102</p> <p>4.3 谓词下推 106</p> <p>4.3.1 连接条件的下推 106</p> <p>4.3.2 过滤条件的下推 112</p> <p>4.3.3 连接顺序 113</p> <p>4.3.4 deconstruct_recurse函数 118</p> <p>4.3.5 make_outerjoininfo函数 124</p> <p>4.3.6 distribute_qual_to_rels函数 132</p> <p>4.3.7 reconsider_outer_join_clauses函数 151</p> <p>4.3.8 generate_base_implied_equalities函数 156</p> <p>4.3.9 记录表之间的等价关系 157</p> <p>4.4 PlaceHolderVar的作用 158</p> <p>4.5 Lateral语法的支持 161</p> <p>4.5.1 Lateral的语义分析 162</p> <p>4.5.2 收集Lateral变量 164</p> <p>4.5.3 收集Lateral信息 164</p> <p>4.6 消除无用连接项 166</p> <p>4.7 Semi Join消除 171</p> <p>4.8 提取新的约束条件 172</p> <p>4.8.1 提取需要满足的条件 173</p> <p>4.8.2 提取流程 174</p> <p>4.8.3 选择率修正 176</p> <p>4.9 小结 177</p> <p> </p> <p>第5章 统计信息和选择率 178</p> <p>5.1 统计信息 178</p> <p>5.1.1 PG_STATISTIC系统表 181</p> <p>5.1.2 PG_STATISTIC_EXT系统表 185</p> <p>5.1.3 单列统计信息生成 187</p> <p>5.1.4 多列统计信息生成 196</p> <p>5.2 选择率 200</p> <p>5.2.1 使用函数依赖计算选择率 204</p> <p>5.2.2 子约束条件的选择率 208</p> <p>5.2.3 基于范围的约束条件的选择率修正 211</p> <p>5.3 OpExpr的选择率 213</p> <p>5.3.1 eqsel函数 215</p> <p>5.3.2 scalargtsel函数 217</p> <p>5.3.3 eqjoinsel函数 220</p> <p>5.4 小结 226</p> <p> </p> <p>第6章 扫描路径 227</p> <p>6.1 代价（Cost） 228</p> <p>6.1.1 代价基准单位 228</p> <p>6.1.2 启动代价和整体代价 231</p> <p>6.1.3 表达式代价的计算 233</p> <p>6.2 路径（Path） 236</p> <p>6.2.1 Path结构体 236</p> <p>6.2.2 并行参数 237</p> <p>6.2.3 参数化路径 239</p> <p>6.2.4 PathKey 242</p> <p>6.3 make_one_rel函数 244</p> <p>6.4 普通表的扫描路径 245</p> <p>6.4.1 顺序扫描 246</p> <p>6.4.2 索引扫描 248</p> <p>6.4.3 位图扫描 281</p> <p>6.5 小结 291</p> <p> </p> <p>第7章 动态规划和遗传算法 292</p> <p>7.1 动态规划 293</p> <p>7.1.1 make_rel_from_joinlist函数 297</p> <p>7.1.2 standard_join_search函数 298</p> <p>7.1.3 join_search_one_level函数 298</p> <p>7.2 遗传算法 301</p> <p>7.2.1 种群初始化 303</p> <p>7.2.2 选择算子 308</p> <p>7.2.3 交叉算子 310</p> <p>7.2.4 适应度计算 311</p> <p>7.3 小结 312</p> <p> </p> <p>第8章 连接路径 313</p> <p>8.1 检查 314</p> <p>8.1.1 初步检查 314</p> <p>8.1.2 **检查 316</p> <p>8.1.3 “合法”连接 318</p> <p>8.2 生成新的RelOptInfo 324</p> <p>8.3 虚表 327</p> <p>8.4 Semi Join和**化路径 328</p> <p>8.5 建立连接路径 331</p> <p>8.5.1 sort_inner_and_outer函数 334</p> <p>8.5.2 match_unsorted_outer函数 345</p> <p>8.5.3 hash_inner_and_outer函数 350</p> <p>8.6 路径的筛选 355</p> <p>8.7 小结 360</p> <p> </p> <p>第9章 Non-SPJ优化 361</p> <p>9.1 集合操作处理 361</p> <p>9.2 Non-SPJ路径 367</p> <p>9.2.1 Non-SPJ预处理 368</p> <p>9.2.2 Non-SPJ路径生成 376</p> <p>9.3 小结 382</p> <p> </p> <p>第10章 生成执行计划 383</p> <p>10.1 转换流程 383</p> <p>10.1.1 扫描计划 384</p> <p>10.1.2 连接计划 390</p> <p>10.2 执行计划树清理 391</p> <p>10.3 小结 395</p>显示全部信息前 言为什么写这本书
我参加过很多次查询优化的培训，也查阅过很多查询优化的资料，但总是感觉对查询优化似懂而非，我总结其原因是多数培训和资料的时长或篇幅较短，内容多是对查询优化的概述，“巧妙”地避开了查询优化的难点，难以触及查询优化的本质，导致查询优化的“大道理”人人都懂，遇到问题却难以发力。
2016年年末，我做了一次查询优化的培训，结合之前培训的经验，我对这次查询优化的培训打了一个“持久战”，不只是拿出几个小时的时间对查询优化进行一个总体描述，而是将查询优化器拆解开来，分阶段地进行详细的解读，大约做了十几次培训，*终的效果是非常显著的。在培训的过程中我发现，目前PostgreSQL数据库查询优化器实现细节相关的资料市场上少之又少，和数据库从业人员对查询优化器的热情远远不成正比，本着抛砖引玉的原则，我写了这本书。
为什么阅读这本书
√ 在数据库内核开发的过程中，你是否有了解查询优化器的实现细节的欲望？
√ 在对数据库进行调优的过程中，你是否感觉无从下手？<p>为什么写这本书</p> <p>我参加过很多次查询优化的培训，也查阅过很多查询优化的资料，但总是感觉对查询优化似懂而非，我总结其原因是多数培训和资料的时长或篇幅较短，内容多是对查询优化的概述，“巧妙”地避开了查询优化的难点，难以触及查询优化的本质，导致查询优化的“大道理”人人都懂，遇到问题却难以发力。</p> <p>2016年年末，我做了一次查询优化的培训，结合之前培训的经验，我对这次查询优化的培训打了一个“持久战”，不只是拿出几个小时的时间对查询优化进行一个总体描述，而是将查询优化器拆解开来，分阶段地进行详细的解读，大约做了十几次培训，*终的效果是非常显著的。在培训的过程中我发现，目前PostgreSQL数据库查询优化器实现细节相关的资料市场上少之又少，和数据库从业人员对查询优化器的热情远远不成正比，本着抛砖引玉的原则，我写了这本书。</p> <p>为什么阅读这本书</p> <p>√ 在数据库内核开发的过程中，你是否有了解查询优化器的实现细节的欲望？</p> <p>√ 在对数据库进行调优的过程中，你是否感觉无从下手？</p> <p>√ 在分析查询优化的源码时，你是否会陷入某一细节而不可自拔？</p> <p>√ 在学习查询优化的理论时，你是否感觉理论与实践之间无法一一对应？</p> <p>如果你希望深入地了解查询优化，那么*好的办法就是了解它的理论基础，然后细致地剖析查询优化器的源代码，通过理论和实践的结合，达到真正掌握相关知识的目的。本书细致地解读了PostgreSQL 10.0的查询优化器的大部分源码，对其中比较重要的理论都给出了说明，足以让读者了解PostgreSQL数据库查询优化器的全貌。</p> <p>虽然本书已经尽量尝试将复杂问题简单化，但是鉴于PostgreSQL数据库的查询优化器的实现本身就具有一定的复杂性，读者阅读的过程可能是“痛苦”的，但请相信“梅花香自苦寒来”，只要坚持阅读就能收获很多。</p> <p>本书的组织结构</p> <p>本书的组织结构基本是按照PostgreSQL数据库的查询优化器处理一个查询的流程来安排的，由简入繁、由易入难。</p> <p>第1章介绍一些查询优化基础理论，这些理论是对查询优化的概述，读者在阅读第1章时可以参考一些经典的数据库实现理论书籍，更详细地了解数据库的基本理论，这样能给后面的阅读打好基础。</p> <p>第2章介绍查询树，查询树是PostgreSQL数据库查询优化器的输入，查询优化器本身是对查询树的等价改造及等价分解。</p> <p>第3章介绍逻辑重写优化，逻辑重写优化是逻辑优化的一部分，它主要是对查询树进行基于规则的等价重写，比较重要的有子查询提升、表达式预处理、外连接消除等。</p> <p>第4章介绍逻辑分解优化，逻辑分解优化仍然是逻辑优化的一部分，和逻辑重写优化不同，它开始尝试分解查询树，经过谓词下推、连接顺序交换、等价类推理等对查询树进行改造。</p> <p>第5章介绍统计信息和选择率，统计信息是代价计算的基石，因此了解统计信息的类型、了解选择率的含义对代价计算有非常重要的意义。</p> <p>第6章介绍扫描路径的建立过程，扫描路径是为了对基表进行扫描的物理算子创建的路径，它负责将物理存储或者缓存中的数据读取上来并进行处理，通常包括顺序扫描、索引扫描、位图扫描等。</p> <p>第7章介绍路径搜索的两个算法，PostgreSQL数据库采用了动态规划方法和遗传算法进行路径搜索，本书对这两种方法的实现都做了详细的介绍。</p> <p>第8章介绍连接路径的建立过程，PostgreSQL数据库的物理连接路径有嵌套循环连接、哈希连接、归并连接等，由于采用的扫描路径不同，导致同一种类型的物理连接路径产生的代价不同。</p> <p>第9章介绍Non-SPJ的相关优化，PostgreSQL数据库对集合操作、聚集操作、分组操作、排序操作等都做了优化处理。</p> <p>第10章介绍执行计划的生成，在扫描路径、连接路径及Non-SPJ路径分别处理之后，会选择一个“*优”的连接树，PostgreSQL数据库需要将这个连接树修正成执行计划树。</p> <p>错误</p> <p>限于我的能力，书中难免有错误，在写作的过程中我也尝试尽量多查阅相关的资料，尽量避免错误的出现，但是相关的资料实在是太少了，因此，欢迎广大读者对本书提出纠正、批评和意见，这也有益于我本身能力的提升。</p> <p>致谢</p> <p>感谢彭煜玮、周正中（德哥Digoal）为本书作序，感谢蒋志勇、文继军、王颖泽、杨瑜、赵殿奎对本书的评价，这对我是极大的鼓励。</p> <p>在写作过程中，卢栋栋、彭信东、李茂增通读了大部分书稿，给出了很多有益的意见和建议，在此表示感谢。林文、翁燕青、白洁对书稿的格式及内容提出了修改建议，在此一并表示感谢。</p> <p>感谢董英编辑，在写稿及后续的审校过程中董英编辑一直在和我沟通，不厌其烦地解答我的各种问题。</p> <p>感谢我的家人。我的父母和妻子在我写作的过程中给予了极大的支持，写作的过程非常枯燥，他们为我提供了*好的写作环境。另外我的两个儿子也经常在我离开电脑的间隙帮我修改书稿，虽然他们的意见一条也没有被采纳，但这里仍然对他们的“贡献”表示感谢。</p>显示全部信息媒体评论作为开源关系数据库领域先进技术的代表，PostgreSQL近年来受到越来越多人的关注，尤其是它的优化器，称得上是一种教科书式的实现。树杰的《PostgreSQL技术内幕：查询优化深度探索》全面解读了PostgreSQL优化器，从关系代数基本原理到PostgreSQL优化器实现中用到的主要数据结构及函数，都进行了准确细致的说明，同时条理清晰地描述了基于规则的查询改写、基于统计信息和代价计算的计划选择、动态规划算法、基因算法等。对于希望学习和深入了解PostgreSQL优化器的同学，���书是一本非常好的教材和参考书。
——蚂蚁金服基础数据部**专家 蒋志勇
查询优化器是数据库的大脑，它生成的执行计划的优劣直接决定了数据库的性能。读者通过本书，可以深入理解和掌握PostgreSQL这个**开源数据库的优化器，更可以推而广之去理解和掌握其他数据库的优化器。在此基础上，如果能再去思考如何创新，那么本书作者的努力就得到超额回报了。
——*云云数据库**架构师 文继军<p> 作为开源关系数据库领域先进技术的代表，PostgreSQL近年来受到越来越多人的关注，尤其是它的优化器，称得上是一种教科书式的实现。树杰的《PostgreSQL技术内幕：查询优化深度探索》全面解读了PostgreSQL优化器，从关系代数基本原理到PostgreSQL优化器实现中用到的主要数据结构及函数，都进行了准确细致的说明，同时条理清晰地描述了基于规则的查询改写、基于统计信息和代价计算的计划选择、动态规划算法、基因算法等。对于希望学习和深入了解PostgreSQL优化器的同学，本书是一本非常好的教材和参考书。</p> <p>——蚂蚁金服基础数据部**专家 蒋志勇</p> <p> </p> <p> 查询优化器是数据库的大脑，它生成的执行计划的优劣直接决定了数据库的性能。读者通过本书，可以深入理解和掌握PostgreSQL这个**开源数据库的优化器，更可以推而广之去理解和掌握其他数据库的优化器。在此基础上，如果能再去思考如何创新，那么本书作者的努力就得到超额回报了。</p> <p>——*云云数据库**架构师 文继军</p> <p> </p> <p> 树杰是数据库内核研发领域的一个老兵，对数据库的内核实现有深刻的理解和认识，始终保持着对数据库技术的热情。本书是国内为数不多的介绍PostgreSQL数据库内核优化器的原创书籍，是作者多年工作经验的总结。正如作者所说， PostgreSQL的先进性体现在其强大的优化器实现上。本书详细介绍了PostgreSQL优化器从逻辑优化、物理优化、直至生成执行计划的各个阶段，结合实现的数据结构和关键代码深入浅出地介绍了优化器各个模块的实现原理及流程，层层剥茧，逐步揭开了查询优化的神秘面纱。</p> <p>——天曦科技数据库事业部技术总监 王颖泽</p> <p> </p> <p> PostgreSQL以其完善的功能、强大的性能、**的扩展性、系统的稳定性和良好的生态而著称，其中查询优化技术是核心的核心。我很高兴能有这样一本翔实的查询优化专业书籍问世。本书源自作者多年查询优化一线工作经验，不仅对总体架构把控到位，脉络清晰，分析深入，而且对关键的细节部分结合大量实例进行了详细阐述，非常符合工程师的需要。我强烈建议所有希望深度探索PostgreSQL查询优化或进行源码分析的朋友阅读本书，它非常值得你拥有！</p> <p>——Pivotal中国研发**工程总监 杨瑜</p> <p> </p> <p> 因为实现细节比较复杂，查询优化器是数据库中非常重要的模块之一，也是数据库中很难掌握的模块之一。本书作者通过深度分析PostgreSQL数据库查询优化器的关键源码，清晰地描绘了查询优化器的实现脉络，我相信读者阅读完本书后，对查询优化器不仅能知其然，更能知其所以然，且能够有逻辑、有条理、有思想地对数据库进行调优，真正做到“胸中有丘壑，眼里存山河”。</p> <p>——阿里巴巴数据库事业部**数据库专家 赵殿奎</p>显示全部信息免费在线读序一
查询可以说是数据库管理系统中*关键、*吸引人的功能之一，每一个生产数据库系统每天都需要处理大量的各类查询，为了让这些查询运行得更快、更好，数据库管理系统的查询优化器中包含了大量的优化技术，这些优化技术是很多研究者和技术人员数十年钻研和探索总结出来的精华。不论是数据库管理系统的***还是数据库应用的***，学习理解查询优化技术都大有裨益。
作为*先进的开源对象关系型数据库管理系统，PostgreSQL及其源代码无疑是学习和体会查询优化技术的*佳平台。除此之外，高质量技术书籍也是研究查询优化技术必不可少的武器。本书结合PostgreSQL的查询优化器源代码，深入分析了一个查询进入PostgreSQL之后一步步被查询优化器转换成一个可执行的、优化后的执行计划的全过程。为了让读者更容易理解，本书还配备了大量的实例来讲解，确实是一部值得一读的好书。
身为一名PostgreSQL爱好者和数据库研究人员，我感到无比幸福和自豪—据我有限的知识，全球仅有几本分析PostgreSQL内核的书籍，而它们全都出自中国作者之手。希望今后有更多、更好的此类书籍面世，也祝愿中国的数据库技术和产品有朝一日能够走向世界。
彭煜玮
2018.4.25于珞珈山
序二
中国有句古话，“巧妇难为无米之炊”，说的是再好的主妇，在没有给任何食材的情况下也做不出可口的饭菜。反过来，什么样的主妇算得上“巧妇”呢？如果给你准备好了烹调所需的所有食材，你能做出可口的饭菜吗？
囊括源码解析、架构分析、关键细节、一线案例 深入浅出全面解读了PostgreSQL查询优化器 作者是数据库内核研发领域的一个老兵 拥有十多年一线数据库开发经验 对数据库内核各个方面都有研究 书中凝结了其对数据库的深刻理解 彭煜玮、周正中（德哥Digoal）倾情作序 蚂蚁金服、JD、*等业内专家力荐 不懂优化器不能算懂数据库 PostgreSQL优化器是一种教科书式的实现 值得数据库技术人员深入研究
张树杰，北京大学工程管理硕士。2005年—2011年，从事**相关的工作，涉及入侵检测、数据库审计、虚拟桌面等等。2011年—2015年，北京人大金仓信息技术股份有限公司，从事数据库内核开发工作。2015年—至今，天津神舟通用数据技术有限公司北京分公司，从事数据库内核开发工作及团队管理工作。