mpp query optimization

2022-11-24 15:17:28 浏览数 (2)

声明:本文基本为多篇文章组合而成,仅供参考!(主要参考https://developer.aliyun.com/article/789901?spm=a2c6h.12873581.technical-group.dArticle789901.290e60bcFsF6TR)

一 Query

1 Parsing

代码语言：javascript复制
    ParserQuery parser(end, settings.enable_debug_queries);
    ASTPtr ast;
    //把Query转化为抽象语法树
    ast = parseQuery(parser, begin, end, "", max_query_size);
​
ASTPtr tryParseQuery()
{
    //Token为lexer词法分析后的基本单位,词法分析后生成的是Token流
    Tokens tokens(pos, end, max_query_size);
    IParser::Pos token_iterator(tokens);
    ASTPtr res;
    //Token流经过语法分析生成AST抽象语法树
    bool parse_res = parser.parse(token_iterator, res, expected);
    return res;
​
}
​
    select_query->setExpression(ASTSelectQuery::Expression::SELECT, std::move(select_expression_list));

-> Query Parsing 通过定义的

负责进行词法和语法分析,把程序从人类高可读的格式(即SQL)转化成机器高可读的格式(AST,抽象语法树)。

词法分析指的是把SQL中的字符序列分解成一个个独立的词法单元——Token(<类型，值>)。语法分析指的是从词法分析器输出的token中识别各类短语，并构造出一颗抽象语法树。而按照构造抽象语法树的方向，又可以把语法分析分成自顶向下和自底向上分析两种。而ClickHouse采用的则是手写一个递归下降的语法分析器。

Token: 代表若干个字符组成的一个有意义的”词“，token有很多type，见src/Parsers/Lexer.h下的宏定义。

Lexer：词法解析器，输入sql语句，吐出一个个token。最终将这些token加上一些有意义的信息按规则组织起来就是最终的Ast树。

Function /ExpressionAnalyzer

AST/Expr Parsing(){

return AST/Expr by Token

}

2 Optimizer

代码语言：javascript复制
     //获取AST
    auto & query = getSelectQuery();
    
    //对AST做进一步语法分析，对语法树做优化重写
    syntax_analyzer_result = SyntaxAnalyzer(context, options).analyze(
        query_ptr, source_header.getNamesAndTypesList(), required_result_column_names, storage, NamesAndTypesList());
    
​
    //每一种Query都会对应一个特有的表达式分析器,用于爬取AST生成执行计划(操作链)
    query_analyzer = std::make_unique<SelectQueryExpressionAnalyzer>(
        query_ptr, syntax_analyzer_result, context,
        NameSet(required_result_column_names.begin(), required_result_column_names.end()),
        options.subquery_depth, !options.only_analyze); 
​
AST是由Interpreter来解析的，执行结果是一个BlockIO,BlockIO是对 BlockInputStream 和 BlockOutputStream 的一个封装。
1 Query Rewrite

Query Logical Optimizer : (RBO 启发式搜索)

即通常我们说的"Logical Optimizer"或基于规则的优化器(Rule-Based Optimizer,即RBO)。

其负责应用一些启发式规则，负责简化和标准化查询，无需改变查询的语义。

常见操作有:谓词和算子下推，视图展开，简化常量运算表达式，谓词逻辑的重写，语义的优化等。

Function/SyntaxAnalyzer

AST/Expr Rewrite(){

return AST/Expr By RBO

}

代码语言：javascript复制
SyntaxAnalyzerResultPtr SyntaxAnalyzer::analyze()
{
     // 剔除冗余列
     removeDuplicateColumns(result.source_columns);
     
     // 根据settings中enable_optimize_predicate_expression配置判断是否进行谓词下移
     replaceJoinedTable(node);
     
     // 根据settings中distributed_product_mode配置重写IN 与 JOIN 表达式
     InJoinSubqueriesPreprocessor(context).visit(query);
     
     // 优化Query内部的布尔表达式
     LogicalExpressionsOptimizer().perform();
​
     // 创建一个从别名到AST节点的映射字典 
     QueryAliasesVisitor(query_aliases_data, log.stream()).visit(query);
    
     // 公共子表达式的消除
     QueryNormalizer(normalizer_data).visit(query);
    
     // 消除select从句后的冗余列
     removeUnneededColumnsFromSelectClause(select_query, required_result_columns, remove_duplicates);
     
     // 执行标量子查询，并且用常量替代标量子查询结果
     executeScalarSubqueries(query, context, subquery_depth);
​
     // 如果是select语句还会做下列优化:
    
     // 谓词下移优化
     PredicateExpressionsOptimizer(select_query, settings, context).optimize();
     
     /// GROUP BY 从句的优化
     optimizeGroupBy(select_query, source_columns_set, context);
     
     /// ORDER BY 从句的冗余项剔除
     optimizeOrderBy(select_query);
     
     /// LIMIT BY 从句的冗余列剔除
     optimizeLimitBy(select_query);
     
     /// USING语句的冗余列剔除
     optimizeUsing(select_query);
   
}
2 Query Optimizer

Physical Optimizer ,CBO

即通常我们所说的"Physical Optimizer"，负责把内部查询表达转化成一个高效的查询计划，指导DBMS如何去取表，如何进行排序，如何Join。如下图所示，一个查询计划可以被认为是一个数据流图，在这个数据流图中，表数据会像在管道中传输一样，从一个查询操作符(operator)传递到另一个查询操作符。

生成物理执行计划

Function/ExpressionAnalyzer

Plan Rewrite(){

return Plan By AST/Expr , CBO

}

代码语言：javascript复制
executeImpl()
     AnalysisResult expressions;
     // 物理计划，判断表达式是否有where,aggregate,having,order_by,litmit_by等字段
     expressions = analyzeExpressions(
                getSelectQuery(),
                *query_analyzer,
                QueryProcessingStage::FetchColumns,
                options.to_stage,
                context,
                storage,
                true,
                filter_info);
既然我们知道了执行计划AnalysisResult(即物理执行计划)，接下来就需要从storage层中读取数据来执行对应的操作，核心逻辑在 executeFetchColumns 中: 核心操作就是从storage层读取所要处理列的Block，并组织成BlockStream。

transformer就是算子的概念,所有 transformer 被编排成一个流水线(pipeline)

3 Query Executor

查询执行器，负责执行具体的查询计划，从存储引擎中获取数据并且对数据应用查询计划得到结果。 执行引擎也分为很多种，如经典的火山模型(Volcano Model)，还有ClickHouse采用的向量化执行模型(Vectorization Model)。

代码语言：javascript复制
     // 从Storage读取数据
     executeFetchColumns(from_stage, pipeline, sorting_info, expressions.prewhere_info, expressions.columns_to_remove_after_prewhere);
​
     // eg:根据SQL的关键字在BlockStream流水线中执行相应的操作, 如where,aggregate,distinct都分别由一个函数负责执行
     executeWhere(pipeline, expressions.before_where, expressions.remove_where_filter);
     
     executeAggregation(pipeline, expressions.before_aggregation, aggregate_overflow_row, aggregate_final);
     
     executeDistinct(pipeline, true, expressions.selected_columns);

4 Return

TCPHandler::runImpl 中，执行完 executeQuery 之后需要调用各种processQuery的方法来给client返回执行SQL后的结果。 我们以 TCPHandler::processOrdinaryQuery 为例做简单分析:

代码语言：javascript复制
void TCPHandler::processOrdinaryQuery()
{
    //把BlockStream封装成异步的Stream,那么从流中读取数据将会是异步操作
    AsynchronousBlockInputStream async_in(state.io.in);
    
    while(true){
         Block block;
         //从IO流读取block数据
         block = async_in.read();
         //发送block数据
         sendData(block);
    }
}

Server负责在 sendData 函数中把输出结果写入到套接字输出缓冲区中,client只要从这个输出缓冲区读取就能够得到结果。

代码语言：javascript复制
void TCPHandler::sendData(const Block & block)
{
    //初始化OutputStream的参数
    initBlockOutput(block);
​
    // 调用BlockOutputStream的write函数,把Block写到输出流
    state.block_out->write(block);
    state.maybe_compressed_out->next();
    out->next();
}

二 Optimize

Top-down win：

  • Volcano的算法中，包含了logical transformation的过程，因此可以去做等价变化，这不仅限于join ordering，各种类型的query transformation（例如group by placement, filter pushdown...）理论上都可以在top-down的search过程中完成，但bottom-up主要还是针对join ordering，描述等价变换比较困难。
  • Top-down的search方法，有一个最大的优点，就是可以做branch-and-bound pruning，由于每递归到一个logical expression，总是带有目标的属性的，因此可以只针对满足这个属性的目标来枚举，而bottom-up枚举时，父节点的情况并不清楚，因此当前节点需要枚举各种可能的物理输出属性，没法只针对一个"branch"，此外由于向下有cost limit这个参数，在深度优先的递归时，一但cost limit无法满足要求就可以立即终止，形成了bound pruning。

Bottom-up win：

  • 由于覆盖的search space更大，top-down搜索花费的时间和空间overhead更大，这也是为什么更多大数据生态的系统或者数仓系统会使用这种优化器，由于查询更复杂且涉及的数据量更大，它牺牲了较多的优化时间来换取更优的查询计划。在像SQL Server这样要处理事务型workload的系统中，优化分为了多个阶段，这样可以基于走一些fast path或者基于某些规则提前结束搜索。

1 动态规划

动态规划

优化器的统计信息、代价模型、计划搜索几个问题都值得深究，这里仅仅涉猎计划搜索这一问题。

具体到查询这一问题，对于初始的Join Tree来说，Join算子会有多种实现，例如NestLoop和HashJoin，也即Join可以分解为两个子问题，NestLoop和HashJoin。而对于NestLoop来说，需要求解其子节点SCAN A和SCAN B，SCAN也有多种实现，例如SeqScan和IndexScan。同时，这里遇到了重叠子问题，在求解HashJoin的时候也需要计算SCAN A

Scan:SeqScan、IndexScan、BitmapScan、TidScan,搜索空间的第一层即为基表 Scan

优化器,可能有很多的规则,遵循的原则为:

  • 最优子结构：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）
  • 无后效性：即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
  • 重叠子问题：自顶向下对问题进行求解时，可能会遇到重复的子问题，对于子问题的解可以记录下来避免重复计算

impala 缺少什么,缺少算子去重

Query Optimizer 动态规划分两种

自顶向下 Cascades

自底向上 System R(Impala,PostgreSQL)

2 System R, bottom-up

自底向上的算法会先计算基表的访问路径（Access Path），通常来说存在几种：顺序扫描、索引扫描、组合索引等，而存在多个索引时，每个索引都视作一个访问路径。接着，枚举两表Join，这里同时还需要对Join的物理实现进行枚举，所以第二层的状态会比第一层多许多。一层层往上搜索，即可得到多表Join的执行计划。

impala 缺少什么,缺少 Bushy Tree

在搜索过程中，如果是纯粹地枚举所有可能的组合，则搜索空间会非常大。因此通常会对Join Tree的形状进行限制，也会在搜索过程中进行一定的剪枝。例如这里的两种典型的Join Tree，Left-deep和Bushy-Join。相比于Bushy-Tree的(2n-2)!/(n-1)!的复杂度，Left-Deep只有n!，搜索空间小了很多。

PG 实现

代码语言：javascript复制
join_search() {
    join_levels[1] = initial_rels;
    for (level : 2 -> N) {
        join_search_one_level() {
            // linear
            for (outer : join_levels[level-1]) {
                for (inner : join_levels[1]) {
                    if (overlap(outer, inner)) {
                        continue;
                    }
                    if (!has_restriction(outer, inner)) {
                        continue;
                    }
                    join_levels[level].add_path(make_join_rel(outer, inner));
        }
            }
            // bushy
            for (k : 2 -> N - 2) {
                for (outer : join_levels[k]) {
                    for (inner : join_levels[N-k]) {
                        ...
                    }
                }
            }
            // cross-product
        }
    }
}

Impala 缺少什么 ,缺少Interesting Order

在搜索过程中，每一层不需要保留所有的组合，而是保留代价最低的即可。但需要考虑到一个问题，两表Join的最优解，未必能得到三表Join的最优解，例如两表用了HashJoin，那么输出的结果会是无序的；相比之下，如果用MergeJoin，两表Join可能不是代价最小的， 但是在三表Join时，就可以利用其有序性，对上层的Join进行优化。

这里其实引出一个问题，自底向上的搜索过程中，下层无法知道上层需要的顺序，即便保留所有的Order，也未必能得到最优解。例如对A、B两表做笛卡尔积再排序，其代价可能要比先排序在做Join要高，但是在枚举Join时，无法知道上层需要的顺序，也就无法搜索这个计划。

3 SystemR 总结

  • 首先计算基表访问路径，PostgreSQL实现了SeqScan、IndexScan、BitmapScan、TidScan等方式
  • 搜索空间的第一层即为基表
  • 向上搜索每一层，先尝试linear tree，枚举上一层的每个Relation，与第一层的Relation进行组合，如果没有重叠并且有Join谓词连接，即调用add_path增加一条访问路径
  • add_path：并不是直接把访问路径加到这一层，而是先评估其代价和Interesting Order，如果代价更优，或者产生了新的Interesting Order，才会加到这一层的访问路径中
  • bushy tree：枚举bushy tree会把[2, N-2]层的Relation和N-k层的Relation进行组合
  • cross-product：如果上述两种枚举都没有搜索出可行的Join，则采取笛卡尔积，这个产生的结果通常较多

注意到其中一个细节，尝试组合两个Relation时，会判断两个Relation是否存在Join 谓词，例如JOIN A, B ON A.x = B.x，如果有连接谓词作为过滤条件，生成的结果会大大减少。这种先枚举再测试连通性的方式称之为『generate and test』，在特定的场景下效率并不高，test这个步骤占据了很大开销，存在一定的优化空间，后面会做介绍。

4 Cascades Top-down

Operator Tree = Memo

最顶层Group 引用了其他Group ,这里便形成了一个Group Tree,在搜索完成之后，我们可以从每个Group中选择出最优的Operator，并递归构建其子节点，即可得到最优的Operator Tree

Operator

Operator -> 1 Group = (1 Logical Operator Group Expression)

Operator -> 1 Group = (1 Logical Operator N(Group))

Operator -> 1 Group = 1 Logical Operator (N Paysical Operator))

