从一到无穷大 #43：Presto History Based Optimizer，基于PlanNode粒度统计的查询计划选择策略

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

本作品 (李兆龙 博文, 由 李兆龙 创作)，由 李兆龙 确认，转载请注明版权。

引言

过年回家这件事在挚友的劝导下，在不回去和一直呆在家之间选择了提前回深圳，从绝大多数方面看这绝对可以算是最近一段时间内做的最正确的决策之一，最直观的结果就是拥有了完整三天个人假期，可以彻彻底底的放松下，提前进入下2025H1的项目攻坚状态，把自己的心态拉回来。

过年期间并不算全部都是颓废的生活，除去阖家团圆的传统剧情，更具现实意义的是在挚友的推荐和自我兴趣驱使下读完了《亲密关系》《恶意》《黄仁勋：英伟达之芯》《廊桥遗梦》，还有一本尚在 todo list 内的《信》，其实对于阅读这件事情我一直很功利，这也是为什么之前只有在交通工具上时我才会读非技术书，平时的大把时间也都是在读领域相关的paper，但是慢慢的发觉，仅有领域知识是远远不够解答所有的困惑的。

回到假期，深圳的三天除了正常的锻炼，看朋友发给我的自媒体资料这两个必做项之外，我一直想，在有限的剩余时间是输入，输出还是躺着？

输出有三个选择：

1. 我非常想写《黄仁勋：英伟达之芯》这本书的书评，虽然传记类文章存在部分魔幻色彩，但是Jensen的经历毋庸置疑是传奇的，而且NVIDIA的崛起之路不夸张的讲能让一个痴迷技术的理工人看到颅内高潮，相比之下《腾讯传》就显得无趣多了。
2. 我最近在做时序数据库的MPP（Massively Parallel Processing），免不了需要去适配Exchange算子，也确实没研究过其他的实现，但Velox中的实现的异步方式确实让人耳目一新，其实现基于ExchangeQueue，ExchangeClient，ExchangeSources三个类，新的实现只需要继承ExchangeSources就好，这里是绝对值得输出的，且目前网上这里的资料是零。
3. Presto的HBO，也就是本文，这篇paper年前就看完了，我其实看绝大多数paper不会写文章，但这篇文章揭示了一个现象，其与我的工作有一些想法上的联系，即越细的监控粒度能够带来更多的可能性，如果能持续下压性能和成本，这就是绝对符合公司（部门）战略的事情，而且我最近也在负责优化器部分的重构，HBO的思路有可能在做部分修改后应用到X-Stor来。长久以来看惯了很多软文的宏大叙事，但其实绝大多数人做的事情就是没有颠覆性价值，抠出一点意义已经是值得投入以年计的时间了，这虽然让人有时觉得沮丧，无力且压抑，但是耐心沉淀对于个人来讲也是必要的，毕竟Jensen也曾在AMD打工。

输入有两个选择：

1. 把新年档的哪吒，唐探，封神看下，事实上已经快忘了我上次在影院看电影是多少年前了
2. 还有两本书想看

躺着：

1. 思考当下生活的核心矛盾点，思考未来想做好的事情，思考我真正想要的东西是什么

正如现在看到的这样，最终的决策是选择输出HBO，如果文章写完还有点剩下的时间，那就去深圳湾人才公园水池旁边的草坪上躺着看星星。

Motivation

Presto的Cardinality Estimator依赖于如下统计信息，粒度为partition级别:

1. Overall cardinality of the partition
2. Column statitstics including
   1. Average size
   2. Number of distinct values
   3. Number of null values
   4. Range(min/max) for the values

传统的CBO（Cost Based Optimizer）通常依靠离线过程收集有关输入数据的统计信息，文章开篇点出CBO存在复杂查询下Cardinality Estimation不准确的情况，进而导致查询计划的选择无法达到最优，具体的，存在如下问题：

1. 需要在查询前执行分析
2. 做出了很多Simplifying Assumptions，比如data uniformity， independence of filters and columns，在复杂表达式下通常无法准确预估Selectivity
3. 使用更复杂的统计信息，比如multi-column和join histograms，但是需要额外的空间和时间，且很难处理，绝大多数系统没有实现

LBO（Learning Based Optimizer）也是最近几年比较火爆的一个方向，其最大的优势是克服了传统CBO的很多Simplifying Assumptions，但是也有如下缺点：

