《PostgreSQL技术内幕：查询优化深度探索》

编辑推荐

囊括源码解析、架构分析、关键细节、一线案例

深入浅出全面解读了PostgreSQL查询优化器

作者是数据库内核研发领域的一个老兵

拥有十多年一线数据库开发经验

对数据库内核各个方面都有研究

书中凝结了其对数据库的深刻理解

彭煜玮、周正中（德哥Digoal）倾情作序

蚂蚁金服、京东、阿里巴巴等业内专家力荐

不懂优化器不能算懂数据库

PostgreSQL优化器是一种教科书式的实现

值得数据库技术人员深入研究

目前仅有的深刻的PostgreSQL查询优化器分析

内容简介

查询优化器是数据库中很重要的模块之一，只有掌握好查询优化的方法且了解查询优化的细节，在对数据库调优的过程中才能有的放矢，否则调优的过程就如无本之木、无源之水，虽上下求索而不得其法。

《PostgreSQL技术内幕：查询优化深度探索》揭示了PostgreSQL数据库中查询优化的实现技术细节，首先对子查询提升、外连接消除、表达式预处理、谓词下推、连接顺序交换、等价类推理等逻辑优化方法进行了详细描述，然后结合统计信息、选择率、代价对扫描路径创建、路径搜索方法、连接路径建立、Non-SPJ路径建立、执行计划简化与生成等进行了深度探索，使读者对PostgreSQL数据库的查询优化器有深层次的了解。

《PostgreSQL技术内幕：查询优化深度探索》适合数据库内核开发人员及相关领域的研究人员、数据库DBA、高等院校相关专业的本科生或者研究生阅读。

作者简介

张树杰，拥有13年IT从业经验，从事国产数据库内核开发工作多年，对数据库内核各个方面均有涉猎，近些年专注于研究如何改进分布式数据库的查询优化、查询执行，目前在Pivotal公司从事ApacheHAWQ数据库的内核开发工作。

精彩书评

作为开源关系数据库领域先进技术的代表，PostgreSQL近年来受到越来越多人的关注，尤其是它的优化器，称得上是一种教科书式的实现。树杰的《PostgreSQL技术内幕：查询优化深度探索》全面解读了PostgreSQL优化器，从关系代数基本原理到PostgreSQL优化器实现中用到的主要数据结构及函数，都进行了准确细致的说明，同时条理清晰地描述了基于规则的查询改写、基于统计信息和代价计算的计划选择、动态规划算法、基因算法等。对于希望学习和深入了解PostgreSQL优化器的同学，《PostgreSQL技术内幕：查询优化深度探索》是一本非常好的教材和参考书。

——蚂蚁金服基础数据部资深专家蒋志勇

查询优化器是数据库的大脑，它生成的执行计划的优劣直接决定了数据库的性能。读者通过《PostgreSQL技术内幕：查询优化深度探索》，可以深入理解和掌握PostgreSQL这个优秀开源数据库的优化器，更可以推而广之去理解和掌握其他数据库的优化器。在此基础上，如果能再去思考如何创新，那么《PostgreSQL技术内幕：查询优化深度探索》作者的努力就得到超额回报了。

——京东云云数据库首席架构师文继军

树杰是数据库内核研发领域的一个老兵，对数据库的内核实现有深刻的理解和认识，始终保持着对数据库技术的热情。《PostgreSQL技术内幕：查询优化深度探索》是国内为数不多的介绍PostgreSQL数据库内核优化器的原创书籍，是作者多年工作经验的总结。正如作者所说，PostgreSQL的先进性体现在其强大的优化器实现上。《PostgreSQL技术内幕：查询优化深度探索》详细介绍了PostgreSQL优化器从逻辑优化、物理优化、直至生成执行计划的各个阶段，结合实现的数据结构和关键代码深入浅出地介绍了优化器各个模块的实现原理及流程，层层剥茧，逐步揭开了查询优化的神秘面纱。

