SQL编译转化为MapReduce的过程

2020-08-24 本文已影响0人眼君

我们知道，目前Hive和ODPS在底层都将SQL编译转换为MapReduce任务执行，本文以ODPS为例，总结了一般SQL编译转化为MapReduce的过程。

为了便于，按照ODPS的逻辑将这一转化过程分为两大阶段：编译和语义分析。

编译阶段，把输入SQL语句转变成抽象语法树AST；
语义分析阶段，将输入的AST转化成执行计划，在底层系统上运行。

编译阶段

在编译阶段，ODPS和Hive主要的工作就是词法分析和语法分析。

词法分析是将一条SQL语句按照定义好的词法，把输入的字符集转换成一个个Token流：

abc => Identifier(标识符)
'abc' => StringLiteral(字符串)
123 => Number(数字)
select => KeyWord(关键字)

比如，当我们输入一条SQL：

SELECT  id+100 FROM dual;

经过词法分析后，就会输出一个如下的Token流：

(KeyWord:SELECT)(Identifier:id)(KeyWord:+)(Number:100)(KeyWord:FROM)(Identifier:dual)；

语法分析会对输入Token流做前置检查，判断其是否复合语法逻辑。通过语法检查后，就会构造出一棵抽象语法树AST。

抽象语法树以树形结构表示Token流，树上每个节点都是一个Token，通过树结构的语法，前面的Token流可以生成类似下图的AST：

SQL编译的过程非常复杂，一般是通过开源工具Antlr实现SQL的词法和语法解析。Antlr是一种语言识别工具，可以用来构建领域语言。Anltr完成了词法分析、语法分析、语义分析、中间代码生成过程。

逻辑分析指分析SQL要做哪些操作，SQL语句基本可以分解为如下的操作：

序号表示执行的顺序，而这些操作可以抽象出一些逻辑算子，这些算子的功能是单一的、不可再分的：

一个逻辑查询计划就是由这些算子组成的有向无环图，它描述的数据流向。
逻辑分析基本上是纯代数的分析过程，它和底层的分布式环境无关，下面重点介绍其中几点：表达式分析、逻辑查询计划、子查询和逻辑优化。

表达式的解析和计算贯穿SQL解析的整个过程，主要包含以下几个方面：

(t1.a>10 AND t2.b<100) OR t3.c>10

会变换成：

(t1.a>10 OR t3.c>10) AND (t2.b<100 OR t3.c>10)

这步操作主要是便于后续的SQL优化。

在上一步的基础上，生成逻辑查询计划就变得相对容易，按照SQL执行顺序遍历AST树，根据操作类型生成相应算子，对SQL语句中的表达式完成表达式分析。

生成逻辑查询计划后，ODPS SQL会先对该计划进行一次优化，避免冗余计算，主要包含以下几方面：