分布式資源描述框架數據管理系統查詢性能評價

馮 鈞，王秉發，陸佳民

（河海大學計算機與信息學院，南京 211100）

0 引言

資源描述框架（Resource Description Framework，RDF）作為萬維網聯盟（World Wide Web consortium，W3C）定義的一種展示、共享和連接語義網絡數據的標準數據模型，已經被廣泛用于各種數據科學應用中。隨著RDF 數據規模的日益增長，集中式存儲已經難以滿足存儲和查詢處理需求，需要高性能的分布式RDF 數據管理系統對大規模的RDF 數據進行管理和重用。

現有的分布式RDF 系統通過一個無共享的集群實現對大規模RDF 數據的存儲和管理［1］，采用基于連接的方法（Join-based）和基于圖匹配（Graph-matching Based）的方法［2］進行SPARQL（Simple Protocol and RDF Query Language）［3］查詢計算。得益于關系數據庫技術的成熟性、健壯性和可擴展性，大量基于關系存儲模式的分布式RDF 系統應運而生。按照系統的執行模型不同，本文中將這些系統分為：基于主存（Random Access Memory，RAM）的系統和基于Spark 的系統。

現有的基于RAM 的系統和基于Spark 的系統僅針對高選擇性的小直徑查詢進行了優化，可以高效地響應小直徑查詢；但是SPARQL 查詢是一個連接密集型查詢，據研究顯示，用戶傾向請求越來越復雜的交互式查詢，交互式DBpedia 的SPARQL 查詢日志中，最高可達10 個連接，而生物醫學領域的分析查詢甚至包括50 個以上的連接［4］。因此，有必要針對交互式查詢中涉及的多連接復雜型查詢進行優化。為了有效提高分布式RDF 系統的查詢性能，現有的研究主要從以下兩個方面進行優化［5］：1）優化關系存儲模式；2）優化SPARQL 到SQL（Structured Query Language）的查詢轉化。通過減少查詢處理期間連接操作數量、輸入數據大小和中間結果大小［6］，提升分布式SPARQL 查詢性能。

本文的主要工作包括：1）詳細調研了現有的基于RAM和基于Spark 的系統在分布式SPARQL 查詢上的相關工作；2）將查詢準確性作為分布式SPARQL 查詢的評價指標，支持SPARQL 查詢結果的持久化，實現了查詢結果的校驗；3）結合查詢準確性、查詢響應時間這兩個評價指標，對8 個代表系統的查詢性能進行了廣泛的實驗評估；4）討論分析當前分布式SPARQL 查詢的局限性，展望了未來可能的研究方向。

1 相關理論

1.1 SPARQL查詢

SPARQL［3］是W3C 提出的一種標準查詢語言，以實現對大規模RDF 數據的查詢與檢索。SPARQL 查詢的基本組成單元是三元組模式，一組三元組模式構成了基本圖模式（Basic Graph Pattern，BGP），其形式化定義如定義1 所示。

定義1三元組模式和基本圖模式。tpi={t|t∈(I∪V∪B)×(I∪V)×(I∪L∪V∪B)}，其中：I表示國際化資源標識符集，B表示空白節點集，L表示字面量集，V表示變量集，并且這四個集合互不相交。如果一個三元組是該集合中的元素，則該三元組稱為一個三元組模式tpi。，基本圖模式由一組三元組模式進行合取運算組成，因此也稱為合取查詢（Conjunctive Query）。

合取查詢本質上是在數據集上對一組經三元組模式選擇后的三元組進行連接運算，三元組模式選擇性［7］的形式化定義如定義2 所示。

定義2三元組模式選擇性。Sel(tpi，D)=，其中：tpi表示SPARQL 查詢Q 的三元組模式；D表示一個數據集；N為數據集D中三元組的總個數；Card(tpi，D)表示D中匹配三元組模式tpi的三元組個數。

SPARQL 查詢由基本圖模式組成，根據查詢圖的結構可將SPARQL 查詢分為三種基本形態：鏈型查詢、星型查詢和雪花型查詢以及由這三種基本查詢組合而成的復雜查詢［8］。SPARQL BGP 的直徑定義為最長路徑，即不考慮邊的方向，最長的三元組模式連通序列［9］。

1）鏈型查詢：對三元組模式間的主語（賓語）?賓語（主語）進行連接，其查詢圖結構如圖1 所示，連接變量在一個三元組中位于主語位置，在另一個三元組中位于賓語位置，鏈型查詢模式的直徑對應查詢模式中三元組模式的個數。

圖1 鏈型查詢圖結構示意圖Fig.1 Schematic diagram of chain query graph structure

