您当前的位置: 全球新闻网 > 科技 > 独家揭秘 | 阿里云分析型数据库AnalyticDB新一代CBO优化器技术

独家揭秘 | 阿里云分析型数据库AnalyticDB新一代CBO优化器技术

发布日期:2020-04-04

原标题:独家揭秘|阿里云分析型数据库AnalyticDB新一代CBO优化器技术

01、概述

对于数据库来说,其中俩个核心的模块是:优化器和执行引擎。优化器负责给执行引擎提供输入,它接收来自SQLParser解析好的AST树,然后需要从所有可能的计划中选择代价最优的计划提供给执行引擎。基于代价的优化器本质上是一个复杂的搜索问题,想要解决好这个问题,需要从四个方向入手:

1)搜索框架:既然是搜索问题,那么就需要一个搜索框架来承载这个问题。从数据库的发展历程来看,基于Cascades的搜索框架已经成为了业界标准,包括商业数据库SQLServer以及开源数据库GP/ORCA都采用Cascades实现。AnalyticDBCBO也是基于Cascades论文实现的。

2)分布式并行计划:相对于传统的单机版数据库,AnalyticDB是一个分布式MPP数据库,优化器生成的计划是一个分布式并行计划。因此需要把分布式并行计划的生成和搜索框架结合起来,基于代价选择最佳的分布式并行计划。

3)代价估算:代价估算是优化器能否寻找到最优计划的关键因素,代价估算做不好,优化器不可能做好。代价估算涉及到统计信息的推导和代价模型。统计信息的推导依赖于:原始表的统计信息、中间算子的推导算法、对数据的各种假设(均匀性假设、独立性假设、包括性假设、包含性假设)以及在一些极端情况下的猜测。因此统计信息的推导存在大量的不确定性,也正是因为这些不确定性,极大的加剧了优化器寻找最优解的难度。

4)统计信息收集:收集必要的统计信息是CBO工作的前提,CBO和统计信息之间的关系犹如一把枪和弹药之间的关系,枪再好如果没有充足的弹药的话,那么无异于巧妇难为无米之炊。统计信息需要做到:基本信息能够自动化收集,自动化更新,高级统计信息可以手动收集,为CBO提供可靠的、多维度的统计信息。

02、架构

搜索框架

搜索框架在整个CBO中处于非常中心的一个位置,它会调用PropertyEnforcement框架,生成分布式执行计划,然后调用代价估算模块,给每一种候选分布式执行计划评估代价,最终基于代价选择最优的分布式执行计划。搜索框架包括以下几个部分:

Memo表示搜索空间:对于一个查询计划来说,首先需要把它初始化,形成初始化的搜索空间。随着搜索的进行,搜索空间会不断扩充。由于搜索空间会非常庞大,因此Memo需要做到高效存储。

Search表示搜索算法:搜索算法由三部分组成,第一部分用于递归遍历搜索空间,第二部分用于调用展开规则产生新的等价候选计划,扩充搜索空间,第三分部用于用于推导分布式计划的属性要求并计算代价值,进而寻求最优的分布式执行计划。

Scheduler表示调度搜索算法的调度器:在当前的AnalyticDBCBO版本中,基于单线程和栈实现:把搜索任务压入到一个栈中,然后循环取栈中的任务去执行,直到任务结束。

考虑到其他开源优化器产品,例如ORCA提到了多线程并行搜索的理念,我们预留了多线程调度器的接口,相对于优化器众多棘手的问题来说,它的优先级并不是那么高,实现并行搜索的好处是非常明显的,它可以显著降低任务调度的执行时间,充分发挥多核并行的能力,从整个查询的角度来看,可以缩短查询优化的耗时,从而降低整体查询的耗时。但是并行搜索带来的线程同步问题,以及线程间依赖处理问题,挑战还是很大的。

Rule表示展开规则:展开规则用于生成等价候选计划,等价候选计划会被放入到Memo中,形成完整的搜索空间。展开规则决定了优化器可以展开多少种候选计划,因此展开规则的种类,以及每种展开规则的算法效率对CBO来说也是至关重要的。展开规则种类越多,搜索空间就越完善,也就更有可能寻求到最优解,同时每种展开规则的算法越高效,生成完整的搜索空间就越高效,查询优化就越快。

分布式并行计划

