电子工业出版社-网上书店

PostgreSQL作为当今最先进的开源关系型数据库，本书揭示PostgreSQL查询引擎运行原理和实现技术细节，其中包括：基础数据结构；SQL词法语法分析及查询语法树；查询分析及查询重写；子连接及子查询处理；查询访问路径创建；查询计划生成，等等。以深入浅出的方式讨论每个主题并结合基础数据结构、图表、源码等对所讨论的主题进行详细分析，以使读者对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章主要分析我们在源码阅读过程中遇到的一些重要辅助函数。
错误说明
由于笔者水平有限，本书中会存在一定的错误，例如笔误、理解错误等，对于本书中出现的错误，读者可以在www.leehao.org中查询该错误的勘误信息，或者发送邮件至hom.lee@hotmail.com与作者联系。笔者非常希望能够与读者共同进步，共同推动国内数据库内核开发人员对PostgreSQL查询引擎的认识。相比MySQL而言，PostgreSQL的相关资料非常少，而专门介绍PostgreSQL查询引擎之类的资料则更加少，而这也是本书成书的原因。
学习资料
源代码作为最好的学习资料，应该永远值得我们认真对待和重视，本书所有分析均基于PostgreSQL 9.4.1版本。读者可以在https://github.com/postgres/postgres中下载最新源码。当然，最新版本的源码可能与本书讨论中给出的源码有所不同，但这并不影响我们对主题问题的讨论。
为了了解最新特性或想参与PostgreSQL内核开发，读者可以订阅PostgreSQL邮件列表，其中包括开发人员邮件列表、本地化相关邮件列表、相关Bugs邮件列表等。
?	http://www.postgresql.org/list/pgsql-cluster-hackers/ 集群相关内核开发人员邮件列表；
?	http://www.postgresql.org/list/pgsql-committers/ 内核commiters邮件列表，为内核日常技术问题讨论，读者可从中了解内核commiters的最新动态；
?	http://www.postgresql.org/list/pgsql-hackers/ 内核开发人员邮件列表；
?	http://www.postgresql.org/list/pgsql-interfaces/ 相关接口讨论邮件列表，例如odbc、jdbc等；
?	http://www.postgresql.org/list/pgsql-docs/ 相关文档邮件列表；
?	http://www.postgresql.org/list/pgsql-bugs/ 相关bugs邮件列表。
相关邮件列表并不限于上述几类，具体内容还请读者参考http://www.postgresql.org/list/中给出的详细信息。
致谢
本书在编写过程中得到了许多朋友的关心和帮助。首先，感谢北大方正信息产业集团基础软件中心（上海）的小伙伴们：王博、王鑫、蒋灿、彭川、罗正海、黄诚一、刘慧娟、何奇、刘钰，等等。正是他们的鼓励和帮助，我才有完成本书的勇气和动力。同时，还要感谢基础软件中心（上海）关健和陈敏敏两位领导。
腾讯TDSQL技术专家赵伟、Oracle MySQL技术专家赖铮阅读了本书的书稿并给出了许多具有洞察力的建议和意见，使得本书增色不少。同样，两位数据库内核专家也为本书撰写了精彩的评论，两位对本书的谬赞让我诚惶诚恐，唯恐书中的错误和不足让两位专家的鼓励蒙羞。两位专家作为我的好友，其毋庸置疑的技术能力和为人、做事一直是我前进路上的榜样。在此，对二位的鼓励表示真挚的感谢。
由书稿到铅字出版，离不开本书的责任编辑博文视点陈晓猛编辑的辛勤工作。无论从本书主题、版式风格，到稿件的修改等诸多方面都体现了晓猛编辑出色的业务能力和辛勤的劳动。本书能够顺利出版离不开他的辛劳，在此表示衷心感谢。
同样要对我成长路上的诸多师长和同学及友人表达最衷心的感谢，正是他们的谆谆教诲和陪伴，我才可以自由地追逐梦想。

李浩

数据库技术

作者具有多年软件开发经验，现任职于北大方正信息产业集团基础软件中心（上海）担任数据库架构师，主要负责查询引擎查询优化方面工作。曾参与方正智睿系列数据库研发，主要负责查询引擎模块的设计和开发，并拥有数十项发明专利。主要研究兴趣包括：查询引擎、大规模并行处理系统（MPP）及SQL on Hadoop相关系统。

腾讯TDSQL数据库技术专家、MySQL技术专家力荐

本书配套资源下载

对不起，暂无音视频资源！

PostgreSQL查询引擎源码技术探析