OpenPie 拓数派

PieCloudDB Database 新一代优化器「达奇」:专为云原生和分布式场景而打造

2023-03-22
3月3日,PostgreSQL 中国技术大会在杭州拉开帷幕。作为 PostgreSQL 技术领域的年度盛会, PostgreSQL 中国技术大会已经连续12年,为所有热爱数据库技术的小伙伴们提供了一个开放合作、共享互助的平台。而本届大会,围绕着安全可靠、突破、进化等主题,召集众多业内大咖和技术高手在这里进行技术切磋与思想碰撞。 作为国内云上数据和数据计算领域的 Day-1 准独角兽,拓数派技术专家郭峰受邀出席本次大会发表主题演讲。 



 

 

在演讲中,郭峰介绍了 PieCloudDB Database 打造的全新优化器——「达奇」。「达奇」名称起源于一款深受年轻人喜爱的游戏:《荒野大镖客》。游戏中一位名为「达奇」的NPC人物的口头禅正是「I have a plan」,和优化器的主要作用”不谋而合”。 

拓数派吉祥物「派派」 

 

优化器是数据库系统中的一个重要组件,它”负责”对用户的查询请求进行解析、优化和执行计划的生成,使得查询结果能够以最快速度和最高效率得到返回。优化器通过生成最优的查询执行计划,来达到优化查询性能的目的。而执行计划的好坏往往会造成成百上千的性能差异。PieCloudDB 打造的优化器「达奇」实现了大量的优化特性,作为数据库系统的”智囊团”,助PieCloudDB 提升性能。 


一、四大阶段的优化特性 


PieCloudDB 查询优化的处理过程一般被分为四个阶段:预处理阶段,扫描/连接优化阶段,扫描/连接之外的优化阶段,后处理阶段。「达奇」在这四个处理阶段均做了大量优化。

 

第一阶段:预处理阶段 


在预处理阶段,优化器「达奇」会通过逻辑上的等价变化,将查询树转换为更加简单高效的等式。由于还未获得一些统计信息来帮助计算代价信息,本阶段一般会通过一些被证明的规则来进行分发约束条件,简化表达式和连接树消除无用连接等操作。 


  • 把 IN, EXISTS 等类型的子查询转换为半连接


PieCloudDB 会基于子查询所在的位置和作用的不同,将子查询分为子连接(SubLink)和子查询(SubQuery)。子连接由于出现在WHERE/ON 等约束条件中,常伴随着ANY/ALL/EXISTS等谓语动词。如果执行器按照子连接的方式处理,会对查询效率造成影响。且由于会产生子计划(SubPlan),优化空间有限。因此,在查询优化的预处理阶段, PieCloudDB 会尽可能的把子连接转为semi-join或anti-join,从而具有更大的优化空间。 

 

以下面一段的 SQL查询为 例: 


SELECT … FROM foo WHEREEXISTS (SELECT1FROM bar WHERE foo.a = bar.c);  

 

其中 EXISTS 里是一个子查询,PieCloudDB 会在预处理阶段将其变成一个Semi-Join: 

 

SELECT ... FROM foo SEMIJOIN bar ON foo.a = bar.c; 

 

  • 提升子查询 


出现在 FROM 关键字后的子句是子查询语句。 如果不进行提升优化,在对这类子查询做执行时,会先做一个单独的计划,生成一个Sub-query scan,再与 Parent Query 做连接,常常无法找到最优解,造成较大的查询代价。 


以下面的例子为例,如果不做任何提升优化,会将 bar 和 baz 先做 JOIN 连接,由于没有连接条件,会直接将 bar 和 baz 做笛卡尔乘积,再和外面的 foo 做 JOIN 连接: 

SELECT * FROM foo JOIN (SELECT bar.c FROM bar JOIN baz ONTRUE) ASsubON foo.a = sub.c;  

 

做完提升后,bar 和 baz 就在同一层面上,可以先生成 foo 和 bar的join,再与baz做join连接,从而实现了代价更小: 

SELECT * FROM foo JOIN (bar JOIN baz ONTRUE) ON foo.a = bar.c;  

 

  • 把外连接转换为内连接/反连接 