——天曦科技数据库事业部技术总监王颖泽

PostgreSQL以其完善的功能、强大的性能、优秀的扩展性、系统的稳定性和良好的生态而著称，其中查询优化技术是核心的核心。我很高兴能有这样一本翔实的查询优化专业书籍问世。《PostgreSQL技术内幕：查询优化深度探索》源自作者多年查询优化一线工作经验，不仅对总体架构把控到位，脉络清晰，分析深入，而且对关键的细节部分结合大量实例进行了详细阐述，非常符合工程师的需要。我强烈建议所有希望深度探索PostgreSQL查询优化或进行源码分析的朋友阅读《PostgreSQL技术内幕：查询优化深度探索》，它非常值得你拥有！

——Pivotal中国研发中心工程总监杨瑜

因为实现细节比较复杂，查询优化器是数据库中非常重要的模块之一，也是数据库中很难掌握的模块之一。《PostgreSQL技术内幕：查询优化深度探索》作者通过深度分析PostgreSQL数据库查询优化器的关键源码，清晰地描绘了查询优化器的实现脉络，我相信读者阅读完《PostgreSQL技术内幕：查询优化深度探索》后，对查询优化器不仅能知其然，更能知其所以然，且能够有逻辑、有条理、有思想地对数据库进行调优，真正做到“胸中有丘壑，眼里存山河”。

——阿里巴巴数据库事业部高级数据库专家赵殿奎

目录

第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.1Node的结构20

2.2Var结构体21

2.3RangeTblEntry结构体23

2.4RangeTblRef结构体25

2.5JoinExpr结构体26

2.6FromExpr结构体27

2.7Query结构体27

2.8查询树的展示31

2.9查询树的遍历31

2.10执行计划的展示32

2.11小结33

第3章逻辑重写优化34

3.1通用表达式35

3.2子查询提升36

3.2.1提升子连接37

3.2.2提升子查询51

3.3UNIONALL优化68

3.4展开继承表69

3.5预处理表达式71

3.5.1连接Var的溯源71

3.5.2常量化简72

3.5.3谓词规范73

3.5.4子连接处理79

3.6处理HAVING子句80

3.7GroupBy键值消除81

3.8外连接消除82

3.9grouping_planner的说明91

3.10小结92

第4章逻辑分解优化93

4.1创建RelOptInfo94

4.1.1RelOptInfo结构体94

4.1.2IndexOptInfo结构体97

4.1.3创建RelOptInfo100

4.2初识等价类102

4.3谓词下推106

4.3.1连接条件的下推106

4.3.2过滤条件的下推112

4.3.3连接顺序113

4.3.4deconstruct_recurse函数118

4.3.5make_outerjoininfo函数124

4.3.6distribute_qual_to_rels函数132

4.3.7reconsider_outer_join_clauses函数151

4.3.8generate_base_implied_equalities函数156

4.3.9记录表之间的等价关系157

4.4PlaceHolderVar的作用158

4.5Lateral语法的支持161

4.5.1Lateral的语义分析162

4.5.2收集Lateral变量164

4.5.3收集Lateral信息164

4.6消除无用连接项166

4.7SemiJoin消除171

4.8提取新的约束条件172

4.8.1提取需要满足的条件173

4.8.2提取流程174

4.8.3选择率修正176

4.9小结177

第5章统计信息和选择率178

5.1统计信息178

5.1.1PG_STATISTIC系统表181

5.1.2PG_STATISTIC_EXT系统表185

5.1.3单列统计信息生成187

5.1.4多列统计信息生成196

5.2选择率200

5.2.1使用函数依赖计算选择率204

5.2.2子约束条件的选择率208

5.2.3基于范围的约束条件的选择率修正211

5.3OpExpr的选择率213

5.3.1eqsel函数215

5.3.2scalargtsel函数217

