本文参考了《Spark SQL内核剖析》（朱峰、张韶全、黄明等著）的目录结构和内容，这本书主要集中在对SQL内核实现的剖析上，从源码实现上学习分布式计算和数据库领域的相关技术，非常值得有相关需求的专业人士学习和购买。我写这篇文章的目的也是基于此做一个关于Spark SQL的学习以及分享了一些自己的理解。
什么是Spark SQL?
Spark SQL是近年来SQL-on-Hadoop解决方案（包括Hive、Presto和Impala等）中的佼佼者，结合了数据库SQL处理和Spark分布式计算模型两个方面的技术，目标是取代传统的数据仓库。
上一部分 Spark SQL内核剖析—学习（一）简单介绍了Spark涉及到的几个简单技术，包括RDD编程模型、DataFrame和DataSet用户接口；描述了Spark SQL内部机制中设计的基本概念，和简单的执行过程。本部分将介绍Spark SQL 编译器 Parser的实现方式以及Spark SQL逻辑算子树生成、分析和优化流程的技术原理和实现方式。
3. Spark SQL 编译器 Parser
查询语句的翻译是数据分析的第一步，包括Spark SQL在内的Hive、Presto等大数据引擎的SQL编译模块都是基于ANTLR构建的。
antlr是指可以根据输入自动生成语法树并可视化的显示出来的开源语法分析器。ANTLR—Another Tool for Language Recognition，其前身是PCCTS，它为包括Java，C++，C#在内的语言提供了一个通过语法描述来自动构造自定义语言的识别器（recognizer），编译器（parser）和解释器（translator）的框架。
antlr的使用方法有很多资料介绍，具体的代码实现和抽象语法树还请大家自己查阅源码或阅读相应书籍（如《Spark SQL 内核剖析》），我就不再赘述了。
在这里介绍一下如果当我们面临开发新的语法支持时，首先需要改动的是ANTLR4文件（在SqlBase.g4中添加文法），重新生成词法分析器（SqlBaseLexer）、语法分析器（SqlBaseParser）和访问者类（SQLBaseVisitor接口与SQLBaseVisitor类），然后在AstBuilder等类中添加相应的访问逻辑，最后添加执行逻辑。
4. Spark SQL 逻辑计划（LogicalPlan)
在这一阶段，字符串形态的SQL语句转换为数结构形态的逻辑算子树，SQL中所包含的各种处理逻辑（过滤、剪裁等）和数据信息都会被整合在逻辑算子树的不同节点中。
4.1. 逻辑计划概述
在第二节介绍过逻辑算子树生成经过的三个阶段Unsolved LogicalPlan、Analyzed LogicalPlan和Optimized LogicalPlan。下面具体介绍一下三个阶段完成的工作。
- 由SparkSqlParser中的AstBuilder执行节点访问，将语法树中的各种Context节点转换为对应的LogicalPlan节点，从而成为一棵未解析的逻辑算子树（Unsolved LogicalPlan），此时的逻辑算子树是最初形态，不包含数据信息与列信息等。
- 由Analyzer将一系列的规则作用在Unsolved LogicalPlan上，对树上的节点绑定各种数据信息，生成解析后的逻辑算子树（Analyzed LogicalPlan）。
- 由Spark SQL中的优化器（Optimizer）将一系列优化规则作用到上一步生成的逻辑算子树中，在确保结果正确的前提下改写其中的低效结构，生成优化过的逻辑算子树（Analyzed LogicalPlan）。
4.2. LogicalPlan简介
LogicalPlan作为数据结构记录了对应逻辑算子树节点的基本信息和基本操作，包括输入输出和各种处理逻辑等。
Logical继承自QueryPlan（详见第二节），根据子节点数目可以将绝大部分的LogicalPlan分为三类，即叶子节点LeafNode、一元节点UnaryNode（仅包含一个子节点）和二元节点BinaryNode（包含两个子节点）。除此以外，还有几个子类直接继承自LogicalPlan不属于这三类，后面单独介绍。
4.2.1. UnaryNode
在LogicalPlan所有类型的节点中，UnaryNode的应用比较广泛，共34种，常用于对数据的逻辑转换操作，包括过滤等。
4.2.2. LeafNode
在LogicalPlan所有类型的节点中，UnaryNode的数目最多，共70多种。LeafNode类型的LogicalPlan节点对应数据表和命令（Command）相关的逻辑，因此这些LeafNode子类中的很大一部分都属于datasources包和command包。具体子类所属的包请读者自行阅读源码。
4.2.3. BinaryNode
BinaryNode类型的节点很少，只定义了5种，常见于数据的组合关联操作，包括Join算子等。
BinaryNode类型的逻辑算子树节点包括连接（Join）、集合操作（SetOperation）和CoGroup三种，其中SetOperation包括Except和Intersect两种算子。
4.2.4. 其他
除上述三种类型的LogicalPlan外，还有三种直接继承自LogicalPlan的逻辑算子节点，分别是ObjectProducer（用于产生只包含Object列的行数据）、Union算子（是一系列LogicalPlan的封装）和EventTimeWatermark（针对Spark Streaming中的watermark机制，一般在SQL中用的不多）。
4.3. AstBuilder机制：Unsolved LogicalPlan生成
Spark SQL首先会从ParserDriver中调用语法分析器中的singleStatement()方法构建整颗语法树，然后通过AstBuilder访问者类对语法树进行访问。
从逻辑上看，对根节点的访问操作会递归访问其子节点。这样逐层向下递归调用，直到访问某个子节点时能够构造LogicalPlan，然后传递给父节点，因此返回的结果可以转换为LogicalPlan类。
从总总体上来看，生成UnsolvedLogicalPlan的过程，可以分为以下三个步骤：
- 生成数据表对应的LogicalPlan
- 生成加入了过滤逻辑的LogicalPlan
- 生成加入列剪裁逻辑的LogicalPlan
还是以前文出现的SQL语句select name from student where age > 18为例，最终生成的Unresolved LogicalPlan涵盖了该SQL语句中的信息，首先是UnresolvedRelation叶子节点，对应未绑定元数据信息的student数据表，过滤（where）节点Filter继承自UnaryNode，最后是列剪裁（select）节点Project同样继承自UnaryNode。
上述举例比较简单，对于节点内部的操作和数据结构也没有做详细说明，仅供简单了解。对于开发人员来说，重点在于熟悉SqlBase.g4文法文件，并抓住AstBuilder访问过程中的主线。
4.4. Analyzer机制：Analyzed LogicalPlan生成
经过上一个阶段AstBuilder的处理，已经得到了Unresolved LogicalPlan。该逻辑算子树中未被解析的有UnsolvedRelation和UnresolvedAttribute两种对象，Analyzer所起的作用就是将这两种节点或表达式解析成有类型的（Typed）对象。在这个过程中，需要用到Catalog的相关信息。
在Unsolved LogicalPlan算子树的操作（如绑定、解析、优化等）中，主要方法都是基于规则（Rule）的，通过Scala语言模式匹配机制（Pattern-match）进行树结构的转换或节点改写。有了各种具体的规则后，还需要驱动程序来调用这些规则，在Catalyst中这个功能由RuleExecutor提供。
下面以前文的SQL语句为例，简述其解析过程。当遍历逻辑算子树的过程中匹配到UnresolvedRelation节点时，对于本例会直接调用lookupTableFromCatalog方法从SessionCatalog中查表（实际上该表在SQL查询的上一步中就已经创建好并与LogicalPlan类型存储在InMemoryCatalog中）。即（UnresolvedRelation ‘student’ -> Relation[age#0L, id#1L, name#2]），Relation中列后面的数字表示下标，age和id都默认设定为Long（“L”字符）。
接下来，进入第二步，执行ResolveReferences规则，主要是Filter节点的age信息从Unsolved状态变成了Analyzed状态（表示Unresolved状态的前缀字符串已经被去掉 'age -> age#0L）。
完成第二步后，会调用TypeCoercion规则集中的ImplicitTypeCasts规则，对表达式中的数据类型进行隐式转换（'Filter(age#0L > 18) -> Filter(age#0L > cast(18 as bigint)) ），
最后一步，再次执行ResolveReferences规则，经过上一步Filter节点已经处于resolved状态，因此Project节点能够完成解析（'Project['name} -> Project[name#2]）。
至此，Analyzed LogicalPlan就完全生成了。从上面的过程可以看出，逻辑算子树的生成实际上是一个迭代的过程，用户可以通过参数spark.sql.optimizer.maxIterations设置RuleExecutor迭代的轮数，默认配置为50轮，对于某些迭代较深的特殊SQL，可以适当的增加轮数。
4.5. Spark SQL 优化器 Optimizer
经过上一阶段Analyzer的处理，Analyzed LogicalPlan对于SQL的逻辑可以很好的表示。然而，在实际应用中，很多低效的写法会带来执行效率的问题，需要进一步对Analyzed LogicalPlan进行处理，得到更优的逻辑算子树。
与Analyzer类似，Optimizer的主要机制也依赖重医定义的一系列规则。Spark 2.1版本的Spark Optimizer中共实现了16个Batch，其中包含了53条优化规则，这里不一一介绍了。下面介绍一下Optimized LogicalPlan的生成过程：
还是以上文的SQL语句为例，首先执行的是Finish Analysis这个Batch中的Eliminate-SubqueryAliases优化规则，用于消除子查询别名使得Filter直接作用于Relation节点。
第二步优化将匹配Opertaor Optimizations这个Batch中的InferFilterFromConstraints优化规则，用来增加过滤条件。经过InferFilterFromConstraints规则优化之后，Filter逻辑算子树节点中多了“isnotnull(age#0L)”这个过滤条件。该过滤条件来自Filter中的约束信息，来确保筛选出来的age字段不为null。
最后一步，上述逻辑算子树会匹配Operator Optimizations这个Bitch中的ConstantFolding优化规则，对LogicalPlan中可以折叠的表达式进行静态运算直接得到结果，简化表达式。可见，Filter过滤条件中的“cast(18, bigint)”表达式经过计算成为“Literal(18, bigint)”，即输出的结果为18.
经过上述步骤，Spark SQL逻辑算子树生成、分析和优化的整个过程都执行完毕。这颗逻辑算子树将作为Spark SQL中生成物理算子树的输入，开始下一个阶段。