PolarDB 并行查询的前世今生

修改搜图

本文会深入介绍PolarDB MySQL在并行查询这一企业级查询加快特性上做的技能探究、形状演进和相关组件的完结原理，所触及功用随PolarDB MySQL 8.0.2版别上线。

一  布景

1  PolarDB

云的兴起为陈旧而固执的数据库商场带来了新的发展机会，据Gartner预测，到 2022 年，全部数据库中将有 75% 部署或迁移到云平台，云原生数据库的诞生为各个数据库厂商、云服务供应商供给了弯道超车的绝好机会，看一下AWS在Re:invent 2020发布的Babelfish，就能嗅到它在数据库商场的野心有多大。
AWS在2017年宣布的关于Aurora的这篇paper[1]，引领了云原生联系型数据库的发展趋势，而作为国内最早布局云核算的厂商，阿里云也在2018年推出了自己的云原生联系数据库PolarDB，和Aurora的理念共同，PolarDB深度交融了云上基础设施，方针是在为客户供给云上特有的扩展性、弹性、高可用性的一起，能够具有更低的呼应推迟和更高的并发吞吐，其根本架构如下：
修改搜图
底层的分布式同享存储突破了单机存储容量的约束，并且能够随用户的数据量增加主动弹性扩容，核算层则是一写多读的典型拓扑，利用RDMA供给的高速长途拜访才能来抵消核算存储分离带来的额定网络开销。

2  应战

从上图能够看到，存储层将答应远大于单机的数据容量（现在是128T），乃至线上会出现一些用户，单表容量到达xx T的级别，这在依据MySQL主从复制的传统部署中是不可思议的。一起许多用户会有对事务数据的实时剖析诉求，如核算、报表等，但咱们对MySQL的直观印象便是：小事务处理快，并发才能强，剖析才能弱，关于这些实时性剖析查询，该怎么应对呢？

3  方案

首先要说的是，跟着互联网的发展，数据量的爆破，一定的数据剖析才能、异构数据的处理才能开端成为事务型数据库的标配，MySQL社区在8.0版别中也对自身的查询处理才能做了补强，包含对子查询的transformation、hash join、window function支撑等，一起PolarDB MySQL优化器团队也做了许多作业来提高对杂乱查询的处理才能，如核算信息增强、子查询更多样的transformation、query cache等。

并行查询(Parallel Query)是PolarDB MySQL在推出伊始就装备的查询加快功用，本质上它处理的便是一个最中心的问题：MySQL的查询履行是单线程的，无法充分利用现代多核大内存的硬件资源。经过多线程并行履行来下降包含IO以及CPU核算在内的处理时刻，来完结呼应时刻的大幅下降。究竟，关于用户来说，一条查询假如能够1分钟用10个核完结，总比10分钟用1个核完结更有意义。此外全部老练的商业型数据库也都具有并行查询的才能。
修改搜图

---

二  并行查询介绍

1  特性

并行查询能够说是PolarDB MySQL在核算层最为重要杂乱度也最高的功用组件，跟着PolarDB的推出现已线上安稳运转多年，并且一直在继续演进，它具有如下几个特性：

• 彻底依据MySQL codebase，原生的MySQL 100%兼容，这儿包含

• 语法兼容
• 类型兼容
• 行为兼容

  
  

• 0 附加成本，随产品发布就带着的功用

• 无需额定存储资源
• 无需额定核算节点

  
  

• 0 保护成本，运用和一般查询没有任何不同，仅仅呼应变快了

• 随集群部署，开箱即用
• 对事务无侵入
• 单一装备参数（并行度）

  
  

• 实时性剖析，PolarDB原生的一部分，受惠于REDO物理复制的低推迟

• 一致底层事务型数据
• 提交即可见

  
  

• 极致功用，跟着PQ的不断完善，关于剖析型算子、杂乱查询结构的支撑才能不断提高

