我们知道，目前Hive和ODPS在底层都将SQL编译转换为MapReduce任务执行，本文以ODPS为例，总结了一般SQL编译转化为MapReduce的过程。
为了便于，按照ODPS的逻辑将这一转化过程分为两大阶段：编译和语义分析。
编译阶段，把输入SQL语句转变成抽象语法树AST；
语义分析阶段，将输入的AST转化成执行计划，在底层系统上运行。
编译阶段
在编译阶段，ODPS和Hive主要的工作就是词法分析和语法分析。
1、词法分析
词法分析是将一条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)；
2、语法分析
语法分析会对输入Token流做前置检查，判断其是否复合语法逻辑。通过语法检查后，就会构造出一棵抽象语法树AST。
抽象语法树AST Tree
抽象语法树以树形结构表示Token流，树上每个节点都是一个Token，通过树结构的语法，前面的Token流可以生成类似下图的AST：
Antlr
SQL编译的过程非常复杂，一般是通过开源工具Antlr实现SQL的词法和语法解析。Antlr是一种语言识别工具，可以用来构建领域语言。Anltr完成了词法分析、语法分析、语义分析、中间代码生成过程。
语义分析阶段
3、逻辑分析
逻辑分析指分析SQL要做哪些操作，SQL语句基本可以分解为如下的操作：
序号表示执行的顺序，而这些操作可以抽象出一些逻辑算子，这些算子的功能是单一的、不可再分的：
一个逻辑查询计划就是由这些算子组成的有向无环图，它描述的数据流向。
逻辑分析基本上是纯代数的分析过程，它和底层的分布式环境无关，下面重点介绍其中几点：表达式分析、逻辑查询计划、子查询和逻辑优化。
表达式分析
表达式的解析和计算贯穿SQL解析的整个过程，主要包含以下几个方面：
- 类型推导，指识别SQL中的常量类型。
- 隐式类型转换，指当出现类型不匹配时，调用函数改变输入参数的类型。
- 布尔表达式分析，基于布尔代数，将输入的布尔表达式变换成“最简合取范式”，即把and、or组成的布尔表达式统一变换为由and连接的最简形式，比如：
(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优化。
- case when表达式分析，case when在计算机中一般被抽象成一组三元函数。
逻辑查询计划
在上一步的基础上，生成逻辑查询计划就变得相对容易，按照SQL执行顺序遍历AST树，根据操作类型生成相应算子，对SQL语句中的表达式完成表达式分析。
逻辑优化
生成逻辑查询计划后，ODPS SQL会先对该计划进行一次优化，避免冗余计算，主要包含以下几方面：
- 常量表达式的计算，例如：常量计算"1+2", 会先将结果算出，在查询计划中替换掉原表达式，防止多次冗余计算"1+2"；
- 列裁剪，生成查询计划时，默认会读出全表的所有列，但实际上用户只需要计算其中几列，这时通过列裁剪可以剪掉不必要的列。
- 谓词下推，可以考虑将WHERE中的谓词提前到JOIN之前运算，从而减少JOIN的数据量。
网友评论