2）星型查詢：對三元組模式間的主語?主語進行連接，其查詢圖結構如圖2 所示，連接變量位于主語位置，查詢直徑為1。星型查詢模式在SPARQL 查詢中經常出現，許多查詢處理器都針對這種工作負載進行了優化。

圖2 星型查詢圖結構示意圖示意圖Fig.2 Schematic diagram of star query graph structure

3）雪花型查詢：由短路徑連接的若干個星型查詢組合而成，其查詢圖結構如圖3 所示，該查詢圖由兩個星型查詢圖組合而成，其查詢直徑為3。

圖3 雪花型查詢圖結構示意圖Fig.3 Schematic diagram of snowflake query graph structure

4）復雜型查詢：由三種基本查詢模式組合而成的復雜查詢，其查詢圖結構如圖4 所示，該查詢圖由兩個星型查詢子圖和一個鏈型查詢子圖組合而成，其查詢直徑為4。

圖4 復雜型查詢圖結構示意圖Fig.4 Schematic diagram of complex query graph structure

1.2 關系存儲模式

現有的基于關系的分布式RDF 系統中，涉及的關系存儲模式包括：

1）垂直劃分（Vertical Partitoning，VP）［10］：按照謂語創建關系模式為（subject，object）的表，將相同謂語的三元組的主語、賓語存入同一張表中，表的總數量為謂語的數量。

2）擴展垂直劃分（Extended VP，ExtVP）［8］：預先對具有連接相關性的兩個垂直劃分表進行半連接計算，當相應的擴展垂直劃分表對原始的垂直劃分表縮減量達到了設定的閾值時才物化這些表。

3）寬屬性表（Wide Property Table，WPT）［11］：按照主語創建關系模式為（subject，property1，…，propertyn）的表，即將同類主語存入一張表中。由于不同主語的謂語集合也存在差異，容易存在空值問題。此外，寬屬性表還存在多值屬性存儲問題。

4）逆寬屬性表（inverse Wide Property Table，iWPT）［12］：按照賓語創建關系模式為(，object)的表，即為數據集中的每個屬性包含一個不同的列，將一個賓語的所有信息存入同一行。因此，基于賓語?賓語的連接計算可以通過對iWPT 進行一次掃描操作獲取。

5）寬屬性表?逆寬屬性表內連接（inner join between WPT and iWPT，jWPT-inner）：預先將寬屬性表和逆寬屬性表進行內連接運算，jWPT-inner 表每一行包含一個資源一跳上的所有信息。

6）六重索引（Sextuple Indexing）［11］：以三元組〈主語，謂語，賓語〉的全排列方式對應地創建主語?謂語?賓語（spo）、主語?賓語?謂語（sop）、謂語?主語?賓語（pso）、謂語?賓語?主語（pos）、賓語?主語?謂語（osp）、賓語?謂語?主語（ops）六張表。六重索引主要分為兩組：一組是主語索引集，包括spo表、sop 表和pso 表；另一組是賓語索引集，包括osp 表、ops 表和pos 表。

關系模式設計［13］對分布式SPARQL 查詢效率起著至關重要的作用，不同的關系模式設計不僅產生不同的物理數據分區，還意味著相同SPARQL 查詢的不同SQL 轉換。因此，通過優化關系存儲模式，可以有效地減少連接操作數量、輸入數據大小和中間結果大小，從而提高SPARQL 查詢處理的效率。

1.3 SPARQL到SQL的查詢轉化

基于連接的SPARQL 查詢計算將每個圖模式轉化為等效的SQL 表達式，并在單張表或多張表上使用連接操作組合每次迭代的結果。在現有的分布式RDF 系統中，SPARQL 查詢是通過三元組模式進行計算，一個查詢執行規劃可以看作三元組模式在變量上的連接。但是由于SPARQL 查詢是連接密集型查詢，并且SPARQL 連接計劃的狀態空間的大小又與連接數量呈指數相關，在這樣的空間下，搜索最優的查詢規劃是一個NP（Non-deterministic Polynomial）困難問題［14］。

現有的分布式SPARQL 查詢優化使用確定的估計器作為查詢規劃的評估指標［15］，對SPARQL 連接狀態空間中所有可能的查詢規劃進行探索，通過代價評估確定最優的查詢規劃。現有的兩種主流的搜索策略為：基于動態規劃的查詢規劃和基于啟發式的查詢規劃［16］。

基于動態規劃的查詢規劃的核心思想是在搜索連接計劃時，根據預先計算的統計信息選擇代價估計最小的作為最優查詢計劃，并通過合并冗余狀態，減小搜索空間。

