概述
生逢DT时代，为了能从价值密度低下的海量数据中淘出真金，人们开发了各种各样的计算数据的利器。自Google陆续发布后来被誉为“三架马车”的三篇著名的论文之后，大数据技术逐步进入了高速发展期。放眼业界，这些年计算技术层出不穷、百花齐放。计算引擎从Hadoop MapReduce、Apache Hive发展至如今如日中天的Apache Spark、Apache Flink。计算范式从批处理、图计算等发展到实时计算、流式计算。每一种计算思想或技术实现都在特定的时代和场景下解决了实际的问题。
本系列文章将通过以Apache Drill为原型，浅析分布式SQL引擎的技术与实现。Apache Drill是一款采用Java编写的老牌MPP引擎，适用于大数据的交互式分析场景，它采用了Share Nothing的分布式无主架构，用户可以通过编写标准SQL，并借助其开放的插件接入能力来查询存储于各种异构数据源的数据。作为一款成熟的MPP，Drill汇集了多项优秀的技术特性，从而打造了其高性能的计算能力。我们将对其进行一一剖析，从而去看看一款高性能分布式SQL引擎是如何炼成的。
本系列文章将暂定以下几个主题，每篇都将以理论结合Drill的代码实现来讲解：
《浅析查询优化器》
《分布式运行框架》
《向量化的列式内存结构》
《运行时探秘》
《基于列式存储的查询优化》
运行时探秘(上)
背景
运行时（Runtime）听上去更像是一个时间状语，而不是事物一个名称。作为类比，我们都知道Java平台有JRE，即用于运行Java程序的运行时环境。SQL查询引擎也类似，我们需要一套环境来运行SQL查询的物理执行计划。这套关键的环境或者说机制，甚至是组件，就是运行时。
为了不一叶障目。我们先简单介绍一下一个常规SQL查询引擎所拥有的几个关键组件以及它们之间的承接关系，并看看“运行时”是在哪个环节起作用的。
SQL解析器
当用户通过客户端向服务端提交查询后，SQL首先会来到SQL解析器，SQL解析器负责对这条文本形式的SQL进行词法分析、语法分析。通常我们会通过成熟的“解析器生成器”来生成面向特定语法的解析器的核心代码，而不会从头开始手写整个SQL解析器，因为这并不是一件简单的事情，也没必要这么做。比较常见的“解析器生成器”有Antlr和JavaCC，而后者主要面向Java用户。由于Drill SQL部分的相关功能重度依赖于一个独立的项目Apache Calcite（这部分内容详见《浅析查询优化器》），而Calcite使用的便是JavaCC。为了能通过JavaCC生成解析器，用户需要按照JavaCC的规范编写特定语法的文法文件，有兴趣的同学可以参考JavaCC官网。经过SQL解析器的处理后，SQL文本被转化成了一棵由SqlNode组成的抽象语法树（AST）。
语义分析器
抽象语法树是完全基于文法结构与对文本内容解析生成的，但是从语义的角度来看这样的组合未必是合理的。举个简单的例子，我们可以用主谓宾这样的结构来分解句子：”I play basketball“这个句子符合主谓宾结构的，而”I eat basketball“这个句子也符合，他们都通过了语法分析及检查。但是从语义的角度看，后者明显是不合常理的。这种“不合常理”就需要语义分析器来发现，而对于合理的节点则需要进一步赋予其更多的有效信息。在对SQL的语义分析中，我们主要会进行语法树节点的检查和重写。举个例子，检查部分会去判断SQL中引用的表名、列名、函数名是否存在、有效。对某些表达式进行有效性验证，比如“+“两边的数据类型是否是可互加的。传给函数的入参的类型列表是否能匹配上该函数的签名。对字面量的值进行范围检查，以防止出现非法值或越界。同时，这个过程还会做一些节点重写，比如为某些场景做一些节点的隐式类型转换，遇到视图节点时会将其展开，目的是能让这棵语法树变得更加接地气，成为一棵具体语法树。该具体语法树实质上是一个查询路径的关系代数表示，我们将其叶子节点称之为关系；而内部节点就是对这些关系的运算符，我们通常称之为逻辑算子。
计划器（优化器）
正如上文所述，语义分析最终的产物是一个查询路径的关系代数表示，这其实已经是一个初步的逻辑执行计划了。而基于关系代数的等价转换，我们可以获得很多种查询路径。那么如何才能找到成本较低的查询路径呢。这就是计划器的第一项优化职责，即逻辑执行计划优化。这一阶段，我们往往会基于一些特定的经验和直观的感受来编写规则，并采用启发式策略来匹配和应用这些规则，初步逻辑执行计划在这些规则的应用下得到一定程度的优化，从而产出了较优的逻辑执行计划。接着，我们需要结合实际的执行引擎和系统实现来将逻辑执行计划转换成可以在特定运行时环境运行的物理执行计划。此时我们就需要为Join算子选择合适的Join算法实现，并为具有分布式特质的实现加入跨机器的Exchange算子等。在这个环节中，我们可以结合统计信息，来对所有具体的物理操作进行成本估算，从而来进一步对物理执行计划进行优化，这就是计划器的第二项优化职责，即物理执行计划优化。Drill的这部分实现重度依赖于Calcite的CBO能力，并为此提供了符合Calcite框架的大量规则。从而确保最终能在合理的时间内尽可能缩小搜索空间，产出较优的物理执行计划（这部分内容详见《浅析查询优化器》）。
运行时（Runtime）
当我们拿到物理执行计划之后，便可以开始去真正执行计算作业了。运行时是用于完成物理执行计划执行工作的组件及环境，我们需要一套环境来运行上述步骤生成的物理执行计划。那么本文讨论的主角就此上场了。
说到这里，SQL查询引擎的关键组件及其脉络已经介绍完了，那么我们来看看传统运行时的一些问题以及对应的改善手段。
Volcano Style之殇
先来看一下的查询
SELECT a.stat_date 日期
,video_lay 视频位置
,video_cnt_1d 当日发布视频数
,CONCAT(a.stat_date,'-',video_lay)
,LENGTH(CONCAT(a.stat_date,'-',video_lay))
FROM (
SELECT *
FROM tbbi.ads_tb_channel_video_1d
WHERE ds >= '20171215'
AND ds <= '20171229'
) a
LEFT OUTER JOIN (
SELECT *
FROM tbbi.ads_tb_channel_all_pv_1d
WHERE ds >= '20171215'
AND ds <= '20171229'
) b
ON a.ds = b.ds
AND a.video_lay = b.lay
LIMIT 10经过上述几个关键组件的前赴后继之后，“运行时”得到了如下的物理执行计划
图中的Scan、Project以及HashJoin等可视为物理算子，每个算子都包含有实现了数据操作逻辑的代码，这些算子组成了的DAG图，数据将从最底下的叶子节点进入，并向上流经有向边上的每个节点，进而汇聚，并最终从最上层的根节点流出，然后返回给查询者。那么传统方式是如何执行该物理执行计划的呢？答案很简单，是迭代模型。在这种模型中，每个算子都会提供一个比如叫“next”的方法。每条记录（即Tuple）流经算子的时候都需要调用一次该算子的next方法。 根据SQL的不同，执行计划可以任意合理的方式将各类算子装配在一起，执行会以算子为界，轮到某个算子时会反复通过调用next从上游拉取数据，同时完成相应的处理并进行物化操作（materialization），以供后续的算子拉取。下游算子再向该上游反复调用next拉取数据进行计算。我们将这种方式称为Volcano Style。
Volcano Style简单明了，也非常灵活。但是在当代CPU的硬件环境与大数据场景下，性能表现却差强人意。究其原因。主要有如下几点：
- 首先，next函数通常是一次虚函数调用。在Java中，为了支持多态，所有的非静态方法与非final方法本质上都是动态绑定的虚函数，在JVM层依赖于invokevirtual和invokeinterface这两个方法指令。虚函数调用与普通函数的调用的区别在于后者是一次直接调用，直接调用的跳转地址在编译时是确定的。而虚函数调用是一次间接调用，需要在运行时才能从虚表获取地址再跳转。所以，虚函数首先会多一次寻址的时间开销；其次，虚函数是无法在编译期内联优化的，所以运行时会实实在在多一次函数调用开销。对于Java来说，方法调用会在运行时会多一次栈桢入栈出栈操作；最后，也是最重要的一点，虚函数的间接调用本身会导致分支预测。据统计，间接分支预测的失败率在25%左右。一旦分支预测失败，将会导致流水线被冲刷，进而需要重新取指、译码，对性能造成严重的影响。
- 其次，这种风格对代码和数据的局部性并不友好。它不能很好的利用CPU的缓存机制。如下图所示：
由于CPU的各级Cache都是从下一级存储按特定长度单位对齐取数的，且取到的数据也是连续的，所以每次取到的连续的数据如果能被集中充分处理，将会得到最大的收益。但next调用每次只处理一条记录，而且Volcano Style是个拉取的模型，即下游什么时候拉取并不随当前算子控制，所以当前算子刚刚cache的数据在只取用了一部分就很有可能马上被其他算子的next调用获取的数据给冲掉(evict)了。而当前算子再次调用next时又会冲掉别人的cache，重新将之前被人冲掉的未处理的数据从较慢的存储中读取来给CPU处理。这样的周而复始，造成了不必要的开销。而且拉取模型也要求严格以算子为界进行物化，其实很多物化点是可以避免的。
- 最后，大数据时代的体量放大了1和2的问题。如果数据量不多，那么1和2的问题并不明显。但是在大数据时代，我们需要处理的数据量从百万到数十亿是家常便饭。每条记录都会经历next的调用，所以性能问题将被放大百万倍、数十亿倍以至更甚。从而警醒我们不容忽视。
那么有哪些手段可以来改善上述的问题的呢？
批量处理
之前提到，在Volcano Style中，next方法是一次处理一条记录，而我们知道next的调用开销是挺高的，而一次处理一条记录对于代码和数据的局部性都不是很友好。所以，如过能next方法改善为例如nextBatch方法，让每次能在算子里一次性处理的数据与CPU的Cache Line对齐，那将在局部性这块上得到最大化的收益。当然，batch不宜过大，正好能放入Cache Line为佳。
改拉为推，Pipeline执行
在Volcano Style中，查询表达是由算子组成的，我们的关注点都在算子上，也就是说，算子是数据处理的分界线。上游算子完成处理后会对数据进行物化，下游算子则通过next从上游算子的物化区获取数据。那么这里涉及到之前提到的两个问题，首先，不必要的物化会造成性能浪费，很多算子之间的衔接是不需要物化的。所以能找到不可避免的物化点，以这些物化点为界来分隔处理阶段，每个阶段之内的算子采用Pipeline的方式来处理数据，它们之间的数据传递不需进行物化。并且能在一个批的量的范围内进行紧凑循环处理，那么我们能长时间保持寄存器里的数据不被evict，并得到最集中的处理。其次，拉取模型容易破坏对已Cache数据的集中处理，所以可以改为推模型，让当前Pipeline能控制CPU寄存器以及Cache数据的生命周期，防止被意外evict。
向量化处理
通过采用基于向量的列式内存数据结构与列式执行(这部分详见《向量化的列式内存结构》)，最大化的利用当代CPU基于深度流水线(deep-pipelined)设计与SIMD指令集的向量化计算能力。
代码生成
当我们提到“代码生成”的时候到底是在讲什么呢？通常我们是先编写代码，再编译，最后运行。而对于本文所提到的“代码生成”的特殊之处在于它发生在“运行时”。当然，这里的“运行时”只是相对于SQL编译成物理执行计划这一“编译”而言。为什么物理执行计划这个“编译”的产物还需要再编译一次？当然是为了解决上述提到的一些问题，由于我们“首次“编译时很多信息都还不知道，比如我们最终会使用哪些物理算子，它们是如何组合的，更有甚者例如Apache Drill，它的一项优势是"schema less"，即不需要用户提前指定数据模式，那么直到运行时读到第一条记录前，它甚至不知道记录的模式和类型，所以无法直接编译成我们所能执行最优的代码。如果不重新编译这个物理执行计划，我们将会面临前文提到的”虚函数“的额外开销，以及Java中的”反射“开销等等。我们来看一个业界的用例。
Impala with LLVM
首先来看一个经典的编译器结构：
这种三段式的设计非常流行，也很经典，C编译器就是这种架构的。它分为前端、优化器和后端。编译器前端负责将特定语言的源代码编译成抽象语法树，并进而转换成优化器能够接受的一种表示，我们暂且将这种表示称为中间代码，而优化器会基于中间代码对其进行进一步优化，并产出优化后的中间代码。而编译器后端会将这种中间代码映射成特定平台的目标代码，也就是基于某种指令集的机器码。正因为这种三段式架构的设计，我们得以复用优化器的同时，接入支持不同语言的前端和支持生成各种指令集的后端。
从而形成了上述的结构，而我们将这种优化器支持的中间表示简称之为IR(Intermediate Representation)。
LLVM((Low Level Virtual Machine)正是一种实现了上述架构的编译套件。
而Impala（一款开源的由C++实现的MPP引擎）官方表示，通过在运行时采用LLVM来进行代码生成，让它的性能提升了5倍。由此可见，花费一点编译开销来换取大数据量的快速查询是一门”赚“的生意。
那么运行时代码生成是如何提升性能的呢？主要是以下几项技术：
- 减少分支
我们生成的物理执行计划中会存在一些类似if或switch这样的判断逻辑。而在运行时，条件的内容已经可知，我们可以直接去掉不必要的分支。另一方面，运行时可以了解到循环代码的具体循环次数，从而可以将循环展开，同样去除了分支判断逻辑。通过类似这样的优化可以消除分支预测，从而极大的提升性能。 - 减少加载
对CPU来说，从内存加载数据是一个非常昂贵的操作，因为它会阻塞流水线的执行。但是在运行时，我们可以判断某些值在函数的多次调用中是不变一致的，那么我们不必每次从主存去加载该值，可以在代码生成时直接用静态值替代变量，从而省去加载开销。 - 将虚函数内联
在运行时，我们已经知道虚函数的地址。所以我们可以直接采用特定函数来替代虚函数调用，从而让编译器能对此进行内联优化。
未完待续
本文主要在理论层面浅析了”运行时“在整个SQL查询引擎中的作用与地位，然后描述了传统迭代方式Volcano Style的问题以及常见的优化方式。下一篇《运行时探秘(下)》我们将从源码入手，从具体实现的角度来看看一个Java版本的运行时是如何炼成的。
参考文献
《Efficiently Compiling Efficient Query Plans for Modern Hardware》
《Runtime Code Generation in Cloudera Impala》
《The Architecture Of Open Source Applications》