一、表達(dá)式求值

1、場景介紹

首先來介紹一下炎凰數(shù)據(jù)產(chǎn)品所關(guān)注并致力于解決的場景。

當(dāng)前各大企業(yè)都面對著海量的數(shù)據(jù)，其中包括 MySQL 等關(guān)系型數(shù)據(jù)庫內(nèi)的結(jié)構(gòu)化數(shù)據(jù)、JSON 格式存儲的半結(jié)構(gòu)化數(shù)據(jù)以及各類日志等非結(jié)構(gòu)化數(shù)據(jù)。需要構(gòu)建一款數(shù)據(jù)分析平臺，能接入各種異構(gòu)數(shù)據(jù)，并高效地從其中挖掘信息，從而獲得有價(jià)值的洞察和啟示。這就是炎凰數(shù)據(jù)產(chǎn)品希望解決的場景。

在處理日志數(shù)據(jù)時(shí)，通常會創(chuàng)建一張表，定義字段等信息。然而，這種做法并非必須。當(dāng)日志數(shù)據(jù)被輸入系統(tǒng)時(shí)，它將會直接進(jìn)入一張數(shù)據(jù)表，無需經(jīng)過任何 ETL 流程或數(shù)據(jù)清洗操作。之后可以通過 SQL 語句對這張數(shù)據(jù)表進(jìn)行實(shí)時(shí)分析及檢索。但在這個分析的過程中，如何才能了解這個數(shù)據(jù)中包含哪些字段以及這些字段如何影響搜索結(jié)果呢？

舉一個簡單的例子，查詢 client 是 iPhone，且 IP 地址為 10.1.2.3。然而，我實(shí)際上并不清楚數(shù)據(jù)庫表中是否存在諸如 IP 這類字段，因?yàn)閿?shù)據(jù)在進(jìn)入到系統(tǒng)的時(shí)候我們并沒有為它創(chuàng)建對應(yīng)的字段信息。

因此，查詢會經(jīng)過兩層過濾，首先根據(jù)查詢中已知的信息，可以迅速利用索引獲取滿足過濾條件 client=‘iPhone’的數(shù)據(jù)。然而，另一個 IP 信息，并沒有相應(yīng)的 IP 字段，需要在計(jì)算層過濾，才能得到所需要的結(jié)果。這就是本文要介紹的場景。

2、表達(dá)式求值問題

首先通過一個簡單的例子來解釋什么是表達(dá)式求值問題。假設(shè)一家航空公司，面臨一個需求，即向滿足特定條件的客戶發(fā)放積分。這個特定條件為航班目的地是深圳，且航班時(shí)間少于 120 分鐘。積分規(guī)則是航班票價(jià)乘以 1.8，再加上其距離除以 1000 的結(jié)果，追加客戶積分。

這樣一個查詢在數(shù)據(jù)庫中的執(zhí)行流程會分為三個階段。首先是 table scan 階段，即系統(tǒng)會從硬盤讀取數(shù)據(jù)至內(nèi)存之中。其中會考慮一些特定的優(yōu)化措施，比如下推計(jì)算、過濾器等技術(shù)。為了便于理解，此處略過這些細(xì)節(jié)。其次是執(zhí)行 where 條件中的篩選操作，其核心在于剔除不符合條件的數(shù)據(jù)，僅留下滿足過濾條件的部分。最后是 projection，即我們常說的投影，上述過濾和投影階段都涉及到表達(dá)式的計(jì)算。

3、解釋執(zhí)行的問題

我們重點(diǎn)來看一下中間的過濾階段。

當(dāng)語法分析器識別到這樣一種表達(dá)式時(shí)，通常情況下，會將其轉(zhuǎn)換成常用的抽象語法樹（Abstract Syntax Tree，簡稱 AST）。此過程極具簡約性，除葉節(jié)點(diǎn)外，其他節(jié)點(diǎn)代表的皆為運(yùn)算符。例如，邏輯運(yùn)算符或用于判斷的等號和不等號。而葉節(jié)點(diǎn)通常是一些字段（field）或者是數(shù)值型的值。