• 全算子并行
• 高效流水线
• 杂乱SQL结构支撑

  
  

• 安稳可靠，作为企业级特性，这个毋庸置疑

• 扩展MySQL测验体系
• 线上多年堆集
• 齐备确诊体系

上面这些听起来像是广告宣传词，但也确实是并行查询的中心竞争力。

2  演进

并行查询的功用是继续堆集起来的，从开端的PQ1.0到PQ2.0，现在进入了跨节点并行的研发阶段并且很快会上线发布，这儿咱们先不介绍跨节点并行才能，只重视已上线的情况。

PQ1.0

最早发布的并行查询才能，其根本的思路是核算的下推，将尽或许多的核算分发到多个worker上并行完结，这样像IO这样的重操作就能够一起进行，但和一般的share-nothing分布式数据库不同，因为底层同享存储，PolarDB并行中关于数据的分片是逻辑而非物理的，每个worker都能够看到全量的表数据，关于逻辑分片后边履行器部分会介绍。
并行拆分的方案形状典型如下：
修改搜图
能够看到有这么几个特点：

• 履行形式是简略的scatter-gather，也便是只要一个plan slice，多个worker完结相同的功用，汇总到leader

• 尽或许的下推算子到worker上

• leader担任完结无法下推的核算

这个方案能够处理许多线上的慢查询问题，得到很好的加快作用，不过也存在着一定的局限性

• 方案形状是单一的，导致算子的并行方法单一，比方group by + aggregation，只能经过二阶段的集合来完结：worker先做partial aggregation，leader上做final aggregation

• 一旦leader上完结集合操作，后续假如有distinct / window function / order by等，都只能在leader上完结，构成单点瓶颈

• 假如存在数据倾斜，会使部分worker没有作业可做，导致并行扩展性差

• 此外完结上还有一些待完善的地方，例如少数算子不支撑并行、一些杂乱的查询嵌套结构不支撑并行

总得来说，PQ1.0的并行形状和PostgreSQL社区的方案比较像，还有改善空间，究竟全部商业数据库的并行形状都要更灵活杂乱。

PQ2.0

PQ2.0弥补了上面说到的那些局限性，从履行形式上对齐了Oracle/SQL Server，完结了愈加强壮的多阶段并行。
方案形状典型如下：
修改搜图
第一眼看到的改变是这儿存在多个worker group，PQ2.0的履行方案是多阶段的，方案会被拆分为若干片段(plan slice)，每个slice由一组worker并行完结，在slice之间经过exchange数据通道传递中心成果，并触发后续slice的流水线履行。其间一些补强的点包含：

• 全新的Cost-based并行优化器，依据核算信息和价值决定最优方案形状

• 全算子的并行支撑，包含上面说到的杂乱的多层嵌套结构，也能够做到彻底的并行

• 引进exchange算子，也便是支撑shuffle/broadcast这样的数据分发操作

• 引进一定自适应才能，即便并行优化完结了，也能够依据资源负载情况做动态调整，如回退串行或下降并行度

这些改变意味着什么呢？咱们来看一个简略且实际的比方：

																				

																					
																					

																						
																						

																							


																						

																					

																					

																						
																						

																							


																						

																					

																					

																						
																						

																							


																						

																					

																					

																						
																						

																							


																						

																					

																					

																						
																						

																							


																						

																					

																					

																						
																						

																							


																						

																					

																					

																						
																						

																							


																						

																					

																				

SELECT t1.a, sum(t2.b)FROMt1 JOIN t2 ON t1.a = t2.aJOIN t3 ON t2.c = t3.cGROUP BY t1.aORDER BY t1.aLIMIT 10;

修改搜图
对上面的简略查询，在经过优化后，PQ1.0会生成图中的履行方案。

• 在join的表调集中，寻找一个能够做逻辑分片的表做拆分，假如3个表都缺乏以拆分足够多的分片，那就选最多的那个，比方这儿挑选了t2，它或许拆出12个分片，但依然无法满意并行度16的要求，导致有4个worker读不到数据而idle。

