一、表达式求值
1、场景介绍
首先来介绍一下炎凰数据产品所关注并致力于解决的场景。
当前各大企业都面对着海量的数据，其中包括 MySQL 等关系型数据库内的结构化数据、JSON 格式存储的半结构化数据以及各类日志等非结构化数据。需要构建一款数据分析平台，能接入各种异构数据，并高效地从其中挖掘信息，从而获得有价值的洞察和启示。这就是炎凰数据产品希望解决的场景。
在处理日志数据时，通常会创建一张表，定义字段等信息。然而，这种做法并非必须。当日志数据被输入系统时，它将会直接进入一张数据表，无需经过任何 ETL 流程或数据清洗操作。之后可以通过 SQL 语句对这张数据表进行实时分析及检索。但在这个分析的过程中，如何才能了解这个数据中包含哪些字段以及这些字段如何影响搜索结果呢？
举一个简单的例子，查询 client 是 iPhone，且 IP 地址为 10.1.2.3。然而，我实际上并不清楚数据库表中是否存在诸如 IP 这类字段，因为数据在进入到系统的时候我们并没有为它创建对应的字段信息。
因此，查询会经过两层过滤，首先根据查询中已知的信息，可以迅速利用索引获取满足过滤条件 client=‘iPhone’的数据。然而，另一个 IP 信息，并没有相应的 IP 字段，需要在计算层过滤，才能得到所需要的结果。这就是本文要介绍的场景。
2、表达式求值问题
首先通过一个简单的例子来解释什么是表达式求值问题。假设一家航空公司，面临一个需求，即向满足特定条件的客户发放积分。这个特定条件为航班目的地是深圳，且航班时间少于 120 分钟。积分规则是航班票价乘以 1.8，再加上其距离除以 1000 的结果，追加客户积分。
这样一个查询在数据库中的执行流程会分为三个阶段。首先是 table scan 阶段，即系统会从硬盘读取数据至内存之中。其中会考虑一些特定的优化措施，比如下推计算、过滤器等技术。为了便于理解，此处略过这些细节。其次是执行 where 条件中的筛选操作，其核心在于剔除不符合条件的数据，仅留下满足过滤条件的部分。最后是 projection，即我们常说的投影，上述过滤和投影阶段都涉及到表达式的计算。
3、解释执行的问题
我们重点来看一下中间的过滤阶段。
当语法分析器识别到这样一种表达式时，通常情况下，会将其转换成常用的抽象语法树（Abstract Syntax Tree，简称 AST）。此过程极具简约性，除叶节点外，其他节点代表的皆为运算符。例如，逻辑运算符或用于判断的等号和不等号。而叶节点通常是一些字段（field）或者是数值型的值。
通常的过滤过程为定义一个 node 节点，前文提到的表达式可以通过此表达式树来表达。还定义了一个函数以获取该节点的具体值。解释执行过程是一个深度遍历的过程，首先判断节点操作符，再依次遍历左节点和右节点。
这种方法看起来简单直观，并且已成为大多数主流数据库普遍采用的方式，但却存在着一些问题。
首先，这种处理方式涉及到大量的虚函数调用，虚函数调用本身对于 CPU 而言属于非确定性指令。也就是说，CPU 在执行此类指令时需要进行分支预测，若存在大量的虚函数调用，则会导致分支预测失败，进而导致 CPU 的整个执行流水线频繁中断。
第二个问题是，计算过程中无法明确其类型，即在执行过程中，需频繁地对其类型进行识别，导致计算过程中产生了大量的动态类型识别需求。
第三个问题是，我们所采用的深度优先搜索（DFS）执行方式，涉及到大量的递归函数调用，也在不断地打断其计算执行的流程。
这类解决方案能被众多数据库采用，是因为在早年这并不是主要问题，那时磁盘才是系统执行的瓶颈。
然而，随着硬件设备的飞速发展，它们已不再是系统运作的瓶颈。相反，单核 CPU 计算单元的发展速度趋缓，与硬件发展并不匹配。当前的硬件系统，有更大的内存、更大的页缓存。同时，越来越多的应用场景催生出新的处理方式——流处理。因此，现在瓶颈已经不在磁盘上了，而是在 CPU 上。解释执行方式存在的缺陷也日益显露。
4、三种数据库表达式求值方式
前文中展示的一个简单的表达式里面，仅包含了基本的 int 类型。然而，在实际应用中，还会遇到更加复杂的数据结构，例如嵌套类型、list 类型、union 类型以及混合类型等等。另外，也不仅是简单的布尔操作和比较操作，还有许多用户自定义的函数。
在这样一种场景下，各数据库开始探索新的解决方案，目前主流的有三种。
第一种仍然采取解释执行的方式，但会在解释执行的过程中加入一些优化措施，比如加大向量的优化力度。
第二种方式是，有些复杂的系统依赖虚拟机来对生成的这种字节码进行优化，不过采用这一技术路线的产品相对较少。
最后一种就是本文要讨论的，JIT 即时编译（Just In Time Compilation）。对于一个抽象语法树，先将其转化为一个中间字节码，然后在执行时再转换为机器码。
上图中列出了一些主流产品所采用的方式。
二、JIT 即时编译技术
JIT 即时编译技术，又称为动态翻译，或运行时编译。其核心在于将程序在运行过程中转换为机器代码，而非在执行前预先编译为机器代码。
比方说，在编写 C++ 程序时，使用 GCC 或 C++ 进行编译，最终执行的实际上是能让机器运行的字节码。然而，JIT技术并非如此，它存在一个中间状态，以 Java 的视角更易于理解。Java 文件会被编译成（complier）进行的 .class 文件，该文件即是一种中间状态的编码，然后由 JIT 的 complier 将其翻译成机器能够认识的机器码。
即时编译技术亦存在其利弊两面。其优势在于，编译代码速度可以得到显著提升，无需一次性将代码转换为机器可执行的格式；其次，这种技术提供了解释的灵活性。然而，其劣势在于运行时需要将代码编译为机器码，这将会产生额外的开销。因此，在应用 JIT 技术时，需针对不同情况进行测试和分析，评估该技术所带来的收益是否大于其带来的开销。
数据库中的即时编译（JIT）技术的运行机制，与上述过程大致相似。主要包括以下几个阶段。
首先，SQL 解析器将语句翻译为抽象语法树；接着，表达式编译器将其转化为中间字节码；最后，JIT 编译器将其进一步转换为最终的机器码。
在此借助程序对 JIT 进行模拟，当然这与实际场景会存在一些差异。程序中有两个函数：首先是名为 generate_code 的函数，其任务是获取一个抽象语法树（AST），之后加载定义，在遍历 code 时，将其转化为一个可理解的 code 字符串。Evaluator 函数直接执行 code 字符串，即生成一个可执行的代码。
三、使用 Gandiva 的 JIT 即时编译技术加速计算
接下来介绍如何运用 JIT 技术对数据库表达式进行求值优化。我们采用了 Apache 的 Gandiva，它是建立在 LLVM 编译器框架基础上的一个表达式编译器，其核心计算适用于 Arrow 列式内存格式，代码编写采用 C++，同时也提供了 Python 与 Java 的绑定接口。
Apache Arrow 内存格式是一种列式存储格式，对于关系型数据库而言，行式存储的形式往往无法在构建计算过程中实现高效的并行处理。而列式存储，即数据在同一列内，其缓冲区内的数据将被集中存储，因此在操作数据时，能极大提升操作效率。
Gandiva 的整体执行流程如上图所示。首先，有一个表达式树；接着，Gandiva 的表达式编译器将生成一种称为 LLVM IR 的中间代码，这是一种中间表达形式；该中间代码将被传递给 Gandiva 的执行内核，整个过程处理的数据被称为 Apache 的 Arrow Record Batches，最终得到预期的输出结果。
早期的 Gandiva 比较简陋，功能性略显不足。近年来已得到了显著的提升，但仍存在一些待改进之处。目前，在 Gandiva 的表达式库中，已具备相当丰富的内容，除了基本的算术运算符以外，还拥有超过 100 个内建函数，以及布尔运算符。这些运算主要用于 project 和 filter 操作，即过滤和投影阶段，因为只有在这两个阶段会涉及到大规模的表达式求值。
上图中是一个简单的 C++ 程序示例，使用了 Gandiva 接口，最上面可以看到表达式为：(x > 2.0) and (x < 6.0)。
借助 Gandiva 的表达式，可以得到一个类似于 LLVM IR 表达式的结果。然而，在这个表达式及生成的代码中可以看到，以 @ 开头的 less_than_float32_float32 等函数形式，这些都是 Gandiva 内置的功能。因此，如果要形象地诠释 JIT 代码生成的原理，这里的内置算子与功能便如同齿轮组，当我们将表达式传达给它们时，Gandiva 就会将这些齿轮组装和运转起来，使表达式得以顺利执行。
通过上图数据可以看到，LLVM 技术的整体效率较之 Java JIT 可实现约 4 至 89 倍的提升。
我们对 Gandiva 进行了一些改进，增添了众多额外功能，比如对时间戳支持，以及针对数组类型新增了超过 20 种有关函数，同时也增强了对于高阶函数的支持，并改进了内存缓存的复用方式。
此外，还有一项极为关键的功能，就是前文中提到的 UDF 注册机制，这也是我们向 Gandiva 项目贡献的一项技术。
最后回顾一下本次分享的内容。文章第一部分探讨了什么是数据库表达式求值问题；第二部分，介绍了 JIT 即时编译技术；最后，运用 Gandiva 的 JIT 技术来加速表达式求值。
炎凰数据产品旨在解决异构数据所面临的复杂场景，欢迎大家关注、试用。
四、Q&A
Q1：Gandiva 生成的 LLVM 是标量值，有用到向量值，就是 SIMD（单指令多数据流）或者 AVX（高级向量扩展）等技术吗？
A1：这是一个非常好的问题，有些人可能会对采用 Gandiva 协助生成 LLVM IR 的代码存在一定担忧，是否能达到预期的性能要求。因为在常规执行过程中，人们通常期望拥有准确、高效的向量化支持。针对这个问题，Gandiva 已经做出了妥善的处理，生成的 LLVM-IR 中间形式均具备向量化支持，以确保所需的功能得以保留。
这些技术使得处理器能够同时处理多个数据，从而大大提高了程序的执行效率。在 Gandiva 中，LLVM IR（中间表示）被转换为可执行代码的序列，这些代码可以由 SIMD 指令集执行。因此，Gandiva 生成的 LLVM IR 序列可以在支持 SIMD 指令集的处理器上高效运行。
Q2：Gandiva 一生成出来就是 LLVM 的形式？就是向量化的执行代码？
A2：是的。它是经过优化的，实际执行的和我刚刚给大家展示的 Arrow code 是不一样的，后者代表了初始的呈现方式，然而在实际执行过程中都是有向量化支持的。
Gandiva 生成的是 LLVM 的形式，并且可以生成向量化的执行代码。Gandiva 是一个开源项目，旨在为 Apache Arrow 提供高效的数据处理功能。它使用 LLVM 作为后端，通过 LLVM 编译器将源代码编译为高效的机器码，并利用 SIMD 指令集实现向量化的执行代码，从而提高数据处理性能。因此，Gandiva 生成的代码可以在支持 SIMD 指令集的处理器上高效运行，实现高性能的数据处理。
Q3：Arrow 社区提供了 compute API 以及各种语言的高性能实现以供基于 Arrow 格式进行数据操作的向量化复用，跟 Gandiva 生成的 LLVM 的形式的向量化有什么区别和联系？
A3：这也是一个很好的问题，Arrow 有自己的一套执行框架，叫做 Arrow Acero，它对向量化的支持是非常友好的。
Arrow 社区提供的 compute API 以及各种语言的高性能实现，是基于 Arrow 格式进行数据操作的开发人员可以直接复用的工具。这些工具可以帮助开发人员更高效地处理数据，并提高程序的执行效率。
而 Gandiva 生成的 LLVM 形式，是利用 LLVM 编译器将源代码编译为高效的机器码，并利用 SIMD 指令集实现向量化的执行代码。这种生成方式可以使得 Gandiva 生成的代码在支持 SIMD 指令集的处理器上高效运行，从而提高数据处理性能。
两者的主要区别在于，Arrow 社区提供的工具主要是提供API和各种语言的高性能实现，而 Gandiva 生成的 LLVM 形式则是通过编译源代码来实现高效的数据处理。另外，Gandiva 生成的 LLVM 形式是向量化的执行代码，可以充分利用处理器的 SIMD 指令集，而 Arrow 社区提供的工具则不一定是向量化的。
所以我们的整个执行引擎在经过了很多次迭代之后完全切到了一个新式的、对流式计算有一个更好的支持的引擎，这个引擎也是基于 Arrow compute 构建的。
Q4：是否有尝试过这样使用表达式求值的方法，因为它代表的是解释执行加向量化的方式，每个算子会把 SIMD 指令解释成向量化的执行代码？
A4：是的。这部分我们也会用，我们是结合在一起用的，不是说单独或者只使用这个，而不使用就是不是以数据执行。从数据从磁盘上读取出来，就是经过过滤、投影再到给用户呈现这个结果的过程中，有很多可以优化的地方。在最开始的时候一定要确保读出来的那个数据集是最小的。然后在这个内存当中或者是在计算过程当中进行过滤时，我们可以通过 JIT 技术对它进行优化，优化是分为多个阶段，就是看你当前所面临的点哪个是最大的瓶颈。
这样使用表达式求值的方法，是解释执行加向量化的方式。每个算子会把 SIMD 指令解释成向量化的执行代码，从而充分利用处理器的并行处理能力，提高程序的执行效率。这种方法的优点是可以方便地扩展到支持向量化的指令集，如 AVX 或 SSE 等。此外，由于使用了向量化的执行代码，还可以在多核处理器上实现真正的并行计算，进一步提高程序的性能。因此，表达式求值的方法在某些情况下可以提供比传统解释执行更高效的性能。
Q5：问一个表达式相关但与JIT无关的问题，是否有一种方法可以判断某个表达式肯定为 true 或者肯定为 false。有没有这样的库或者方法？
A5：此环节往往在项目初期便已完成，若是库的问题，或许仍需根据具体情况着手实施。当前较为常用的解决方案是 Apache 旗下的 Calcite，它可用于实现 SQL 语句的语法解析。Apache Calcite 是一款开源 SQL 解析工具，能够将各类 SQL 语句解析为抽象语法树（Abstract Syntax Tree，AST），随后通过对 AST 的操纵，可将 SQL 所蕴含的算法及关系映射到具体的代码中。然而，我们并未采用此类方法，而是独立开发了自己的解决方案。在物理执行计划转化为实际代码之前，我们已经对其进行了全面优化，这个优化过程贯穿始终。
Q6：分享一下思路吧，我们在做的过程中产生困扰，比如 x＞0 and x ＜0 这样的筛选条件？
A6：对，这是一个比较典型的场景，这个可能得和具体的产品结合来看。就是（x＞0 and x ＜0）这个明显是一个 false 的场景。
当遇到 x＞0 and x ＜0 这样的筛选条件时，语法解析器会将其视为无效的语法。因为在一个逻辑表达式中，and 操作符连接的两个条件必须都是真值，即 x＞0 和 x ＜0 两个条件必须同时满足，这在逻辑上是矛盾的，因此无法解析这样的表达式。
语法解析器在解析 SQL 语句时，会根据语言的语法规则将输入的字符串转换成抽象语法树 AST（Abstract Syntax Tree）。在解析 AST 时，语法解析器会根据语法规则对 AST 进行验证，确保 AST 符合语法的约束条件。
在处理 and 操作符时，语法解析器会检查其左右两个操作数的真值性。如果两个操作数都是真值，则整个 and 表达式为真值；如果其中一个操作数为假值，则整个 and 表达式为假值。因此，当遇到 x＞0 and x ＜0 这样的表达式时，由于两个条件在逻辑上是矛盾的，因此整个表达式为假值。
在处理筛选条件时，语法解析器会根据表达式的类型和上下文信息来解析。对于比较操作符（如 ＞、＜、= 等）连接的两个表达式，语法解析器会先解析每个表达式，确定其类型和值，然后根据比较操作符的类型进行比较运算。如果比较运算的结果是真值，则该条件可以被筛选出来；如果比较运算的结果是假值，则该条件不能被筛选出来。
总之，语法解析器在解析 SQL 语句时，会根据语言的语法规则对输入的字符串进行解析和验证，确保生成的 AST 符合语法的约束条件。对于无效的语法，语法解析器会报错并提示用户进行修正。
对于这种情况可以采用的一个办法是假设法，即假设 x > 0 为真，在这个假设的基础上去判断 x < 0 是否为真，如果不成立那么两者 and 的结果一定为假。
原文地址：https://mp.weixin.qq.com/s/SUQWW2XsD8Z5I2mmh0ZPrg