5 Cascades 统计信息

经过以上的铺垫，自底向上的方法基本有了一个轮廓，同时我们在探索的过程中也意识到自底向上的一些局限性：

  • 适用于Join Enumeration问题，但对其他的优化并不适用
  • 在处理Interesting Order问题时，不能覆盖所有的搜索空间
  • 剪枝有限，很有可能下层会产生一些代价非常大的解决方案，本可以预先剪枝掉

由于Group中的多个Expression是逻辑等价的，因此他们共享一个statistics

Stats Derivation

在搜索过程中，需要对Group Expression的代价进行评估，而代价评估则依赖于统计信息。统计信息的构建是一个自底向上的过程，每个基表维护直方图等统计信息，向上可进一步推导出Join 的统计信息。由于Group中的多个Expression是逻辑等价的，因此他们共享一个statistics。这一过程称之为『Stats Derivation』。

Branch and bound

上线和下线

Transformation/Rewrite/Normalize的阶段，应用一些Heuristic的规则

前面提到自顶向下的搜索可以进行更多的剪枝，这里的原理是根据代价的upper bound剪枝。将最初的Operator Tree的代价计算其lower bound和upper bound，之后的搜索过程中，如果还没搜索到最底层的节点，其代价已经超过了upper bound，那么这个解决方案即可放弃，不会更优只会雪上加霜。

