摘要：本文主要介紹 Query 層的整體結構，并通過一條 nGQL 語句來介紹其通過 Query 層的四個主要子產品的流程。
一、概述
分布式圖資料庫 Nebula Graph 2.0 版本相比 1.0 有較大改動，最明顯的變化便是，在 1.0 版本中 Query、Storage 和 Meta 子產品代碼不作區分放在同一個代碼倉中，而 Nebula Graph 2.0 開始在架構上先解耦成三個代碼倉：
nebula-graph、
nebula-common和
nebula-storage，其中 nebula-common 中主要是表達式的定義、函數定義和一些公共接口、nebula-graph 主要負責 Query 子產品、nebula-storage 主要負責 Storage 和 Meta 子產品。
本文主要介紹 Query 層的整體結構，并通過一條 nGQL 語句來介紹其通過 Query 層的四個主要子產品的流程，由于 Nebula Graph 2.0 仍處于開發中，版本變化比較頻繁，本文主要針對 2.0 的 nebula-graph 倉中 master 分支的 aea5befd179585c510fb83452cb82276a7756529 版本。
二、架構
Query 層主要架構如下所示：
主要分為 4 個子子產品
- Parser：詞法文法解析子產品
- Validator：語句校驗子產品
- Planner：執行計劃和優化器子產品
- Executor：執行算子子產品
三、代碼結構
下面講下 nebula-graph 的代碼層次結構，如下所示
|--src
|--context // 校驗期和執行期上下文
|--daemons
|--executor // 執行算子
|--mock
|--optimizer // 優化規則
|--parser // 詞法文法分析
|--planner // 執行計劃結構
|--scheduler // 排程器
|--service
|--util // 基礎元件
|--validator // 語句校驗
|--vistor 四、一個案例聊 Query
自 Nebula Graph v2.0 起，nGQL 的文法規則已經支援起始點的類型為
string
，正在相容 1.0 的
int
類型。舉個例子：
GO FROM "Tim" OVER like WHERE like.likeness > 8.0 YIELD like._dst 上面的一條 nGQL 語句在 Nebula Graph 的 Query 層的資料流如下所示：
主要流程如下：
第一階段：生成 AST
第一階段：首先經過 Flex 和 Bison 組成的詞法文法解析器子產品 Parser 生成對應的 AST, 結構如下:
在此階段 Parser 會攔截掉不符合文法規則的語句。舉個例子，
GO "Tim" FROM OVER like YIELD like._dst
這種文法使用錯誤的語句會在文法解析階段直接被攔截。
第二階段：校驗
第二階段：Validator 在 AST 上進行一系列的校驗工作，主要工作如下：
- 中繼資料資訊的校驗
在解析
OVER
、
WHERE
和
YIELD
語句時，會查找 Schema，校驗 edge、tag 的資訊是否存在。或者在
INSERT
資料時校驗插入資料類型和 Schema 中的是否一緻
- 上下文引用校驗
遇到多語句時，例如：
$var = GO FROM "Tim" OVER like YIELD like._dst AS ID; GO FROM $var.ID OVER serve YIELD serve._dst
，Validator 會校驗
$var.ID` 首先檢查變量 `var` 是否定義，其次再檢查屬性 `ID` 是否屬于變量 `var`, 如果是将 `$var.ID
替換為
$var1.ID` 或者 `$var.IID
, 則會校驗失敗。
- 類型推斷校驗
推斷表達式的結果屬于什麼類型，并根據具體的子句，校驗類型是否正确。比如
WHERE
子句要求結果是
bool
，
null
或者
empty
。
- *'' 展開**
例如，若輸入語句為
GO FROM "Tim" OVER * YIELD like._dst, like.likeness, serve._dst
，則在校驗
OVER
子句時需要查詢 Schema 将
*
展開為所有的邊，假如 Schema 中隻有 like 和 serve 兩條邊時，該語句會展開為:
GO FROM "Tim" OVER serve, like YIELD like._dst, like.likeness, serve._dst
- 輸入輸出校驗
遇到
PIPE
語句時，例如：
GO FROM "Tim" OVER like YIELD like._dst AS ID | GO FROM $-.ID OVER serve YIELD serve._dst`，Validator 會校驗 `$-.ID
由于 ID 在上一條語句中已經定義，則該子句合法，如果是将$-.ID 換為 `$-.a` 而此時 a 未定義，是以該子句非法。
第三階段：生成可執行計劃
第三階段：經過 Validator 之後會生成一個可執行計劃，其中執行計劃的資料結構在
src/planner
目錄下，其邏輯結構如下：
Query 執行流
執行流：該執行計劃是一個有向無環圖，其中節點間的依賴關系在 Validator 中每個子產品的
toPlan()函數中确定，在這個例子中 Project 依賴 Filter， Filter 依賴 GetNeighbor，依次類推直到 Start 節點為止。
在執行階段執行器會對每個節點生成一個對應的算子，并且從根節點（這個例子中是 Project 節點）開始排程，此時發現此節點依賴其他節點，就先遞歸調用依賴的節點，一直找到沒有任何依賴的節點（此時為 Start 節點），然後開始執行，執行此節點後，繼續執行此節點被依賴的其他節點（此時為 GetNeighbor 節點)，一直到根節點為止。
Query 資料流
資料流：每個節點的輸入輸出也是在
中确定的, 雖然執行的時候會按照執行計劃的先後關系執行，但是每個節點的輸入并不完全依賴上個節點，可以自行定義，因為所有節點的輸入、輸出其實是存儲在一個哈希表中的，其中 key 是在建立每個節點的時候自己定義的名稱，假如哈希表的名字為 ResultMap，在建立 Filter 這個節點時，定義該節點從
ResultMap["GN1"]
中取資料，然後将結果放入
ResultMap["Filter2"]
中，依次類推，将每個節點的輸入輸出都确定好，該哈希表定義在 nebula-graph 倉下
src/context/ExecutionContext.cpp
中，因為執行計劃并不是真正地執行，是以對應哈希表中每個 key 的 value 值都為空（除了開始節點，此時會将起始資料放入該節點的輸入變量中），其值會在 Excutor 階段被計算并填充。
這個例子比較簡單，最後會放一個複雜點的例子以便更好地了解執行計劃。
第四階段：執行計劃優化
第四階段：執行計劃優化。如果
etc/nebula-graphd.conf
配置檔案中
enable_optimizer
設定為
true
，則會對執行計劃的優化，例如上邊的例子，當開啟優化時：
此時會将 Filter 節點融入到 GetNeighbor 節點中，在執行階段當 GetNeighbor 算子調用 Storage 層的接口擷取一個點的鄰邊的時候，Storage 層内部會直接将不符合條件的邊過濾掉，這樣就可以極大的減少資料量的傳輸，俗稱過濾下推。
在執行計劃中，每個節點直接依賴另外一個節點。為了探索等價的變換和重用計劃中相同的部分，會将節點的這種直接依賴關系轉換為 OptGroupNode 與 OptGroup 的依賴。每個 OptGroup 中可以包含等價的 OptGroupNode 的集合，每個 OptGroupNode 都包含執行計劃中的一個節點，同時 OptGroupNode 依賴的不再是 OptGroupNode 而是 OptGroup，這樣從該 OptGroupNode 出發可以根據其依賴 OptGroup 中的不同的 OptGroupNode 拓展出很多等價的執行計劃。同時 OptGroup 還可以被不同的 OptGroupNode 共用，節省存儲的空間。
目前我們實作的所有優化規則認為是 RBO（rule-based optimization），即認為應用規則後的計劃一定比應用前的計劃要優。CBO(cost-based optimization) 目前正在同步開發。整個優化的過程是一個"自底向上"的探索過程，即對于每個規則而言，都會由執行計劃的根節點（此例中是 Project 節點）開始，一步步向下找到最底層的節點，然後由該節點開始一步步向上探索每個 OptGroup 中的 OptGroupNode 是否比對該規則，直到整個 Plan 都不能再應用該規則為止，再執行下一個規則的探索。
本例中的優化如下圖所示：
例如，當搜尋到 Filter 節點時，發現 Filter 節點的子節點是 GetNeighbors，和規則中事先定義的模式比對成功，啟動轉換，将 Filter 節點融入到 GetNeighbors 節點中，然後移除掉 Filter 節點，繼續比對下一個規則。
優化的代碼在 nebula-graph 倉下
src/optimizer/
目錄下。
第五階段：執行
第五階段：最後 Scheduler 會根據執行計劃生成對應的執行算子，從葉子節點開始執行，一直到根節點結束。其結構如下：
其中每一個執行計劃節點都一一對應一個執行算子節點，其輸入輸出在執行計劃期間已經确定，每個算子隻需要拿到輸入變量中的值然後進行計算，最後将計算結果放入對應的輸出變量中即可，是以隻需要從開始節點一步步執行，最後一個算子的結果會作為最終結果傳回給使用者。
五、執行個體
下面執行一個最短路徑的執行個體看看執行計劃的具體結構，打開
nebula-console, 輸入下面語句
FIND SHORTEST PATH FROM "YAO MING" TO "Tim Duncan" OVER like, serve UPTO 5 STEPS
，在這條語句前加
EXPLAIN
關鍵字就可以得到該語句生成的執行計劃詳細資訊：
上圖從左到右依次顯示執行計劃中每個節點的唯一 ID、節點的名稱、該節點所依賴的節點 ID、profiling data（執行 profile 指令時的資訊）、該節點的詳細資訊（包括輸入輸出變量名稱，輸出結果的列名，節點的參數資訊）。
如果想要可視化一點可以在這條語句前加
EXPLAIN format="dot"
，這時候 nebula-console 會生成 dot 格式的資料，然後打開
Graphviz Online這個網站将生成的 dot 資料粘貼上去，就可以看到如下結構，該結構對應着執行階段各個算子的執行流程。
因為最短路徑使用了雙向廣度搜尋算法分别從
"YAO MING"
"Tim Duncan"
兩邊同時擴充，是以中間的
GetNeighbors
BFSShortest
Project
Dedup
分别有兩個算子，通過
PassThrough
算子連接配接輸入，由
ConjunctPath
算子拼接路徑。然後由
LOOP
算子控制向外擴充的步數，可以看到
DataCollect
算子的輸入其實是從
ConjuctPath
算子的輸出變量中取值的。
各個算子的資訊在 nebula-graph 倉下的
src/executor
作者有話說：Hi，我是明泉，是圖資料 Nebula Graph 研發工程師，主要工作和資料庫查詢引擎相關，希望本次的經驗分享能給大家帶來幫助，如有不當之處也希望能幫忙糾正，謝謝~
喜歡這篇文章？來來來，給我們的
GitHub點個 star 表鼓勵啦~~ 🙇♂️🙇♀️ [手動跪謝]
交流圖資料庫技術？交個朋友，Nebula Graph 官方小助手微信：
NebulaGraphbot拉你進交流群~~