基于數(shù)據(jù)倉庫的典型圖查詢處理技術(shù)

郭家鼎，王 鵬

（1.復(fù)旦大學(xué) 軟件學(xué)院，上海 200438；2.復(fù)旦大學(xué) 計算機科學(xué)技術(shù)學(xué)院，上海 200438）

0 概述

隨著數(shù)據(jù)量的增長和數(shù)據(jù)關(guān)聯(lián)的日益復(fù)雜，圖數(shù)據(jù)庫系統(tǒng)逐步得到人們的關(guān)注［1］，并在知識圖譜［2-3］、網(wǎng)絡(luò)檢測預(yù)警［4］、社交網(wǎng)絡(luò)［5］、交通網(wǎng)絡(luò)［6］、人工智能［7-8］等領(lǐng)域發(fā)揮越來越重要的作用。圖數(shù)據(jù)可以簡單理解為頂點、邊和上面屬性所組成的集合?，F(xiàn)有的圖查詢一般涉及頂點和邊上屬性的查詢、頂點或邊之間的遍歷以及屬性結(jié)果的聚合、排序等操作。圖遍歷將實體間關(guān)聯(lián)起來，因此也是圖查詢的核心操作。如果使用結(jié)構(gòu)化數(shù)據(jù)模型存儲圖數(shù)據(jù)，需要將頂點和邊分開存儲，每行代表一個實體，通過耗時的連接（JOIN）操作實現(xiàn)圖遍歷［1］。考慮到圖數(shù)據(jù)模型的靈活性和復(fù)雜性，現(xiàn)有的圖數(shù)據(jù)庫大多拋棄了傳統(tǒng)的關(guān)系型模型，使用NoSQL［9］或原生圖結(jié)構(gòu)［10］進行存儲。

由于圖數(shù)據(jù)庫使用了獨特的存儲結(jié)構(gòu)，因此在業(yè)務(wù)流程中需要通過抽取、轉(zhuǎn)換、加載（Extract，Transform，Load，ETL）過程攝取上游數(shù)據(jù)源。常見的應(yīng)用場景為：用戶的交易數(shù)據(jù)存儲在事務(wù)型數(shù)據(jù)庫中，如果有數(shù)據(jù)查詢或報表的需要，則將數(shù)據(jù)導(dǎo)入數(shù)據(jù)倉庫（簡稱數(shù)倉）進行分析；如果有圖查詢的需求，則需要再進行一次ETL 過程，將數(shù)倉中相關(guān)圖結(jié)構(gòu)導(dǎo)入圖數(shù)據(jù)庫進行查詢。ETL 過程消耗大量計算資源，存在磁盤空間消耗大、數(shù)據(jù)延遲、運維繁瑣等問題。

隨著CPU 性能提升、DRAM 容量變大和 SSD 存儲的流行，數(shù)據(jù)處理內(nèi)存成為瓶頸［11］。近年來，隨著向量化查詢［12］、大規(guī)模并行處理［13］等技術(shù)的應(yīng)用，新型數(shù)倉不僅在查詢性能上具有優(yōu)勢，在擴展性、生態(tài)工具方面也逐漸成熟。對于圖數(shù)據(jù)庫來說，它專門為圖的存儲和計算設(shè)計，但在分布式擴展性能和查詢性能上略有劣勢。

如果使用新型數(shù)倉作為圖數(shù)據(jù)庫的后端并提供圖查詢的功能，那么一方面可以直接獲得數(shù)倉的性能優(yōu)勢和成熟的生態(tài)工具，另一方面省去了繁雜耗時的ETL 過程，減少了存儲壓力，提高了數(shù)據(jù)新鮮度。本文提出一套基于數(shù)倉的圖數(shù)據(jù)庫系統(tǒng)PandaGraph。在存儲方面，PandaGraph 結(jié)合數(shù)倉的列式存儲特性，并考慮圖查詢過程和數(shù)倉查詢執(zhí)行特點，基于關(guān)系模型高效存儲圖數(shù)據(jù)。在查詢方面，基于PandaGraph 設(shè)計了Gremlin-PandaNodeTree-Panda TableTree-SQL 的翻譯過程，實現(xiàn)從圖查詢Gremlin 語言到數(shù)倉使用的SQL 語言的翻譯轉(zhuǎn)化過程。PandaGraph 使用多種優(yōu)化方法對生成的 SQL 語句進行改寫，提高圖查詢性能。

1 相關(guān)工作

1.1 標(biāo)簽屬性圖模型

目前的圖數(shù)據(jù)庫大多采用標(biāo)簽屬性圖模型［14］，簡稱屬性圖。屬性圖在簡單圖模型的基礎(chǔ)上新增了標(biāo)簽來區(qū)分不同類型的頂點或邊，頂點或邊有零個或多個屬性。屬性圖可定義為如下元組：

其中：V是頂點的有限集；E是邊的有限集；λ為全函數(shù)，定義了頂點或邊到標(biāo)簽的映射關(guān)系；σ為偏函數(shù)，定義了頂點或邊到屬性值的映射關(guān)系。

1.2 圖存儲模式

