共计 7885 个字符，预计需要花费 20 分钟才能阅读完成。
作者：范振（花名辰繁），阿里云计算平台 - 开源大数据 -OLAP 方向负责人，高级技术专家，StarRocks Community Champion
随着阿里云 EMR StarRocks 上线，在和用户交换的过程中，越来越多被问到 StarRocks 和 ClickHouse 的区别，其中 Join 能力最受客户关怀。提到 Join，最为重要的便是 Optimizer 的实现，所以我来写一篇对于 Optimizer 的详解文章，心愿给大家一个全面的了解。
StarRocks 作为近年来十分优良的 OLAP 引擎，在 Planner/Optimizer 上有高效、稳固的实现，这篇文章会从剖析支流 Optimizer 框架的模型动手，具体解构 StarRocks 的 Optimizer 实现过程。
内容提要：
- Cascades/Orca 论文波及的 Top-Down 优化思路与剖析。
- 针对 CMU15-721 的一些 PPT、观点、论断加以解析。
- 着重联合 StarRocks 的实现，并介绍 StarRocks 的 Optimizer 次要借鉴的 CMU noisepage（https://github.com/cmu-db/noi…）我的项目以及 Cascades/Orca 论文的思路。
#01
SQL 优化流程图
—
在业务上，咱们遇到了以下几个次要痛点：
下图体现了 SQL 文本到最终的分布式 Physical Plan 的全流程：
- Analyzer 须要联合外部 / 内部 Catalog 零碎，次要是查看 Table、Column 等信息是否非法。
- Rewriter 阶段（RBO）次要是一些 Logical->Logical 的变换操作，基于一些经典的代数变换来进行。
- Optimizer（CBO）须要联合外部 / 内部的 Cost 模块，罕用的计算采集信息包含行数、列基数、列最大最小值、每行均匀大小、直方图等信息。
本文次要聚焦在 CBO 阶段的技术原理解析。
#02
Rewriter
—
Tree Rewrite 的过程大体思路是：
- 实质上是二叉树的转换，利用已知的 Transformation Rule 和已知的 Pattern，对逻辑二叉树做匹配、转换，造成一棵新的二叉树。
- Top-Down 的迭代（即每条 Rule 自顶向下的匹配 Tree 以及 Subtree）形式，将所有合乎规定的 Rule 全副利用到逻辑二叉树，造成新的逻辑二叉树。
咱们以下图的 Predicate PushDown 为例进行剖析：
每一个 Transformation Rule 有一个 Pattern，首先会查看 Rule 的 Pattern 是否可能 Match Logical Tree，本例中以下的 Rule 能够匹配上图的 Tree。
- 确认可能匹配之后，就是 Tree 的 Transform 过程，针对本例大体流程是：
- 将 FilterOperator 的 Predicates 决裂开，能够失去几个 Predicates。
- 依据 Pattern 的数据结构可知，取 FilterOperator 的子节点，肯定是 JoinOperator。将匹配的 Predicates 分给 FilterOperator，将不匹配的 Predicates 生成新的 FilterOperator 挂到 FilterOperator 的 2 个子节点之上、JoinOperator 之下。
- 这样就实现了一层下推动作，同理持续迭代的进行 Subtree 的匹配、下推操作。
当所有的 Rules 都进行了一次匹配操作之后（如果 Match 不匹配，不进行 Transform），Rewriter 的工作就完结了，失去了一个新的 Logical Plan。
#03
CBO 架构
—
1、 整体优化思路
CBO 的指标是将一棵重写后的 Logical Tree 转换为 Physical Tree，使得这棵 Physical Tree 的执行代价最小，或者是在肯定束缚下的“最小”（这里的条件本质指的是 Property，每个 Property 对应一个最小代价的 Tree，或者说 Plan）。
查问优化的整体思路是：
- 通过逻辑变换（代数变换），找到所有等价的 Logical Plan，例如 Join 的交换律、结合律等。
- 将 Logical Plan 转变成 Physical Plan，例如将 LogicalJoin 拓展为 PhysicalHashJoin、PhysicalSortMergeJoin、PhysicalNestLoopJoin 等，将 LogicalScan 拓展为 SeqScan、IndexScan 等。
- 第一步、第二步确立了残缺的、对立的搜寻空间。
- 依据不同算子的代价模型，计算出每一种 Physical Plan 的代价。
- 选取代价最小的作为最终的 Physical Plan。
然而，面临着几个问题：
- 依据逻辑打算推导出的物理打算特地多，多表 Join 收缩的数量级比拟大，在无限工夫内可能无奈全副计算。
- 要晓得哪些 Subtree 的代价被计算过了，要晓得哪些 Transformation Rule 针对哪些算子被利用过了。
- 须要尽量通过缩小搜寻空间，尽早地剪枝。
- 如何评估每个算子的代价。
查问优化的几个比拟重要的准则，参考《CMU15-721-Optimizer》中所述：
- 对于一个给定的查问，找到一个正确的，最低“cost”的执行打算
- 这是数据库系统中最难实现好的一部分（是一个 NP 齐全问题）
- 没有优化器可能真正产生一个“最优的”打算，咱们总是
- 用估算的形式去“猜”实在打算的 cost
- 用启发式（heuristics）的形式去限度搜寻空间的大小
晚期对于 CBO、特地是 Bottom-Up 系列的优化器，利用很少，疏忽不讲。对于古代优化器的一些 Paper 的钻研状况大抵如下：
- Volcano 是更早的 Top-Down 优化框架，古代数据库曾经没有落地，疏忽不讲。
- Cascades 是改良 Volcano 的另一种基于 Top-Down 的优化框架，是古代数据库利用的最多的 Optimizer 框架，论文比拟形象，指出了很多方法论，实际意义比拟强。
- ORCA 是针对大数据场景的、基于 DXL 通信的 Standalone 的优化器（能够把优化器局部抽出来，独立 service 部署），它引入了 Distribution（包含 Shuffle、Broadcast 等网络传输算子）的 Property，标准了可能的数据分布。ORCA 能够认为是 Cascades 的优化实现版本，给出了更加丰盛的实现细节和步骤。
2、 Cascades Framework & ORCA Architecture\
根底概念
- Expressions
- Groups
- Rules
- Memo
外围优化流程
- Exploration，将原始的 Logical Plan 转成等价的 Logical Plan，比方 Join 的结合律、交换律等。
- Statistics Derivation，将所有的逻辑打算，沿着 Tree->Subtree Top-Down 形式进行统计信息收集。实现中，能够认为是 Tree 的后根遍历，先进行子节点的 Statistics 收集，再依据子节点提供的 Statistics 收集本身的 Statistics。
- Implementation，将所有 Exploration 失去的 Logical Plan 转成对应的 Physical Plan，转换过程中一个 Logical Plan 对应着多个 PhysicalPlan，比方 LogicalJoin，能够转换为 PhysicalHashJoin、PhysicalSortMergeJoin、PhysicalNLJoin 等。
- Optimization，开始进行真正的计算代价，这部分会在前面的“优化的流程”章节中具体阐明。
须要留神的是：真正实现过程中，不应该程序依照这四步来，至多 StarRocks 不是这么做的。CMU15-721 以及 Cascades 论文都有解释：
- Stratified search vs unified search，分层搜寻是先 Logical->Logical，再 Logical->Physical；对立搜寻是 Logical->Logical 以及 Logical->Physical 一起都做了，都属于同一个 Group 中的等价变换。
- 这样做的益处是，在 Exploration Logical Plan 时，有可能其 Subtree 对应的 Physical plan 曾经不满足条件（比方因为 Cost 过大，被剪枝了），所以不须要持续进行。Cascades 中与此思维靠近的形容是：Cascades 搜索引擎确保只有那些真正能够参加查问评估打算的子树和相关联的（interesting）属性失去优化。每次当一个输出被优化之后，优化工作能够取得一个最小的 Cost，用这个 Cost 去限度下一次的优化输出下限。这样，能够尽可能地紧凑（tight）剪枝。
- 对于一个 Tree 或者 Subtree，它的 Cost 是逐步递加的。会将上一次 Tree 计算失去的 Cost 后果当做下一次 Tree 的 Limit，这样有利于搜寻剪枝，即一旦 Subtree 计算 Cost 的过程中超过 Limit，会立刻被剪枝。
- 这样做须要更多的 Memo 存储空间。
Property Enforcement
在 ORCA 框架中 Property 有多种，这里重点介绍 Sort 和 Distribution，咱们用 {Sort,Distribution} 示意，如果均为任意属性，示意为{Any, Any}。Property 实际上就是最终某个算子须要什么样的个性（Required Properties），举以下例子：
- Select a from A order by a。这个 Query 心愿最终可能可能依照 Column a 来排序，那么咱们会在查问最初退出对于 a 的排序个性来满足最终的需要，那么对于这个 Query 要求{Sort(A.a), Any}。同时父节点须要把 Required Property 传导上来，给到 Scan A 子节点。这样咱们面临着两种抉择：
- 要求子节点 Scan A 排序，即{Sort(A.a), Any}，父节点 Project 不须要排序间接输入。
- 要求子节点不排序，即{Any, Any}，父节点退出排序算子（即须要 Enforce 操作）后间接输入。
- 以上两种策略供咱们抉择，咱们能够潜在利用 A 表的有序性，进行 IndexScan（例如利用 B+Tree 的有序性）。
- Select * from A Join B where A.a=B.b。这个 Query 中，咱们对于 Join 后果没有散布要求，Property 能够为 Any。针对 PhysicalHashJoin 算子，咱们有两组 Required Properties
- 左表 A 是{Any, Any}，右表 B 是{Any, Broadcast}。
- 左表 A 是{Any, Hash<A.a>}，右表 B 是{Any, Hash<B.b>}。
为了满足 Required Properties，咱们须要针对物理算子的理论行为，进行 Enforcer。比方 A 表并没有依照 Hash<A.a> 进行散布，那么就须要退出 Shuffle[A.a] 算子。如果须要 A 表 Broadcast，须要退出 Broadcast 算子。
退出了对应的 Enforcers，因为引入了新的算子（例如 Shuffle、Broadcast），咱们计算 Cost，须要评估 Enforcers 自身的 Cost。
优化的流程
在分布式系统中，每一个 Group 对应的 Best Plan 实际上都是针对某一 Property 来说的，在 StarRocks 中是如下数据结构
- Map<PhysicalPropertySet, Pair<Double, GroupExpression>> LowestCostExpressions。代表每一个 Group 中，满足 Required Property 条件的最佳 Expression（GroupExpression 能够简略了解为与 Expression 等价）。
- Map<PhysicalPropertySet, Pair<Double, List<PhysicalPropertySet>>> LowestCostTable。代表每一个 GroupExpression 中，满足了 Required Property 条件的节点，它的子节点须要满足的 Required Properties。
所以 Optimizer 的工作就是一直依据 Rules Transformation 拓展失去 Logical/Physical Plan，插入到 Memo 中，通过比拟 Cost 来一直迭代更新这两个数据结构。在搜寻的过程中通过 Cost 来提前的 Prune 有效的 Subtree。
下图为 ORCA 最终的动态图，起始的 Required Property 为{Singleton, <T1.a>}，通过以上两个数据结构，最终失去了 Best Plan。
动静布局算法解释
- 整体的搜寻过程是 DP 算法，最小 Cost 是问题（即 DP[property_a,n]）的最优解，它是所有 Exploration 失去的 Physical Plan 的解空间（即 DP[property_b, n-1]，DP[property_c,n-1] …）中，满足特定 Property 的最小 Cost 值。这样问题就能够变成求子树的最小 Cost，就能够归为 DP 问题。
- 利用 Memo 来做 DP Memorization，每一个 Group 记录某一 Required Property 对应的 Best Expr。
- 通过 Cost Limit 的一直递加来做剪枝操作。
#04
StarRocks 优化器具体解析
—
1、根底数据解构
- 在 StarRocks 每一个 Logical Plan 中，Physical Plan 都能够认为是 OptExpression，下文咱们称为 Logical Expression 和 Physical Expression。其中的 GroupExpression 和 OptExpression 能够相互通过变换生成。
- 起初的 Root OptExpression（通过 rewriter 后的 Logical Plan）通过封装造成 Root GroupExpression 后，后续根本所有的操作都是基于 GroupExpression 数据结构的。
- StarRocks 根本遵循了 Cascades/ORCA 的思维，进行了一部分的改良，这些优化在上文中也有过形容，不再赘述，整体的架构如下。
- StarRocks 中的 TaskScheduler 基于 Stack 和 OptimizerTask 形象，实现了一套任务调度框架，Task 的类型有以下几种：
- DeriveStatsTask 对应 ORCA 中的 Statistics Derivation 过程，通过树的后根遍从来取得所有节点的 Statistics，留神这里的 Statistics 不是 Cost，通过 Logical Plan（次要是依据表、列的元信息统计）就能够取得每个 Group 对应的 Statistics。
- OptimizeExpressionTask 对应 ORCA 中的 Exploration 和 Implementation 过程。针对所有的 Rules（以后有 26 个 Implementation Rule 和 6+ 个 Transformation Rule）进行 Pattern 匹配，可能匹配 GroupExpression 对象的成为 Valid Rule，造成 ApplyRuleTask 对象。
- ApplyRuleTask 对应 ORCA 中的 Exploration 和 Implementation 过程。将 Rule 利用到 Logical Plan 中，实现 Logical->Logical、Logical->Physical 的转换，通过等价变换拓展每个 Group 的搜寻空间。
- EnforceAndCostTask 对应了计算 Physical Plan 的 Cost 的过程，如果某个 Expression 不满足 Property，会 Enforce 出其余 Operator，例如 Broadcast、Shuffle、Sort 等算子。
2、三表 Join 优化示例
上面几张图以三表 Join 为例，体现了 StarRocks 的 Memo 一直变动的过程，最终通过上文中提到的 2 个数据结构的不断更新，失去了最终的 Best Plan。
- Memo Init 的过程，间接把三表 Join Rewriter 之后的 Logical Plan 插入到 Memo 中，失去了 6 个 Group。
- 通过 Implementation Rule 对每个 Group 通过 Top-Down 遍历（利用 Stack 实现树的后根遍历）进行 Logical->Physical、Logical->Logical 的拓展。下图为 Join 交换律，因为 Join 交换律并没有减少新的 Join 组合，所以并没有新增 Group。
- 同样地，通过 Top-Down 遍历利用 Join 结合律进行 Transformation，因为 Join 结合律生成了新的 Join 组合，所以会新增 Group。
- 一直进行 Cost 计算，通过设置 Cost Limit 收敛进行剪枝，通过 Memo/Group 来记录每种不同的 Required Property 对应的 Best Expr，来更新上文提到的 2 个数据结构，最终到 Best Plan。
3、CostModel
StarRocks 中每个 Group 的 Statistics 有以下变量
- double outputRowCount
- Map<ColumnRefOperator, ColumnStatistic> columnStatistics
其中每个 Column 对应一个 ColumnStatistic 对象，次要有以下变量
- minValue
- maxValue
- averageRowSize
- distinctValuesCount
- …
有了这些 Stats，咱们其实能够预估任意一个算子的 Cost，比方预估 HashJoin 的办法如下图，即：
- cpuCost 为左右孩子输入的数据大小之和，即行数 * 每行对应的 avgRowSize。留神：这个 avgRowSize 统计的是通过 Column Prune 之后的列数对应的均匀行大小。
- memoryCost 为右孩子的输入数据大小。做 HashJoin，右表为 Builder 表，占用内存，如果是 crossJoin 会计算对应的 Penalty（此处为 10^8L）。
- networkCost 此处为 0，因为 HashJoin 自身不产生任何的网络替换。
参加采集、计算 Stats 相干的类为：
- CreateAnalyzeJobStmt，负责建设采集信息的异步 Schedule Job。
- AnalyzeStmt，手动 Analyze 命令收集 Stats。
- StatisticAutoCollector，负责 Schedule 采集 Stats。
- StatisticsCalulator，真正的外围类，负责计算各种算子的 Statistics，在上文提到的 DeriveStatsTask 中调用。
#05
Reference
—
[1]https://www.cse.iitb.ac.in/in…
[2] https://15721.courses.cs.cmu….
[3]https://github.com/StarRocks/…
对于 StarRocks
StarRocks 创建两年多来，始终专一打造世界顶级的新一代极速全场景 MPP 数据库，帮忙企业建设“极速对立”的数据分析新范式，助力企业全面数字化经营。
以后曾经帮忙腾讯、携程、顺丰、Airbnb、滴滴、京东、众安保险等超过 110 家大型用户构建了全新的数据分析能力，生产环境中稳固运行的 StarRocks 服务器数目达数千台。
2021 年 9 月，StarRocks 源代码凋谢，在 Github 上的星数已超过 3000 个。StarRocks 的寰球社区飞速成长，至今已有超百位贡献者，社群用户冲破 5000 人，吸引几十家国内外行业头部企业参加共建。