通常的過濾過程為定義一個 node 節(jié)點(diǎn)，前文提到的表達(dá)式可以通過此表達(dá)式樹來表達(dá)。還定義了一個函數(shù)以獲取該節(jié)點(diǎn)的具體值。解釋執(zhí)行過程是一個深度遍歷的過程，首先判斷節(jié)點(diǎn)操作符，再依次遍歷左節(jié)點(diǎn)和右節(jié)點(diǎn)。

這種方法看起來簡單直觀，并且已成為大多數(shù)主流數(shù)據(jù)庫普遍采用的方式，但卻存在著一些問題。

首先，這種處理方式涉及到大量的虛函數(shù)調(diào)用，虛函數(shù)調(diào)用本身對于 CPU 而言屬于非確定性指令。也就是說，CPU 在執(zhí)行此類指令時(shí)需要進(jìn)行分支預(yù)測，若存在大量的虛函數(shù)調(diào)用，則會導(dǎo)致分支預(yù)測失敗，進(jìn)而導(dǎo)致 CPU 的整個執(zhí)行流水線頻繁中斷。

第二個問題是，計(jì)算過程中無法明確其類型，即在執(zhí)行過程中，需頻繁地對其類型進(jìn)行識別，導(dǎo)致計(jì)算過程中產(chǎn)生了大量的動態(tài)類型識別需求。

第三個問題是，我們所采用的深度優(yōu)先搜索（DFS）執(zhí)行方式，涉及到大量的遞歸函數(shù)調(diào)用，也在不斷地打斷其計(jì)算執(zhí)行的流程。

這類解決方案能被眾多數(shù)據(jù)庫采用，是因?yàn)樵谠缒赀@并不是主要問題，那時(shí)磁盤才是系統(tǒng)執(zhí)行的瓶頸。

然而，隨著硬件設(shè)備的飛速發(fā)展，它們已不再是系統(tǒng)運(yùn)作的瓶頸。相反，單核 CPU 計(jì)算單元的發(fā)展速度趨緩，與硬件發(fā)展并不匹配。當(dāng)前的硬件系統(tǒng)，有更大的內(nèi)存、更大的頁緩存。同時(shí)，越來越多的應(yīng)用場景催生出新的處理方式——流處理。因此，現(xiàn)在瓶頸已經(jīng)不在磁盤上了，而是在 CPU 上。解釋執(zhí)行方式存在的缺陷也日益顯露。

4、三種數(shù)據(jù)庫表達(dá)式求值方式

前文中展示的一個簡單的表達(dá)式里面，僅包含了基本的 int 類型。然而，在實(shí)際應(yīng)用中，還會遇到更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，例如嵌套類型、list 類型、union 類型以及混合類型等等。另外，也不僅是簡單的布爾操作和比較操作，還有許多用戶自定義的函數(shù)。

在這樣一種場景下，各數(shù)據(jù)庫開始探索新的解決方案，目前主流的有三種。

第一種仍然采取解釋執(zhí)行的方式，但會在解釋執(zhí)行的過程中加入一些優(yōu)化措施，比如加大向量的優(yōu)化力度。

第二種方式是，有些復(fù)雜的系統(tǒng)依賴虛擬機(jī)來對生成的這種字節(jié)碼進(jìn)行優(yōu)化，不過采用這一技術(shù)路線的產(chǎn)品相對較少。

最后一種就是本文要討論的，JIT 即時(shí)編譯（Just In Time Compilation）。對于一個抽象語法樹，先將其轉(zhuǎn)化為一個中間字節(jié)碼，然后在執(zhí)行時(shí)再轉(zhuǎn)換為機(jī)器碼。

上圖中列出了一些主流產(chǎn)品所采用的方式。

二、JIT 即時(shí)編譯技術(shù)

JIT 即時(shí)編譯技術(shù)，又稱為動態(tài)翻譯，或運(yùn)行時(shí)編譯。其核心在于將程序在運(yùn)行過程中轉(zhuǎn)換為機(jī)器代碼，而非在執(zhí)行前預(yù)先編譯為機(jī)器代碼。

