学习数据库优化器如何入手?

2个月前 (01-15) 0 点赞 0 收藏 0 评论 5 已阅读

导师让下周给他讲四篇paper,感恩节也没法休息咯。


前言

导师主要是做ML for DB的方向,所以这几篇paper也是关于这个方面的,更具体来讲是强化学习在优化器和查询调度上的应用。这次的paper带来的是Bao,一个具备高度可落地性的强化学习查询优化组件。在此之前其实已经有很多关于在优化器中应用机器学习的先例,比如Neo。这些工作虽然在一定程度上解决了问题,但是在工程落地的方面都或多或少存在不足。

冷启动的问题。由于之前的很多工作是对原有的优化器进行了替换,所以所有的统计信息都需要重新开始收集。这就导致了需要大量的初始化训练数据来构建一个可用的模型。无法根据动态变化的workload和数据进行调整。之前基于监督学习的优化器对于数据和workload的动态调整没有办法做到快速响应,因为每一次的数据和workload变更都会导致一次昂贵的重训练。尾延时过高。之前的工作更多的是在优化平均延时,但是对于尾延时来说甚至比原有的性能慢两个数量级。可解释性不足带来的黑盒问题。对于DBA和用户来说,这些基于机器学习的优化器非常难以理解,他们也无法搞清楚它是如何做出的最终决策。实际部署上的成本过大。所有现有的类似系统都还处在research原型阶段,距离生产部署还有很长的路要走。

不同于之前的工作,BAO的目标不是取代DBMS原有的优化器,而是在它的基础上进行构建。具体来说,BAO会维护一组优化提示集合。对于每一个集合,BAO会让优化器生成一个特定的执行计划,然后利用BAO的RL推理框架选择其中一个下发到DBMS的执行引擎。

这一套方案对上述的每一条不足都进行了针对性的解决。

更少的启动时间。这个很好理解,因为Bao并没有取代原有的优化器,而是在其之上进行工作,所以可以直接复用优化器使用的全局信息。带来更低的尾延时。关于这一点下文有详细的描述。更好的可视化与可解释性。Bao提供一整套决策可视化的接口以供调用方查看它具体的决策流程。与此同时,Bao还可以以query为粒度开启或关闭。更低的接入成本。由于Bao的设计,它在与db结合的时候往往只需要获取相应的hint以及调用hook即可。由于这些信息通常已经被db通过接口的形式暴露在外,所以大部分时候可以做到无侵入的接入Bao。更好的扩展性。Bao可以很轻松的添加额外的优化提示,例如可以在向量的最后加上有关机器缓存的状态。Bao在学习到这一个hint之后可能会做出更理性的决策。这一点在看完下文关于Bao对于查询计划的向量化表示就可以更好的理解。

Bao的系统架构

Bao的架构可以参考上图。具体来说,它是由一个多层的Tree-CNN组成。这个Tree-CNN的设计以及它是如何结合汤普森采样的我们放到下一段再讲。

再来看看Bao的工作流程。Bao会维护一组优化提示集合,每一个集合包含各种优化开关,例如走不走索引,用不用hash join等等。当一个查询下发之后,Bao会为每一个优化提示集合生成一个查询计划,并对这个查询计划的执行时间进行估算。获得估算的指标之后,需要用到汤普森采样的方法来选择合适的执行计划下发到执行引擎。至于在这一步为什么不直接选择,这涉及到其中的统计学问题。

简单来说,如果我们一味的选择best performance的执行计划,那么由于我们此时获得的执行时间也是估计的,并且有可能并不准确,这会让我们一直陷入一个错误的选择当中。此外,如果我们一直不去尝试其他的选择,那么就永远不会从他们当中学习到经验。这是一个exploration与exploitation的取舍问题,也是Bao在实际场景中面临的统计学抽象问题CMAB的核心之一。这一部分在下文Bao的学习过程中会有简单的描述。

执行结束之后,Bao会将真正执行的时间以及其他性能指标加入Bao的经验集中,为下一次重新训练做准备。至此,一次完整的query就结束了。

Bao的学习过程

这一块可能会涉及一些RL和统计学知识,我对这方面也只是略懂皮毛。想了解更多的话推荐去看 @覃含章 大佬的回答,讲的很牛逼。简单来说,Bao面临的问题可以被抽象的定义为一个contextual multi-arm bandit问题(CMAB)。在CMAB中,优化的目标是尽可能地最小化regret(例如我们可以定义regret为,最优优化提示产生的I/O次数与实际执行产生的I/O次数的差值就可以被理解为regret)。通过使用比较经典的汤普森采样方法可以解决这一类的问题。

预测模型

预测模型是Bao应用汤普森采样的核心部分,它在这里使用了Tree-CNN(TCNN)来做预测。在这一部分我们主要关注如何将一个查询计划转换成树形向量来作为TCNN的输入,以及如何将TCNN与汤普森采样结合。

构建输入

这一部分看图理解更容易一些。首先将查询计划树进行二值化(如上图所示)之后,Bao将每一个查询算子的类型进行one-hot编码,并在后面加上相应的cost和cardinality组成了一组树形向量(如下图所示)。在每个向量的后面还可以根据需求添加相应的统计信息,例如当前的系统cache状态等等。

TCNN包括一组构建于查询计划树上的树形过滤器。通过这一组过滤器可以构建一个变换之后的新树。过滤器的作用在于层级查找查询计划树上的规律,例如一组hash join,一个不必要的索引查询等等。越靠后的过滤器越可以发掘到更复杂的规律,例如一个很长的链式merge join等。在过滤器之后是一个用来扁平化向量的动态池化层,以及两个用来将池化的向量map到最终预测值的全连接层。