為了靈活存儲圖結(jié)構(gòu)，現(xiàn)有的圖數(shù)據(jù)庫大多采用NoSQL 或原生 結(jié)構(gòu)存 儲圖數(shù) 據(jù)。Titan［15］、HugeGraph［16］等圖數(shù)據(jù)庫使用鍵值對存儲圖數(shù)據(jù)，頂點作 為Key 鍵，Value 存儲邊 和屬性。Neo4j［17］是一款基于原生圖結(jié)構(gòu)的圖數(shù)據(jù)庫系統(tǒng)，它通過鏈表將頂點、邊和屬性把前后指針串聯(lián)起來，圖遍歷的過程即為鏈表遍歷的過程。

現(xiàn)有的數(shù)倉大多采用列式結(jié)構(gòu)化方式存儲數(shù)據(jù)。在結(jié)構(gòu)化模型中，數(shù)據(jù)以二維行、列進行存儲，每行代表一個實體。IBM Db2［18］通過定義相關(guān)的圖邏輯映射關(guān)系，與結(jié)構(gòu)化數(shù)據(jù)庫中的原始數(shù)據(jù)進行關(guān)聯(lián)，并在上層統(tǒng)一組織元數(shù)據(jù)，生成SQL 進行圖查詢。SQLGraph［19］使用行存方式存儲頂點和邊，屬性值信息采用JSON 列進行存儲，標(biāo)簽信息單獨存儲在表格的一列中，數(shù)據(jù)用哈希算法打散存儲。頂點表和邊表單獨存儲ID 和屬性，此外邊表又拆分為主邊表和從邊表存儲連接關(guān)系。這種存儲方式不方便通過標(biāo)簽查找不同的實體，并且屬性存儲在JSON 中導(dǎo)致讀取性能較差。SAP HANA［20］基于原有的列式數(shù)據(jù)庫增加了圖查詢功能。在存儲方面，它將頂點和邊分別按標(biāo)簽值進行存儲，屬性存儲在對應(yīng)的表中，但它并沒有針對圖查詢語句的特點進行存儲優(yōu)化，只是簡單地將圖數(shù)據(jù)拆分成結(jié)構(gòu)化數(shù)據(jù)。

現(xiàn)有的基于結(jié)構(gòu)化存儲的圖查詢系統(tǒng)要么沒有對底層存儲結(jié)構(gòu)修改，只完成了元數(shù)據(jù)映射關(guān)系，要么基于行式事務(wù)型數(shù)據(jù)庫進行設(shè)計，簡單地將圖數(shù)據(jù)模式映射到存儲引擎上，沒有考慮到列式存儲特點和圖查詢語句的特點。因此，如何在列式數(shù)倉上設(shè)計合理的存儲結(jié)構(gòu)是一個重要挑戰(zhàn)。

1.3 圖查詢翻譯

為了方便描述圖中實體間的連接關(guān)系，業(yè)界提出了許多專有圖查詢語言，Gremlin［21］即為其中的一種。Gremlin 是一種靈活的圖查詢語言，它由基本的遍歷步驟構(gòu)成，通過將Gremlin 步驟串聯(lián)起來，用戶可在圖上完成擴展遍歷的過程。現(xiàn)有的許多圖查詢應(yīng)用已經(jīng)采用了大量的Gremlin 查詢語句，使用數(shù)倉作為圖查詢引擎的后端需要將Gremlin 語言翻譯轉(zhuǎn)化為對應(yīng)等價的SQL 語言，保證上層圖應(yīng)用的兼容性。

研究人員在圖查詢語言翻譯SQL 方面進行了研究。SQLGraph［19］提供了一系列翻譯的原語模板，將 Gremlin 步驟組裝成SQL 語句，但生成的SQL 為多層嵌套，不方便調(diào)試和閱讀，而且沒有對生成的SQL進行深入優(yōu)化。Cytosm［22］是將另一種流行的圖查詢語言Cypher 轉(zhuǎn)換成SQL 的中間件，它依賴圖拓?fù)湓跀?shù)據(jù)上構(gòu)建模式，將Cypher 路徑表達(dá)式切分成一系列rOCQ 結(jié)構(gòu)，結(jié)合模板生成SQL。

將當(dāng)前的圖查詢語言翻譯成SQL 語句的工作大多比較簡單，它們只是對某些步驟進行了模板式的替換翻譯，因此生成的SQL 語句比較復(fù)雜，易讀性較差。同時，由于Gremlin 語言靈活度較高，如何對翻譯生成的SQL 語句進行等價改寫也是一個值得研究的問題。

2 PandaGraph 系統(tǒng)

2.1 系統(tǒng)架構(gòu)

結(jié)合數(shù)倉在數(shù)據(jù)分析上的優(yōu)勢，并實現(xiàn)圖數(shù)據(jù)庫的查詢功能，本文設(shè)計了一套基于數(shù)倉的圖數(shù)據(jù)庫系統(tǒng)PandaGraph，從上到下分別為查詢層、計算層和存儲層，如圖1 所示。

圖1 PandaGraph 系統(tǒng)架構(gòu)Fig.1 PandaGraph system architecture

