广东快乐10分预测

当前位置：广东快乐10分预测 > 广东快乐10分预测 > Spark SQL Catalyst优化器广东快乐10分预测

Spark SQL Catalyst优化器广东快乐10分预测

来源：http://www.btxygg.com 作者：广东快乐10分预测 时间：2019-11-03 15:19

CBO

Reference

  • Deep Dive Into Catalyst: Apache Spark’s Optimizer
  • Spark SQL Optimization – Understanding the Catalyst Optimizer
  • Catalyst——Spark SQL中的函数式关系查询优化框架
  • SparkSQL – 从0到1认识Catalyst
  • Spark-Catalyst Optimizer
  • sparksql执行流程分析
  • SparkSQL优化器Catalyst
  • spark catalyst source code
  • Cost-Based Optimizer in Apache Spark 2.2

ROWID: 表中的每一行在数据文件中都有一个物理地址，ROWID伪列返回的就是该行的物理地址。使用ROWID可以快速的定位表中的某一行，ROWID值可以唯一的标识表中的一行，由于ROWID返回的是该行的物理地址，因此使用ROWID可以显示行是如何存储的。

而数据库主要由三部分组成，分别是解析器、优化器和执行引擎。

Overview

Spark SQL的核心是Catalyst优化器，是以一种新颖的方式利用Scala的的模式匹配和quasiquotes机制来构建的可扩展查询优化器。

广东快乐10分预测 1

sparkSql pipeline

sparkSql的catalyst优化器是整个sparkSql pipeline的中间核心部分，其执行策略主要两方向，

  1. 基于规则优化/Rule Based Optimizer/RBO
    • 一种经验式、启发式优化思路
    • 对于核心优化算子join有点力不从心，如两张表执行join，到底使用broadcaseHashJoin还是sortMergeJoin，目前sparkSql是通过手工设定参数来确定的，如果一个表的数据量小于某个阈值（默认10M？）就使用broadcastHashJoin
      • nestedLoopsJoin，P，Q双表两个大循环, O(M*N)
      • sortMergeJoin是P，Q双表排序后互相游标
      • broadcastHashJoin，PQ双表中小表放入内存hash表，大表遍历O(1)方式取小表内容
  2. 基于代价优化/Cost Based Optimizer/CBO
    • 针对每个join评估当前两张表使用每种join策略的代价，根据代价估算确定一种代价最小的方案
    • 不同physical plans输入到代价模型（目前是统计），调整join顺序，减少中间shuffle数据集大小，达到最优输出

或者使用如下，使用HINT方式：

SQL优化是我们经常会遇到的问题，无论你是专职的数据分析人员还是全栈开发大神或者是CURD搬运工。

SparkPlanner模块

至此，OLP已经得到了比较完善的优化，然而此时OLP依然没有办法真正执行，它们只是逻辑上可行，实际上spark并不知道如何去执行这个OLP。

  • 比如join只是一个抽象概念，代表两个表根据相同的id进行合并，然而具体怎么实现这个合并，逻辑执行计划并没有说明

广东快乐10分预测 2

optimized logical plan -> physical plan

此时就需要将左边的OLP转换为physical plan物理执行计划，将逻辑上可行的执行计划变为spark可以真正执行的计划。

  • 比如join算子，spark根据不同场景为该算子制定了不同的算法策略，有broadcastHashJoin、shuffleHashJoin以及sortMergeJoin，物理执行计划实际上就是在这些具体实现中挑选一个耗时最小的算法实现，这个过程涉及到cost model/CBO

广东快乐10分预测 3

CBO off

广东快乐10分预测 4

CBO on

CBO中常见的优化是join换位，以便尽量减少中间shuffle数据集大小，达到最优输出。

WHERE ROWNUM <= 5); // 取工资最高的前5名

从描述来看，CBO是优于RBO的，RBO只认规则，对数据不敏感，而在实际的过程中，数据的量级会严重影响同样SQL的性能。所以仅仅通过RBO生成的执行计划很有可能不是最优的。而CBO依赖于统计信息和代价模型，统计信息的准确与否、代价模型是否合理都会影响CBO选择最优计划。

SELECT ROWNUM, ename, job, sal FROM emp WHERE ROWNUM <= 5; // 取前5名员工的信息

RBO(Rule-Based Optimizer) 基于规则的优化器。是根据已经制定好的一些优化规则对关系表达式进行转换，最终生成一个最优的执行计划。它是一种经验式的优化方法，优化规则都是预先定义好的，只需要将SQL按照优化规则的顺序往上套就行，一旦满足某个规则则进行优化。

0. Overview
1. Catalyst工作流程
2. Parser模块
3. Analyzer模块
4. Optimizer模块
5. SparkPlanner模块
6. Job UI
7. Reference

参考：