由于汤普森采样要求从给定的经验集中进行采样,最简单的一种方式就是从经验集E的替换样本中随机采样n=sizeof(n)个样本对模型进行训练。Bao正是采用了这种方式来维护了汤普森采样的要求。

训练流程

Bao的训练过程基本遵循一个经典的汤普森采样流程。当一个查询进来之后,Bao会通过给优化器提供优化提示集的方式生成很多的查询计划树,通过它的预测模型得到一个预测值。执行结束之后,Bao会获取实际执行的性能指标并将其加入到经验集当中。Bao会周期性的对模型进行重训练,通过对神经网络的权重进行采样的方式,来平衡exploration和exploitation。

在实际的应用场景中,由于经验集会随之query的增加而不断变大,每一次采样与重训练的时间也会无限制的增长。因此Bao做了两个方面的调整。第一点是Bao只会在每n个query之后进行采样,从而减少采样带来的开销。其次,Bao只会存储最近的k个”经验“,从而控制了经验集过度增长的问题。

此外,Bao做的另外一个优化跟云深度相关。在如今的云服务上,GPU都是按秒计费。那么在Bao触发重训练的时候,可以将训练卸载到绑定的GPU上,从而尽量降低对整个系统对外服务的影响。当训练完成之后,会将新的参数从GPU换回CPU,然后解绑GPU结束这一次的重训练。

Bao在PostgreSQL上的集成

Bao的启用时机

Bao可以通过设置会话变量的方式,以每一条query为粒度进行开启和关闭。当开启的时候,会用上文描述的汤普森采样进行查询计划的选择。以如此细的粒度进行开关很大程度上避免了Bao对于短查询带来的额外训练开销,同时如果DBA已经结合业务对sql进行了深度的优化,那么关闭Bao可以避免打乱这些现有的优化。

当Bao关闭的时候,也可以选择继续让它进行训练学习。每一条sql执行结束之后,它的相关性能信息会被记录到Bao的经验集当中,这个流程可以被看作是一个off-policy RL。这一部分也很有实际应用场景,通过让Bao学习DBA专家写的sql来让它更贴合业务,提供更强大的支持。

Bao的运行模式

在实际运行的时候,Bao有active和advisor两种模式。在Active模式下,顾名思义,Bao就像上文描述的那样正常工作,选择合适的查询计划,然后把结果反馈到Bao的结果集当中。在Advisor模式下,Bao不会介入到查询优化的过程中,而是让PostgreSQL的优化器全权接管。但是,当一个查询结束的时候,与上文类似,Bao依然会记录相关的性能信息,并在合适的实际训练模型。

另外一个有意思的地方在于,当用户用EXPLAIN来查看具体信息的时候,Bao对于这一条语句的优化建议以及预估运行时间也会展示给用户(也因此得名advisor模式)。感觉这一点对DBA十分友好啊,可以帮助探索性能边界。

实验成果

首先需要通过实验回答的问题是,Bao是否像论文所说的那样适合落地。文中从以下几个方面进行了回答。

云上的开销和性能。可以看到Bao在两个系统上都带来的非常大的提升,很大程度的降低了成本和执行时间。

对于硬件的适配。可以看到相比PostgreSQL,Bao对于不同的硬件配置更加敏感,从而带来更高的性能。

尾延时。由于生产环境更加关注尾延时的性能提升,所以这里论文也专门针对尾延时进行了实验。这里可以看到在不同的机器上,Bao都显著降低了P95,P99以及P99.5的延时。

训练与收敛时间。收敛时间其实是任何一个带有RL组件的系统最关键的指标,可以看到在经过最初两个小时的冷启动之后,Bao的执行速度迅速与PostgreSQL拉开了差距。由于这里使用的数据集是动态数据,会导致模型重训练,所以侧面佐证了模型训练和收敛时间对Bao的影响不大。

然后是关于优化提示的分析:到底什么样的提示可以最大限度提高性能?实验发现,在85%的情况下,Bao对于查询优化的选择与PostgreSQL优化器构建的并不相同。在这其中,有将近75%选择了不同的查询路径,40%选择了不同的join顺序。而这40%的查询计划在前500条性能提升最大的sql中贡献了472条。所以可见,不同的join顺序对于查询时间的影响是巨大的。

最后是关于Bao预测模型的性能分析。

通过将Bao与普通的随机森林和线性回归预测模型进行对比,发现引入神经网络对于整个预测的性能提升是最大的,也是必要的。

Bao的预测准确性随着时间的推移迅速降低。尽管在冷启动时会遇到Q-Error过高的问题,但是实验表明这也没有给整个系统带来严重的影响。

Bao在其优化目标regret上的表现也远超PostgreSQL。

通过允许自定义Bao的优化目标regret,可以使得整个系统更加适应云上多租户以及复杂workload的环境。例如,上图分别描述了regret定义为最小化CPU时间与最小化I/O请求。不同的目标会带来不同的表现,这就允许云上系统根据系统实时分配的资源情况进行动态调整,从而更好的发挥Bao的性能。

结论

总结来看,Bao为我们带来了一个适合工程落地的RL查询优化器的解法。我以后的工作可能也会在Bao上面继续做一些文章,例如将Bao带到云上,验证在多租户分布式云数据库上的可行性(现在正在和Amazon Redshift聊这个事情),以及探索Bao与传统优化器更加深度的结合,感兴趣的朋友可以关注一下。

关于Bao就讲到这里吧,得抓紧去复现了 :)

学习数据库优化器如何入手?

本文收录在
0评论

登录

忘记密码 ?

切换登录

注册