在圖1 中，查詢層負(fù)責(zé)接收Gremlin 查詢語句，是PandaGraph 的前端，可以通過API 代碼或在網(wǎng)絡(luò)上監(jiān)聽HTTP 請求獲得查詢語句。計算層將給定的Gremlin 查詢翻譯為對應(yīng)的SQL 查詢，首先通過TinkerPop 框架［23］獲得對應(yīng)的Gremlin 步驟，對于符合元數(shù)據(jù)的語句，依據(jù)不同的步驟特點構(gòu)建關(guān)于遍歷過程的PandaNodeTree。然后找到涉及的數(shù)據(jù)表，建立 PandaTableTree 并進行優(yōu)化。最后將PandaTableTree 展開生成對應(yīng)的SQL 語句，生成的查詢SQL 將通過JDBC 發(fā)送到數(shù)據(jù)庫，最終的執(zhí)行結(jié)果將返回查詢層。存儲層對圖數(shù)據(jù)建模，構(gòu)建合適的元數(shù)據(jù)和表格設(shè)計。在構(gòu)建表結(jié)構(gòu)時，PandaGraph 在內(nèi)存中維護了元數(shù)據(jù)，方便計算層進行元數(shù)據(jù)檢查。

2.2 圖結(jié)構(gòu)與存儲表映射

2.2.1 頂點表映射

為了存儲頂點，PandaGraph 為每一種頂點單獨構(gòu)建頂點表，如圖2 所示。頂點表定義了兩類字段：第一類是保留字段ID，類型為BIGINT；第二類是用戶定義的屬性字段，相關(guān)屬性數(shù)據(jù)類型可以從數(shù)據(jù)庫的Schema 定義中獲取。

圖2 頂點表存儲 Fig.2 Vertex table storage

2.2.2 邊表映射

與頂點類似，PandaGraph 為每一種邊構(gòu)建邊表。邊表保留字段有ID、FROM、TO，F(xiàn)ROM 代表出點ID，TO 代表入點ID。3 種保留字段都采用BIGINT存儲，屬性字段從數(shù)據(jù)庫的Schema 定義中獲取，如圖3 所示。圖3（a）是以出方向為主的E_OUT 表，以FROM 和TO 作為主鍵列，圖3（b）是以入方向為主的E_IN 表，以TO 和FROM 作為主鍵列，后續(xù)未加粗的字段為屬性列。

圖3 邊表存儲 Fig.3 Edge table storage

PandaGraph 在出方向為主的E_OUT 表中選取先FROM 后TO 作為鍵列，數(shù)據(jù)以先FROM 后TO 進行排序。如果需要找出邊的信息，可以將FROM 鍵以約O（logan）的時間復(fù)雜度對ID 進行精確查找，迅速找到此時的出點（即TO 字段值）以及出邊上的ID和屬性值。由于同樣為TO 字段進行了二次排序，在篩選出點時也可以使用粗略索引。圖遍歷的過程本質(zhì)上就是頂點表和邊表的JOIN 過程，通過將FROM和TO 作為主鍵列，可以快速找到出邊遍歷的下一步節(jié)點。類似地，如需找到入邊的相關(guān)信息，只需在E_IN 上尋找即可。通過存儲E_OUT 表和E_IN 表兩份數(shù)據(jù)，在不同方向上遍歷時可以靈活選擇，提高JOIN 的性能。

3 PandaGraph 查詢翻譯和優(yōu)化

3.1 查詢翻譯

3.1.1 Gremlin 基礎(chǔ)

為兼容現(xiàn)有的大部分應(yīng)用，PandaGraph 選擇使用Gremlin 作為圖查詢的前端語言。本文對常見的Gremlin 基本步驟進行了總結(jié)和分類，如表1 所示，其中，起始、條件、擴展、映射選擇、聚合和修飾分別用S、C、E、P、A 和M 表示。

表1 Gremlin 常見步驟分類及含義 Table 1 Gremlin common step classification and meanings

依據(jù)步驟的作用，本文將常見的Gremlin 步驟分為起始、條件、擴展、映射選擇、聚合和修飾6 類。后續(xù)將根據(jù)Gremlin 步驟的分類不同，根據(jù)基本步驟的特點進行Gremlin 到SQL 的翻譯。以查詢g.V（）.hasLabel（“Person”）.hasId（“1”）.out（“Create”）.has（“l(fā)ang”，“java”）.order（）.by（“Id”，Order.ASC）.by（“name”，Order.DESC）.limit（2）.valueMap（“id”，“Name”）為例。起始的g.V（）步驟選擇了所有頂點，hasLabel 和hasId 步驟選擇了id 為1，標(biāo)簽為Person的頂點。后續(xù)的out 步驟和has 步驟遍歷到j(luò)ava 編寫的軟件，通過order by 步驟將軟件按id 和name 排序，并最終根據(jù)limit 和valueMap 步驟輸出前兩個的id屬性和name 屬性。

3.1.2 翻譯概覽

本文設(shè)計一套Gremlin-PandaNodeTree-Panda TableTree-SQL 的翻譯過程，如圖4 所示。左上部分為待翻譯的Gremlin 查詢（①）。PandaGraph 依據(jù)不同Gremlin 步驟的特性，將關(guān)于遍歷的步驟構(gòu)建成PandaNode 樹，并把步驟的信息合并到樹上節(jié)點中（②）。接著將PandaNodeTree 中涉及的數(shù)倉表找到，生成PandaTableTree（③）。最后通過PandaTableTree中的表信息和其他屬性信息，找到SQL 的子句部分，翻譯成SQL 語句（④）。

