Presto 从提交SQL到获取结果 源码详解(2)

逻辑执行计划：

//进入逻辑执行计划阶段
doAnalyzeQuery().new LogicalPlanner().plan(analysis);//createAnalyzePlan
createAnalyzePlan(analysis, (Analyze) statement);//返回RelationPlan，（返回root根节点，逻辑树上包含输出字段、meta与字段映射关系、索引等）
return createOutputPlan(planStatementWithoutOutput(analysis, statement), analysis);/*
逻辑执行计划是基于Visitor模型生成的，逻辑计划为受访者，优化器为访问者
逻辑执行计划的节点都是PlanNode的实现类：最核心的accept()方法，代表这个当前node接收访问，就是调用Visitor的visitPlan()方法LogicalPlanner 遍历各种优化器对应的 optimize()方法。对PlanTree 进行优化，并对生成的Plan 进行验证。
优化过程中，优化器会在 Plan中插入 Exchange 结点。之后planFragmenter会根据这些Exchange结点将 Plan切分成 SubPlan。
*/if (stage.ordinal() >= Stage.OPTIMIZED.ordinal()) {for (PlanOptimizer optimizer : planOptimizers) {root = optimizer.optimize(root, session, symbolAllocator.getTypes(), symbolAllocator, idAllocator, warningCollector);requireNonNull(root, format("%s returned a null plan", optimizer.getClass().getName()));}
}//optimizer.optimize方法中，以rewritewith形式，重写现有逻辑树
SimplePlanRewriter.rewriteWith

优化器介绍：

常规优化器：

        需要实现optimize()方法。且需要自定义和实现整个Visitor的角色，即重载vistor*()的相关方法，例如visitAggregation，visitTopN，visitOutput等（PlanVisitor中定义了各种visit*()方法）

大致流程：

PlanOptimizer
    .optimize 
        .visitPlan
            context.defaultRewrite
                .rewrite
                .replace
            是否继续替换条件判断
                否：生成PlanNode返回

当 PlanNode 接受 Rewriter时，会进行
1. PlanNode 类型匹配：Rewriter 中的每个 visit* 方法都是针对特定类型的 PlanNode 设计的。例如，visitProject 是处理 ProjectNode 类型的节点，visitOutput 是处理 OutputNode 类型的节点。当 PlanNode 的类型与某个 visit* 方法匹配时，该方法就会被调用。
2. 递归遍历：Rewriter 通常会递归地遍历查询计划树。当它访问到一个节点时，会根据节点的具体类型调用相应的 visit* 方法。如果该节点类型没有特定的 visit* 方法，通常会调用一个更通用的 visitPlan 方法。
3. 方法执行：在 visit* 方法中，Rewriter 可以根据需要修改或替换当前节点。例如，它可能会添加新的节点，修改节点的属性，或者调整子节点的结构。

示例
假设有一个查询计划树，其中包含 OutputNode, ProjectNode, 和 FilterNode。Rewriter 在处理这个树时，会：
对于 OutputNode，调用 visitOutput 方法。
对于 ProjectNode，调用 visitProject 方法。
对于 FilterNode（如果没有特定的 visitFilter 方法），调用 visitPlan 方法。

LimitPushDown

//Limit下推优化器, 功能：判断是否可以下推Limit条件，以筛除数据,提高运行速度，减少资源消耗public class LimitPushDown implements PlanOptimizer.visitPlan
PlanNode rewrittenNode = context.defaultRewrite(node);//遍历所有node，调用rewrite方法
node.getSources().stream().map(child -> rewrite(child, context))//获取当前node的全局Limit条件是否存在，!=null则不能直接替换，生成LimitNode对象，返回LimitContext limit = context.get();
if (limit != null) {// Drop in a LimitNode b/c we cannot push our limit down any furtherrewrittenNode = new LimitNode(idAllocator.getNextId(), rewrittenNode, limit.getCount(), limit.isPartial());
}//替换原树
replaceChildren(node, children);/*
如果 LimitNode 的上游还有一个 LimitNode 那么把这两个 LimitNode 进行合并。
如果合并之后要 LimitNode 的count 是 0，那么直接把这个 LimitNode 节点换成一个空的 Values 节点。
如果 LimitNode 的上游有一个 TopN 节点，那么把 Limit 和 TopN 节点进行合并。
如果碰到 Union 节点，那么把 Limit 节点推到 Union 下面去。*///谓词下推,与Limit逻辑基本一致
public class PredicatePushDown implements PlanOptimizer

 

AddExchanges

public class AddExchanges implements PlanOptimizer
plan.accept(new Rewriter(idAllocator, symbolAllocator, session), PreferredProperties.any());/*介绍：划分子图，为查询计划添加交换节点，确保任务正确分布在各个节点，直接影响SubPlan 的划分
功能：1.确保数据正确分布。例如 groupby 根据hash分布至不同节点上2.优化节点分布,减少网络传输，提高查询效率流程：1. 分析查询计划：优化器首先分析当前的查询计划，识别出需要数据交换的操作。这包括但不限于聚合、连接、排序等操作。2. 确定数据分布需求：对于每个操作，AddExchanges 确定数据需要如何分布以满足操作需求。例如，对于一个基于某个键的聚合操作，数据需要根据该键进行哈希分布。3. 插入交换节点：根据确定的数据分布需求，AddExchanges 在查询计划中适当的位置插入交换节点。这些节点负责在执行时将数据从一个节点传输到另一个节点。4. 优化数据路径：在添加交换节点的同时，AddExchanges 还会尝试优化数据传输的路径，减少跨节点的数据移动，优化整体查询性能。5. 递归处理：由于查询计划可能非常复杂，包含多层嵌套的操作，AddExchanges 通常需要递归地处理整个查询计划树，确保所有需要的数据交换都被正确处理。
*/ExhangeNode.Type:GATHER          收集类型。出现在局部聚合或Coordinator OutPut  REPARTITION     shuffle类型。按hashcode分发至指定节点，出现在groupby或join时REPLICATE       拷贝类型。出现在小表join大表，广播时
ExhangeNode.Scope:LOCAL 预聚合REMOTE 任务切分，生成SubPlan

