深度 | 如何玩转PG查询处理与执行器算法

作者介绍

孙旭，腾讯云高级工程师。10年数据库内核研发经验，熟悉PostgreSQL、Teradata数据库内核，熟悉数据库的查询优化、执行、事务并发以及存储等子系统；对分布式数据库有深入的研究和研发经验。目前在腾讯云从事CynosDB数据库研发工作。

一、导语

数据库查询处理（Query Processing）是数据库比较核心的技术，也是距离用户最近的子系统。数据库系统在除了实现事务的隔离界别外，还需要在SQL上做到一定程度的兼容，因为数据库本身就是在做查询处理，很多的内核模块工作都是为了支持这个功能。本文将简要介绍一下PostgreSQL的查询处理过程。 

二、关系代数与SQL（结构化查询语言）

大家在学校学到的可能更多的是关系代数（Relational Algebra），它定义了一组在关系（Relation）上进行操作的操作符。关系代数的操作数是关系（即，数据库中的二维表），其结果也是关系。操作符包含如下几类：

• 集合操作符：交，并，差；
• 过滤/投影；
• 连接；
• 别名（alias）；
• 一些扩展的操作符，例如：分组，去重，Aggregate。

除了关系代数，还有一种描述二维关系表的操作方法：DataLog（Database Logic）。这种方式相对来说比较强大，关系代数的操作符都可以用它来表述，但是有些关系的操作是关系代数表示不了的，只能用DataLog来表述，比如：递归查询。

直接使用关系代数对数据库操作比较晦涩，难度比较高，因此，今天的商业数据库都实现了一种更高级的查询语言——SQL（Structured Query Language），在表达上更加简洁易懂，也更容易学习。

实际上，在数据库系统内部，SQL语句也是被转化成对应关系代数的操作符，然后再进行处理，只是这些工作对最终用户来说是不可见的。其实，关系型数据库直接的“本地语言”是关系代数，SQL语言只是人类与关系数据库进行交流的“更加便捷的”桥梁。

可能大家有疑问，为何使用SQL作为交流桥梁，而不是用C、Java或者Python作为数据库的查询语言？

因为一个较短的SQL可以完成千百行C或者Java的工作，特别是在访问一些层次化的数据模型（例如：Oracle的层次查询，一条语句可以把层次结构输出出来；PostgreSQL的WITH-RECURSIVE语句也可以完成类似的功能）。

更加重要的是，数据库内核在实现SQL查询的时候，可以对SQL进行特定的优化，产生更加有效的访问方法，这些都是高级语言不太可能具备的功能。

三、PostgreSQL查询处理流程

从用户在客户端发送一条SQL语句，经过网络传输给PostgreSQL进行处理、执行，其流程经过如下几个步骤：

1、语法分析

SQL字符串可以认为是一个大的正则式，语法分析来检查这个大的“正则式”是否match定义好的规则。

在PostgreSQL中，pg_parse_query是语法分析的入口函数，实际上由scan.l（Flex文件）以及gram.y（Bison文件）完成语法检查。

scan.l是词法分析，将输入SQL分解一个个的Token，输入到gram.y中进行规则匹配。gram.y中定义了所有SQL类型的语法规则以及操作符的优先级和结合律，例如，下段代码定义了操作符的优先级和结合规则：

下段代码定了语法规则：

语法分析结束后，以查询（SELECT）为例，返回的结构体是SelectStmt，它会作为作为语义分析模块的输入。SelectStmt保存了SQL语句中的各个语法子部分，例如：from子句，投影列，group子句等，从其定义可以看出更多细节：

2、语法检查

parse_analyze()函数是这一步的入口函数，根据不同的语句类型调用transformXXXXStmt()函数进行分析处理。对于SelectStmt，调用的transformSelectStmt()，对于DeleteStmt调用transformDeleteStmt()。在这一步将会：

• 检查表是否存在，列是否合法，将表、排序列、投影列等转化为内部对象ID；
• SQL语义是否正确合法。

比如：Aggregate 函数不能用在WHERE中。如下查询：

select 1 from x where max(x2) > 1;

调整聚集函数在适当的层次中计算，如下查询：

select (select max(x.x2) from y) from x;