比方說，在編寫 C++ 程序時(shí)，使用 GCC 或 C++ 進(jìn)行編譯，最終執(zhí)行的實(shí)際上是能讓機(jī)器運(yùn)行的字節(jié)碼。然而，JIT技術(shù)并非如此，它存在一個中間狀態(tài)，以 Java 的視角更易于理解。Java 文件會被編譯成（complier）進(jìn)行的 .class 文件，該文件即是一種中間狀態(tài)的編碼，然后由 JIT 的 complier 將其翻譯成機(jī)器能夠認(rèn)識的機(jī)器碼。

即時(shí)編譯技術(shù)亦存在其利弊兩面。其優(yōu)勢在于，編譯代碼速度可以得到顯著提升，無需一次性將代碼轉(zhuǎn)換為機(jī)器可執(zhí)行的格式；其次，這種技術(shù)提供了解釋的靈活性。然而，其劣勢在于運(yùn)行時(shí)需要將代碼編譯為機(jī)器碼，這將會產(chǎn)生額外的開銷。因此，在應(yīng)用 JIT 技術(shù)時(shí)，需針對不同情況進(jìn)行測試和分析，評估該技術(shù)所帶來的收益是否大于其帶來的開銷。

數(shù)據(jù)庫中的即時(shí)編譯（JIT）技術(shù)的運(yùn)行機(jī)制，與上述過程大致相似。主要包括以下幾個階段。

首先，SQL 解析器將語句翻譯為抽象語法樹；接著，表達(dá)式編譯器將其轉(zhuǎn)化為中間字節(jié)碼；最后，JIT 編譯器將其進(jìn)一步轉(zhuǎn)換為最終的機(jī)器碼。

在此借助程序?qū)?JIT 進(jìn)行模擬，當(dāng)然這與實(shí)際場景會存在一些差異。程序中有兩個函數(shù)：首先是名為 generate_code 的函數(shù)，其任務(wù)是獲取一個抽象語法樹（AST），之后加載定義，在遍歷 code 時(shí)，將其轉(zhuǎn)化為一個可理解的 code 字符串。Evaluator 函數(shù)直接執(zhí)行 code 字符串，即生成一個可執(zhí)行的代碼。

三、使用 Gandiva 的 JIT 即時(shí)編譯技術(shù)加速計(jì)算

接下來介紹如何運(yùn)用 JIT 技術(shù)對數(shù)據(jù)庫表達(dá)式進(jìn)行求值優(yōu)化。我們采用了 Apache 的 Gandiva，它是建立在 LLVM 編譯器框架基礎(chǔ)上的一個表達(dá)式編譯器，其核心計(jì)算適用于 Arrow 列式內(nèi)存格式，代碼編寫采用 C++，同時(shí)也提供了 Python 與 Java 的綁定接口。

Apache Arrow 內(nèi)存格式是一種列式存儲格式，對于關(guān)系型數(shù)據(jù)庫而言，行式存儲的形式往往無法在構(gòu)建計(jì)算過程中實(shí)現(xiàn)高效的并行處理。而列式存儲，即數(shù)據(jù)在同一列內(nèi)，其緩沖區(qū)內(nèi)的數(shù)據(jù)將被集中存儲，因此在操作數(shù)據(jù)時(shí)，能極大提升操作效率。

Gandiva 的整體執(zhí)行流程如上圖所示。首先，有一個表達(dá)式樹；接著，Gandiva 的表達(dá)式編譯器將生成一種稱為 LLVM IR 的中間代碼，這是一種中間表達(dá)形式；該中間代碼將被傳遞給 Gandiva 的執(zhí)行內(nèi)核，整個過程處理的數(shù)據(jù)被稱為 Apache 的 Arrow Record Batches，最終得到預(yù)期的輸出結(jié)果。

早期的 Gandiva 比較簡陋，功能性略顯不足。近年來已得到了顯著的提升，但仍存在一些待改進(jìn)之處。目前，在 Gandiva 的表達(dá)式庫中，已具備相當(dāng)豐富的內(nèi)容，除了基本的算術(shù)運(yùn)算符以外，還擁有超過 100 個內(nèi)建函數(shù)，以及布爾運(yùn)算符。這些運(yùn)算主要用于 project 和 filter 操作，即過濾和投影階段，因?yàn)橹挥性谶@兩個階段會涉及到大規(guī)模的表達(dá)式求值。