5.3.3eqjoinsel函数220

5.4小结226

第6章扫描路径227

6.1代价（Cost）228

6.1.1代价基准单位228

6.1.2启动代价和整体代价231

6.1.3表达式代价的计算233

6.2路径（Path）236

6.2.1Path结构体236

6.2.2并行参数237

6.2.3参数化路径239

6.2.4PathKey242

6.3make_one_rel函数244

6.4普通表的扫描路径245

6.4.1顺序扫描246

6.4.2索引扫描248

6.4.3位图扫描281

6.5小结291

第7章动态规划和遗传算法292

7.1动态规划293

7.1.1make_rel_from_joinlist函数297

7.1.2standard_join_search函数298

7.1.3join_search_one_level函数298

7.2遗传算法301

7.2.1种群初始化303

7.2.2选择算子308

7.2.3交叉算子310

7.2.4适应度计算311

7.3小结312

第8章连接路径313

8.1检查314

8.1.1初步检查314

8.1.2精确检查316

8.1.3“合法”连接318

8.2生成新的RelOptInfo324

8.3虚表327

8.4SemiJoin和唯一化路径328

8.5建立连接路径331

8.5.1sort_inner_and_outer函数334

8.5.2match_unsorted_outer函数345

8.5.3hash_inner_and_outer函数350

8.6路径的筛选355

8.7小结360

第9章Non-SPJ优化361

9.1集合操作处理361

9.2Non-SPJ路径367

9.2.1Non-SPJ预处理368

9.2.2Non-SPJ路径生成376

9.3小结382

第10章生成执行计划383

10.1转换流程383

10.1.1扫描计划384

10.1.2连接计划390

10.2执行计划树清理391

10.3小结395

精彩书摘

序一

查询可以说是数据库管理系统中最关键、最吸引人的功能之一，每一个生产数据库系统每天都需要处理大量的各类查询，为了让这些查询运行得更快、更好，数据库管理系统的查询优化器中包含了大量的优化技术，这些优化技术是很多研究者和技术人员数十年钻研和探索总结出来的精华。不论是数据库管理系统的开发者还是数据库应用的开发者，学习理解查询优化技术都大有裨益。

作为最先进的开源对象关系型数据库管理系统，PostgreSQL及其源代码无疑是学习和体会查询优化技术的最佳平台。除此之外，高质量技术书籍也是研究查询优化技术必不可少的武器。《PostgreSQL技术内幕：查询优化深度探索》结合PostgreSQL的查询优化器源代码，深入分析了一个查询进入PostgreSQL之后一步步被查询优化器转换成一个可执行的、优化后的执行计划的全过程。为了让读者更容易理解，《PostgreSQL技术内幕：查询优化深度探索》还配备了大量的实例来讲解，确实是一部值得一读的好书。

身为一名PostgreSQL爱好者和数据库研究人员，我感到无比幸福和自豪—据我有限的知识，全球仅有几本分析PostgreSQL内核的书籍，而它们全都出自中国作者之手。希望今后有更多、更好的此类书籍面世，也祝愿中国的数据库技术和产品有朝一日能够走向世界。

彭煜玮

2018.4.25于珞珈山

序二

中国有句古话，“巧妇难为无米之炊”，说的是再好的主妇，在没有给任何食材的情况下也做不出可口的饭菜。反过来，什么样的主妇算得上“巧妇”呢？如果给你准备好了烹调所需的所有食材，你能做出可口的饭菜吗？