• 集合操作先在worker上做部分集合，leader上做汇总集合，假如各个worker上分组的聚拢不佳，导致leader依然会收到来自下面的许多分组，leader上就会依然有很重的集合核算，leader算的慢了，会来不及收worker数据，从而反压worker的履行速度，导致查询全体变慢。

修改搜图

而PQ2.0的履行方案如下
修改搜图

• 尽管依然只能在t2上做数据分片，但12个worker只需求完结t1 join t2这个操作，在join完结后一般数据量会膨胀，经过Shuffle(Repartition)将更多的中心成果分发到后续的slice中，从而以更高的并行度完结与t3的join

  
  

• 各worker完结部分集合后，假如分组仍许多，能够依据group by key做一次Shuffle来将数据打散到下一层slice，下一组worker会并行完结较重的集合操作，以及随后的order by部分排序，终究leader只需求做一次merge sort的汇总

修改搜图
这样就处理了单点瓶颈和数据量缺乏导致的扩展性问题，完结线性加快。

为什么线性扩展如此重要？
修改搜图
从上图能够看到，跟着并行度的增加，E2E的呼应时刻是线性下降的，这关于客户有两个重要作用：

• 跟着事务增加数据不断膨胀，经过相应提高并行度来运用匹配的核算资源，来继续得到安稳可预期的查询功用

• 一直快速的剖析时刻能够驱动快速的事务决策，使企业在快速改变的商场环境中坚持竞争力

完美的线性加快便是，Parallel RT = Serial RT / CPU cores，当然这并不实际

3  架构

并行查询组件的全体架构如下
修改搜图
中心部分包含在3层中，从上到下顺次是：

• Cost-based Parallel Optimizer，嵌入在MySQL的优化器结构中，完结并行优化部分

• Parallel Plan Generator，依据笼统的并行方案描绘，生成可供worker履行的物理履行方案

• Parallel Executor，并行履行器组件，包含一些算子内并行功用和数据分发功用等

详细每个组件的完结会在后边详细介绍

4  功用

修改搜图
由所以个人文章这儿隐去了详细履行时刻（能够网上查找下），主要看下PQ2.0的查询加快才能，这儿并行度是32（或许有同学会古怪为什么Q6/Q12的加快比超过了32，后边会详细讲到）
总的数字是：100%的SQL能够被加快，总和加快比是18.8倍。

5  运用方法

从易用性的视点，用户开启并行查询只需求设置一个参数：
set max_parallel_degree = xxx;
假如想查看并行履行方案，只需求和一般查询相同，履行EXPLAIN / EXPLAIN FORMAT=TREE 即可。
修改搜图
Explain 做了必要的增强来显现并行相关的information，包含价值、并行形式、分发方法等。

三  并行查询完结

上面是一些总体性的内容，没有什么技能细节，后边的章节会顺次dive到每个模块中介绍下。

1  并行优化器

在PQ2.0中，因为方案形状会变得愈加多样，假如拆分方案仅仅依靠简略规矩和简略核算是很难得到最优解的，因而咱们从头完结了一套彻底依据cost的并行优化器。
根本的流程是在MySQL串行优化后，进一步做并行拆分，这儿或许有同学疑惑为什么不像Oracle或Greenplum那样搞成一体化的，也便是在优化流程中一致考虑串/并行的履行战略。原因在于，MySQL的优化流程中，各个子过程之间没有明晰的鸿沟，并且深度递归的join ordering算法以及嵌入其间的semi-join优化战略挑选等，都使得代码逻辑与结构愈加杂乱，很难在不许多侵入原生代码的前提下完结一体化优化，而一旦对社区代码损坏严重，就无法follow社区后续的版别迭代，享用社区盈利。
因而采用了两步走的优化流程，这也是业界常用的方法，如Spark、CockroachDB、SQL Server PDW、Oceanbase等都采用了类似的方案。