圖4 PandaGraph 翻譯過程Fig.4 PandaGraph translation process

3.1.3 PandaNodeTree 生成

PandaNodeTree 是圖查詢語句關(guān)于遍歷過程的抽象樹結(jié)構(gòu)。PandaNode 中存儲了當(dāng)前遍歷涉及的步驟、步驟的標(biāo)簽、遍歷方向、過濾和聚合條件等信息。為了生成PandaNodeTree，需要對所有的Gremlin 步驟進行遍歷判斷，對于起始類（S）步驟，PandaGraph 創(chuàng)建根節(jié)點，對于擴展類（E）步驟，PandaGraph 構(gòu)建關(guān)于擴展的PandaNode 并連接到樹的葉子節(jié)點上，對于條件類（C）、映射選擇類（P）、聚合類（A）和修飾類（M）步驟，PandaGraph 將對應(yīng)的輔助信息存儲在當(dāng)前處理的節(jié)點中。

3.1.4 PandaTableTree 生成

PandaNodeTree 只對查詢語句的遍歷過程進行組合，而遍歷涉及頂點表和邊表之間的JOIN 操作，因此需要找出遍歷涉及的存儲表。PandaTable 在PandaNode 的基礎(chǔ)上添加了當(dāng)前遍歷涉及的表格信息。具體生成方法見算法1。

算法1PandaTableTree 生成

PandaTableTree 生成算法首先找到所有起始的表。從元數(shù)據(jù)中找到所有的表，比對PandaNodeTree的根節(jié)點的標(biāo)簽斷言，如果符合則添加到集合中。得到起始表后，起始表根據(jù)PandaNodeTree 進行擴展。如果當(dāng)前PandaNode 代表的step 是VertexStep（包括頂點out、in 步驟和邊outE、inE 步驟）時，這類Node 都是從當(dāng)前頂點向外進行的遍歷，那么需要通過元數(shù)據(jù)獲取出入的邊標(biāo)簽。如果步驟遍歷的結(jié)果是邊（outE 和inE 步驟），那么只需要將此邊添加到對應(yīng)的PandaTable 中。如果遍歷結(jié)果是頂點（out 和in步驟），那么需要將頂點連接的邊或頂點通過連接關(guān)系添加到PandaTableTree 中。如果當(dāng)前PandaNode代表的step 是EdgeVertexStep（包 括outV 和inV 步驟），這類Node 從邊指向頂點，那么將該邊對應(yīng)的頂點表添加到PandaTableTree 中即可。

3.1.5 SQL 翻譯

獲得關(guān)于查詢存儲表的PandaTableTree 后，可通過樹信息生成最終的SQL。具體生成方法見算法2。

算法2SQL 生成

首先是SELECT 部分，為了避免SQL 中的重復(fù)表名問題，需要將表名重新進行映射。如果該表沒有輸出標(biāo)記，則可以直接跳過；否則根據(jù)當(dāng)前的信息輸出對應(yīng)的字段和普通表信息，包括聚合信息字段或DISTINCT 信息字段等和ID、對應(yīng)屬性值。

FROM 語句部分需要逐個輸出相關(guān)的表名稱，并將表別名信息通過AS 語句輸出即可。

WHERE 語句包括兩部分：一部分是原始的表上條件信息；另一部分是圖遍歷過程中的等價條件。前者只需要輸出PandaTable 內(nèi)的斷言信息即可。后者需要將PandaTables 中前后兩個表取出，根據(jù)連接關(guān)系（邊的方向）等值連接ID 相關(guān)字段。

最后是GROUP BY、ORDER BY 和LIMIT 語句。這3 類的信息都存儲在葉子節(jié)點中，因此只需要取出最后一個節(jié)點，判斷是否有相關(guān)信息并輸出即可。

3.2 基于規(guī)則的優(yōu)化

3.2.1 表選擇

圖遍歷的過程實際就是頂點和邊表進行ID 等值連接的過程。數(shù)倉無法創(chuàng)建基于數(shù)字的精準(zhǔn)索引，因此為了加速連接過程，PandaGraph 依靠主鍵的排序索引存儲了兩張邊表，方便不同方向的遍歷查詢。

本文記遍歷擴展步驟為ε，擴展的表名和方向用下標(biāo)表示，如εEab←Va表示從頂點a向外擴展到邊ab。對于out 的遍歷，需要通過FROM 字段尋找TO 字段，其中FROM 字段是索引的核心，因此可以使用FROM 在前、TO 在后的EO 表（E_OUT）：

in 遍歷情況類似，需要通過TO 字段尋找FROM字段，其中TO 字段是索引的核心，使用TO 在前、FROM 在后的EI 表（E_IN）：

在算法2 的翻譯過程中，只需要在添加邊表時考慮方向即可。對于out 方向使用E_OUT 表，對于in 方向使 用E_IN 表。

3.2.2 JOIN 選擇