相对于传统的单机版数据库来说,分布式MPP数据库给优化器带来了新的挑战。在分布式MPP数据库中,数据的分布属性变得十分的重要,它会直接影响到数据的正确性。为了满足不同算子对数据分布的要求,我们往往需要做数据重分布。

然而数据的重分布,也就是数据shuffle的代价非常昂贵,因此,在保证数据正确性的前提下,尽可能的减少数据shuffle,可以大幅度提升分布式计划的执行性能。作为分布式MPP数据库优化器来说,需要把数据的Partitioning属性,以及Sorting、Grouping属性,也纳入到搜索空间来综合考虑,基于代价选择最优的分布式并行执行计划。

因此我们设计实现了一套完整的PropertyEnforcement框架,用于描述在分布式场景下,分布式计划对数据分布的要求。同时我们把PropertyEnforcement的过程和搜索框架无缝的结合在一起,实现了面向分布式MPP数据库的CBO。

代价估算

代价估算是整个CBO质量好坏的关键因素,代价估算做的好,CBO才有可能选择出最优的计划,它包括三个部分。

Statistics用于描述原始表的统计信息。包括表级别的统计信息RowCount,单个字段的统计信息:每个字段的NDV值(distinct值),Max值,Min值,NULL值,Histogram值(分布信息,用于区间查询),Count-MinSketch值(用于等值查询),DataSize值。这些统计信息我们把它归纳为基础统计信息,需要做到自动收集,自动更新。

同时考虑到多个字段之间的关联度、Functionaldeplendency、数据的倾斜等这些因素对统计信息估算的影响,还会提供命令行工具,手动收集这些信息,对于这些需要手动收集的信息,我们把它归纳为高级统计信息,只有在必要的时候,才需要显示的手动收集。另外,对于一些复杂的predicate,例如like,那么即使收集了Histogram也无法支持这种场景,因此我们也会在运行时基于动态采样来获取对应的统计信息。

StatsDerivation用于推导经过各个算子之后的统计信息。统计信息的推导依赖于原始表的统计信息,数学公式,对数据属性的假设(例如,数据的分布是均匀的,多列之间的选择率是没有相关性的),以及极端情况下,启发式的假设(例如对于一个用户自定义的UDF,它的选择率只能给一个默认值)。

统计信息的推导的好坏对优化器来说至关重要,这也一直是学术界的研究热点。本质上来说,只有打破对数据属性的假设,才有可能使得统计信息的估算做到知其然知其所以然,然而打破这些假设,依赖于对原始数据的分析,生成更多维度的统计信息,必然也要付出更多的代价。

CostModel表示代价模型。代价模型的工作必须要建立在合理的统计信息推导的基础之上,否则它的意义不会很大。代价模型需要对实际的计算模型进行评估,把统计信息转换为可以量化的代价值,从而为优化器提供决策依据。

统计信息收集

Analyze用于收集统计信息。对于商业数据库来说,为了提升用户体验,做到开箱即用,都致力于Autoanalyze,即统计信息收集的自动化,以及自动更新。但是收集本身也是有代价的,因此我们把统计信息分为俩类:基础统计信息和高级统计信息。

基础统计信息就是前面提到的:表级别的统计信息rowcount,单个字段的统计信息:每个字段的NDV值(distinct值),Max值,Min值,NULL值,Histogram值(分布信息,用于区间查询),Count-MinSketch值(用于等值查询),DataSize值。基础统计信息必须要做到自动化收集、自动化更新,否则很可能由于这些统计信息的缺失,导致优化器产生灾难性的计划。

同时为了提升优化器在复杂情况下的决策质量,还提供了一些高级的命令用于收集更加复杂的统计信息,例如可以收集columngroup的统计信息,来获取多个字段之间的关联度信息。高级统计信息需要手工触发收集,只有在必要的时候才会收集。

基于Analyze命令收集统计信息,无论是自动化收集,还是手工收集,本质上来说所,它都是一个独立的进程:Analyze会调用DataProfiling任务,对原始数据进行分析,生成统计信息,并存储在Metadata库中。

考虑到实际情况下,可能存在一些非常复杂的查询条件,不管是基础的统计信息还是高级统计信息,都无法很好的对它做合理的估算,这个时候,dynamicsampling动态采样就可以发挥它的价值,动态采样会实时下发采样,获取必要的统计信息,提升优化器的决策质量。