价值模型的增强

既然是依据cost的优化，在过程中就必然要能够得到各个算子并行履行的价值信息。为此PolarDB也做了许多核算信息增强的作业：

1. 核算信息主动更新

   
   

2. 串行优化流程中做针对并行履行的补强，例如修正table扫描方法等，这也是上面功用数据中Q6/Q12会有超线性加快比的原因

   
   

3. 全算子核算信息推导+价值核算，补充了一系列的cost formula和cardinality estimation推导机制

修改搜图
这儿只能展示下核算信息增强带来的作用，收益的不止是并行查询，串行履行也会提高。

自适应履行战略

在早期版别中，串行优化和并行优化，并行优化和并行方案生成之间存在一定的耦合性，导致的问题便是在开端并行优化后会无法退化回串行，假如体系中这样的查询并发较多，会一起占用许多worker线程导致CPU打爆。新的并行优化器处理了这个问题。
修改搜图

1. 串行优化与并行优化解耦，并行优化会从头构建笼统算子树，并以此为输入开端enumeration

   
   

2. 并行优化与并行方案生成解耦，优化的成果是方案子片段的笼统描绘，作为输出进行plan generation

这样就使履行战略的灵活性成为或许，答应在资源缺乏情况下，要么退回串行，要么下降并行度，或许进入调度行列排队等资源。

依据价值的穷尽式枚举

这是一个比较大的论题，概略来说，并行优化是一个自底向上，依据动态规划的穷尽式枚举过程，完结思路参阅了SQL Server PDW paper[2]，在过程中会针对每个算子，枚举或许的并行履行方法和数据分发方法，并依据输出数据的phsical property(distribution + order)构建物理等价类，从而做部分剪枝，获取部分子问题的最优解并向上层传递，终究到root operator获取大局最优解。
下图是针对t1 NLJ t2这个算子，做枚举过程的一个简要示例：
修改搜图
在全体枚举完结后，方案空间中会产生一系列带有数据分发Exchange Enforcer的物理算子树，依据价值挑选最优树即可，然后以Enforcer作为子方案的切分点，能够构建出一系列的履行方案笼统描绘，输出到plan generator中。

2  并行方案生成

从工程完结视点，并行方案生成能够说是整个组件中杂乱度最高，坑最多的部分。这儿采用了physical plan clone的机制来完结，也便是说，依据优化器生成的并行方案描绘，从原始串行方案clone出各个方案片段的物理履行方案。
为什么要用这种方法呢？还是和MySQL自身机制相关，MySQL的优化和履行是耦合在一起的，并没有一个明晰的鸿沟，也便是在优化过程中构建了相关的履行结构。所以没有办法依据一个独立的方案描绘，直接构建出各个物理履行结构，只能从串行方案中“clone”出来，这能够说是全部杂乱度的本源。
MySQL的履行结构非常杂乱，expression(Item)和query block(SELECT_LEX)的交叉引证，内外层查询的相关(Item_ref)等等，都使得这项使命难度大增，但在这个不断填坑不断完善的过程中，团队也对MySQL的优化履行结构有了很深入的理解，还发现了社区不少bug...
修改搜图
以上图中简略的查询为例

																																									

																																										
																																										

																																											
																																											

																																												


																																											

																																										

																																										

																																											
																																											

																																												


																																											

																																										

																																										

																																											
																																											

																																												


																																											

																																										

																																										

																																											
																																											

																																												


																																											

																																										

																																										

																																											
																																											

																																												


																																											

																																										

																																									

SELECT t1.a, sum(t2.b) sumbFROM t1 join t2ON t1.c = t2.cGROUP BY t1.aORDER BY sumb;

