SQL on Hadoop技术综述
一、系统架构
runtime framework v.s. mpp
在SQL on Hadoop系统中，有两种架构：
1、一种是基于某个运行时框架来构建查询引擎，典型案例是Hive；
2、另一种是仿照过去关系数据库的MPP架构，就是参考过去的MPP数据库架构打造一个专门的系统，于是就有了Impala，Presto等等。
前者现有运行时框架，然后套上sql层，后者则是从头打造一个一体化的查询引擎。
对于SQL on Hadoop系统很重要的一个评价指标就是：快。
DAG v.s. MR：最主要的优势，中间结果不写磁盘（除非内存不够），一气呵成。
•流水线计算：上游stage一出结果马上推送或者拉到下一个stage处理，比如多表join时前两个表有结果直接给第三个表，不像MR要等两个表完全join完再给第三个表join。
•高效的IO：本地查询没有多余的消耗，充分利用磁盘。这个后面细说。
•线程级别的并发：相比之下MR每个task要启动JVM，本身就有很大延迟，占用资源也多。
MPP模式也有其劣势：
•一个是扩展性不是很高，这在关系数据库时代就已经有过结论；
•另一个是容错性差，对于Impala来说一旦运行过程中出点问题，整个查询就挂了。
但是，经过不断的发展，Hive也能跑在DAG框架上了，不仅有Tez，还有Spark。上面提到的一些劣势，其实大都也可以在计算模型中解决。基于Spark的Spark SQL完全不逊色于Presto，基于Tez的Hive也不算很差，至少在并发模式下能超过Presto，足见MPP模式并不是绝对占上风的。
二、核心组件
不管是上面提到的那种架构，一个SQL on Hadoop系统一般都会有一些通用的核心组件，这些组件根据设计者的考虑放在不同的节点角色中，在物理上节点都按照master/worker的方式去做
三、执行计划
编译流程
从SQL到执行计划，大致分为5步。
•第一步将SQL转换成抽象语法树AST。这一步一般都有第三方工具库可以完成，比如antlr。
•第二步对AST进行语义分析，比如表是否存在，字段是否存在，SQL语义是否有误（比如select中被判定为聚合的字段在group by中有没有出现）。
•第三步生成逻辑执行计划,这是一个由逻辑操作符组成的DAG。比如对于Hive来说扫表会产生TableScanOperator，聚合会产生GroupByOperator。对于类MPP系统来说，情况稍微有点不同。逻辑操作符的种类还是差不多，但是会先生成单机版本，然后生成多机版本。多机版本主要是把aggregate，join，还有top n这几个操作并行化，比如aggregate会分成类似MR那样的本地aggregate，shuffle和全局aggregate三步。
•第四步做逻辑执行计划做优化。
•第五步把逻辑执行计划转换成可以在机器上运行的物理计划。
四、优化器
关于执行计划的优化，虽然不一定是整个编译流程中最难的部分，但却是最有看点的部分，而且目前还在不断发展中。Spark系之所以放弃Shark另起炉灶做Spark SQL，很大一部分原因是想自己做优化策略，避免受Hive的限制。早期在Hive中只有一些简单的规则优化，比如谓词下推（把过滤条件尽可能的放在table scan之后就完成），操作合并（连续的filter用and合并成一个operator，连续的projection也可以合并）。后来逐渐增加了一些略复杂的规则，比如相同key的join + group by合并为1个MR，还有star schema join。
但是，基于规则的优化（RBO）不能解决所有问题。在关系数据库中早有另一种优化方式，也就是基于代价的优化CBO。CBO通过收集表的数据信息（比如字段的基数，数据分布直方图等等）来对一些问题作出解答，其中最主要的问题就是确定多表join的顺序。CBO通过搜索join顺序的所有解空间（表太多的情况下可以用有限深度的贪婪算法），并且算出对应的代价，可以找到最好的顺序。这些都已经在关系数据库中得到了实践。
五、存储格式
对于分析类型的workload来说，最好的存储格式自然是列存储，这已经在关系数据库时代得到了证明。目前hadoop生态中有两大列存储格式，一个是由Hortonworks和Microsoft开发的ORCFile，另一个是由Cloudera和Twitter开发的Parquet。
ORCFile顾名思义，是在RCFile的基础之上改造的。RCFile虽然号称列存储，但是只是“按列存储”而已，将数据先划分成row group，然后row group内部按照列进行存储。
ORCFile已经弥补了这些特性，包括：
•块过滤与块统计：每一列按照固定行数或大小进一步切分，对于切分出来的每一个数据单元，预先计算好这些单元的min/max/sum/count/null值，min/max用于在过滤数据的时候直接跳过数据单元，而所有这些统计值则可以在做聚合操作的时候直接采用，而不必解开这个数据单元做进一步的计算。
•更高效的编码方式：RCFile中没有标注每一列的类型，事实上当知道数据类型时，可以采取特定的编码方式，本身就能很大程度上进行数据的压缩。常见的针对列存储的编码方式有RLE（大量重复数据），字典（字符串），位图（数字且基数不大），级差（排序过的数据，比如日志中用户访问时间）等等。
Parquet的设计原理跟ORC类似，不过它有两个特点：
•通用性：相比ORCFile专门给Hive使用而言，Parquet不仅仅是给Impala使用，还可以给其他查询工具使用，如Hive、Pig，进一步还能对接avro/thrift/pb等序列化格式。
•基于Dremel思想的嵌套格式存储：关系数据库设计模式中反对存储复杂格式（违反第一范式），但是现在的大数据计算不仅出现了这种需求（半结构化数据），也能够高效的实现存储和查询效率，在语法上也有相应的支持（各种UDF，Hive的lateral view等）。Google Dremel就在实现层面做出了范例，Parquet则完全仿照了Dremel。
多数据源查询：Presto支持从mysql，cassandra，甚至kafka中去读取数据，这就大大减少了数据整合时间，不需要放到HDFS里才能查询。Impala和Hive也支持查询hbase。
近似查询：count distinct（基数估计）一直是sql性能杀手之一，如果能接受一定误差的话可以采用近似算法。Impala中已经实现了近似算法（ndv），Presto则是请blinkDB合作完成。两者都是采用了HyperLogLog Counting。