基于啟發式的查詢規劃的核心思想是通過一定的搜索策略對部分狀態空間進行啟發式搜索，與動態規劃方法相比，它能節約大量的搜索時間，但是確定的查詢規劃不一定是最優的。

2 基于Spark的系統

S2RDF（SPARQL on Spark for RDF）［8］使用垂直劃分和基于半連接預處理的擴展垂直劃分相結合的混合關系存儲模式進行存儲。在數據加載階段，S2RDF 通過選擇性閾值物化部分垂直劃分數據表之間的左半連接結果并存儲在關系數據表中，減小了連接操作時輸入數據的大小。在查詢處理階段，S2RDF 首先根據統計信息為基本圖模式中的每一個三元組模式選擇查詢候選表，接著通過Jena ARQ（a SPARQL Processor for Jena）將SPARQL 查詢解析到相應的代數樹上，應用基本的代數優化后生成等效的Spark SQL 表達式，然后通過經驗知識進行連接順序優化，避免連接懸掛三元組模式，從而避免了笛卡兒積，減小了中間連接結果大小，有效地提高了查詢效率。S2RDF 通過預先計算三元組模式中變量的半連接結果，有效地提高了查詢性能，但導致磁盤占用空間大、數據加載時間長等問題。此外，優化查詢連接時，S2RDF 假設較小的連接輸入通常導致較小的連接輸出，但這個假設并不是完全正確的。

SPARQLGX［17］使用垂直劃分模式進行RDF 數據存儲，基于連接選擇性進行連接順序優化。在查詢處理階段，SPARQLGX 對基本圖模式的每個查詢模式分別進行處理，從磁盤中讀取相關數據并使用常量進行過濾；然后尋找具有相同變量的三元組模式進行連接，通過中間結果的統計信息，優化連接順序；最終將SPARQL 查詢片段中的每個操作符轉化為符合Spark 的Scala 命令序列，通過Spark API（Application Programming Interface）直接執行查詢。Li 等［18］在SPARQLGX 的基礎上進行改進，提出了一種基于語義連接信息鏈的查詢優化方法SparkIlink。SparkIlink 在查詢處理階段，首先根據變量對三元組模式進行映射，然后通過循環遍歷映射圖搜索具有值交集的映射并將其加入語義信息鏈，最后根據語義信息鏈的順序和連接三元組信息確定查詢連接順序，通過Spark API 直接執行查詢。SparkIlink 通過語義連接信息鏈優化連接順序，減小了中間連接結果大小，在SPARQLGX 的基礎上有效提高了鏈型、星型和雪花型這三種基本查詢類型的查詢性能。

PRoST（Partitioned RDF on Spark Tables）［19］采用垂直劃分和寬屬性表進行混合存儲。查詢處理階段，PRoST 將SPARQL 查詢轉化為連接樹，根據連接樹節點的優先級，自底向上進行計算。其核心思想是將主語相同的三元組模式歸為一組，存入根節點，使用屬性表進行查詢；將其余的節點存入葉子節點，使用垂直劃分表處理。PRoST 通過寬屬性表減少了連接操作的數量，通過數據加載階段的統計信息優化查詢連接順序，有效地減小了中間結果的大小，從而提高了查詢效率。

Hassan 等［20］在2018 年提出了兩種新的關系存儲模式VPExp 和3CStore。VPExp 模式根據賓語的顯式類型信息拆分垂直劃分表，從而最小化查詢計算時輸入數據的大小；但是它的適用范圍僅針對謂詞為“rdf_type”且賓語為字面量的三元組模式。3CStore 模式存儲三元組模式間相關性（除賓語?賓語相關）的預連接計算結果，從而減少了查詢處理時的輸入數據大小和連接操作數量。在查詢處理階段，根據查詢編譯器將SPARQL 查詢解析到相應的代數樹中，并將相應的關系存儲模式轉化為等效的SQL 表達式進行查詢計算。2019 年Hassan 等［21］又在PRoST 的基礎上，提出了一種名為“子集寬屬性表”（Subset Property Table，SPT）的關系存儲模式，它通過顯式地避免存儲空值和采用嵌套數據結構存儲多值屬性的方式，有效地解決了傳統屬性表中所存在的空值和多值問題；通過拆分寬屬性表，最小化查詢連接時輸入數據的大小，降低了連接的復雜度。SPT+VP 中采用子集寬屬性表和垂直劃分相結合的混合存儲模式存儲數據，在查詢處理階段，與PRoST 的思想一致，使用子集寬屬性表處理星型查詢，使用垂直劃分表處理其他查詢；通過自定義的查詢編譯器將SPARQL 轉化為Spark SQL，根據三元組模式中常量的數量和數據集統計信息設定查詢連接的優先級，從而優化查詢。