max(x.x2)在SQL语义上应该是在最外层查询中计算，而不是将x.x2传入到内层子查询，在内层子查询中计算Aggregate函数max()的值。而对于如下查询：

select (select max(x.x2+y.x2) from y) from x;

max(x.x2+y.x2)是在内层子查询中被计算，而不是作为外层查询的Aggregate函数。

经过语义检查，会将SelectStmt变形为Query结构，作为查询重写的输入。Query结构包含的部分与SelectStmt类似，只不过内容更加丰富：

• 保存的都是数据库内部的对象信息；
• 一些flag标记，表明是否包含：Aggregate函数、窗口函数、SubLink子查询等；
• 确定了表达式所在的Query层次。

之前提到过，数据库内核处理SQL时都是转化成关系代数相关的元素，这个在Query结构体中可以看到这点：

例如：

• 关系代数的投影是：targetList；
• 关系代数的过滤/join是：jointree；
• 关系代数的Aggregate是：targetList；
• 关系代数的分组：groupClause；
• 关系代数的sort是：sortClause。

后续所有的工作都是基于上面的元素进行。

3、查询重写

根据用户定义的规则对查询进行重写，实际是对Query结构里面的成员进行修改或替换，这些规则可以使用CREATE RULE创建。如果用户在查询对应的表上没有规则，此步跳过。

4、查询优化

查询优化是比较复杂子系统，通常称这个模块是“优化器”，也用来衡量数据库系统优秀的一个方面。在数据库领域另一个复杂的子系统是事务处理，这里也不做展开。

PostgreSQL在这一步的输入是Query对象，入口函数是planner()，输出查询计划（Query Plan），查询计划是指导查询如何被执行以及用何种方法执行的一种结构，通常是树形结构。

优化器做的主要工作就是对Query结构的各个语法部分，选择较优的执行算法，输出较优的执行计划。在PostgreSQL中，通常分成如下几步：

1）子查询处理

在PostgreSQL内部有2类的子查询：一种在from语句后面称为SubQuery，另一种在作为表达式的一部分，可以出现在targetList，过滤条件，连接条件中，称为sub-link。

这两种都可以统称为Sub-Select，而优化器在这一步会进行Sub-Select Elimination：将子查询上拉到顶层查询，消除子查询。

这样做可以减少查询层数，增加上层表的个数，从而增加join顺序的搜索空间，有助于找到较优的连接顺序。以sub-link为例，说明一下这个步骤的工作。对于查询：

select * from x where x.x2 in (select y.x2 from y);

PostgreSQL在这步可以将IN语句转化成Semi-Join，原来的O(m*n)的查找算法简化为O(1)HASH-JOIN算法。

这里执行计划并没有使用Hash Semi-Join，是因为inner plantree用了group hashagg进行了去重，所以原来的Semi-Join可以进一步优化为Hash Join，这种优化进一步扩大了Join顺序搜索空间。

2）执行表达式预处理

在这一步，会将targetList，过滤条件等列修改为对基表的引用；对表达式里面的SubLink递归调用优化器优先进行优化；计算表达式里面的常量表达式等。

3）移除无用的GROUP BY列

如果内核可以确定GROUP BY中的一些属性集合Y函数依赖于其他属性集合X，那么可以删除GROUP BY中的属性集合Y。函数依赖检查工作由check_functional_grouping完成。这样可以减少分组计算代价。

4）Reduce outer join

将某些OUTER JOIN转化为INNER JOIN。

5）选择优化的Join顺序

在这一步完成主要完成：条件的下推，基于连接条件生成等价类，以及通过动态规划选择较优的JOIN顺序。从整体来看，JOIN顺序的选择是Condition-Driven，而不是完全的对所有的表进行排列组合求解。例如对于查询：

select * from r, p, q where r1 = (p1+q1) and r2=q2;

通常我们可能认为r和q在r2=q2的条件进行连接，然后与p在r1 = (p1+q1)上进行连接；但是PostgreSQL内核在也会做这样的尝试：将p和q进行product join，再与r在条件r1 = (p1+q1) and r2=q2;进行连接，p和q之所以可以连接完全是由r1 = (p1+q1)决定的。

6）其他子句优化处理

