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

郭家鼎，王 鵬

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

0 概述

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

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

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

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

1 相關(guān)工作

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

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

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

1.2 圖存儲(chǔ)模式

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

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

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

1.3 圖查詢翻譯

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

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

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

2 PandaGraph 系統(tǒng)

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

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

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

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

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

2.2.1 頂點(diǎn)表映射

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

圖2 頂點(diǎn)表存儲(chǔ) Fig.2 Vertex table storage

2.2.2 邊表映射

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

圖3 邊表存儲(chǔ) Fig.3 Edge table storage

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

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

3.1 查詢翻譯

3.1.1 Gremlin 基礎(chǔ)

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

表1 Gremlin 常見(jiàn)步驟分類(lèi)及含義 Table 1 Gremlin common step classification and meanings

依據(jù)步驟的作用，本文將常見(jiàn)的Gremlin 步驟分為起始、條件、擴(kuò)展、映射選擇、聚合和修飾6 類(lèi)。后續(xù)將根據(jù)Gremlin 步驟的分類(lèi)不同，根據(jù)基本步驟的特點(diǎn)進(jìn)行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（）步驟選擇了所有頂點(diǎn)，hasLabel 和hasId 步驟選擇了id 為1，標(biāo)簽為Person的頂點(diǎn)。后續(xù)的out 步驟和has 步驟遍歷到j(luò)ava 編寫(xiě)的軟件，通過(guò)order by 步驟將軟件按id 和name 排序，并最終根據(jù)limit 和valueMap 步驟輸出前兩個(gè)的id屬性和name 屬性。

3.1.2 翻譯概覽

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

圖4 PandaGraph 翻譯過(guò)程Fig.4 PandaGraph translation process

3.1.3 PandaNodeTree 生成

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

3.1.4 PandaTableTree 生成

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

算法1PandaTableTree 生成

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

3.1.5 SQL 翻譯

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

算法2SQL 生成

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

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

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

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

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

3.2.1 表選擇

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

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

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

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

3.2.2 JOIN 選擇

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

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

3.2.3 遍歷去除

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

1）起點(diǎn)去除。如果在遍歷的起點(diǎn)只需要ID 信息，那么可以省略對(duì)第一張頂點(diǎn)表的JOIN 操作，只需要對(duì)中間邊表和最終的頂點(diǎn)表進(jìn)行JOIN 操作。因?yàn)橹虚g邊表的FROM 或TO 字段已經(jīng)存儲(chǔ)了頂點(diǎn)的ID 信息，此時(shí)的遍歷操作可簡(jiǎn)化如下：

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

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

遍歷去除過(guò)程可見(jiàn)算法3。

算法3遍歷去除

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

3.2.4 DISTINCT 下推

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

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

算法4DISTINCT 下推

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

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

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

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)置與實(shí)驗(yàn)數(shù)據(jù)

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

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

表2 實(shí)驗(yàn)數(shù)據(jù)集 Table 2 Experiment datasets

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

數(shù)據(jù)導(dǎo)入時(shí)間對(duì)比如圖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)入時(shí)間對(duì)比Fig.5 Comparison of data import time

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

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

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

表3 存儲(chǔ)空間占用對(duì)比 Table 3 Comparison of storage space occupancy

4.3 翻譯正確性驗(yàn)證

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

4.4 k 跳算法查詢時(shí)間

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.6 表選擇優(yōu)化

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

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

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

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

當(dāng)k=6 時(shí)，同樣可以帶來(lái)性能提升，這是因?yàn)槎啾鞪OIN 同樣需要對(duì)中間結(jié)果進(jìn)行等值匹配，選擇合適的主鍵可以減少不必要的數(shù)據(jù)讀取，在4 種數(shù)據(jù)集上總計(jì)可獲得1.19 倍到1.43 倍的性能提升。

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

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

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

5 結(jié)束語(yǔ)

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