Chawla 等［5］提出了HyPSo，它采用垂直劃分和哈希劃分相結合的混合關系存儲模式進行數據存儲。HyPSo 首先對初始RDF 數據集進行垂直劃分，然后對垂直劃分后的結果集進行基于主語的哈希劃分，這種混合劃分方式有效地減少了處理星型查詢時所需的通信開銷，同時又減少了連接操作的數量和數據搜索空間，從而優化了星型查詢。

Schievelbein 等［12］提出了一種名為“逆屬性增強的寬屬性表”（iWPT）的關系存儲模式，并利用相同RDF 數據圖的多個寬屬性表擴展表來進行混合存儲。其核心思想是根據不同關系模式構造中間抽象樹來表示SPARQL 查詢，以最小化查詢計算所需要的連接操作數量。實驗結果表明，采用寬屬性表、逆寬屬性表和寬屬性表?逆寬屬性內連接（WPT+iWPT+jWPT-inner）的混合存儲模式，優化了除鏈型查詢外的所有查詢類型的查詢性能；但是，使用混合存儲進行存儲時，需要權衡查詢計算中連接操作的數量與所有查詢候選表的行數。

3 基于RAM的系統

Gurajada 等［22］提出了內存型分布式RDF 系統TriAD（Triple Asynchronous Distributed），它是一種基于內存的分布式RDF 系統，使用六重索引模式進行RDF 數據存儲，通過MPI（Message Passing Interface）協議進行SPARQL 查詢處理。在數據預處理階段，TriAD 在主節點上建立一個全局概述圖，并將其水平劃分為若干塊分發到從節點上。在查詢處理階段，首先在主節點上對概述圖進行圖匹配獲取查詢圖中每個三元組模式的候選三元組，然后在從節點上對數據圖上的候選三元組進行連接操作獲得最終解。采用自底向上的動態規劃算法確定概要圖的最優探索順序和針對六重索引的最優三元組模式連接順序，使用灌木叢計劃來限制動態規劃搜索樹的形狀，從而減少搜索空間。TriAD 的查詢性能始終比集中式RDF 引擎性能好兩個數量級；但是，TriAD 中大量的索引導致數據冗余、存儲空間消耗大、數據更新的一致性維護代價大等問題。

Harbi 等［23］提出了內存型分布式RDF 系統AdPart，它通過基于主語的哈希劃分方式實現RDF 數據的初始劃分，通過分層熱圖監控查詢工作負載，設定頻繁閾值標識頻繁模式，使用頻繁模式指導RDF 數據進行增量重劃分。在查詢處理階段，采用動態規劃算法設計查詢連接順序，使用右深度樹約束搜索樹形狀，基于局部性哈希和自適應劃分加速SPARQL 查詢。AdPart 通過掃描索引獲得子查詢的局部匹配結果，利用分布式半連接（Distributed Semi-Join，DSJ）算法獲得整個子查詢的計算結果。由于數據駐留在內存中并且是哈希索引的，可以利用局部性哈希來并行處理星型查詢，最小化了查詢計算期間的通信代價。此外，使用頻繁模式驅動數據進行增量重劃分，實現了對系統對查詢工作負載的自適應性，有效地提高了分布式SPARQL 的查詢性能；但是，AdPart 存在查詢準確性較低，查詢計算過程中發生內存溢出等問題。

Potter 等［24］提出了內存型分布式RDF 系統RDFox，它使用圖劃分的方式進行數據存儲，使用哈希索引在內存中索引數據。在查詢處理階段，使用索引嵌套循環連接作為分布式連接算法，讓集群節點在數據分區上并行計算查詢。RDFox在查詢處理期間動態交換數據，使用流量控制機制限制分布式連接計算中連接中間結果的物化，從而大大限制查詢計算期間的內存占用。RDFox 通過動態數據交換和流量控制機制，使得RDFox 在查詢響應時間、網絡通信和內存使用方面優于其他方法。此外，通過在分布式連接算法中限制內存使用，成功響應了復雜鏈型查詢。但是，RDFox 在低選擇性的復雜型查詢上的性能仍然較差。

4 實驗設置

4.1 對比系統

Abdelaziz 等［25］對12 個具有代表性的分布式RDF 系統在不同數據集和查詢負載上進行了實驗評估，實驗結果表明AdPart 和TriAD 的查詢性能持續優于其他系統。因此，本文使用AdPart 和TriAD 作為基于RAM 的分布式RDF 對比系統。此外，由于AdPart 和TriAD 不能響應低選擇性的大直徑查詢，Potter 等［24］提出的RDFox 通過動態數據交換和流量控制機制成功響應了復雜型查詢，因此，將RDFox 也作為基于RAM 的對比系統。由于RDFox 未公開源代碼，所以本文中與RDFox 相關的實驗均采用了文獻中公布的結果。