做完Join Plan之后，再针对GROUP BY、Aggregate、ORDER BY、LIMIT等子句进行处理。以GROUP BY为例，在PostgreSQL内部，实现GROUP BY的有2个算法：Sort Group By以及 HashAgg Group By，通过函数cost_group以及cost_agg分别来计算二者代价，选择较优的算法执行。

完成这些这些步骤后，调用set_plan_references()以及SS_finalize_plan()函数最后处理参数和变量引用后，就可以输出最终的查询计划（Execution Query Plan）了。查询计划由很多节点组成：投影、扫描、连接、Aggregate、GROUP BY、排序等，从这些名称也可以看出他们就是关系代数的操作符，它们会被传给查询执行组件进行执行。如下查询计划示例：

5、查询执行

这是查询处理的最后一步，将优化器输出的执行计划，进行初始化、执行。查询执行子系统我们一般称为执行器。执行过程有ExecutorStart、ExecutorRun、ExecutorFinish这三个入口函数，分别完成对查询计划的初始化，执行，以及清理。在这个过程中会访问数据库的其他子系统，如：事务系统、存储系统、日志系统。

以上就是在PostgreSQL内核中对一个查询处理的整个生命周期，基本可以了解到一个SQL字符串在数据库内核中是如何一步步被解析，直到到执行的基本过程。

上文中描述的一些方法和理论不仅仅在PostgreSQL数据库有效，也可以推导到其他数据库系统中。

四、PostgreSQL执行器算法之SeqScan

上文讲述了数据库内核中查询处理的基本流程，现在我们先展开讲述执行器算法。

数据库的执行器包含了很多个算子的执行算法，比较简单的一种就是SeqScan，就是从按照顺序（一般是存储顺序）对表进行扫描。

1、页面结构

PostgreSQL页面存储与大多数数据库的类似，包含：页面头，ItemId 数组，以及Item（元组），布局如下：

其中PageHeader包含了页面LSN，ItemId数组最后一个元素的页面偏移（pd_lower），第一条元组在页面内偏移（pd_upper），以及其他字段。

2、顺序扫描算法

PostgreSQL的顺序扫描的入口函数是SeqNext，每次执行这个函数会返回一条元组，主要工作是由heapgettup：

1）初始化扫描过程

初始化扫描过程就是设置HeapScanDesc对象，主要设置初始扫描的页面，一般从0号页面的第一个元组开始，即scan->rs_startblock是0。

在PostgreSQL的扫描过程有一个优化，即sync_scan，这个特性允许当前的扫描从表的中间页面开始扫描，这个页面是其他扫描进程填写到共享内存，由ss_report_location完成，代表这些页面刚刚被访问过，如果当前扫描从这些页面开始，那么可以直接在内存中访问到，从而减少存储读取页面的IO次数，提升性能。

每次更新表的sync start page时，需要遍历整个list。为了减少这个list的访问，每隔SYNC_SCAN_REPORT_INTERVAL个页面才去更新list，这个数值是128 * 1024 / BLCKSZ。

2）读取页面进行扫描

按照页面结构扫描页面。首先读取页面头（PageHeaderData）的pd_linp成员，这是一个Offset数组（ItemIdData），记录了元组在页面上的偏移（lp_off）。

后续的主要逻辑是遍历pd_linp数组，通过offset+page地址获取到元组内存地址。然后对元组做可见性判断。逻辑如下：

HeapTupleSatisfiesVisibility进行元组可见性判断，PostgreSQL是MVCC实现的事务隔离，这个函数就是MVCC的入口逻辑。

3）读取下一个页面继续进行扫描

继续读取后续页面进行扫描。

所有的扫描状态保存在HeapScanDesc，下次扫描的时候，可以从上次的状态开始。

江湖召集令

9月27日-11月6日，腾讯云数据库王者挑战赛（点击查看详情） 等你挑战！花几分钟参加比赛免费将☟☟抱回家！

• MacBook/iPhone 11/AirPods
• 25台Kindle
• 8万元腾讯云创业基金
• MySQL之父 Michael Widenius 面对面交流

拥有与殿堂级大神的合影和亲笔签名书籍的你，

能让隔壁码农羡慕到流泪！

转发下方海报参与活动可以获得腾讯公仔和腾讯云数据库购买直抵代金券，详情请添加海报上机器人二维码咨询。

 比赛详情&报名入口

请扫下方二维码

↓↓活动报名直达