尽管社区对履行器做了依据Iterator model的重构，但本质上，物理履行方案依然是由QEP_TAB组成的序列，其间group by+aggr由一个tmp table1完结，order by由tmp table2完结。
在做plan generation时，有两个中心的操作：

• clone

依据串行physical plan和子slice的描绘，将相对应的结构clone到各个worker线程中，如上图右下部分，将在worker上履行的t1 join t2和下推的集合操作clone了下来。

• refix

原始的串行方案需求转换为leader方案，因而要替掉不必要的履行结构并调整一些引证联系，如上图右上部分，因为t1 join t2和部分集合操作现已下推，leader上需求去掉不必要的结构，并替换为从一个collector table中读取worker传递上来的数据，一起需求将后续过程中引证的t1/t2表的结构转为引证collector表的对应结构。
这儿仅仅举了最为简略的比方，还没有触及子查询和多阶段plan，实际的工程完结成本要高许多。

3  并行履行器

PQ完结了一系列算子内并行的机制，如对表的逻辑分区和并行扫描，parallel hash join等，来使并行履行成为或许或进一步提高功用，还有多样化的子查询处理机制等，这儿选一些具有代表性的来介绍。

parallel scan

PolarDB是同享存储的，全部数据对全部节点均可见，这和sharding的分布式体系有所不同，不同worker处理哪一部分数据无法预先确定，因而采用了逻辑分区的方案：
修改搜图
在btree这个level，会将数据切分红许多小分片，不同worker担任不同分片来触发并行履行，这儿有一些优化点：

1. 尽量做细粒度的切分，使分片数 >> worker数，然后worker之间经过round robin的方法去“抢”分片来履行，这样天然做到了能者多劳，防止因为数据分布skew导致的负载不均衡问题，这是shared storage体系的一个天然优势。

   
   

2. 切分时能够不用dive到叶子节点，也便是以page作为最小分区单位，来加快初始分区速度。

parallel hash join

hash join是社区8.0为加快剖析型查询所引进的功用，并跟着版别演进对semi hash/anti hash/left hash join均做了支撑，PolarDB也引进了这些patch来完结完好的hash join功用，并完结了多种并行履行战略。
修改搜图
parallel hash join在build/probe两个阶段均做了并行支撑

1. build阶段，多个worker向同一个同享的lock-free hash table中插入数据。

   
   

2. probe阶段，多个worker并行到hash table做查找。

两个阶段没有堆叠，这样就完结了全阶段的并行，但parallel hash join也有自身的问题，例如同享hash table过大导致spill to disk问题，并行插入尽管无锁，但仍有“同步”原语带来的cache invalidation。

partition hash join

partition hash join则能够防止以上问题，但价值则是引进数据shuffle的开销：
修改搜图
如图所示，查询的履行过程分为了3个阶段

1. build/probe两侧都依据join key做shuffle，将数据分发到方针partition；

   
   

2. 在每个partition内，build侧各自构建小hash table；

   
   

3. 在每个partition内，probe侧各自查找对应的hash table；

这样就在各个partition内，完结了co-located join，每个hash table都更小来防止落盘，此外也没有了build中的并发问题。
以上两个方案哪个更优？由并行优化器依据Cost决定。

子查询并行 - pushdown exec

这儿子查询是表达式中的一部分，能够存在于select list / where / having等子句中。关于相关子查询，仅有的并行方法是随外层依赖的数据（表）下推到worker中，在每个worker内完好履行，但因为外层并行了，每个worker中子查询履行次数还是能够等比例减少。
例如如下查询：

																																																					

																																																						
																																																						

																																																							
																																																							

																																																								


																																																							

																																																						

																																																						

																																																							
																																																							

																																																								


																																																							

																																																						

																																																						

																																																							
																																																							

																																																								


																																																							

																																																						

																																																						

																																																							
																																																							

																																																								


																																																							

																																																						

																																																						

																																																							
																																																							

																																																								


																																																							

																																																						

																																																						

																																																							
																																																							

																																																								


																																																							

																																																						

																																																					