此外，為了驗證不同關系存儲模式對查詢性能的影響，本文還將S2RDF、PRoST、WiW（WPT+iWPT）、C3W（WPT+iWPT+jWPT-inner）和C2WVP（WPT+iWPT+VP）作為對比系統。其中S2RDF 的選擇性閾值設定為0.25，WiW 采用屬性表和逆屬性表進行混合存儲，C3W 使用屬性表、逆屬性表和屬性表?逆屬性表的內連接表進行混合存儲，C2WVP 采用屬性表、逆屬性表和垂直劃分表進行混合存儲，這些系統都沿用PRoST 中的查詢執行器執行SPARQL 查詢計算。以上實驗對比系統的相關特征如表1 所示。

表1 實驗對比系統的相關特征Tab.1 Related characteristics of experimental systems for comparison

4.2 基準數據集和查詢集

基準數據集可以分為合成數據集和真實數據集［7］。真實數據集可以使用真實數據和用戶查詢日志對系統進行基準測試，但是真實數據集無法測試不同數據集大小和查詢工作負載下RDF 系統的可伸縮性。合成數據集利用生成數據，有助于測試不同數據集大小下系統的可伸縮性。本文中同時在合成數據集WatDiv（Waterloo SPARQL Diversity Test Suite）和真實數據集YAGO2（Yet Another Great Ontology version 2.0）上進行實驗。表2 中展示了十億規模下的WatDiv 數據集（WatDiv-1B）和YAGO2 數據集統計信息。

表2 實驗所使用數據集的統計信息Tab.2 Statistics of datasets used in experiments

WatDiv 基準［26］：加拿大滑鐵盧大學于2014 年提出的用于描述用戶實體相關信息的數據集，包括數據生成器和查詢生成器。WatDiv 查詢集由查詢器根據預定義的查詢模板生成。本文中的查詢集由基礎測試用例和增量鏈型測試用例組成。其中，基礎測試用例由20 個預定義的基礎類型查詢模板生成，根據查詢形狀可分為：鏈型（Ln）、星型（Sn）、雪花型（Fn）和復雜型（Cn）四類；增量鏈型測試用例由18 個增量鏈型（Incremental Linear，IL）查詢模板生成，根據三元組模式中主語類別分為：IL-1、IL-2 和IL-3 三類查詢，IL-1、IL-2 和IL-3 查詢分別由綁定的用戶、綁定的零售商以及未綁定的主語組成，每個查詢類型的直徑由5 增大為10。

YAGO2［27］：來源于多種語言的維基百科，包含WordNet、GeoNames 和其他數據源，其中包含1.5 億個三元組。據YAGO2 查詢日志顯示，有77%的三元組模式都涉及星型連接，平均每個查詢有1.8 個基于主語的連接。由于YAGO2是真實數據，沒有提供查詢基準，所以本文中仍然遵循文獻［23］中提出的四種代表性查詢類型。

4.3 評價指標

查詢響應時間：在各類查詢類型上的執行查詢處理的總時間，包括查詢編譯時間和查詢執行時間。

查詢準確率：在各類查詢類型上查詢結果正確查詢的個數與查詢總個數的比值。本文中支持將SPARQL 查詢結果持久化到Hadoop 分布式文件系統（Hadoop Distributed File System，HDFS）文件中，通過將查詢結果與基準結果進行校驗，從而客觀準確地對系統的查詢準確率進行定量評估。

4.4 實驗環境

搭建一個由10 個節點組成的無共享服務器集群，通過專用帶寬為1 Gb/s 的網絡進行連接。每個服務器運行Ubuntu 16.04 系統，有8 個vCPU、32 GB RAM 和512 GB 磁盤存儲空間，安裝Hadoop 2.7.1 和Spark 2.0.2，每個Spark 執行器都設置為20 GB 內存。

對每個查詢進行10 次評估，記錄每個系統報告的查詢計算時間，并計算每種查詢類型的查詢時間的幾何平均值（Geometric Mean，GM）。

5 實驗與結果分析

為了全面評估上述8 個分布式RDF 系統的查詢性能，本文中選擇了影響SPARQL 查詢性能的三個特征：查詢類型、查詢直徑以及數據集類型，對相關系統進行了實驗，并結合查詢響應時間和查詢準確性兩個指標對實驗結果進行分析。

5.1 查詢響應時間分析

