基于數據倉庫的典型圖查詢處理技術

郭家鼎，王 鵬

（1.復旦大學 軟件學院，上海 200438；2.復旦大學 計算機科學技術學院，上海 200438）

0 概述

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

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

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

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

1 相關工作

1.1 標簽屬性圖模型

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

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

1.2 圖存儲模式

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

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

現有的基于結構化存儲的圖查詢系統要么沒有對底層存儲結構修改，只完成了元數據映射關系，要么基于行式事務型數據庫進行設計，簡單地將圖數據模式映射到存儲引擎上，沒有考慮到列式存儲特點和圖查詢語句的特點。因此，如何在列式數倉上設計合理的存儲結構是一個重要挑戰。

1.3 圖查詢翻譯

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

研究人員在圖查詢語言翻譯SQL 方面進行了研究。SQLGraph［19］提供了一系列翻譯的原語模板，將 Gremlin 步驟組裝成SQL 語句，但生成的SQL 為多層嵌套，不方便調試和閱讀，而且沒有對生成的SQL進行深入優化。Cytosm［22］是將另一種流行的圖查詢語言Cypher 轉換成SQL 的中間件，它依賴圖拓撲在數據上構建模式，將Cypher 路徑表達式切分成一系列rOCQ 結構，結合模板生成SQL。

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

2 PandaGraph 系統

2.1 系統架構

結合數倉在數據分析上的優勢，并實現圖數據庫的查詢功能，本文設計了一套基于數倉的圖數據庫系統PandaGraph，從上到下分別為查詢層、計算層和存儲層，如圖1 所示。

圖1 PandaGraph 系統架構Fig.1 PandaGraph system architecture

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

2.2 圖結構與存儲表映射

2.2.1 頂點表映射

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

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

2.2.2 邊表映射

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

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

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

3 PandaGraph 查詢翻譯和優化

3.1 查詢翻譯

3.1.1 Gremlin 基礎

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

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

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

3.1.2 翻譯概覽

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

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

3.1.3 PandaNodeTree 生成

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

3.1.4 PandaTableTree 生成

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

算法1PandaTableTree 生成

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

3.1.5 SQL 翻譯

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

算法2SQL 生成

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

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

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

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

3.2 基于規則的優化

3.2.1 表選擇

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

本文記遍歷擴展步驟為ε，擴展的表名和方向用下標表示，如ε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）將不同的表依據條件等值拼接，符合圖上遍歷的定義。但對于g.V（）.out（）.dedup（）.count（）等類似的查詢，如果滿足：1）只在最終步驟的輸出結果；2）中間重復結果需要去除，則可以使用半連接（SEMI JOIN）進行替代。等值連接根據匹配的數量重復返回多次，而半連接僅返回某個表的元組且最多返回一次，可以傳輸更少的元組，帶來更高的查詢效率。out 遍歷可以優化如下：

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

3.2.3 遍歷去除

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

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

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

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

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

算法3遍歷去除

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

3.2.4 DISTINCT 下推

在遍歷的過程中有時需要對最終結果進行去重，如果只在最后一步去重，中間遍歷結果的重復數據增加了數據傳輸的開銷，也增加了JOIN 的表構建和探測的時間。因此，當遍歷的某一步需要進行去重操作時，可以將該步的去重操作下推到之前的所有遍歷步驟中：

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

算法4DISTINCT 下推

3.3 翻譯優化完備性和正確性討論

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

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

4 實驗與結果分析

4.1 實驗設置與實驗數據

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

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

表2 實驗數據集 Table 2 Experiment datasets

4.2 數據導入和存儲

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

圖5 數據導入時間對比Fig.5 Comparison of data import time

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

圖6 數據導入時間分解Fig.6 Data import time breakdown

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

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

4.3 翻譯正確性驗證

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

4.4 k 跳算法查詢時間

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

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

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

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

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

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

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

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

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

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

當k=6 時，只有PG 全部在合理時間內完成所有的查詢任務，此時生成的查詢計劃可以將大量的中間數據進行劃分和去重，通過多線程同步進行，同時多步聚合操作進一步提高了聚合的效率，因此可以在合理的時間內完成查詢任務。

4.5 規則優化

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

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

表7 SQL 規則優化下的查詢時間 Table 7 Query time of SQL rule optimization 單位：ms

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

4.6 表選擇優化

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

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

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

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

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

4.7 表結構優化

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

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

5 結束語

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