我们在工作中经常会听到这样的声音：“查询慢?加个索引吧”。虽然加索引并不一定能解决问题，但是这体现了SQL优化的思想。

Catalyst工作流程

  • Parser，利用ANTLR将sparkSql字符串解析为抽象语法树AST，称为unresolved logical plan/ULP
  • Analyzer，借助于数据元数据catalog将ULP解析为logical plan/LP
  • Optimizer，根据各种RBO，CBO优化策略得到optimized logical plan/OLP，主要是对Logical Plan进行剪枝，合并等操作，进而删除掉一些无用计算，或对一些计算的多个步骤进行合并

RBO

Analyzer模块

通过解析后ULP有了基本骨架，但是系统对表的字段信息是不知道的。如sum，select，join，where还有score，people都表示什么含义，此时需要基本的元数据信息schema catalog来表达这些token。最重要的元数据信息就是，

  • 表的schema信息，主要包括表的基本定义（表名、列名、数据类型）、表的数据格式（json、text、parquet、压缩格式等）、表的物理位置
  • 基本函数信息，主要是指类信息

Analyzer会再次遍历整个AST，对树上的每个节点进行数据类型绑定以及函数绑定，比如people词素会根据元数据表信息解析为包含age、id以及name三列的表，people.age会被解析为数据类型为int的变量，sum会被解析为特定的聚合函数，

广东快乐10分预测 5

词义注入

//org.apache.spark.sql.catalyst.analysis.Analyzer.scala
  lazy val batches: Seq[Batch] = Seq( //不同Batch代表不同的解析策略
    Batch("Substitution", fixedPoint,
      CTESubstitution,
      WindowsSubstitution,
      EliminateUnions,
      new SubstituteUnresolvedOrdinals(conf)),
    Batch("Resolution", fixedPoint,
      ResolveTableValuedFunctions ::
      ResolveRelations ::  //通过catalog解析表或列基本数据类型,命名等信息
      ResolveReferences :: //解析从子节点的操作生成的属性，一般是别名引起的，比如people.age
      ResolveCreateNamedStruct ::
      ResolveDeserializer ::
      ResolveNewInstance ::
      ResolveUpCast ::
      ResolveGroupingAnalytics ::
      ResolvePivot ::
      ResolveOrdinalInOrderByAndGroupBy ::
      ResolveMissingReferences ::
      ExtractGenerator ::
      ResolveGenerate ::
      ResolveFunctions :: //解析基本函数,如max,min,agg
      ResolveAliases ::
      ResolveSubquery :: //解析AST中的字查询信息
      ResolveWindowOrder ::
      ResolveWindowFrame ::
      ResolveNaturalAndUsingJoin ::
      ExtractWindowExpressions ::
      GlobalAggregates :: //解析全局的聚合函数，比如select sum(score) from table
      ResolveAggregateFunctions ::
      TimeWindowing ::
      ResolveInlineTables ::
      TypeCoercion.typeCoercionRules   
      extendedResolutionRules : _*),
    Batch("Nondeterministic", Once,
      PullOutNondeterministic),
    Batch("UDF", Once,
      HandleNullInputsForUDF),
    Batch("FixNullability", Once,
      FixNullability),
    Batch("Cleanup", fixedPoint,
      CleanupAliases)
  )

ORACLE HINT:

广东快乐10分预测 6

Optimizer模块

Optimizer是catalyst的核心，分为RBO和CBO两种。
RBO的优化策略就是对语法树进行一次遍历，模式匹配能够满足特定规则的节点，再进行相应的等价转换，即将一棵树等价地转换为另一棵树。SQL中经典的常见优化规则有，

  • 谓词下推（predicate pushdown）
  • 常量累加（constant folding）
  • 列值裁剪（column pruning）
  • Limits合并（combine limits）

广东快乐10分预测 7

由下往上走，从join后再filter优化为filter再join

广东快乐10分预测 8

从`100 80`优化为`180`，避免每一条record都需要执行一次`100 80`的操作

广东快乐10分预测 9

剪裁不需要的字段，特别是嵌套里面的不需要字段。如只需people.age，不需要people.address，那么可以将address字段丢弃