5.1.1 不同查詢類型下的查詢效率

本組實驗使用WatDiv-1B 作為數據集，WatDiv 基礎測試用例作為查詢集，對各個系統在不同查詢類型下的查詢性能進行評估。表3 展示了各個系統在不同查詢類型的查詢響應時間。

表3 WatDiv基本查詢集上各系統的查詢響應時間對比Tab.3 Comparison of query time of different systems on WatDiv basic query set

實驗結果表明：1）不同查詢類型下的查詢時間差異明顯，基于RAM 和基于Spark 的系統在鏈型查詢、星型查詢上的查詢效率都優于雪花型查詢和復雜型查詢；2）基于RAM的系統在基礎測試用例下的查詢效率優于基于Spark 的系統三個數量級，在不到1 s 的時間內就可以響應10 億三元組的RDF 圖上的基準測試查詢；3）對于基于Spark 的系統而言，不同的關系存儲模式對于查詢效率也有顯著的影響。

下面結合實驗結果對各個系統在不同查詢類型下的查詢響應時間進行具體分析。基于RAM 的系統在基礎測試用例下表現出了優越的查詢性能，主要原因是基礎查詢用例都是小直徑的高選擇性查詢，查詢連接過程中的中間結果較小，而基于RAM 的系統在查詢過程中將數據駐留在內存中，并且通過異步執行的方式進行并行計算，有效提高了查詢效率，而基于Spark 的系統受限于Spark 同步執行查詢計劃的限制，減少了查詢計算的并行性，極大影響了查詢性能。

對于雪花型查詢（Fn），其涉及的基本查詢圖模式中只包含主語?賓語連接、主語?主語連接。C3W 在該類查詢上的性能優于其他基于Spark 的系統，主要是該系統中預先對屬性表和逆屬性表進行了內連接計算，通過一次表掃描就可以獲得一個資源一跳上的所有信息，從而最大限度地減少了連接操作數量，縮短了查詢時間。WiW 在查詢F4 中的性能顯著低于其他基于Spark 的系統，主要由于在該類查詢中涉及屬性表和逆屬性表的連接操作，從而導致查詢效率的降低。

對于復雜型查詢（Cn），查詢C1 和C2 包含四種不同的連接模式，查詢C3 只包含低選擇性的主語?主語連接。基于RAM 的系統在該類查詢上的性能比基于Spark 的系統高出兩個數量級，對于C3 查詢RDFox 和TriAD 可以快速響應，但AdPart 要比它們慢兩個數量級。PRoST、WiW 以及C2WVP在C1 和C3 查詢上的性能大致相當。S2RDF 在C3 查詢上由于涉及大量的連接操作，查詢性能顯著降低。而C3W 由于jWPT-inner 表中存在較多的行數，查詢的性能受限于輸入數據大小，因此無法響應C2 查詢。

5.1.2 不同查詢直徑下的查詢效率

WatDiv 基礎測試用例可以有效地評估系統對于不同復雜度的查詢工作負載的效率，但是基礎測試用例中絕大多數查詢的查詢直徑都很小，因此為了測試實驗系統在不同查詢直徑下的查詢性能，本組實驗中使用了由Sch?tzle 等［8］提出的增量鏈型查詢集進行實驗，實驗結果如表4 所示。

表4 WatDiv增量鏈型查詢集上各系統的查詢響應時間對比Tab.4 Comparison of query response time of different systems on WatDiv incremental linear query set

實驗結果表明：1）基于RAM 的系統在低選擇性的增量鏈型查詢IL-1 和IL-2 的效率高出基于Spark 的系統四個數量級；2）各個系統的查詢時間與查詢直徑大小未呈明顯關系；3）RDFox 和AdPart 在IL-1 和IL-2 上的查詢效率比TriAD 高出三個數量級；4）不同的關系存儲模式在不同查詢直徑下的查詢效率也存在較大影響；5）基于RAM 對于低選擇性查詢IL-3 的伸縮性差，AdPart 和TriAD 不能響應IL-3 查詢，而RDFox 在此類查詢上的效率也低于基于Spark 相關系統一個數量級。

下面結合查詢特征進行具體分析，由于IL-1 和IL-2 都是主語綁定的高選擇性鏈型查詢，查詢結果數量較小，因此與基礎測試用例下的結果基本類似，基于RAM 的系統查詢性能仍優于基于Spark 的系統。此外，各個系統的查詢時間與查詢直徑大小也未呈現明顯關系。例如，在S2RDF 中IL-2-5雖然是IL-2 中其他查詢類型的子類型，但是其查詢效率卻是最低的，這表明增大查詢直徑甚至可以提高查詢效率。