迭代优化器 IterativeOptimizer 

迭代优化器是在基础优化器开发基础上，做的代码重构。/*
Memo对象背景：
源码中，为保证程序稳定，避免潜在问题。PlanNode对象是不可变的(immutable)，但每次修改则需要重构树，性能有所下降且修改麻烦。为解决这个问题，则声明了一个Memo可变对象。
Memo中，PlanNode被包装成 GroupReference(不可变),GroupReference包含Group(可变)，Group包含PlanNode(用于修改优化)。通过遍历GroupReference修改PlanNode。
Group 伴随引用计数，如被优化或不被任何Group引用，则需要清理掉// 增加引用计数
incrementReferenceCounts(node, group);// 更新节点
getGroup(group).membership = node;// 减少引用计数，如果为0，则删除
decrementReferenceCounts(old, group);*///流程：
optimize:new Memo();new PlanNodeMatcher();exploreGroup(memo.getRootGroup(), context, matcher);//遍历Rule
Iterator<Rule<?>> possiblyMatchingRules = ruleIndex.getCandidates(node).iterator();
//Match  getPattern()
Rule.Result result = transform(node, rule, matcher, context);
//对应规则逻辑  rule.apply()
result = rule.apply(match.value(), match.captures(), ruleContext(context));

关于Join优化器

distributed_join 是否使用分布式Join

distributed_sort 是否使用分布式Sort

join_distribution_type 分布式Join策略类型

join_reordering_strategy  重排序策略

max_reordered_joins 重排序组内容许Join表的最大值

push_aggregation_through_join  是否在Join前预聚合

task.max-partial-aggregation-memory  预聚合HashTable内存大小，默认16M

ReorderJoins in Presto 重排序优化：影响Join执行顺序，基于CBO动态规划生成,有超时问题

1. 枚举所有可能的连接顺序
chooseJoinOrder 方法首先会枚举所有可能的连接顺序。（生成选择生成left-deep tree ）
2. 计算每种连接顺序的成本
对于每一种可能的连接顺序，Presto 会计算其成本。成本的计算通常基于多个因素，如数据大小、过滤器的选择性、连接键的分布等。Presto 使用成本模型来估算不同连接顺序的执行成本。
3. 选择最低成本的连接顺序
在所有可能的连接顺序中，chooseJoinOrder 方法会选择成本最低的一个。这是通过比较每种连接顺序的预估成本来实现的。
4. 递归优化每个子连接
一旦选择了一个连接顺序，chooseJoinOrder 方法会递归地优化每个子连接。这意味着对于每个连接操作，它会再次调用自身来优化该连接操作中涉及的表的连接顺序。
5. 应用最优连接顺序
最后，选择的连接顺序会被应用到查询计划中。这可能涉及到重构原始的查询计划树，以便按照选择的顺序执行连接

注意：重排优化选择成本最低的顺序即最优顺序，Hive不支持直方图，因此无法使用该优化

EliminateCrossJoins ： 对表之间的Join顺序重新排列，避免笛卡尔积问题

InnerJoin包裹CrossJoin 通过更改执行顺序，优化为InnerJoin包裹InnerJoin

DetermineJoinDistributionType 控制分布式优化规则：用于决定Join类型，基于CBO生成

Partial Aggregations  预聚合优化器

通过push_partial_aggregation_through_join配置使用（默认：关闭）。预聚合并不影响数据量。如果hash分布特别散时，反而会使查询变慢。

额外话题：

   RBO(Rule-Based Optimization)，基于规则的优化器。

• 谓词下推
• 列裁剪
• 常量折叠
• 表达式改写
• 最大最小消除
• 消除空算子
• 投影消除
• 函数下推
• 子查询去关联化
• 短路径优化查询
• 优化中断
• 其他

    CBO(Cost-Based Optimization),   基于成本的优化器。

        根据数据的统计信息、基数估计、算子代价模型等。在构造SQL搜索空间中的执行计划时，选择代价(CPU\内存\网络IO)最小的执行计划

        大致流程：

                1.根据转换规则，生成多个逻辑计划

                2.根据逻辑计划，生成Operator物理计划

                3.根据统计信息，生成多个方案，评估最小代价方案。

CBO的目的不是得到最优的方案,而是一个足够好的方案。

相关基础知识：数据库内核-CBO 优化器基本概念 - 知乎

总结：

基础优化器，通过vistor模式重写了各种方法。当对应PlanNode类型访问时，要执行的其自定义优化方法,最后判断是否符合更新规则，更新原树结构。
迭代优化器, 定义了各种规则(Rule)，模式匹配（PlanNodeMatcher）当前树是否符合规则，符合则调用对应规则进行优化，输入原树，输出新树。

区别：
基础优化器需要定义各种Node类型，实现vistor对象，重新visit*方法
迭代优化器编写Rule,重写getPattern(匹配规则)、apply（优化方法）即可,同时还可以控制由Session参数，决定是否启用某个优化规则（EliminateCrossJoins只有在满足join条件时才运行）。

备注：

validate 验证  

extract 提取  

phase 阶段

SymbolAllocator 符号分配器