腾讯云高级工程师如何玩转 PG 查询处理与执行器算法

阅读数:2772 2019 年 9 月 8 日 08:00

腾讯云高级工程师如何玩转PG查询处理与执行器算法

本文由 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 类型的语法规则以及操作符的优先级和结合律,例如,下段代码定义了操作符的优先级和结合规则:

腾讯云高级工程师如何玩转PG查询处理与执行器算法

下段代码定了语法规则:

腾讯云高级工程师如何玩转PG查询处理与执行器算法

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

腾讯云高级工程师如何玩转PG查询处理与执行器算法

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 结构体中可以看到这点:

腾讯云高级工程师如何玩转PG查询处理与执行器算法

例如:

  • 关系代数的投影是: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 算法。

腾讯云高级工程师如何玩转PG查询处理与执行器算法

这里执行计划并没有使用 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、排序等,从这些名称也可以看出他们就是关系代数的操作符,它们会被传给查询执行组件进行执行。如下查询计划示例:

腾讯云高级工程师如何玩转PG查询处理与执行器算法

5、查询执行

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

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

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

四、PostgreSQL 执行器算法之 SeqScan

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

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

1、页面结构

PostgreSQL 页面存储与大多数数据库的类似,包含:页面头,ItemId 数组,以及 Item(元组),布局如下:

腾讯云高级工程师如何玩转PG查询处理与执行器算法

其中 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 次数,提升性能。

腾讯云高级工程师如何玩转PG查询处理与执行器算法

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

2)读取页面进行扫描

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

腾讯云高级工程师如何玩转PG查询处理与执行器算法

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

腾讯云高级工程师如何玩转PG查询处理与执行器算法

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

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

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

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

作者介绍

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

原文链接

https://mp.weixin.qq.com/s?__biz=MzI4NTA1MDEwNg==&mid=2650780737&idx=2&sn=159122edf44b37d4d0ebcbc384cddd50&chksm=f3f901d4c48e88c213f3b4a95a259c84d7f00fc57349d849612b9d47ce2a0b4707f3c1511009&scene=27#wechat_redirect

评论

发布