等值連接（EQUI JOIN）將不同的表依據(jù)條件等值拼接，符合圖上遍歷的定義。但對于g.V（）.out（）.dedup（）.count（）等類似的查詢，如果滿足：1）只在最終步驟的輸出結(jié)果；2）中間重復(fù)結(jié)果需要去除，則可以使用半連接（SEMI JOIN）進行替代。等值連接根據(jù)匹配的數(shù)量重復(fù)返回多次，而半連接僅返回某個表的元組且最多返回一次，可以傳輸更少的元組，帶來更高的查詢效率。out 遍歷可以優(yōu)化如下：

in 遍歷的優(yōu)化類似，同時這個過程是連續(xù)的，如果中間同樣不需要輸出結(jié)果，則最后一步的SEMI JOIN 可以在前面步驟中提前進行。

3.2.3 遍歷去除

上述的遍歷翻譯過程需要中間邊做支點，頂點到頂點的遍歷涉及兩張頂點表和一張邊表：

1）起點去除。如果在遍歷的起點只需要ID 信息，那么可以省略對第一張頂點表的JOIN 操作，只需要對中間邊表和最終的頂點表進行JOIN 操作。因為中間邊表的FROM 或TO 字段已經(jīng)存儲了頂點的ID 信息，此時的遍歷操作可簡化如下：

2）結(jié)尾去除。如果在遍歷的結(jié)尾步驟只需要ID信息，或借助ID 信息即可進行處理（如count 步驟，只需要計數(shù)ID 信息），則此時只需要對開始的頂點表和中間的邊表進行JOIN 操作，最終步驟的ID 信息存儲在邊表的FROM 或TO 字段中：

3）中轉(zhuǎn)去除。在進行遍歷的過程中，經(jīng)常出現(xiàn)多步遍歷操作，原始的生成方法可以生成中間以頂點作為支點進行JOIN 的遍歷過程。如果在此過程中不需要對中間的頂點表進行條件篩選或輸出，則可以將中間的頂點省去，用邊表中的FROM 或TO 字段中的ID 作為遍歷中間支點：

遍歷去除過程可見算法3。

算法3遍歷去除

中轉(zhuǎn)去除的過程需要考慮當(dāng)前節(jié)點、父節(jié)點和祖父節(jié)點，對“邊-頂點-邊”的序列進行判斷和去除。起點和結(jié)尾去除的過程只需要考慮根和葉子節(jié)點即可。遍歷去除減少了JOIN 的數(shù)量，提高了查詢效率。

3.2.4 DISTINCT 下推

在遍歷的過程中有時需要對最終結(jié)果進行去重，如果只在最后一步去重，中間遍歷結(jié)果的重復(fù)數(shù)據(jù)增加了數(shù)據(jù)傳輸?shù)拈_銷，也增加了JOIN 的表構(gòu)建和探測的時間。因此，當(dāng)遍歷的某一步需要進行去重操作時，可以將該步的去重操作下推到之前的所有遍歷步驟中：

DISTINCT 下推的過程見算法4。從葉子節(jié)點出發(fā)向上遍歷，將所有可以DISTINCT 下推的節(jié)點進行標(biāo)記即可。

算法4DISTINCT 下推

3.3 翻譯優(yōu)化完備性和正確性討論

Gremlin 語言的靈活度大，圖遍歷的表達(dá)方式多樣，其基本步驟可分為變換（Transform）、過濾（Filter）、副作用（Side Effect）和條件（Branch）4 類［19］。本文的翻譯涉及變換、過濾和副作用3 類共28 個步驟，已經(jīng)可以滿足常見的遍歷場景。

本文支持的步驟中條件、映射和選擇、聚合、修飾這4 個步驟與SQL 語言一一對應(yīng)，可以直接進行翻譯。起始步驟主要涉及的頂點表和邊表，可以通過元數(shù)據(jù)和斷言獲取。擴展步驟表示圖遍歷的移動過程，與JOIN 操作等價，因此可以通過“頂點-邊-頂點”的連接進行翻譯。同時，上述優(yōu)化方法不改變實際的遍歷含義和執(zhí)行結(jié)果，是等價的查詢語句替換。綜上，本文提出的翻譯和優(yōu)化方法可以保證翻譯和優(yōu)化的正確性，后續(xù)實驗章節(jié)也對典型的例子進行了交叉驗證。

4 實驗與結(jié)果分析

4.1 實驗設(shè)置與實驗數(shù)據(jù)

本文實驗在配置為32 核Intel Xeon E5 處理器、128 GB內(nèi)存、12 TB HDD 磁盤和CentOS 7.9 的單機上進行。PandaGraph（PG）使用Java 編寫，底層數(shù)倉為Doris 1.1。根據(jù)實現(xiàn)方式不同，對比圖數(shù)據(jù)庫為：使用鍵 值對存儲的 HugeGraph 0.12（HG）和NebulaGraph 3.0（NG），鏈表存儲的Neo4j 4.1（N4），原生圖存儲的TigerGraph 3.6（TG），關(guān)系型存儲的SQLGraph（SG）。底層采用PostgreSQL 14.5 實現(xiàn)。

本文運用Graph500（G）、Flickr（F）、LiveJournal（J）、Twitter（T）、LDBC1（L1）、LDBC10（L10）數(shù)據(jù)集進行實驗，如表2 所示。

表2 實驗數(shù)據(jù)集 Table 2 Experiment datasets

4.2 數(shù)據(jù)導(dǎo)入和存儲