理想情况下，这种剪枝能过滤掉很多不必要的搜索，但依赖于初始计划的代价。初始计划如果很糟糕，代价很大，对后续的搜索将无法发挥剪枝的作用。因此通常的优化器会在搜索之前进行称之为Transformation/Rewrite/Normalize的阶段，应用一些Heuristic的规则，预先对Plan进行优化，减小后面的搜索空间。

Search

优化规则和搜索过程是Cascades的核心，也是优化器的工作重心。在传统的优化器实现中，往往是面向过程的，一条一条地应用优化规则，对Operator Tree进行变换。这种hardcode的方式往往难以扩展，想增加一条规则较为困难，需要考虑规则之间的应用顺序。而Cascades在处理这一问题时，将搜索过程与具体的规则解耦，用面向对象的方式对优化规则进行建模，规则的编写不需要关心搜索过程。

这里的搜索过程分解为几种Task：

  • Optimize Group：对一个Group进行优化，具体来说就是对其中每个Expression进行优化
  • Optimize Expression：优化一个Expression，对每个Expression应用优化规则，并寻找代价最小的Expression
  • Explore Group & Explore Expression：Explore过程是对逻辑算子进行等价变化
  • Apply Rule：应用具体的优化规则，从逻辑表达式推导出等价的逻辑表达式，或者从逻辑表达式推导物理表达式
  • Optimize Input：对代价进行估算，这是一个自底向上的过程，需要递归地计算子节点的统计信息和代价，再计算当前节点