上圖中是一個簡單的 C++ 程序示例，使用了 Gandiva 接口，最上面可以看到表達(dá)式為：(x > 2.0) and (x < 6.0)。

借助 Gandiva 的表達(dá)式，可以得到一個類似于 LLVM IR 表達(dá)式的結(jié)果。然而，在這個表達(dá)式及生成的代碼中可以看到，以 @ 開頭的 less_than_float32_float32 等函數(shù)形式，這些都是 Gandiva 內(nèi)置的功能。因此，如果要形象地詮釋 JIT 代碼生成的原理，這里的內(nèi)置算子與功能便如同齒輪組，當(dāng)我們將表達(dá)式傳達(dá)給它們時(shí)，Gandiva 就會將這些齒輪組裝和運(yùn)轉(zhuǎn)起來，使表達(dá)式得以順利執(zhí)行。

通過上圖數(shù)據(jù)可以看到，LLVM 技術(shù)的整體效率較之 Java JIT 可實(shí)現(xiàn)約 4 至 89 倍的提升。

我們對 Gandiva 進(jìn)行了一些改進(jìn)，增添了眾多額外功能，比如對時(shí)間戳支持，以及針對數(shù)組類型新增了超過 20 種有關(guān)函數(shù)，同時(shí)也增強(qiáng)了對于高階函數(shù)的支持，并改進(jìn)了內(nèi)存緩存的復(fù)用方式。

此外，還有一項(xiàng)極為關(guān)鍵的功能，就是前文中提到的 UDF 注冊機(jī)制，這也是我們向 Gandiva 項(xiàng)目貢獻(xiàn)的一項(xiàng)技術(shù)。

最后回顧一下本次分享的內(nèi)容。文章第一部分探討了什么是數(shù)據(jù)庫表達(dá)式求值問題；第二部分，介紹了 JIT 即時(shí)編譯技術(shù)；最后，運(yùn)用 Gandiva 的 JIT 技術(shù)來加速表達(dá)式求值。

炎凰數(shù)據(jù)產(chǎn)品旨在解決異構(gòu)數(shù)據(jù)所面臨的復(fù)雜場景，歡迎大家關(guān)注、試用。

四、Q&A

Q1：Gandiva 生成的 LLVM 是標(biāo)量值，有用到向量值，就是 SIMD（單指令多數(shù)據(jù)流）或者 AVX（高級向量擴(kuò)展）等技術(shù)嗎？

A1：這是一個非常好的問題，有些人可能會對采用 Gandiva 協(xié)助生成 LLVM IR 的代碼存在一定擔(dān)憂，是否能達(dá)到預(yù)期的性能要求。因?yàn)樵诔Ｒ?guī)執(zhí)行過程中，人們通常期望擁有準(zhǔn)確、高效的向量化支持。針對這個問題，Gandiva 已經(jīng)做出了妥善的處理，生成的 LLVM-IR 中間形式均具備向量化支持，以確保所需的功能得以保留。

這些技術(shù)使得處理器能夠同時(shí)處理多個數(shù)據(jù)，從而大大提高了程序的執(zhí)行效率。在 Gandiva 中，LLVM IR（中間表示）被轉(zhuǎn)換為可執(zhí)行代碼的序列，這些代碼可以由 SIMD 指令集執(zhí)行。因此，Gandiva 生成的 LLVM IR 序列可以在支持 SIMD 指令集的處理器上高效運(yùn)行。

Q2：Gandiva 一生成出來就是 LLVM 的形式？就是向量化的執(zhí)行代碼？

A2：是的。它是經(jīng)過優(yōu)化的，實(shí)際執(zhí)行的和我剛剛給大家展示的 Arrow code 是不一樣的，后者代表了初始的呈現(xiàn)方式，然而在實(shí)際執(zhí)行過程中都是有向量化支持的。