数据库是一个比较神奇的软件，我们都知道可以用SQL和数据库沟通，让数据库处理SQL和让主妇做饭是一样的道理，数据库能不能及时响应SQL请求，能不能用最优的计划完成SQL请求，取决于数据库本身提供了哪些“料”，以及数据库打算怎么“烹调”用户提交的SQL。例如，一个简单查询SQL，数据库的扫描方法（我暂且把它称为数据库的“料”之一）就有全表扫描、索引扫描、位图扫描、跳跃扫描等。一个SQL中包括了多个函数、表达式时，数据库先处理哪个表达式或函数，又或者在什么时候处理这些表达式或函数呢？数据库“烹调”一条SQL时，如何“烹调”，如何分解，是靠什么来做决定的？在数据库决定了怎么做之后，又是如何按部就班地执行的？如果说数据库的“扫描方法、表达式、操作符、UDF、索引接口”等是数据库的“料”，那么数据库的优化器就是“巧妇”之手，它包括了“JOIN算法、SQL重写规则、多表JOIN的遗传算法、动态路径规划、选择性算法、各种NODE的成本计算算法、成本因子、并行计算成本算法”等方方面面，为数据库如何执行SQL提供了全套流程。

PostgreSQL作为一个非常经典的ORDBMS，包含了很多“料”，同时有着非常先进的优化器，为高效地执行SQL提供了良好的基础。

《PostgreSQL技术内幕：查询优化深度探索》作者长期致力于数据库内核的研发，有非常丰富的理论与实践经验，《PostgreSQL技术内幕：查询优化深度探索》以PostgreSQL为背景，详细介绍了PostgreSQL查询优化器中的核心概念，从“查询树、SQL重写、UNION优化、逻辑分解”到“下推、JOIN、选择性、统计信息、扫描路径、动态规划、遗传算法”等方方面面，实为作者呕心沥血之作，同时也是数据库工作者，特别是PGer之福。

《PostgreSQL技术内幕：查询优化深度探索》是不可多得的教科书级PostgreSQL内核读物，同时不乏实战性。建议想了解数据库优化器工作原理的读者及PostgreSQL爱好者深入学习。

感谢作者为PostgreSQL生态的辛勤付出，期待《PostgreSQL技术内幕：查询优化深度探索》大卖。

PGer，Digoal

前言/序言

为什么写这《PostgreSQL技术内幕：查询优化深度探索》

我参加过很多次查询优化的培训，也查阅过很多查询优化的资料，但总是感觉对查询优化似懂而非，我总结其原因是多数培训和资料的时长或篇幅较短，内容多是对查询优化的概述，“巧妙”地避开了查询优化的难点，难以触及查询优化的本质，导致查询优化的“大道理”人人都懂，遇到问题却难以发力。

2016年年末，我做了一次查询优化的培训，结合之前培训的经验，我对这次查询优化的培训打了一个“持久战”，不只是拿出几个小时的时间对查询优化进行一个总体描述，而是将查询优化器拆解开来，分阶段地进行详细的解读，大约做了十几次培训，最终的效果是非常显著的。在培训的过程中我发现，目前PostgreSQL数据库查询优化器实现细节相关的资料市场上少之又少，和数据库从业人员对查询优化器的热情远远不成正比，本着抛砖引玉的原则，我写了这《PostgreSQL技术内幕：查询优化深度探索》。

为什么阅读这《PostgreSQL技术内幕：查询优化深度探索》

√在数据库内核开发的过程中，你是否有了解查询优化器的实现细节的欲望？

√在对数据库进行调优的过程中，你是否感觉无从下手？

√在分析查询优化的源码时，你是否会陷入某一细节而不可自拔？

√在学习查询优化的理论时，你是否感觉理论与实践之间无法一一对应？

如果你希望深入地了解查询优化，那么最好的办法就是了解它的理论基础，然后细致地剖析查询优化器的源代码，通过理论和实践的结合，达到真正掌握相关知识的目的。《PostgreSQL技术内幕：查询优化深度探索》细致地解读了PostgreSQL10.0的查询优化器的大部分源码，对其中比较重要的理论都给出了说明，足以让读者了解PostgreSQL数据库查询优化器的全貌。