數(shù)據(jù)導(dǎo)入時間對比如圖5 所示。除了Twitter 數(shù)據(jù)集上TG 最快外，其他情況下PG 的導(dǎo)入速度最快，PG 較TG、N4、HG、SG 和NG 有最多1.71、2.50、5.62、14.42 和18.19 倍的導(dǎo)入性能提升。HG 未能成功導(dǎo)入LDBC10 數(shù)據(jù)集。

圖5 數(shù)據(jù)導(dǎo)入時間對比Fig.5 Comparison of data import time

以L1 數(shù)據(jù)集為例對導(dǎo)入時間進行分解，如圖6所示。由于數(shù)據(jù)模擬的真實稀疏圖邊數(shù)量多，因此導(dǎo)入時間也較長，占TG、HG、N4、SG 和PG 總導(dǎo)入時間的23.6%～71.8%。NG 在多線程導(dǎo)入時不區(qū)分頂點和邊，在圖中統(tǒng)一表示，這部分占比81.4%。對于PG來說，其他時間主要為數(shù)據(jù)建表操作，而LDBC 數(shù)據(jù)集表數(shù)量較多，有59 張表，開銷約占總時間的9.3%。其余圖數(shù)據(jù)庫的其他時間占總時間的12.6% 到65.4%，這部分時間主要用來進行數(shù)據(jù)預(yù)處理、建立索引和內(nèi)存管理等操作。

圖6 數(shù)據(jù)導(dǎo)入時間分解Fig.6 Data import time breakdown

不同圖數(shù)據(jù)庫的存儲空間占用結(jié)果如表3 所示。HG 和NG 的底層鍵值對系統(tǒng)采用LSM-Tree 結(jié)構(gòu)［24］存儲，存在寫放大問題［25］，因此空間占用較多。SG 存儲了多份數(shù)據(jù)和索引，加上行式存儲的壓縮效率不高，因此空間占用最大。N4 將節(jié)點和邊用鏈表的方式存儲起來，需要額外存儲鏈接信息。TG 沒有公開存儲設(shè)計細(xì)節(jié)，其存儲空間占用僅次于SG。PG底層數(shù)倉采用列式存儲，并且采用了數(shù)據(jù)壓縮技術(shù)，即使存儲了兩份邊表，存儲空間占用依舊是最少的。

表3 存儲空間占用對比 Table 3 Comparison of storage space occupancy

4.3 翻譯正確性驗證

為了驗證PG 翻譯Gremlin 的正確性，本文在L1數(shù)據(jù)集上對不同類型的查詢語句進行驗證，結(jié)果如表4所示。正確性驗證分為6類，包括起始（S）、條件（C）、映射選擇（P）、擴展（E）、聚合（A）和修飾（M），與前文介紹的Gremlin 步驟分類對應(yīng)。每類查詢包含3 個語句，共計18 個。本文同時書寫了相同語義的Cypher 語句供N4 執(zhí)行，與HG 和N4 的結(jié)果交叉驗證。3 種圖數(shù)據(jù)庫的查詢結(jié)果相同，表明PG 的翻譯結(jié)果是正確的。

4.4 k 跳算法查詢時間

為了探究PG 的性能信息，本文選取了k跳（k-hop）算法進行測試。k跳算法是經(jīng)典圖查詢算法之一，從起點出發(fā)找出k層上與之關(guān)聯(lián)的節(jié)點數(shù)量。例如，當(dāng)k=2 時，對應(yīng)的Gremlin 查詢語句寫為g.V（ID）.out（）.out（）.dedup（）.count（）。

本節(jié)對 低k跳（k=1，2，3）和 高k跳（k=4，5，6）兩種類型進行了研究。使用前文所述所有優(yōu)化方法對PG 生成的SQL 查詢進行優(yōu)化，超時時間設(shè)置為300 s。與其他數(shù)據(jù)庫不同，TG 首先通過安裝（install）步驟預(yù)翻譯并優(yōu)化查詢，然后通過運行（run）步驟查詢安裝后的語句。對于確定模式的查詢來說這種優(yōu)化是有效的，一次安裝后可多次運行查詢，但對于臨時查詢來說，安裝過程顯著增加了查詢時間。如果僅考慮安裝后的查詢時間，TG 在大多數(shù)情況下都表現(xiàn)最優(yōu)。此外，由于TG 不開源也不支持查看查詢計劃，本文無法詳細(xì)分析安裝和運行期間執(zhí)行的操作，因此后文僅列出了TG 的實驗數(shù)據(jù)，不對查詢的結(jié)果進行分析和對比。

在低k跳實驗中，本文隨機選取了100 個有k度鄰居的點，記錄下幾何平均查詢時間，如表5 所示，其中嘆號加粗的數(shù)據(jù)表示超時的查詢個數(shù)。

當(dāng)k=1 時，即查詢當(dāng)前點的鄰居數(shù)量時，不同圖數(shù)據(jù)庫的平均查詢時間比較穩(wěn)定。PG、HG、NG、SG通過主鍵索引，N4 通過B 樹索引直接定位到對應(yīng)的節(jié)點。Twitter（T）數(shù)據(jù)集較大，N4 和NG 仍保持了相對穩(wěn)定的性能，其余圖數(shù)據(jù)庫性能都稍有降低?？偟貋砜?，N4、SG、NG 和PG 的查詢性能都優(yōu)于HG。