//@see http://blog.csdn.net/oopsoom/article/details/38121259
//org.apache.spark.sql.catalyst.optimizer.Optimizer.scala
  def batches: Seq[Batch] = {
    // Technically some of the rules in Finish Analysis are not optimizer rules and belong more
    // in the analyzer, because they are needed for correctness (e.g. ComputeCurrentTime).
    // However, because we also use the analyzer to canonicalized queries (for view definition),
    // we do not eliminate subqueries or compute current time in the analyzer.
    Batch("Finish Analysis", Once,
      EliminateSubqueryAliases,
      ReplaceExpressions,
      ComputeCurrentTime,
      GetCurrentDatabase(sessionCatalog),
      RewriteDistinctAggregates) ::
    //////////////////////////////////////////////////////////////////////////////////////////
    // Optimizer rules start here
    //////////////////////////////////////////////////////////////////////////////////////////
    // - Do the first call of CombineUnions before starting the major Optimizer rules,
    //   since it can reduce the number of iteration and the other rules could add/move
    //   extra operators between two adjacent Union operators.
    // - Call CombineUnions again in Batch("Operator Optimizations"),
    //   since the other rules might make two separate Unions operators adjacent.
    Batch("Union", Once,
      CombineUnions) ::
    Batch("Subquery", Once,
      OptimizeSubqueries) ::
    Batch("Replace Operators", fixedPoint,
      ReplaceIntersectWithSemiJoin,
      ReplaceExceptWithAntiJoin,
      ReplaceDistinctWithAggregate) ::
    Batch("Aggregate", fixedPoint,
      RemoveLiteralFromGroupExpressions,
      RemoveRepetitionFromGroupExpressions) ::
    Batch("Operator Optimizations", fixedPoint,
      // Operator push down
      PushProjectionThroughUnion,
      ReorderJoin,
      EliminateOuterJoin,
      PushPredicateThroughJoin, //谓词下推之一
      PushDownPredicate, //谓词下推之一
      LimitPushDown,
      ColumnPruning, //列值剪裁,常用于聚合操作,join左右孩子操作,合并相邻project列
      InferFiltersFromConstraints,
      // Operator combine
      CollapseRepartition,
      CollapseProject,
      CollapseWindow,
      CombineFilters, //谓词下推之一,合并两个相邻的Filter。合并2个节点，就可以减少树的深度从而减少重复执行过滤的代价
      CombineLimits, //合并Limits
      CombineUnions,
      // Constant folding and strength reduction
      NullPropagation,
      FoldablePropagation,
      OptimizeIn(conf),
      ConstantFolding, //常量累加之一
      ReorderAssociativeOperator,
      LikeSimplification,
      BooleanSimplification, //常量累加之一,布尔表达式的提前短路
      SimplifyConditionals,
      RemoveDispensableExpressions,
      SimplifyBinaryComparison,
      PruneFilters,
      EliminateSorts,
      SimplifyCasts,
      SimplifyCaseConversionExpressions,
      RewriteCorrelatedScalarSubquery,
      EliminateSerialization,
      RemoveRedundantAliases,
      RemoveRedundantProject) ::
    Batch("Check Cartesian Products", Once,
      CheckCartesianProducts(conf)) ::
    Batch("Decimal Optimizations", fixedPoint,
      DecimalAggregates) ::
    Batch("Typed Filter Optimization", fixedPoint,
      CombineTypedFilters) ::
    Batch("LocalRelation", fixedPoint,
      ConvertToLocalRelation,
      PropagateEmptyRelation) ::
    Batch("OptimizeCodegen", Once,
      OptimizeCodegen(conf)) ::
    Batch("RewriteSubquery", Once,
      RewritePredicateSubquery,
      CollapseProject) :: Nil
  }

CBO和RBO区别：

目前各大数据库和大数据计算引擎都已经在使用CBO了，比如Oracle、Hive、Spark、Flink等等。

Parser模块

将sparkSql字符串切分成一个一个token，再根据一定语义规则解析为一个抽象语法树/AST。Parser模块目前基本都使用第三方类库ANTLR来实现，比如Hive，presto，sparkSql等。

广东快乐10分预测 10

parser切词

Spark 1.x版本使用的是Scala原生的Parser Combinator构建词法和语法分析器，而Spark 2.x版本使用的是第三方语法解析器工具ANTLR4。

Spark2.x SQL语句的解析采用的是ANTLR4，ANTLR4根据语法文件SqlBase.g4自动解析生成两个Java类：词法解析器SqlBaseLexer和语法解析器SqlBaseParser。

SqlBaseLexer和SqlBaseParser都是使用ANTLR4自动生成的Java类。使用这两个解析器将SQL字符串语句解析成了ANTLR4的ParseTree语法树结构。然后在parsePlan过程中，使用AstBuilder.scala将ParseTree转换成catalyst表达式逻辑计划LogicalPlan。

 

顾名思义，就是在执行计划生成的过程中动态优化的方式。随着大数据技术的飞速发展，静态的CBO已经无法满足我们SQL优化的需要了，静态的统计信息无法提供准确的参考，在执行计划的生成过程中动态统计才会得到最优的执行计划。

记录一下个人对sparkSql的catalyst这个函数式的可扩展的查询优化器的理解，目录如下，

SELECT * FROM

上篇文章我们提到了Calcite，Calcite本身就支持两种优化方式分别是RBO和CBO。