这些Task会进行递归搜索，因此有两种选择，一种是直接递归调用，另一种则是用一个显式的的Stack，对任务进行调度：

Property Enforcer

前面提到Interesting Order的问题，在自顶向下的搜索过程中可以更加优雅地解决。这里讲Interesting Order的问题推广到Property，在分布式数据库的场景下，Property包含了数据分布的方式。例如分布式HashJoin要求两个表按照Hash分布，如果不满足这个属性，则需要对数据进行一次重分布。

自顶向下的搜索过程可以用需求驱动的方式来计算属性，例如需要对T1.a进行排序的方式有多种，即可分解成多个子问题，对HashJoin的结果进行归并排序，或者把数据收集到一个节点之后再进行排序，都是可能的解决方案。对于不同的解决方案仍然是基于代价来选择出最优的方案，从而形成整体的最优解。

Cascades

至此，基本覆盖了Cascades的原理，虽然理解起来很简单，但具体实现需要考虑更多的问题，工程实现的细节在这里无法一一枚举，有兴趣可参考具体的实现。在工业界，Peleton、Orca、SQL Server、Calcite、Cockroach等都算是Cascades的实现，其中不乏开源的优秀实现。

三 GP ORCA

模块化，以独立的Service形态单独存在，并不依附于特定的数据库产品，对外是标准化的接口和协议( )，这样理论上可以被集成到任何数据库系统中。

