ast
语法分析是编译过程的一个逻辑阶段； 此阶段的任务是在词法分析的基础上将单词序列组合成各类语法短语、表达式等。 语法分析程序一般称之为Parser。
SQL解析的本质是语言转换，就是把文本代码转换成计算机语言能描述的数据结构。
常用SQL编译工具介绍
lexical compiler ，是一个词法分析器（scanner）的生成工具， 使用正则表达式来描述各个词法单元。
Yacc 是一个经典的生成语法分析器的工具，采用自下而上（LALR）语法分析方法。 可以将任何一种编程语言的所有语法翻译成针对此种语言的 Yacc 语法解析器。但是其生成的代码一般都比较晦涩难懂。
Lex 和Yacc 可以结合使用。
ANTLR是采用java编写的，基于自顶向下的递归下降 LL 算法实现的语法解析器生成器。
SQL解析的结果是生成抽象语法树 AST（abstract syntax tree）。
3.逻辑计划
AST会被解析成一个逻辑计划，包含用户书写的数据处理逻辑及顺序。
逻辑处理顺序，指的是一条SQL语句应该如何执行，每一个关键字、子句部分在什么时刻执行。
logical_plan
需要注意的是，SQL的执行顺序，并不是按书写顺序从上到下，从左到右执行的。
下面列出了一个标准SQL的实际数据处理顺序：
FROM <左表的名字>
ON <join的条件>
<join的类型> <右表的名字>
WHERE <where的条件>
GROUP BY <group by的字段>
HAVING <having的条件>
SELECT
DISTINCT <要查询的字段>
ORDER BY <order by的条件>
LIMIT <limit的数字>
可以看出，操作的顺序是先选定需要操作的表，之后使用on和where条件过滤，然后按业务进行分区重组，最后进行排序操作。
4.RBO 和 CBO优化
由于用户的能力不同，同一个业务书写出来的SQL脚本可能千差万别，这样会导致逻辑计划可能不是最优的执行路径。所以逻辑计划需要被优化。
数据库一般有两种查询优化器：
RBO: Rule-Based Optimization 基于规则的优化器
该优化器按照硬编码在数据库中的一系列规则来决定SQL的执行计划。比如查询时索引的优先级大于全表扫描属于RBO优化，谓词下推也属于RBO优化。
CBO: Cost-Based Optimization 基于代价的优化器
该优化器通过根据优化规则对关系表达式进行转换，生成多个执行计划，然后CBO会通过根据统计信息(Statistics)和代价模型(Cost Model)计算各种可能“执行计划”的“代价”， 即COST，从中选用COST最低的执行方案，作为实际运行方案。
统计信息包括表的数据量、执行路径的IO、网络IO、CPU的使用情况。 对表做预分析，就是预先统计表的分布和数据量，属于CBO优化。
5.执行计划
逻辑计划经过RBO和CBO优化之后，就会生成执行计划。
分布式数据库中，执行计划是可以分布式并行执行的，其任务之间的关系可以看作是一个有向无环图DAG。
exec_plan
上图中的执行计划被拆分成了4个子任务，每个任务都可以被提交到一个或者多个节点上执行。
6.权限控制
用户在提交SQL时，是附带了个人身份认证信息的，权限控制会校验当前用户是否有SQL中对应DDL、DCL、DML等权限。
7.资源调度
权限审核通过后，任务将被发送到各个执行节点的任务队列上。每个任务需要先申请相应的CPU和内存资源，准备就绪后，才能真正的执行。
在大数据体量下，CPU和内存资源的消耗是非常巨大的，这也是为什么大数据量的并发查询，有时慢的像蜗牛一样。
8.分布式任务执行
前面说过分布式任务之间的关系可以看作是一个有向无环图DAG，每一个子任务完成后，都会将结果作为下一个任务的输入继续执行，直到完成最顶层的任务。
一般来说，最底层的任务(带有TableScan算子)都属于IO密集型的，需要从磁盘中读取所需的数据，中间任务(带有Filter或Join算子)是需要CPU进行判断或者做笛卡尔积操作等大量计算，而一些排序操作则需要大量的内存参与。
9.返回最终结果
待所有的任务完成并汇总到根节点时，服务器便将SQL的执行结果返回给客户端。
以上为剖析一个SQL的解析及执行过程，「分布式技术专题」是国产数据库Hubble团队精心整编，专题会持续更新，欢迎大家保持关注。