對于IL-1-n和IL-2-n查詢，RDFox 和AdPart 的查詢性能比TriAD 高出三個數量級，主要原因是RDFox 和AdPart 使用哈希索引在內存中索引數據，使用異步的方式沿著查詢計劃并行運行多個連接操作，并且在進行連接時只交換投影連接列的唯一值，通過提高查詢的并行性大大提高了查詢性能。而TriAD 通過六重索引數據，使用摘要圖對查詢搜索空間進行剪枝，但當執行分布式合并連接（merge join）和哈希連接（hash join）時，TriAD 需要在集群節點上對連接關系進分片，因此在并發執行連接時產生較大且不必要的中間結果，從而影響了查詢效率。PRoST、WiW 以及C2WVP 在IL-1-n和IL-2-n查詢上的性能大致相當，而C3W 由于jWPT-inner 表中存在較多的行數，查詢的效率受限于數據大小，查詢效率顯著降低。S2RDF 在選擇性閾值設定為0.25 的情況下，查詢效率低于除C3W 外的其他混合存儲模式。

對于IL-3-n型查詢，由于它是非選擇性的鏈型查詢，查詢連接的中間結果很大，返回的查詢結果數量也比其他查詢多出幾個數量級。AdPart 和TriAD 未能響應此類查詢，主要原因是這兩個系統中哈希連接的內存使用由中間結果大小決定，極大限制了系統的伸縮性，因此對于高選擇性的查詢這兩個系統都發生了內存溢出。而RDFox 通過使用索引嵌套循環連接并通過流量控制機制限制內存的使用，從而成功響應IL-3-n查詢。對于基于Spark 的系統而言，通過內置的調度策略對集群資源進行調度，有效避免了內存溢出的發生，因此S2RDF、PRoST、WiW、C3W 以及C2WVP 在IL-3-n型查詢上的效率更高。

5.1.3 不同數據集下的查詢效率

除了使用合成數據集WatDiv-1B 外，本組實驗還使用了真實數據集YAGO2 和用戶查詢日志進行對比實驗。由于未能在TriAD 和AdPart 上完成數據集加載，因此這兩個系統采用文獻［23］中發布的實驗結果作為參照結果，而RDFox 因為無法復現，未對其進行相關實驗，詳細實驗結果如表5 所示。

表5 YAGO2查詢集上各系統的查詢響應時間對比Tab.5 Comparison of query response time of different systems on YAGO2 query set

實驗結果表明：1）YAGO2 上的查詢結果總體與WatDiv數據集上的結果一致，對于YAGO2 上的四種基準查詢，AdPart 的效率比基于Spark 的系統高出兩個數量級，比TriAD高出一個數量級；2）對于基于Spark 的系統而言，不同存儲模式在YAGO2 上的查詢效率也存在明顯差別，C2WVP 除了在Y2 查詢上都取得了最佳性能。

下面針對YAGO2 數據集下各系統在各類查詢上的查詢響應時間進行具體分析。對于Y1 和Y2 查詢主要涉及主語?賓語連接，AdPart 在不需要通信的情況下就可以處理Y1 和Y2 中的大多數連接，因此AdPart 比TriAD 性能更優越。而Y3 和Y4 查詢中包含賓語?賓語連接，因此包含逆屬性表模式的WiW 和C2WVP 系統在這兩類查詢上的效率明顯高于其他幾種混合關系存儲模式。C3W 雖然也采用了逆屬性表模式，但是在查詢時由于jWPT-inner 表中存在較多的行數，查詢的效率受限于輸入數據大小。

5.2 查詢準確性分析

本組實驗對比分析不同系統（不含RDFox）的SPARQL查詢準確性，各個系統在不同查詢維度上的查詢準確率如表6 所示。實驗結果表明，S2RDF、AdPart 在SPARQL 查詢上存在著較大的查詢誤差。從表6 可知，在WatDiv 基礎測試用例上，S2RDF 的平均準確率為82%、AdPart 僅為70%，主要原因是這兩個系統在查詢計算過程中出現了大量重復答案，而其余系統在基本查詢類型上未出現錯誤。對于WatdDiv 增量鏈型查詢而言，S2RDF 在增量鏈型查詢IL-1、IL-2、IL3 上出現了查詢錯誤，AdPart 在IL-2 上出現錯誤答案，而TriAD 和AdPart 由于內存溢出未能響應IL-3 查詢，因此在IL-3 上的準確率為0。對于YAGO2 基礎測試用例上而言，由于YAGO2上的查詢都為高選擇性的查詢，因此上述7 個系統都未出現查詢錯誤。

