更新时间:2022-06-13 13:02:58
最近一年一直在做PolarDB的并行优化器,过程中调研了各种分布式数据库系统的优化和执行框架,后续几篇文章将一一分享,首先介绍对PolarDB MySQL的并行优化框架影响最大的,也就是SQL Server PDW。
SQL Server PDW(Parallel DataWarehouse)是SQL Server的MPP版本,目前已经演进为Azure DataWarehouse部署在云上,用来存储大容量数据并处理分析型查询。总体上是一个share nothing的经典MPP架构,类似于Greenplum,它也会利用单机SQL Server作为其sharding data和meta data的存储+计算实例。
集群中每个节点都部署单个SQL Server instance + DMS服务,节点具备2种角色:
表数据的分片方式包括hash-partitioned和replicated(复制表)。
用户query到达control node后,优化生成分布式执行计划,称为DSQL。和MemSQL不同,PDW的分布式plan可以用一系列的step来描述,每个step之间不构成pipelining,step直接顺序依次执行,中间结果数据要物化到temp table后,才能开始下一step,step内是并行。
DSQL plan包含4种operation,每种operation都用SQL来描述(和MemSQL类似)
整体来说,PDW的查询优化分为了2个步骤,分别在2个不同的组件中完成。
由于SQL Server的单机优化器是基于Cascades的,优化的结果保存在一个Memo的结构中,有关Cascades的原理,可参考之前的paper解读以及Orca的实现。但有所不同的是,这里并不选出最优的串行执行计划,而是将Memo中整个search space都保留下来。
3. 将Memo传递给XML generator做序列化。
4. 传递Memo给PDW optimizer,它基于memo中各种alternative的plans,根据数据分布情况,枚举可能的分布式执行方式+数据分发方式。相当于扩展了search space的新维度,加入了分布相关的信息,生成了新的候选plan集合,并基于cost,从中选出最优结果。
这种2-pass的方式有很多好处,首先,它可以完全复用SQL Server强大的单机优化器能力,众所周知SQL Server的QO应该是众多commercial database中最为优秀的,这样实现完全解耦了并行优化和单机优化,工程难度也降低了1个数量级。而且由于保存了整个Memo,不会导致串 -> 并带来的计划次优性问题。
在分布式组件PDW optimizer中,只需要去扩展DMS cost model,扩展physical property加入distribution即可。
从上图的流程可以看到,概念上这个过程并不复杂,但工程实现的挑战还是很多的,下面一一介绍。
这是本篇paper的核心,也就是如何枚举分布式算子,基本原理如下
引入针对特定列(join列/group列)的distribution propery:(哪列,如何分布)
从root group中获取最优的plan tree
从paper中的描述来看,PDW的cost model只考虑数据传输+DMS做temp table物化的代价,而不考虑执行SQL操作的代价,这有几个原因
其基本假设是
但很遗憾paper没有给出设计细节。
DMS支持多种数据分发方式,这和PDW的并行执行能力相关,例如
Shuffle Move(N : N) ,最经典的redistribution,基于shuffle key的hash value
Partition Move(N : 1),相当于汇总
Broadcast Move (N : ALL),数据从部分compute node分发到所有compute node
Replicated broadcast(1 : ALL),从1个compute node分发到所有compute node
...
总的来说,DMS被分为source + target 两个component,source发送和targe接收是同时进行的:
由于以上操作都是异步的,而cost衡量的就是query执行时间,其cost formula是
Csource = max(Creader, Cnetwork).
Ctarget = max(Cwriter, CSQLBulkCpy).
Cdms = max(Csource, Ctarget).
在这篇著名的paper 中,我们都看到这样一个结论:由于Cardinality Estimation通常具有很大的误差,导致cost model的精确性变得不那么重要。
这里PDW的设计者们也做出了类似的判断,认为精细的cost model会使得plan对于数据分布/统计信息/执行环境等的微小变化都更为敏感,反而不够robust,此外维护和调试成本也更高,因此这里每个Cxx的计算都非常简单:Cxx = B * λ,B是操作处理的字节数,λ是不同操作对应的常量代价因子,可以看到cost model保持了尽可能的简单。
paper中给出了一个简单的例子,SQL是
SELECT * FROM CUSTOMER C, ORDERS O WHERE C.C_CUSTKEY = O.O_CUSTKEY AND O.O_TOTALPRICE > 1000;
上图非常清晰的描述了4个主要步骤都发生了什么:
(a)用户输入到PDW engine
(b)Parser生成AST
(c)在单机SQL Server中完成单机优化,形成Final (Serial) Memo,传递给PDW optimizer,枚举Shuffle/Replicate等算子,生成Augmented (Parallel) Memo。
(d)从c的Parallel Memo中选出最优分布式计划
(e)转换为DSQL的plan描述,其中包括DMS operation + SQL operation...
SQL Server PDW的并行优化方案还是非常优雅的,从本质上,它利用Cascades的top-down strategy完成单机串行的优化,再利用System-R的bottom-up完成并行的分布式优化,将两者结合了起来,是非常聪明的解决方案。不需要太多调整原有的Cascades组件,又简洁高效的生成了分布式计划。