外连接对谓词下推以及连接顺序搜索等都会有很多限制,因此「达奇」在预处理阶段会尽可能将外连接转换为内连接(Inner Join)或反连接(Anti Join。 


在下面的 SQL 语句中,LEFT JOIN 的结果会产生一些以 NULL 结尾的 tuple,而 WHERE 条件中的等号为严格约束条件,意味着输入如果为NULL,输出也必须是NULL或FALSE。如果 bar上的 column 为NULL值,则 bar.d = 42 的过滤结果为FALSE。也就是说,LEFT JOIN 产生的以 NULL 填充的 tuple 会被 WHERE 条件过滤掉,此时,LEFT JOIN 就从语义上变为了INNER JOIN。 


SELECT... FROM foo LEFT JOIN bar ON (...) WHERE bar.d = 42

 

在这样的情况下,PieCloudDB 「达奇」优化器自动识别此类查询,并利用这样的优化机会,将外连接转为内连接。 

SELECT... FROM foo INNER JOIN bar ON (...) WHERE bar.d = 42

 

对于某些情况下的外连接,PieCloudDB 优化器会在预处理阶段将外连接转换为反连接。以下面的SQL语句为例, 

SELECT * FROM foo LEFTJOIN bar ON foo.a = bar.c WHERE bar.c ISNULL

 

同前例,LEFT JOIN 也会产生很多以NULL填充的tuple的结果集,此时 WHERE 条件限定只取 bar.c 为NULL 的结果,此时的语义上 LEFT JOIN 就是一个反连接。PieCloudDB 会在预处理阶段自动检测到这种优化机会,并会将外连接转为反连接: 

SELECT * FROM foo ANTI JOIN bar on foo.a = bar.c; 

 

除了这些优化,在预处理阶段,优化器「达奇」还实现了多个优化,包括: 

  • 分发约束条件
  • 构建等价类
  • 收集外连接信息
  • 消除无用连接
  • 简化表达式

….

 

第二阶段: 扫描/连接优化阶段 


扫描/连接优化阶段可谓是优化器处理过程中最复杂的阶段。在这一阶段,优化器「达奇」会以代价驱动,处理查询语句中的 FROM 和 WHERE 部分,同时会考虑到 ORDER BY 的信息。 

 

在这一阶段,优化器「达奇」的处理主要可以分为两步。首先会为基表生成扫描路径,并计算扫描路径的代价和结果集大小,从而获得后面连接操作的代价。第二个步骤中,「达奇」会搜索整个连接顺序空间,为连接操作生成最优的连接路径。这一步骤的复杂度非常高(n!级别),PieCloudDB 采用了动态规划和遗传算法两个算法来进行处理,并根据 GUC 值进行算法选择。如果查询语句中涉及外连接,考虑到外连接对连接顺序的限制,无法像内连接那样随意切换连接顺序,会加大这一步骤的复杂度。 

 

第三阶段: 扫描/连接之外的优化阶段 


相对于第二阶段,这一阶段虽然处理的事情很多,但复杂度相对较低。在这一阶段,「达奇」会先处理Group By、聚集、窗口函数、DISTINCT,再对集合操作进行处理,最后再处理 ORDER BY。以上的每一步操作都会产生一个或多个路径,「达奇」会对这些路径根据代价大小进行筛选,并为筛选出的路径添加 LockRows,Limit,ModifyTable。 

 

第四阶段:后处理阶段 


经过前面三个阶段,「达奇」已经生成了一个大概的查询计划。在后处理阶段,「达奇」会把选出的最优路径转换为查询计划,并对最优计划进行一些调整。 

 

 

二、针对分布式和云原生的优化特性 


除了上述的优化特性,针对用户对于云上数据查询性能需求,PieCloudDB 优化器「达奇」对复杂查询场景做了大量的优化和改进,实现了众多高阶的分布式与云原生特性。 


「达奇」的分布式特性 


在以上优化特性的基础上,「达奇」优化器拓展了众多针对分布式的优化特性。首先「达奇」引入了 Motion 的概念,使数据可以在不同的执行节点(Executor)之间移动。利用 Motion,「达奇」可以产生分布式的查询计划。这些查询计划会被分为更小的单元,并被分发到不同的执行节点中并行执行。有了并行执行,很多复杂查询都能进行进一步的优化,例如对于聚集操作,利用分布式的优势,在执行节点之间可以通过多阶段聚集来提升性能。 

 

以这段查询为例来讲解一下多阶段聚集,针对这段SQL查询,「达奇」会生成这样的查询计划: 


# explain (costsoff) select sum(distinct b) from t groupby a; 

                            QUERY PLAN 
------------------------------------------------------------------ 
 Gather Motion 3:1  (slice1; segments: 3) 
   ->  HashAggregate 
         Group Key: a 
         ->  HashAggregate 
               Group Key: a, b 
               ->  Redistribute Motion 3:3  (slice2; segments: 3) 
                     Hash Key: a 
                     ->  Streaming HashAggregate 
                           Group Key: a, b 
                           ->  Seq Scan on t 

 

由于存在一个去重的操作,「达奇」会进行三个阶段的聚集,在第一个阶段,PieCloudDB 会在每个执行节点上,以 a,b 为 group key 先做一个局部的聚集,这里就完成了一个局部去重的操作。接着,利用 Motion 做一次 Reshuffle 的操作,此时再进行一次聚集操作,完成全局去重。最后再根据 group key 完成最后的聚集操作,得到查询结果。 

 

「达奇」的云原生特性 


由于PieCloudDB的存储引擎「简墨」采用的是对象存储的设计,结合这一设计,PieCloudDB 优化器「达奇」实现了更多高阶的优化,包括聚集下推、Block Skipping、预计算等。这里将对聚集下推进行介绍,关于「达奇」的其他云原生特性,欢迎关注即将陆续推出的其他内容。 

 

PieCloudDB 实现了聚集下推(Aggregate Pushdown),可以在查询执行计划中有效的减少数据的传输和处理,提高查询效率。在分析型场景中,SUM、AVG、MAX、MIN等聚集操作是常见的操作,可以用来对数据库表中的数据进行聚合计算。大部分数据仓库在处理聚集操作时,通常需要先完成对表的扫描和连接操作,之后再计算聚合函数。在数据量非常大的 情况下,这样的查询性能会比较低。 


而 PieCloudDB 优化器「达奇」实现的聚集下推优化策略,通过把聚集操作下推到连接操作之前去执行,可以极大的减少连接操作需要处理的数据量,经测试,在某些情况下,性能会得到成百甚至上千倍的提升。 

 

以下面的 SQL 查询为例,这段查询需要对 t1 表和 t2 表进行连接操作,在此基础上,根据 t1.a 做分组,来获得 t2.c 的平均值。在不进行聚集下推优化的情况下,会先完成 t1 和 t2 的连接操作,再按 t1.a的分组进行聚集操作。此时,如果 t1 和 t2 表都很大的话,进行连接操作的代价很高,会对性能产生一定影响。而在进行聚集下推的优化下,会在连接之前先做聚集操作,此时如果 t2.b非常有聚集性,数据量会减小很多,此时再进行连接操作,性能会大幅提高。 

 

# EXPLAIN (COSTS OFF) SELECT t1.a, avg(t2.c) FROM t1 JOIN t2 ON t1.b = t2.b GROUP BY t1.a; 

                        QUERY PLAN 
------------------------------------------------------------------- 
 Gather Motion 3:1  (slice1; segments: 3) 
   ->  Finalize GroupAggregate 
         Group Key: t1.a 
         ->  Sort 
               Sort Key: t1.a 
               ->  Redistribute Motion 3:3  (slice2; segments: 3) 
                     Hash Key: t1.a 
                     ->  Hash Join 
                           Hash Cond: (t1.b = t2.b) 
                           ->  Seq Scan on t1 
                           ->  Hash 
                               >  Broadcast Motion 3:3  (slice3; segments: 3) 
                                  ->  Partial HashAggregate 
                                      Group Key: t2.
                                       ->  Seq Scan on t2 

 

查询优化器是数据库系统最重要、也是最复杂的组件之一。 PieCloudDB 作为一款云原生虚拟数仓,将不断对优化器「达奇」进行打磨,在确保数据库系统的高效和稳定运行的前提下,不断驱动性能的提升。 

 

3月14日,基于新一代云原生数仓虚拟化打造的 PieCloudDB 「云上云」版已正式发布,欢迎大家登录拓数派官网免费试用。 


相关博文

暂无相关推荐