本文由 dbaplus 社群授权转载。
一、导语
数据库查询处理（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 中。如下查询：
调整聚集函数在适当的层次中计算，如下查询：
max(x.x2)在 SQL 语义上应该是在最外层查询中计算，而不是将 x.x2 传入到内层子查询，在内层子查询中计算 Aggregate 函数 max()的值。而对于如下查询：
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 为例，说明一下这个步骤的工作。对于查询：
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、排序等，从这些名称也可以看出他们就是关系代数的操作符，它们会被传给查询执行组件进行执行。如下查询计划示例：
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，下次扫描的时候，可以从上次的状态开始。
作者介绍：
孙旭，腾讯云高级工程师。10 年数据库内核研发经验，熟悉 PostgreSQL、Teradata 数据库内核，熟悉数据库的查询优化、执行、事务并发以及存储等子系统；对分布式数据库有深入的研究和研发经验。目前在腾讯云从事 CynosDB 数据库研发工作。
原文链接：
数据连接未来
分布式云行业实践指南（2023）
业内首个分布式云行业实践方法论、工具箱。
评论