1. 训练和改进模型需要大量的投入
2. 可解释性差

HBO（History Based Optimizer） 在 Operator Node 级别统计 Query Execution Statistics，并使用这些数据来预测相似查询的未来性能。HBO基于一种假设，即用户查询虽然复杂，但本质上是重复性的，一般使用使用模版生成相同结构的查询，这会造成查询计划基本一致，进而可以通过简易的方法找到之前的统计信息，然后用来执行精确的估计，这种假设从我们的经验来看是对的。

HBO解决了之前无法解决的问题：

1. Accuracy：在实际执行运行期间记录统计数据，并在运算符级别进行跟踪，消除了使用基础表统计数据引入的较大估计误差。
2. Automation：每次查询运行时，历史记录都由轻量级进程跟踪，从而避免了采样开销或模型训练。
3. Adaptiveness：对基础数据分布的更改会自动反映在跟踪的历史记录中，并用于未来的优化。
4. Explicability：用户和 DBA 可以查看估计数据的来源以及它与实际值的差距。

Architecture

Presto CBO可以为简单查询生成准确的估计，但随着查询变得越来越复杂，误差幅度会呈指数级增长。

HBO希望做到的约束如下：

1. Estimates need to be accurate：解决复杂查询下的基数估计不准的问题
2. Accommodate changes to both data and queries：数据和查询不是静态的，但是一般也不会短时间存在巨大波动，HBO要能适应数据变化
3. Minimal overhead to query processing：轻量级统计，无需大量计算
4. Ease of use and operation：可调试性，且用户易于使用
5. Seamless integration with classic methods for deriving cost：HBO不可用回退至CBO

HBO的思路非常简单，有几个不那么难的难点需要解决：

1. 查询模版虽然不变，但是其中参数和查询条件数量存在变化
2. 统一查询模版的查询计划可能存在差异，因为可能被不同的优化策略该写过
3. 搜索类似查询计划的开销很大，毕竟每个查询都会有数据存储，且在执行之前都会做统计信息获取

这些难点可以用三个工程方法解决：

1. 模版归一化，具体的操作是Canonicalizing Table scans，Canonicalizing plan nodes，Pruning constants
2. 将stat-equav的计划存储在一起
3. 哈希

简单来说整个HBO可以分为以下几个步骤：

1. 对plan nodes归一化，并且找到stat-equav的plan nodes
2. worker执行完plan后，把统计信息交给Coordinator
3. Coordinator负责将plan及其stats-equav plan nodes统计信息写入到redis 里面
4. 未来查询的时候，同样可以根据归一化的plan node去redis里面拿统计信息

肉眼可见的简单，但是也伴随着极大的工程化落地工作量

HBO Scenario

目前有如下场景用到了HBO：

1. Join reordering：HBO可以准确的拿到之前join算子的准确数据，自然可以选择最优的连接顺序
2. Join distribution type：拿到join算子的准确数据，即不同表的真实数据输入，自然可以选择最优的join方法
3. Partial aggregations：通过aggregation算子的输入大小就知道是否需要做二级aggregations了
4. Skew mitigation：可以知道算子级别准确的null数量，而不是基于假设的估算，这样就可以判断是否应用优化规则
5. Scaled writers：write多文件小，write小写入性能不足，通过历史记录选择相对较优的write数量

Experiments

简单查询CBO已经足够，复杂查询HBO可以带来更优的查询策略

因为选择了更优的执行计划，性能提升很明显

在presto的场景下，10%的查询有2.5x的性能提升，中位数为1-1.2x的性能提升，但是也有10%有8%的性能下降

HBO的开销论文中提到占整个查询的0.5%左右，大概几毫秒，大多数是网络开销。

结束语

在我们的场景中查询简单，且查询场景多为交互式，对时延要求高，虽然加个几毫秒问题也不是特别大，但是目前除了Partial aggregations没有看到其他很好的使用场景，也许可以先研究下presto中150多种优化策略具体有哪些使我们能用的比较重要。

参考:

1. How Good Are Query Optimizers, Really? vldb2015
2. Presto’s History-based Query Optimizer 论文笔记
3. How Good Are Query Optimizers, Really?论文笔记
4. 数据库分布式Join类型及意义Broadcast Join、Shuffle Join 和 Colocate Join