扩展性，可以扩展新的operator/cost model/property/rules

支持并行优化，其自身实现了subtask和job scheduler

可验证性，实现了方便测试与debug的工具集，便于复现问题 debug或者test，也便于快速迭代新功能

1 交互流程

  • 作为一个standalone服务单独存在是Orca比较有趣的一点，其基本流程

  1. Query进入DB后，要经过parser转换为AST，然后通过Query2DXL这个模块，将AST描述为DXL可以表述的标准形式（DXL Query）
  2. Orca接收到query后开始优化，在过程中会获取必要的元信息（如表/列的schema信息，统计信息等），这通过MD Provider实现，并转换为DXL MD传递给Orca，Orca内部是有MD cache的，来避免频繁获取metadata，metadata维护一个version信息，来判断是否过时。
  3. Orca完成优化流程，确定最优plan后，以DXL Plan的形式，传递给DB端，DB端使用DXL2Plan这个模块转换为内部可识别的physical plan，交由Executor执行。

可以看到Query2DXL，MD Provider，DXL2Plan这3个模块构成了适配层，不同的DB侧只需要根据自身特点完成转换工作即可。但个人感觉这个过程还是有些重，DXL(XML）本身就是复杂而臃肿的协议，query/plan的复杂性、metadata的维护都还是有一定工程挑战的。

2 总体框架

Orca的整体框架和各个组件如下

1. Memo : Cascades中的概念，是整个搜索空间的全局容器，代表逻辑等价类Group，表达式 Expr，都包含在其中，内部通过一些机制来实现高效的结构重用，减少内存开销。

2. Search Job Scheduler，表示具体的算法流程和执行优化的任务调度，和Cascades的paper一样，它把优化任务拆分为subtask。Search的整体过程和Cascades paper中虽然没有完全对齐，但基本思路是一致的：

exploration进行逻辑变换 <-> implementation完成物理算法选择 -> 递归到下层继续优化。

3. Transformation : 这里包括logical physical的转换，每个rule，都是可以单独开/关的。可以看到，Orca中的transformation，既包含逻辑等价变换，也包含选择物理算子，而它的exploration则是纯粹的等价变换，为了便于区分，我们还是使用exploration来表示逻辑变换，而使用implementation表示选择物理执行算法。

4. Property Enforcement : property的描述是规范且可扩展的，可以具有不同类型，paper中列举了logical property(输出哪些columns），physical property（数据的有序性，分布情况） scalar property（join columns，这里猜测是和property有关？？)。

这里的property和Cascades中的概念完全一致，在上层算子确定物理执行方式的同时，会对下层产生某种对输入数据的物理属性要求（e.g sort merge join要求数据在join key上有序），下层算子可以自身来保证满足这种物理属性要求（e.g index scan提供有序性）或者利用Enforcer来保证（e.g 加入sorting操作）。

5. Metadata Cache缓存在Orca侧，metadata通过version number来判断是否失效，这样下次再获取meta时可以先验证version信息，如果已过期再获取新数据，避免过多大量信息交互。

3 优化流程

paper中使用了一个简单SQL 来示例优化流程：

代码语言：javascript复制
SELECT T1.a FROM T1, T2
 WHERE T1.a = T2.b
 ORDER BY T1.a;

数据是sharding的，T1 基于Hash(T1.a）分布，T2基于Hash(T2.a)分布。这个plan的初始状态是

可以看到，自顶向下，每个group描述一个逻辑操作，上层group 0中通过编号1,2引用了下层group。每个group内的编号0，是初始的expr。

1. Exploration:

在group内，基于已有expr做logical transformation，这里可能会生成新的expr，在本例中可以通过join交换律从 Inner join [1,2] => Inner join [2,1]。如果逻辑变换较大，则可能生成新的group，例如执行view merge操作展开内层表到外层，就会出现作为外层表的多个table group。

从论文中的描述，感觉exploration是集中完成的，而没有和implentation交错执行，估计交错方式实现复杂度太高。

2. Statistics Derivation:

在完成exploration后，就可能建立起由逻辑等价类（group）组成的多棵候选的plan tree。在开始搜索物理plan之前，先要有必要的统计信息才可以计算相关的代价，因此有一个收集 生成统计信息的过程。在Orca中，这个统计信息主要就是指一系列的column histograms，用它来做Cardinality Estimation和检测data skew。

这里针对每个group的statistics，提出了一个非常有趣的概念： ，Statistics promise。我们都知道统计信息都是不精确的，那么在同一个逻辑表达式上，也许有多个统计信息可以使用，可以尽量选择置信度高的统计信息用于估算。例如一个group中，可能有多个表示inner join的等价group expr，其中1种join组合方式，涉及的join condition较少，而另一种join组合方式的join condition则更多（不同join order），这时选择更少condition的可能误差就会更少（cardinality estimation的误差会随着乘积传播和扩大）。

对各个group，自底向上完成，histogram的估算有很多方法，例如SQL Server中的方法：

上图并不难理解，根据join两侧的column histogram，获取两个domain中的bucket boundaries集合，等于将两个histogram都切分成了更小的sub bucket，在每个sub bucket内仍假设均匀分布，并基于join inclusion的假设来计算join cardinality，再累计起来，就得到了join group expr的histogram。

3. Implementation:

为每个logical group expr，选择所有可能使用的物理实现算法，包括scan方式，join算法等，生成对应的physical group expr。

4. Optimization:

Search plan space，过程中会计算相应cost。初始会从root group开始，根据一个optimization goal(cost limit , property requirement)，对一个group开始优化，等同于从这个group开始，选出其内部最优的physical expr以及其下层整个physical expr tree。

在一个group内，会从每个step 3生成的每个physical expr为起点深度优先，向下查找，首先会扣除它自身的cost，并根据其上层的property requirement以及expr自身的property特性，形成对其输入group的physical property要求，这样就从当前level 1 的(cost , prop requirement1) 递归到了下层group (level 2)，optimization goal变为了 (cost - l1 cost, prop requirement2)。

对每个physical expr来说，如果所属group的optimization goal中的property requirement可以被expr本身输出的物理属性所满足，则可以直接应用该expr，否则需要加入enforcer来强制目标属性，下图中给出了一个简单的inner hash join的优化过程：

图(a)中，初始的optimization goal施加在group 0上，它要求输出数据在单个节点中(singleton)，且按照T1.a有序。当进入group内处理每个physical expr时（本图中是Inner hash join[1,2]这个expr），会结合inner hash join的特点，生成对children group的optimization goal，这里分别是左右child的 Hash(join key), 顺序则是Any，也就是说，要求左右table数据都分布在join key上，且由于hash join不保序，因此其children也不要求输出有序。

图(b)中，假设T1的数据已经在T1.a列上分布，而T2的分布键却不是T2.b，因此无法满足Hash(T2.b)这个物理属性，需要加入Redistribution(T2.b)这个enforcer来满足分布要求。

图(c,d)中，inner hash join已经在各个节点上完成了co-located join，但数据并不满足singleton的要求，也不满足有序的要求，这时需要加入新的enforcer，那么有两种选择：

要么如图c中，先在各节点排序后在汇总到leader节点，即sort -> gather -> mergesort。

要么如图d中，先gather到leader节点，再对全量数据排序。

选哪种方案，就取决于cardinality 和 cost了。

5. Memo

Memo中高效的组织了Group、Group Expr的信息，使其可以被复用，具体来说

每个group维护一个hash table，保存{property request -> 本group最优physical group expr}的映射。

每个group expr维护一个local hash table，保存(property request -> 各个input的property request)的映射。

上图中是一个比较完整的Memo结构，其中灰色方框的是physical group expr，黑色方框则是enforcer。每个group左侧的table就是 request -> best expr，每个expr下方的小表格，则是property request（表格第一列） -> input children（表格第二列）。

这样首先同一个expr/enforcer，可以以编号的形式被多个其他expr引用，从而实现了结构的复用最小化内存占用。如果想要获取最优expr tree，只需要顺着root group request -> group hash -> group内最优expr -> expr local hash -> children group request -> ...的方式，串连起整个expr/enforcer tree。

6. Metadata exchange

MD 获取的设计提前其作为外挂优化器的灵活性：

不同的外部系统，都可以基于MD Provider提供适配的元数据，元数据会在优化期间保存在MD Cache中，优化结束后可以释放，有个有趣的地方是最左侧的File based Provider，也就是说Orca可以完全不依赖于一个在线系统，这种用local file来mock一个DB的方式，使得Orca可以被更好的测试、调试和验证。

7. 可验证性

优化器可以说是数据库系统中最为复杂和不确定性的组件，在漫长的开发流程中，高效的验证能力，快速发现regression，快速定位问题是保证开发效率以及解决线上问题的必要条件。因此围绕Orca，引入了两个工具：

四 总结

cascades框架是理论上最为灵活且扩展性最强的优化器实现方案，但可惜目前业界成熟的实现并不多，开源的更少。

  1. Calcite虽然广为使用但其自身主要针对异构数据源的兼容，在优化规则的支持上并不很丰富
  2. Orca虽然强大，但由于与Postgres生态的耦合较深，导致无法被广泛应用
  3. CockroachDB的优化器虽然也采用cascades，但主要集中在heuristic上，cost based的部分较少
  4. 最为成熟的应该是G. Graefe主导的SQL Server optimizer，可惜不开放...

看起来最值得研究的还是GPORCA，后续笔者争取能写一些关于Orca的设计实现和代码分析文章，敬请期待。

五 素源

https://developer.aliyun.com/article/765184

https://github.com/ClickHouse/ClickHouse/tree/master/src/Parsers

https://github.com/ClickHouse/ClickHouse/tree/master/src/Analyzer

https://github.com/ClickHouse/ClickHouse/tree/master/src/Processors/Transforms

https://zhuanlan.zhihu.com/p/73545345

https://developer.aliyun.com/article/789901?spm=a2c6h.12873581.technical-group.dArticle789901.290e60bcFsF6TR

https://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/Papers/Cascades-graefe.pdf

https://paperhub.s3.amazonaws.com/dace52a42c07f7f8348b08dc2b186061.pdf

数据库 分布式数据库TDSQL 云数据仓库ClickHouse

0 人点赞