Gandiva 生成的是 LLVM 的形式，并且可以生成向量化的執(zhí)行代碼。Gandiva 是一個開源項(xiàng)目，旨在為 Apache Arrow 提供高效的數(shù)據(jù)處理功能。它使用 LLVM 作為后端，通過 LLVM 編譯器將源代碼編譯為高效的機(jī)器碼，并利用 SIMD 指令集實(shí)現(xiàn)向量化的執(zhí)行代碼，從而提高數(shù)據(jù)處理性能。因此，Gandiva 生成的代碼可以在支持 SIMD 指令集的處理器上高效運(yùn)行，實(shí)現(xiàn)高性能的數(shù)據(jù)處理。

Q3：Arrow 社區(qū)提供了 compute API 以及各種語言的高性能實(shí)現(xiàn)以供基于 Arrow 格式進(jìn)行數(shù)據(jù)操作的向量化復(fù)用，跟 Gandiva 生成的 LLVM 的形式的向量化有什么區(qū)別和聯(lián)系？

A3：這也是一個很好的問題，Arrow 有自己的一套執(zhí)行框架，叫做 Arrow Acero，它對向量化的支持是非常友好的。

Arrow 社區(qū)提供的 compute API 以及各種語言的高性能實(shí)現(xiàn)，是基于 Arrow 格式進(jìn)行數(shù)據(jù)操作的開發(fā)人員可以直接復(fù)用的工具。這些工具可以幫助開發(fā)人員更高效地處理數(shù)據(jù)，并提高程序的執(zhí)行效率。

而 Gandiva 生成的 LLVM 形式，是利用 LLVM 編譯器將源代碼編譯為高效的機(jī)器碼，并利用 SIMD 指令集實(shí)現(xiàn)向量化的執(zhí)行代碼。這種生成方式可以使得 Gandiva 生成的代碼在支持 SIMD 指令集的處理器上高效運(yùn)行，從而提高數(shù)據(jù)處理性能。

兩者的主要區(qū)別在于，Arrow 社區(qū)提供的工具主要是提供API和各種語言的高性能實(shí)現(xiàn)，而 Gandiva 生成的 LLVM 形式則是通過編譯源代碼來實(shí)現(xiàn)高效的數(shù)據(jù)處理。另外，Gandiva 生成的 LLVM 形式是向量化的執(zhí)行代碼，可以充分利用處理器的 SIMD 指令集，而 Arrow 社區(qū)提供的工具則不一定是向量化的。

所以我們的整個執(zhí)行引擎在經(jīng)過了很多次迭代之后完全切到了一個新式的、對流式計(jì)算有一個更好的支持的引擎，這個引擎也是基于 Arrow compute 構(gòu)建的。

Q4：是否有嘗試過這樣使用表達(dá)式求值的方法，因?yàn)樗淼氖墙忉寛?zhí)行加向量化的方式，每個算子會把 SIMD 指令解釋成向量化的執(zhí)行代碼？

A4：是的。這部分我們也會用，我們是結(jié)合在一起用的，不是說單獨(dú)或者只使用這個，而不使用就是不是以數(shù)據(jù)執(zhí)行。從數(shù)據(jù)從磁盤上讀取出來，就是經(jīng)過過濾、投影再到給用戶呈現(xiàn)這個結(jié)果的過程中，有很多可以優(yōu)化的地方。在最開始的時(shí)候一定要確保讀出來的那個數(shù)據(jù)集是最小的。然后在這個內(nèi)存當(dāng)中或者是在計(jì)算過程當(dāng)中進(jìn)行過濾時(shí)，我們可以通過 JIT 技術(shù)對它進(jìn)行優(yōu)化，優(yōu)化是分為多個階段，就是看你當(dāng)前所面臨的點(diǎn)哪個是最大的瓶頸。

這樣使用表達(dá)式求值的方法，是解釋執(zhí)行加向量化的方式。每個算子會把 SIMD 指令解釋成向量化的執(zhí)行代碼，從而充分利用處理器的并行處理能力，提高程序的執(zhí)行效率。這種方法的優(yōu)點(diǎn)是可以方便地?cái)U(kuò)展到支持向量化的指令集，如 AVX 或 SSE 等。此外，由于使用了向量化的執(zhí)行代碼，還可以在多核處理器上實(shí)現(xiàn)真正的并行計(jì)算，進(jìn)一步提高程序的性能。因此，表達(dá)式求值的方法在某些情況下可以提供比傳統(tǒng)解釋執(zhí)行更高效的性能。