other

Optimizer是catalyst工作最后阶段了，后面生成physical plan以及执行，主要是由sparkSql来完成。

  • SparkPlanner
    • 优化后的逻辑执行计划OLP依然是逻辑的，并不能被spark系统理解，此时需要将OLP转换成physical plan
    • 从逻辑计划/OLP生成一个或多个物理执行计划，基于成本模型cost model从中选择一个
  • Code generation
    • 生成Java bytecode然后在每一台机器上执行，形成RDD graph/DAG

(SELECT ROWNUM R, ename, job, sal FROM emp WHERE ROWNUM <= 10)

这样的结果就是同样一条SQL，无论读取的表中的数据是怎样的，最后生成的执行计划都是一样的。而且SQL的写法不同也很有可能影响最终的执行计划，从而影响SQL的性能(基于优化规则顺序执行)。

Job UI

广东快乐10分预测 11

sp.prepare.PrepareController

  • WholeStageCodegen，将多个operators合并成一个java函数，从而提高执行速度
  • Project，投影/只取所需列
  • Exchange，stage间隔，产生了shuffle

SELECT ROWNUM, T.* FROM

动态CBO

select * from 

其执行逻辑是我们输入的SQL语句通过解析器解析成关系表达式，通过优化器把关系表达式转换成执行计划，最终通过执行引擎进行执行。所以优化器在很大程度上决定了一个系统的性能。优化器的作用就好比找到两点之间的最短路径。

Oracle的优化器有两种优化方式,即基于规则的优化方式(Rule-Based Optimization，简称为RBO)和基于代价的优化方式(Cost-Based Optimization，简称为CBO)，在Oracle8及以后的版本,Oracle强列推荐用CBO的方式
    RBO方式：优化器在分析SQL语句时,所遵循的是Oracle内部预定的一些规则。比如我们常见的，当一个where子句中的一列有索引时去走索引。

所以说，虽然RBO是一个老司机，知道常见的套路，但是当路况不同时，无法针对性的达到最佳的效果。

ROWNUM: 在查询的结果集中，ROWNUM为结果集中每一行标识一个行号，第一行返回1，第二行返回2，以此类推。通过ROWNUM伪列可以限制查询结果集中返回的行数。

CBO(Cost-Based Optimizer)基于代价的优化器。根据优化规则对关系表达式进行转换，生成多个执行计划，最后根据统计信息和代价模型计算每个执行计划的Cost。从中挑选Cost最小的执行计划作为最终的执行计划。

参考：

    CBO方式：它是看语句的代价(Cost),这里的代价主要指Cpu和内存。优化器在判断是否用这种方式时,主要参照的是表及索引的统计信息。统计信息给出表的大小、有少行、每行的长度等信息。这些统计信息起初在库内是没有的，是做analyze后才出现的，很多的时侯过期统计信息会令优化器做出一个错误的执行计划,因些应及时更新这些信息。

(select tftl.*, rownum rn from
(select * from test where req_brh_code='111' order by id desc) tftl
where rownum <= 40
)
where rn > 20;

 

(SELECT ename, job, sal FROM emp ORDER BY sal DESC) T

 

SELECT ROWID, ename FROM emp WHERE sal > 2000;

select /* FIRST_ROWS */ * from
( select A.*, rownum rn
FROM (select * from test where req_brh_code='111' order by id desc) A
where rownum <= 40)
where rn > 20;

Hint 是Oracle 提供的一种SQL语法，它允许用户在SQL语句中插入相关的语法，从而影响SQL的执行方式，因为Hint的特殊作用，所以对于开发人员不应该在代码中使用它，Hint 更像是Oracle提供给DBA用来分析问题的工具 。在SQL代码中使用Hint，可能导致非常严重的后果，因为数据库的数据是变化的，在某一时刻使用这个执行计划是最优的，在另一个时刻，却可能很差，这也是CBO 取代RBO的原因之一，规则是死的，而数据是时刻变化的，为了获得最正确的执行计划，只有知道表中数据的实际情况，通过计算各种执行计划的成本，则其最优，才是最科学的，这也是CBO的工作机制。 在SQL代码中加入Hint，特别是性能相关的Hint是很危险的做法。

WHERE R > 5;

ROWID和ROWNUM不同，ROWID是插入数据时生成的，而ROWNUM是查询数据时生成的，ROWID是表示行的物理地址，ROWNUM标识的是查询结果中的行的次序。

这里牵涉到oracle的分页问题，可以写出如下代码，查询速度很快：

本文由广东快乐10分预测发布于广东快乐10分预测,转载请注明出处：Spark SQL Catalyst优化器广东快乐10分预测

关键词： 简介 sql O spark Oracle

上一篇：2018-04-18广东快乐10分预测

下一篇：没有了

相关阅读：