當(dāng)k=2 時，PG 和SG 將頂點和邊存儲在不同的表中，需要進行表JOIN 操作，但 PG 進行了數(shù)據(jù)的拆分和聚合，當(dāng)數(shù)據(jù)量小時性能較差，SG 在G 和T 數(shù)據(jù)集上生成的嵌套SQL 使優(yōu)化器錯誤地選擇了SORT MERGE JOIN，查詢性能最差。對于HG、NG 和N4來說，前兩者通過鍵值對將頂點和邊存儲在一起，后者用鏈表的形式將頂點和邊鏈接起來，在存儲空間上具有連續(xù)性，因此性能最好。

當(dāng)k=3時，G 數(shù)據(jù)集的結(jié)果較大（平均31 000 ms），N4、HG 和NG 都需要順序遍歷所有的結(jié)果，而PG 生成的多線程計劃可以分割JOIN 任務(wù)來并行處理，因此PG 更有優(yōu) 勢，相 比N4 和NG 有1.27 和5.88 倍的性能提升。由于SG 需要JOIN 多張主從頂點表和邊表，因此耗時最長。F 和J 數(shù)據(jù)集的結(jié)果并不大（平均692 ms、2.0×104ms），很難抵消PG 執(zhí)行JOIN 的開銷，因此性能表現(xiàn)最差。數(shù)據(jù)量最大的T 數(shù)據(jù)集上（平均結(jié)果2.2×107ms）也有類似的表現(xiàn)，除PG 外其余圖數(shù)據(jù)庫都出現(xiàn)了超時的情況。

在高k跳實驗中，本文隨機選取了50 個有k度鄰居的點，幾何平均查詢時間如表6 所示，其中嘆號加粗的數(shù)據(jù)表示超時的查詢個數(shù)。

表6 高k 跳（k=4，5，6）查詢時間 Table 6 High k-hop（k=4，5，6）query time 單位：ms

當(dāng)k=4 時，由于遍歷的最終結(jié)果較大，HG 和SG在G、F 和T 數(shù)據(jù)集上都有超時。N4 的查詢計劃顯示需要進行先遍歷后去重最后聚合的操作，在這個過程中步數(shù)較多，較大的中間結(jié)果增加了遍歷的開銷，而且此時N4 無法準(zhǔn)確預(yù)估每步的中間結(jié)果數(shù)量（提示為0），因此也無法給優(yōu)化器提供更多的信息來做進一步優(yōu)化。PG 相比N4 有4.23、1.07 和3.07 倍的性能提升。

當(dāng)k=5 時，遍歷的結(jié)果繼續(xù)增大，如果沒有中間去重的優(yōu)化，中間結(jié)果的計算的壓力進一步增大。NG 的查詢計劃同樣顯示沒有對每步的中間結(jié)果進行去重操作，因此出現(xiàn)了多次超出內(nèi)存限制或RPC錯誤。類似地，HG 在全部的數(shù)據(jù)集上都出現(xiàn)了超時，N4 只在J 數(shù)據(jù)集上完成了測試，在T 數(shù)據(jù)集上出現(xiàn)了超出內(nèi)存的錯誤。PG 相較N4 有18.5 倍的性能提升。

當(dāng)k=6 時，只有PG 全部在合理時間內(nèi)完成所有的查詢?nèi)蝿?wù)，此時生成的查詢計劃可以將大量的中間數(shù)據(jù)進行劃分和去重，通過多線程同步進行，同時多步聚合操作進一步提高了聚合的效率，因此可以在合理的時間內(nèi)完成查詢?nèi)蝿?wù)。

4.5 規(guī)則優(yōu)化

根據(jù)PandaGraph 的翻譯過程，k跳算法是“頂點-邊-頂點”的JOIN 遍歷過程。通過前文的各種優(yōu)化規(guī)則可生成更優(yōu)的SQL 語句。本節(jié)把樸素翻譯生成的SQL 記為O0，SEMI JOIN 優(yōu)化記為O1，去除起點JOIN 記為O2，去除結(jié)束點JOIN 記為O3，去除中間頂點JOIN 記為O4，DISTINCT 下推記為O5。

在4 種數(shù)據(jù)集上隨機選取了50 個有6 度鄰居的起始點來研究不同優(yōu)化規(guī)則對查詢的性能影響，查詢的幾何平均時間如表7 所示，其中，超時用加粗嘆號進行標(biāo)注，O2～O5 的執(zhí)行時間下方標(biāo)注了相比前者優(yōu)化的加速比。通過使用不同的優(yōu)化方法，相比O1 優(yōu)化最好可以得到1.37 倍的性能提升。

表7 SQL 規(guī)則優(yōu)化下的查詢時間 Table 7 Query time of SQL rule optimization 單位：ms