SELECT c1 FROM t1WHERE EXISTS (  SELECT c1 FROM t2 WHERE t2.a = t1.a     <= EXISTS subquery  )ORDER BY c1LIMIT 10;

修改搜图EXISTS子查询完好的clone到各个worker中，跟着WHERE条件的evaluation重复触发履行。

子查询并行 - pushdown shared

这种并行方法的子查询能够是表达式的一部分，也能够是派生表(derived table)。
概略的来说，这种并行方法适用于非相关子查询，因而能够提前并行物化掉，构成一个暂时成果表，后续外层在并行中，各worker引证该子查询时能够直接从表中并行读取成果数据。
例如如下查询

																																																							

																																																								
																																																								

																																																									
																																																									

																																																										


																																																									

																																																								

																																																								

																																																									
																																																									

																																																										


																																																									

																																																								

																																																								

																																																									
																																																									

																																																										


																																																									

																																																								

																																																								

																																																									
																																																									

																																																										


																																																									

																																																								

																																																								

																																																									
																																																									

																																																										


																																																									

																																																								

																																																								

																																																									
																																																									

																																																										


																																																									

																																																								

																																																							

SELECT c1 FROM t1WHERE t1.c2 IN (  SELECT c2 FROM t2 WHERE t2.c1 < 15      <= IN subquery  )ORDER BY c1LIMIT 10;

修改搜图
另外线上用户的报表类查询中，一种非常常见的Query形式便是derived table的多层嵌套，关于这类SQL，pushdown shared战略能够很好的提高并行履行的功用，例如如下示例：
修改搜图
上图中每个色彩的方块，代表了一层query block，这儿就构成了多层derived table的嵌套逻辑，有些层中经过UNION ALL做了汇总，有些层则是多个表（包含derived table）的join，关于这样的查询，MySQL会对每个derived table做必要的物化，在外层构成一个暂时成果表参加后续核算，而PQ2.0对这种常见的查询形式做了更遍及的支撑，现在每一层查询的履行都是并行完结的，力争到达线性的加快作用。

Exchanges

要生成高效灵活的履行方案，数据分发组件是必不可少的，现在PolarDB支撑了Shuffle/Broadcast/Gather三种分发方法，完结上利用lock-free shared ring buffer，做到流水线形式的高效数据传输。

下图展示了Shuffle(Repartition)的根本形状
修改搜图
到这儿，并行查询的线上版别功用及完结现已大体介绍完了。
作为一款老练的企业级功用特性，团队还完结了一整套完善的辅助工具集，来配合提高产品的易用性，完结功用的可监控、可干预、可反馈，但这儿篇幅现已很大了，就先不介绍了。

四  未来规划

这儿说是未来规划并不切当因为团队现已在跨节点并行上做了许多的作业并进入了开发周期的尾端，跨节点的并行会把针对海量数据的杂乱查询才能提高到另一个水平：

• 打通节点间核算资源，完结更高的核算并行度

• 突破单节点在IO / CPU上的瓶颈，充分利用分布式存储的高吞吐才能

• 结合大局节点管理与资源视图，平衡调度大局核算资源，完结负载均衡的一起确保查询功用

• 结合大局共同性视图，确保对事务性数据的正确读取

修改搜图
[1]https://www.allthingsdistributed.com/files/p1041-verbitski.pdf[2]https://www.scinapse.io/papers/2160963784#fullText

---

互联网技能实战营·数据智能专题

互联网企业数据运营正在经历从工具化到数据化，从数据化向智能化演进的改变。以数据智能驱动科学运营，洞察用户行为，优化运营战略，从而完结用户的精细化和智能化运营。

本次课程面向重视数据管理与用户增加的互娱、电商、游戏等互联网企业，特邀阿里云的技能专家分享最佳实践和处理方案，您可按需挑选想要学习的课程。