其次,动态采样也可以作为统计信息收集的一种兜底策略,当基础统计信息由于某些原因导致未收集的情况下,动态采样的存在可以避免优化器由于缺失统计信息而产生灾难性的计划。但是动态采样是在查询优化阶段同步阻塞执行的,因此它必然会增加查询优化的整体耗时,同时也会增加整个数据库系统的负载,因此我们严格限制动态采样的使用场景。

03、设计与实现

接下来我们会通过一个例子来展开搜索框架、PropertyEnforcement框架、以及代价估算的设计与实现。

查询语句

这一个简化版的TPCHq3,非常典型的三表Join。其中customer表按照c_custkey进行分区,orders表按照o_orderkey进行分区,lineitem表按照l_orderkey进行分区。

SELECT

l_orderkey,

o_orderdate,

o_shippriority

FROM

customer,

orders,

lineitem

WHERE

c_custkey=o_custkey

ANDl_orderkey=o_orderkey

查询优化

在进入到CBO之前,原始的执行计划如下图所示,customer表和orders表先Join,Join的结果再和lineitem表Join,然后输出结果。

进入到CBO后,首先需要把查询计划转换为Group和GroupExpression,并初始化Memo搜索空间。可以看到共有6个Group,每个Group都有一个GroupExpression。Group和GroupExpression都是搜索空间里面的重要概念,关于它的详细介绍可以参考:AnalyticDBCostbasedOptimizer搜索框架,这里不展开。

简单来说:对于逻辑等价的,可以产生相同结果的LogicalExpression和PhysicalExpression的集合称为Group,GroupExpression则包括LogicalGroupExpression和PhysicalGroupExpression,每一种GroupExpression表示一种等价候选计划。

在这里,我们为了简化描述,只考虑Join的Order,以及分布式Join情况下,RepartitionJoin和ReplicateJoin这两种属性要求,对于Join的算法默认只考虑Hash-join物理实现。

其他算子:TableScan和Output也默认只有一种物理实现。调度器调度搜索任务,执行搜索流程,扩展搜索空间。可以看到随着搜索算法的不断迭代,Memo里面的Group和GroupExpression会新增:白色表示LogicalGroupExpression,灰色表示PhysicalGroupExpression。

可以看到,在应用了Join的结合律之后,新产生了Group7和Group8这俩个Group;同时应用了Join的交换律之后,Group5和Group3里面新增了很多等价的LogicalGroupExpression;同样Group7和Group8里面也有等价的LogicalGroupExpression。

最终考虑俩种分布式Join实现:RepartitionJoin和ReplicateJoin,这样就生成了完整的搜索空间。

当整个搜索空间被完整的扩充出来之后,接下来需要调用PropertyEnforcement框架,对每一种物理执行计划,去Enforce必要的属性,从而满足分布式执行计划的要求,然后再调用代价估算模块,去计算每一种分布式计划的代价,并把代价最小的计划标记为最优解,也就是Winner。当每一个Group的Winner都被计算出来之后,将每个Winner串接起来,就是最优的分布式执行计划。

关于PropertyEnforcement和代价估算的详情,可以参考下面这三篇文章,这里不展开。

AnalyticDBCostbasedOptimizer分布式并行计划

AnalyticDBCostbasedOptimizer代价估算

AnalyticDBCostbasedOptimizer统计信息收集

下图中黑色意味着Winner,表示的是在满足某种属性要求的情况下,代价最低最低的物理执行计划。

我们遍历每个Group的Winner,将Winner串接起来,就形成了最优的分布式执行计划。

每一个Winner经过PropertyEnforcement之后,都会在必要的时候插入必要的Exchange节点,来满足分布式计划的属性要求,所以生成的分布式执行计划如下图所示。可以看到:首先customer表做了一个全表广播到所有节点,进而满足和orders表Join的要求,Join之后的结果按照order表分布,orders表和lineitem表数据分布本身就满足Join的要求,因此不需要插入Exchange节点,最终Join的结果要输出到Output节点,因此插入Gather节点,汇总到单节点。

04、参考

AnOverviewofQueryOptimizationinRelationalSystems

TheCascadesFrameworkforQueryOptimization

Efficiencyinthecolumbiadatabasequeryoptimizer

Orca:AModularQueryOptimizerArchitectureforBigData

IncorporatingPartitioningandParallelPlansintotheSCOPEOptimizer

ProfilingRelationalData–ASurvey

上云就看云栖号,点此查看更多:https://yqh.aliyun.com/?utm_content=g_1000100940

本文为阿里云内容,未经允许不得转载。