虽然《PostgreSQL技术内幕：查询优化深度探索》已经尽量尝试将复杂问题简单化，但是鉴于PostgreSQL数据库的查询优化器的实现本身就具有一定的复杂性，读者阅读的过程可能是“痛苦”的，但请相信“梅花香自苦寒来”，只要坚持阅读就能收获很多。

《PostgreSQL技术内幕：查询优化深度探索》的组织结构

《PostgreSQL技术内幕：查询优化深度探索》的组织结构基本是按照PostgreSQL数据库的查询优化器处理一个查询的流程来安排的，由简入繁、由易入难。

第1章介绍一些查询优化基础理论，这些理论是对查询优化的概述，读者在阅读第1章时可以参考一些经典的数据库实现理论书籍，更详细地了解数据库的基本理论，这样能给后面的阅读打好基础。

第2章介绍查询树，查询树是PostgreSQL数据库查询优化器的输入，查询优化器本身是对查询树的等价改造及等价分解。

第3章介绍逻辑重写优化，逻辑重写优化是逻辑优化的一部分，它主要是对查询树进行基于规则的等价重写，比较重要的有子查询提升、表达式预处理、外连接消除等。

第4章介绍逻辑分解优化，逻辑分解优化仍然是逻辑优化的一部分，和逻辑重写优化不同，它开始尝试分解查询树，经过谓词下推、连接顺序交换、等价类推理等对查询树进行改造。

第5章介绍统计信息和选择率，统计信息是代价计算的基石，因此了解统计信息的类型、了解选择率的含义对代价计算有非常重要的意义。

第6章介绍扫描路径的建立过程，扫描路径是为了对基表进行扫描的物理算子创建的路径，它负责将物理存储或者缓存中的数据读取上来并进行处理，通常包括顺序扫描、索引扫描、位图扫描等。

第7章介绍路径搜索的两个算法，PostgreSQL数据库采用了动态规划方法和遗传算法进行路径搜索，《PostgreSQL技术内幕：查询优化深度探索》对这两种方法的实现都做了详细的介绍。

第8章介绍连接路径的建立过程，PostgreSQL数据库的物理连接路径有嵌套循环连接、哈希连接、归并连接等，由于采用的扫描路径不同，导致同一种类型的物理连接路径产生的代价不同。

第9章介绍Non-SPJ的相关优化，PostgreSQL数据库对集合操作、聚集操作、分组操作、排序操作等都做了优化处理。

第10章介绍执行计划的生成，在扫描路径、连接路径及Non-SPJ路径分别处理之后，会选择一个“最优”的连接树，PostgreSQL数据库需要将这个连接树修正成执行计划树。

错误

限于我的能力，书中难免有错误，在写作的过程中我也尝试尽量多查阅相关的资料，尽量避免错误的出现，但是相关的资料实在是太少了，因此，欢迎广大读者对《PostgreSQL技术内幕：查询优化深度探索》提出纠正、批评和意见，这也有益于我本身能力的提升。

致谢

感谢彭煜玮、周正中（德哥Digoal）为《PostgreSQL技术内幕：查询优化深度探索》作序，感谢蒋志勇、文继军、王颖泽、杨瑜、赵殿奎对《PostgreSQL技术内幕：查询优化深度探索》的评价，这对我是极大的鼓励。

在写作过程中，卢栋栋、彭信东、李茂增通读了大部分书稿，给出了很多有益的意见和建议，在此表示感谢。林文、翁燕青、白洁对书稿的格式及内容提出了修改建议，在此一并表示感谢。

感谢董英编辑，在写稿及后续的审校过程中董英编辑一直在和我沟通，不厌其烦地解答我的各种问题。

感谢我的家人。我的父母和妻子在我写作的过程中给予了极大的支持，写作的过程非常枯燥，他们为我提供了最好的写作环境。另外我的两个儿子也经常在我离开电脑的间隙帮我修改书稿，虽然他们的意见一条也没有被采纳，但这里仍然对他们的“贡献”表示感谢。