Q5：問一個表達(dá)式相關(guān)但與JIT無關(guān)的問題，是否有一種方法可以判斷某個表達(dá)式肯定為 true 或者肯定為 false。有沒有這樣的庫或者方法？

A5：此環(huán)節(jié)往往在項(xiàng)目初期便已完成，若是庫的問題，或許仍需根據(jù)具體情況著手實(shí)施。當(dāng)前較為常用的解決方案是 Apache 旗下的 Calcite，它可用于實(shí)現(xiàn) SQL 語句的語法解析。Apache Calcite 是一款開源 SQL 解析工具，能夠?qū)⒏黝?SQL 語句解析為抽象語法樹（Abstract Syntax Tree，AST），隨后通過對 AST 的操縱，可將 SQL 所蘊(yùn)含的算法及關(guān)系映射到具體的代碼中。然而，我們并未采用此類方法，而是獨(dú)立開發(fā)了自己的解決方案。在物理執(zhí)行計(jì)劃轉(zhuǎn)化為實(shí)際代碼之前，我們已經(jīng)對其進(jìn)行了全面優(yōu)化，這個優(yōu)化過程貫穿始終。

Q6：分享一下思路吧，我們在做的過程中產(chǎn)生困擾，比如 x＞0 and x ＜0 這樣的篩選條件？

A6：對，這是一個比較典型的場景，這個可能得和具體的產(chǎn)品結(jié)合來看。就是（x＞0 and x ＜0）這個明顯是一個 false 的場景。

當(dāng)遇到 x＞0 and x ＜0 這樣的篩選條件時(shí)，語法解析器會將其視為無效的語法。因?yàn)樵谝粋€邏輯表達(dá)式中，and 操作符連接的兩個條件必須都是真值，即 x＞0 和 x ＜0 兩個條件必須同時(shí)滿足，這在邏輯上是矛盾的，因此無法解析這樣的表達(dá)式。

語法解析器在解析 SQL 語句時(shí)，會根據(jù)語言的語法規(guī)則將輸入的字符串轉(zhuǎn)換成抽象語法樹 AST（Abstract Syntax Tree）。在解析 AST 時(shí)，語法解析器會根據(jù)語法規(guī)則對 AST 進(jìn)行驗(yàn)證，確保 AST 符合語法的約束條件。

在處理 and 操作符時(shí)，語法解析器會檢查其左右兩個操作數(shù)的真值性。如果兩個操作數(shù)都是真值，則整個 and 表達(dá)式為真值；如果其中一個操作數(shù)為假值，則整個 and 表達(dá)式為假值。因此，當(dāng)遇到 x＞0 and x ＜0 這樣的表達(dá)式時(shí)，由于兩個條件在邏輯上是矛盾的，因此整個表達(dá)式為假值。

在處理篩選條件時(shí)，語法解析器會根據(jù)表達(dá)式的類型和上下文信息來解析。對于比較操作符（如 ＞、＜、= 等）連接的兩個表達(dá)式，語法解析器會先解析每個表達(dá)式，確定其類型和值，然后根據(jù)比較操作符的類型進(jìn)行比較運(yùn)算。如果比較運(yùn)算的結(jié)果是真值，則該條件可以被篩選出來；如果比較運(yùn)算的結(jié)果是假值，則該條件不能被篩選出來。

總之，語法解析器在解析 SQL 語句時(shí)，會根據(jù)語言的語法規(guī)則對輸入的字符串進(jìn)行解析和驗(yàn)證，確保生成的 AST 符合語法的約束條件。對于無效的語法，語法解析器會報(bào)錯并提示用戶進(jìn)行修正。

對于這種情況可以采用的一個辦法是假設(shè)法，即假設(shè) x > 0 為真，在這個假設(shè)的基礎(chǔ)上去判斷 x < 0 是否為真，如果不成立那么兩者 and 的結(jié)果一定為假。