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

孙旭 2019-08-30 09:39:39

作者介绍

孙旭,腾讯云高级工程师。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,下次扫描的时候,可以从上次的状态开始。

最新评论
访客 2019年09月18日

请问下为什么不用logstash同步呢?

访客 2019年09月16日

写的太好了,我这就开始学

访客 2019年09月16日

Discretized Streams 就要过时了??

访客 2019年09月07日

写的就跟屎一样

访客 2019年09月01日

没看懂啊,PK的时候,没懂,怎就就从 (1,1)变成了…

活动预告