作者介绍

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

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

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

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

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

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

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

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

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

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子句等，从其定义可以看出更多细节：

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

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

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

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

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

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

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

例如：

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

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

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

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

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

1）子查询处理

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

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

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

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，而不是完全的对所有的表进行排列组合求解。例如对于查询：

通常我们可能认为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、排序等，从这些名称也可以看出他们就是关系代数的操作符，它们会被传给查询执行组件进行执行。如下查询计划示例：

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

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

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

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

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

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

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

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，下次扫描的时候，可以从上次的状态开始。