在所有的數(shù)據(jù)集上，原始O0 查詢都無法在規(guī)定時間內(nèi)完成測試。這是因為不使用DISTINCT 的JOIN 的結(jié)果約為dˉk（其中dˉ是圖的平均度數(shù)），在k較大時結(jié)果十分龐大，需要較長的時間進行數(shù)據(jù)處理。O1 優(yōu)化就是一個去重過程，通過將INNER JOIN 轉(zhuǎn)化成SEMI JOIN，在JOIN 過程中只傳輸了去重的頂點，減少了中間結(jié)果傳輸，帶來了顯著效果。理論上O2～O5 操作都減少了JOIN 的步驟，降低了計算量和傳輸量，應(yīng)該帶來性能的提升，但不同的優(yōu)化方法在某些數(shù)據(jù)集上都出現(xiàn)了不同程度的性能下降，甚至O4 優(yōu)化在T 數(shù)據(jù)集上出現(xiàn)了42 次超時。以T 數(shù)據(jù)集上的O4 優(yōu)化為例，通過查看生成的查詢計劃，PG錯誤生成了Shuffle Join 計劃，帶來了大量的數(shù)據(jù)傳輸開銷。如果優(yōu)化器正常，可在其他數(shù)據(jù)集上獲得1.11、1.07、1.23 和1.04 倍的性能提升。綜合來看，最優(yōu)可獲得1.22、1.37、1.30 和1.13 倍的性能提升。這說明對不同的數(shù)據(jù)集，數(shù)倉的優(yōu)化器也起重要的作用，如果不能提供合適的統(tǒng)計信息并生成正確的執(zhí)行計劃，將會嚴(yán)重影響查詢性能。

4.6 表選擇優(yōu)化

為了探究遍歷過程中表選擇與查詢時間的關(guān)系，本節(jié)修改了上述k跳算法的遍歷方向，探究k=1或k=6 時選擇不同的表對性能的影響，將默認(rèn)不優(yōu)化的查詢記為O0，將修改了其中i個E_OUT 表為E_IN 表的查詢記為Oi。本文在4 種數(shù)據(jù)集上隨機選取了50 個有1 度或6 度鄰居的點，幾何平均查詢時間匯總?cè)绫? 和表9 所示，其中，括號內(nèi)數(shù)字為相比前者優(yōu)化的加速比。

表8 k=1 時表選擇優(yōu)化的查詢時間 Table 8 Query time of table selection optimization when k=1 單位：ms

表9 k=6 時表選擇優(yōu)化查詢時間 Table 9 Query time of table selection optimization when k=6 單位：ms

當(dāng)k=1 時，索引的性能對查詢時間有較大影響。當(dāng)不使用表優(yōu)化時，PG 的主鍵建立在FROM 鍵上，但需要對TO 鍵進行查詢，因此需要掃描全部的數(shù)據(jù)，隨著數(shù)據(jù)量的增加，查詢時間也隨之增加。如果使用主鍵為TO 的E_IN 表，則可以直接定位對應(yīng)的數(shù)據(jù)，減少了不必要的磁盤讀取。表選擇優(yōu)化在4 種數(shù)據(jù)集上有最少9.73 倍和最多74.39 倍的性能提升。由于訪問模式相同，使用E_IN 表時查詢的時間和反方向的k=1 跳查詢時間相差不大。

當(dāng)k=6 時，同樣可以帶來性能提升，這是因為多表JOIN 同樣需要對中間結(jié)果進行等值匹配，選擇合適的主鍵可以減少不必要的數(shù)據(jù)讀取，在4 種數(shù)據(jù)集上總計可獲得1.19 倍到1.43 倍的性能提升。

4.7 表結(jié)構(gòu)優(yōu)化

為了研究表主鍵選擇對查詢時間的影響，選取了以ID 為主鍵作為基準(zhǔn)，與PandaGraph 系統(tǒng)以FROM/TO 為主鍵進行對比。本節(jié)選取1～6 跳的查詢語句，在4 種數(shù)據(jù)集上選取了100 個有k度鄰居的點，查詢時間的幾何平均值見表10。

在低k跳時，PG 使用頂點作為主鍵可以獲得最多265 倍的性能提升，在高k跳時，PG 也能獲得最多2.7 倍的性能提升。這是因為在遍歷的過程中需要對中轉(zhuǎn)ID 進行定位，使用FROM/TO 為主鍵時可以通過主鍵索引命中對應(yīng)ID。在低k跳時，時間取決于ID 的定位時間，因此修改表主鍵后加速比較大，在高k跳時，主要依靠動態(tài)布隆過濾器進行過濾，修改主鍵可加速查詢，但性能提升不如低k跳時明顯。

5 結(jié)束語

本文設(shè)計并實現(xiàn)一套基于數(shù)倉的圖數(shù)據(jù)庫系統(tǒng)PandaGraph。PandaGraph 結(jié)合數(shù)倉的列式存儲特性，在兼顧高效圖查詢的同時，降低導(dǎo)入時間，減少空間占用，并提出一種Gremlin 語言翻譯SQL 的方法，在保持原有圖查詢應(yīng)用兼容性的前提下高效完成圖查詢。實驗結(jié)果表明，PandaGraph 在經(jīng)典的k跳算法中相較現(xiàn)有專有圖數(shù)據(jù)庫可獲得18.5 倍的查詢性能提升。下一步擬提出更加完備的Gremlin代數(shù)規(guī)則，實現(xiàn)復(fù)雜語句的翻譯和優(yōu)化，同時對數(shù)倉的底層數(shù)據(jù)結(jié)構(gòu)進行優(yōu)化，提高低k跳的查詢效率。