一、表達式求值

1、場景介紹

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

當前各大企業(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ù)，并高效地從其中挖掘信息，從而獲得有價值的洞察和啟示。這就是炎凰數(shù)據(jù)產(chǎn)品希望解決的場景。

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

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

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

2、表達式求值問題

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

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

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

我們重點來看一下中間的過濾階段。

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

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

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

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

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

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

這類解決方案能被眾多數(shù)據(jù)庫采用，是因為在早年這并不是主要問題，那時磁盤才是系統(tǒng)執(zhí)行的瓶頸。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、Q&A

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

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

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

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

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

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

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

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

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

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

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

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

Q4：是否有嘗試過這樣使用表達式求值的方法，因為它代表的是解釋執(zhí)行加向量化的方式，每個算子會把 SIMD 指令解釋成向量化的執(zhí)行代碼？

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

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

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

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

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

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

當遇到 x＞0 and x ＜0 這樣的篩選條件時，語法解析器會將其視為無效的語法。因為在一個邏輯表達式中，and 操作符連接的兩個條件必須都是真值，即 x＞0 和 x ＜0 兩個條件必須同時滿足，這在邏輯上是矛盾的，因此無法解析這樣的表達式。

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

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

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

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

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