表6 不同SPARQL查詢下各系統的查詢準確率 單位：%Tab.6 Accuracy of different SPARQL queries in different systems unit：%

綜合不同維度上的實驗結果可以得出以下結論，現有系統僅在高選擇性的小直徑查詢上具有較高的查詢準確性，對于低選擇性的大直徑查詢存在較大的查詢誤差。

5.3 實驗總結

本文通過四組對比實驗對8 個典型的分布式RDF 系統的查詢性能進行了系統的評估。實驗結果顯示，上述實驗系統針對鏈型查詢和星型查詢進行了優化，但是對于分布式SPARQL 查詢的伸縮性差，不能動態適應查詢工作負載的變化，部分系統甚至還存在查詢準確性的問題。基于RAM 的系統可以高效地響應高選擇性的小直徑查詢，但是對于低選擇性的大直徑查詢性能低甚至無法響應。基于Spark 的系統則在低選擇性的大直徑查詢上具有較高的查詢性能，但是對于高選擇性的小直徑查詢的性能差。但總的來說，現有的系統難以滿足真實應用中對低選擇性大直徑復雜查詢的需求。

此外，經實驗論證上述系統還存在以下問題：

1）在現有的關系存儲模式中存在著數據傾斜、表掃描時間過長的問題，例如在WatDiv-1B 數據集對應的VP 表中，最大的VP 表中含有4.5 億個三元組，而最小的VP 表僅含有240 個三元組。嚴重的數據傾斜導致了SPARQL 查詢計算的連接復雜度過高，對大表的掃描時間過長，同時還導致了集群節點之間的通信代價增大，制約了分布式SPARQL 查詢的性能。

2）上述的基于Spark 的系統依賴RDF 特定的概要統計信息或特征集的方式進行基數評估，采用貪婪搜索的方式規劃查詢計劃；基于RAM 的系統依賴基于摘要圖進行基數評估，采用動態規劃的方式搜索查詢計劃。但是這些系統中的基數評估方法依賴條件獨立性假設、函數依賴性假設或者一致性假設，但是這些假設并非總是成立，限制了基數評估的準確性，導致了查詢優化器生成次優的查詢連接計劃，從而限制了分布式SPARQL 的查詢性能。

3）上述系統在SPARQL 查詢規劃階段，采用貪婪搜索或者動態規劃的方式規劃查詢計劃，選擇代價估計最小的作為最優查詢計劃，但是對于大直徑的復雜型查詢，搜索SPARQL 查詢連接狀態空間的時空復雜性過高，導致查詢編譯時間極大。在查詢規劃過程中，除了TriAD 外，均將查詢計劃構造為左深度樹或右深度樹，極大限制了SPARQL 查詢計算的并行度，從而影響了分布式SPARQL 查詢效率。

6 結語

本文系統地闡述了現有的基于RAM 和基于Spark 的分布式RDF 系統的查詢優化方法，使用了大規模的合成數據集和真實數據集對具有代表性的8 個系統進行了廣泛的實驗評估，并對實驗結果進行了全面的總結分析。

通過本文的實驗分析與比較，可以看出目前分布式SPARQL 查詢優化上已經取得了一定的成果；但是仍然存在著查詢效率低、查詢準確性差和伸縮性差等局限性，在垂直領域的應用上仍面臨著許多問題和挑戰。因此，未來的研究方向包括：

1）探索面向垂直領域應用的關系存儲模式，針對垂直領域查詢需求對RDF 數據進行高效、平衡劃分，實現數據的負載均衡，有效解決現有系統中由于存在數據傾斜而導致的連接復雜性過高的問題。

2）設計基于混合存儲模式的數據索引與過濾機制，對表中不包含目標值的數據進行快速過濾，減少不必要的磁盤I/O 操作，從而提高SPARQL 查詢計算過程中目標RDF 數據的查找速度，有效解決實驗中出現的查詢性能受限于表掃描時間的問題。

3）設計一種高準確性的SPARQL 基數估計器，例如使用基于學習的方法訓練基數評估器，通過神經網絡模型學習RDF 數據特征以及三元組模式間的相關性，提高對查詢連接中間連接結果大小的預測準確度，實現對三元組模式間連接順序、連接方式的優化，有效防止實驗中出現的由于中間結果過大而導致內存溢出、查詢復雜度過高的問題。

4）設計一種基于代價評估的啟發式查詢規劃算法，利用代價評估模型生成最優查詢計劃，并將最優查詢計劃構造為并行性更高的查詢樹，有效解決現有系統中查詢并行度低、查詢編譯時間和執行時間長的問題，從而有效提高分布式SPARQL 查詢的性能。