文檔-關(guān)系數(shù)據(jù)查詢執(zhí)行技術(shù)研究與實(shí)現(xiàn)*

馬志程，袁海峰，谷 洋，劉亞茹，張 孝+

1.國(guó)網(wǎng)甘肅省電力公司電力科學(xué)研究院，蘭州 730070

2.數(shù)據(jù)工程與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室（中國(guó)人民大學(xué)），北京 100872

3.中國(guó)人民大學(xué) 信息學(xué)院，北京 100872

1 引言

近年來(lái)，數(shù)據(jù)已經(jīng)滲透到當(dāng)今每一個(gè)行業(yè)和業(yè)務(wù)職能領(lǐng)域，成為重要的生產(chǎn)因素。人們對(duì)于海量數(shù)據(jù)的挖掘和運(yùn)用，預(yù)示著新一波生產(chǎn)率增長(zhǎng)和消費(fèi)者盈余浪潮的到來(lái)[1]。關(guān)系數(shù)據(jù)庫(kù)是數(shù)據(jù)管理中不可或缺的技術(shù)，尤其在涉及到用戶、財(cái)物等需要精細(xì)管理的應(yīng)用領(lǐng)域時(shí)，更是具有不可替代的地位[2]。但是傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)在大數(shù)據(jù)背景下存在一些技術(shù)缺陷，尤其是在速度、存儲(chǔ)量以及多樣化結(jié)構(gòu)數(shù)據(jù)的處理問(wèn)題上存在一些短板。目前的大數(shù)據(jù)應(yīng)用中包含的數(shù)據(jù)類型是多種多樣的，既可以是結(jié)構(gòu)化的關(guān)系數(shù)據(jù)與圖數(shù)據(jù)等，還可以是JSON（Javascript object notation）、XML（extensible markup language）等半結(jié)構(gòu)化數(shù)據(jù)，甚至是網(wǎng)頁(yè)、視頻等非結(jié)構(gòu)化的數(shù)據(jù)[3]。數(shù)據(jù)模型是一個(gè)數(shù)據(jù)管理系統(tǒng)的核心，純關(guān)系模型已經(jīng)無(wú)法靈活地管理多種類型的數(shù)據(jù)。其次，在包含大量節(jié)點(diǎn)的集群中，高速處理海量數(shù)據(jù)也是一個(gè)難點(diǎn)。再次，在關(guān)系數(shù)據(jù)庫(kù)上無(wú)法完成對(duì)數(shù)據(jù)的復(fù)雜分析[4]。

進(jìn)入大數(shù)據(jù)時(shí)代之后，已經(jīng)無(wú)法使用某種單一的數(shù)據(jù)庫(kù)管理系統(tǒng)來(lái)完成所有應(yīng)用的數(shù)據(jù)管理。和關(guān)系數(shù)據(jù)庫(kù)不同的是，文檔數(shù)據(jù)庫(kù)往往是把某個(gè)對(duì)象的所有信息全部存儲(chǔ)在一個(gè)集合中，并且集合中的每個(gè)對(duì)象的內(nèi)部結(jié)構(gòu)無(wú)需完全相同，這種設(shè)計(jì)思想極大地簡(jiǎn)化了從外部對(duì)象到數(shù)據(jù)庫(kù)對(duì)象的映射處理[5]。NoSQL（not only structured query language）數(shù)據(jù)庫(kù)目前處于百花齊放的狀態(tài)，由于存儲(chǔ)模式的不同，也沒(méi)有提供統(tǒng)一的查詢語(yǔ)言，也因此導(dǎo)致了NoSQL 數(shù)據(jù)庫(kù)沒(méi)有統(tǒng)一的數(shù)據(jù)訪問(wèn)接口[6]。需要一種更加開(kāi)放的數(shù)據(jù)庫(kù)管理系統(tǒng)。將具有豐富多樣的數(shù)據(jù)類型的數(shù)據(jù)在同一個(gè)數(shù)據(jù)管理系統(tǒng)中進(jìn)行存儲(chǔ)、組織與管理。這也就意味著單一的數(shù)據(jù)庫(kù)引擎必定無(wú)法完成數(shù)據(jù)的統(tǒng)一訪問(wèn)，需要能夠容納與支持多種數(shù)據(jù)模型的處理引擎并存于系統(tǒng)中。在異構(gòu)數(shù)據(jù)的自適應(yīng)存儲(chǔ)前提下（即不同結(jié)構(gòu)的數(shù)據(jù)可能被獨(dú)立存儲(chǔ)在不同的數(shù)據(jù)庫(kù)中，或者為了更好地服務(wù)于查詢，同樣語(yǔ)義的數(shù)據(jù)被冗余地存儲(chǔ)于不同結(jié)構(gòu)的數(shù)據(jù)庫(kù)中），如何基于關(guān)系數(shù)據(jù)庫(kù)的架構(gòu)融入NoSQL數(shù)據(jù)庫(kù)引擎，怎樣面對(duì)用戶定義的操作，如何針對(duì)不同引擎的查詢特點(diǎn)來(lái)實(shí)現(xiàn)跨引擎的查詢以及如何處理大數(shù)據(jù)管理系統(tǒng)中的查詢表達(dá)與查詢優(yōu)化并提高查詢性能，是構(gòu)建能容納和支持多種不同結(jié)構(gòu)數(shù)據(jù)處理引擎并存的大數(shù)據(jù)管理系統(tǒng)需要考慮的重點(diǎn)問(wèn)題。

基于以上的研究背景，啟動(dòng)了將關(guān)系型數(shù)據(jù)庫(kù)和NoSQL數(shù)據(jù)庫(kù)進(jìn)行集成的通用性大數(shù)據(jù)管理平臺(tái)DataCloud 項(xiàng)目的研究設(shè)計(jì)。本文的研究是Data-Cloud 大數(shù)據(jù)管理平臺(tái)的一個(gè)子課題。本文研究了關(guān)系型數(shù)據(jù)庫(kù)和NoSQL文檔數(shù)據(jù)庫(kù)融合的查詢處理技術(shù)，實(shí)現(xiàn)了一個(gè)執(zhí)行引擎ENTIA，將支持結(jié)構(gòu)化數(shù)據(jù)和半結(jié)構(gòu)化數(shù)據(jù)的兩種不同的數(shù)據(jù)庫(kù)引擎集成在同一大數(shù)據(jù)管理系統(tǒng)中，提供統(tǒng)一的訪問(wèn)接口，來(lái)完成混合引擎的查詢處理，并基于啟發(fā)式規(guī)則完成部分查詢優(yōu)化功能，為構(gòu)建支持多種數(shù)據(jù)模型的通用性大數(shù)據(jù)管理系統(tǒng)奠定基礎(chǔ)。

此外，本文的研究?jī)?nèi)容也對(duì)解決實(shí)際工程中的問(wèn)題，提高開(kāi)發(fā)效率具有很重要的意義。由于NoSQL數(shù)據(jù)庫(kù)采用非規(guī)范統(tǒng)一的存儲(chǔ)方式，即一種數(shù)據(jù)庫(kù)只服務(wù)于一種數(shù)據(jù)庫(kù)類型，導(dǎo)致截至目前仍然沒(méi)有統(tǒng)一的查詢表達(dá)來(lái)訪問(wèn)所有的NoSQL數(shù)據(jù)庫(kù)。在實(shí)際的項(xiàng)目開(kāi)發(fā)中，當(dāng)需要同時(shí)訪問(wèn)關(guān)系數(shù)據(jù)庫(kù)和NoSQL 數(shù)據(jù)庫(kù)時(shí)，往往需要程序員針對(duì)不同的數(shù)據(jù)庫(kù)引擎分別創(chuàng)建連接，用相應(yīng)的數(shù)據(jù)庫(kù)引擎定義的查詢語(yǔ)言給出查詢請(qǐng)求，在獲取各個(gè)處理引擎返回的查詢結(jié)果之后，再以代碼的方式手工合并各部分結(jié)果從而完成整體的功能需求。這種處理方式不僅要求程序員需要掌握多種數(shù)據(jù)庫(kù)的查詢語(yǔ)言，還增加了研發(fā)的工作量，降低了開(kāi)發(fā)效率。此外，無(wú)法充分基于數(shù)據(jù)、查詢與數(shù)據(jù)庫(kù)引擎本身的特性來(lái)對(duì)整體查詢做進(jìn)一步的優(yōu)化。

本文的主要貢獻(xiàn)如下：

（1）系統(tǒng)地介紹了執(zhí)行引擎ENTIA 的整體架構(gòu)與設(shè)計(jì)實(shí)現(xiàn)。ENTIA包含四大模塊：查詢解析模塊、查詢優(yōu)化模塊、查詢翻譯模塊和查詢執(zhí)行模塊。并具體地闡述了各個(gè)模塊的功能與實(shí)現(xiàn)原理。

（2）提供了統(tǒng)一的數(shù)據(jù)訪問(wèn)接口。設(shè)計(jì)了全局視圖來(lái)屏蔽底層數(shù)據(jù)的結(jié)構(gòu)類型與物理存儲(chǔ)的位置，并基于此定義查詢語(yǔ)言，使得用戶仍然采用熟悉的SQL（structured query language）來(lái)完成包含一種或多種存儲(chǔ)引擎、多種數(shù)據(jù)模型的混合查詢，大大提高了開(kāi)發(fā)效率。

（3）基于啟發(fā)式規(guī)則進(jìn)行查詢優(yōu)化。在數(shù)據(jù)冗余存儲(chǔ)的前提下，將原查詢分解成若干子查詢，進(jìn)而把計(jì)算推向合適的存儲(chǔ)引擎，充分利用各數(shù)據(jù)庫(kù)引擎的查詢優(yōu)勢(shì)，從而提高整體查詢的性能。

（4）進(jìn)行充分的實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。通過(guò)實(shí)驗(yàn)證明：與傳統(tǒng)方案對(duì)比，多引擎、多數(shù)據(jù)模型下的混合查詢?cè)诒ＷC查詢結(jié)果正確的前提下，不降低查詢性能，證明了方法的正確性；與任一單獨(dú)數(shù)據(jù)庫(kù)的查詢性能進(jìn)行對(duì)比，表明了優(yōu)化方法對(duì)數(shù)據(jù)庫(kù)性能提升的有效性。

2 相關(guān)工作

異構(gòu)數(shù)據(jù)庫(kù)集成的研究初期是以外部數(shù)據(jù)的管理開(kāi)始的。Melton 等提出了一種稱為SQL/MED 的架構(gòu)設(shè)計(jì)[7]。MED 的含義是Management of External Data。SQL/MED 提供了對(duì)SQL 語(yǔ)法的擴(kuò)展，以及一組用于開(kāi)發(fā)和管理訪問(wèn)SQL 數(shù)據(jù)和NoSQL（也稱為外部）數(shù)據(jù)的應(yīng)用程序的例程。SQL/MED 可以分為兩大部分。第一部分稱為包裝接口（wrapper inter-face），提供了可以查看由一個(gè)或多個(gè)外部服務(wù)器上外部數(shù)據(jù)的功能。外部數(shù)據(jù)可以存儲(chǔ)在文件系統(tǒng)、HTML 格式的網(wǎng)頁(yè)、XML 文檔或其他一些專門的存儲(chǔ)庫(kù)中[8-9]。SQL/MED 的第二部分稱為數(shù)據(jù)鏈（data-links），它提供了一些工具，使一個(gè)SQL Server能夠控制對(duì)駐留在一個(gè)或多個(gè)文件系統(tǒng)中的數(shù)據(jù)的引用完整性、恢復(fù)和授權(quán)的管理。

Tatemura等給出了一個(gè)原型系統(tǒng)Partiqle[10]，它將SQL引擎集成在基于鍵值存儲(chǔ)NoSQL數(shù)據(jù)庫(kù)HBase之上，以達(dá)到支持關(guān)系數(shù)據(jù)庫(kù)中的OLTP（on-line transaction process）特性的目的。在這個(gè)原型系統(tǒng)中，重點(diǎn)研究了如何將關(guān)系數(shù)據(jù)庫(kù)中的事務(wù)引入到HBase 中。Partiqle系統(tǒng)定義了一種“事務(wù)類”的聲明規(guī)范，來(lái)約束工作負(fù)載中的事務(wù)。給定一個(gè)SPJ（select-project-join）查詢，系統(tǒng)的編譯模塊會(huì)基于鍵值存儲(chǔ)的查詢優(yōu)化器之上產(chǎn)生一個(gè)新的執(zhí)行計(jì)劃。執(zhí)行引擎和事務(wù)管理器會(huì)以一種樂(lè)觀的并發(fā)控制方式來(lái)執(zhí)行此查詢計(jì)劃。所謂樂(lè)觀的并發(fā)控制方式就是，系統(tǒng)會(huì)緩沖寫(xiě)操作，來(lái)提交HBase中的check-and-put的原子操作[10]。

Vila?a 等針對(duì)NoSQL 數(shù)據(jù)庫(kù)中的查詢需要手工編寫(xiě)的缺陷[11]，在HBase 基礎(chǔ)之上集成了SQL 的引擎。在保留了NoSQL數(shù)據(jù)庫(kù)的高可擴(kuò)展性與模式靈活性的前提下，融入了SQL 查詢，為NoSQL 數(shù)據(jù)庫(kù)增加了原來(lái)所不能支持的一些操作符，比如join等[12]。文中采用的方法是重寫(xiě)關(guān)系數(shù)據(jù)庫(kù)的內(nèi)部架構(gòu)，在保留一部分原來(lái)組件的基礎(chǔ)之上，增加了NoSQL 數(shù)據(jù)庫(kù)的部分組件。查詢處理器將以SQL表達(dá)的訪問(wèn)請(qǐng)求進(jìn)行翻譯、編譯和執(zhí)行，同時(shí)包括底層存儲(chǔ)的數(shù)據(jù)類型、存儲(chǔ)模式、索引以及各類操作符的一系列轉(zhuǎn)換，最終完成數(shù)據(jù)查詢[13]。該研究中采用了開(kāi)源、輕量級(jí)用Java 編寫(xiě)的Apache Derby 數(shù)據(jù)庫(kù)和HBase 來(lái)作為NoSQL數(shù)據(jù)庫(kù)[11]。

無(wú)論是同構(gòu)數(shù)據(jù)庫(kù)的集成還是異構(gòu)數(shù)據(jù)庫(kù)的集成，數(shù)據(jù)模式都是非常核心與具有挑戰(zhàn)性的研究工作。Mason等在研究如何集成同構(gòu)數(shù)據(jù)庫(kù)時(shí)提出了一種基于“注解”的方法來(lái)動(dòng)態(tài)地生成全局語(yǔ)義視圖[14]。“注解”方法將復(fù)雜的語(yǔ)義識(shí)別任務(wù)轉(zhuǎn)移到局部注釋器而不是全局集成器，從而消除了全局視圖構(gòu)建的瓶頸。這使得集成更加自動(dòng)化、可擴(kuò)展和可快速部署。數(shù)據(jù)源管理員使用有意義的名稱（可能使用本體）對(duì)架構(gòu)進(jìn)行注釋，并在XML文檔中導(dǎo)出具有注釋的架構(gòu)設(shè)計(jì)。系統(tǒng)會(huì)加載每個(gè)單獨(dú)的注釋，匹配注釋中的名稱以生成集成視圖，然后標(biāo)識(shí)用于跨數(shù)據(jù)庫(kù)連接全局鍵，最終得到一份數(shù)據(jù)模式的全局視圖[15]。

3 查詢引擎的實(shí)現(xiàn)

本章將系統(tǒng)闡述基于關(guān)系型數(shù)據(jù)庫(kù)PostgreSQL和NoSQL 數(shù)據(jù)庫(kù)MongoDB 所實(shí)現(xiàn)的執(zhí)行引擎ENTIA 的架構(gòu)設(shè)計(jì)，分析各個(gè)關(guān)鍵模塊的功能與實(shí)現(xiàn)細(xì)節(jié)。并以具體實(shí)例介紹如何通過(guò)該引擎來(lái)完成異構(gòu)數(shù)據(jù)庫(kù)的混合查詢。

3.1 ENTIA的系統(tǒng)架構(gòu)

ENTIA 主要用于解決在集成關(guān)系數(shù)據(jù)庫(kù)與NoSQL數(shù)據(jù)庫(kù)的系統(tǒng)中的查詢處理問(wèn)題。該引擎包含查詢解析、查詢優(yōu)化、查詢重寫(xiě)和查詢執(zhí)行四個(gè)模塊，其系統(tǒng)架構(gòu)如圖1所示。

Fig.1 Architecture diagram of ENTIA system圖1 ENTIA系統(tǒng)架構(gòu)圖

從圖1 中可以看到，不同的客戶端應(yīng)用通過(guò)ENTIA提供的統(tǒng)一訪問(wèn)接口來(lái)向服務(wù)器發(fā)出查詢請(qǐng)求。查詢解析模塊與元數(shù)據(jù)模塊協(xié)作完成查詢請(qǐng)求的解析工作，其中元數(shù)據(jù)模塊存儲(chǔ)著多源異構(gòu)數(shù)據(jù)庫(kù)的數(shù)據(jù)模式的全局視圖，查詢解析后的結(jié)果以Java對(duì)象的形式來(lái)表示。查詢優(yōu)化模塊基于解析后的結(jié)果與元數(shù)據(jù)信息給出執(zhí)行效率最高的查詢計(jì)劃。根據(jù)優(yōu)化器給出的查詢計(jì)劃，查詢翻譯模塊會(huì)將原本的查詢進(jìn)行翻譯，即以SQL 表達(dá)的查詢請(qǐng)求轉(zhuǎn)換為該查詢計(jì)劃中所參與的各個(gè)數(shù)據(jù)庫(kù)引擎所能識(shí)別接受的查詢語(yǔ)言，最終給出與用戶原查詢等價(jià)的查詢?nèi)蝿?wù)列表。查詢執(zhí)行模塊負(fù)責(zé)接收所有查詢?nèi)蝿?wù)，并給出最終的查詢結(jié)果。查詢執(zhí)行器集成了不同數(shù)據(jù)庫(kù)引擎的訪問(wèn)驅(qū)動(dòng)，它既可訪問(wèn)關(guān)系數(shù)據(jù)庫(kù)，又可訪問(wèn)NoSQL數(shù)據(jù)庫(kù)。查詢執(zhí)行器將查詢?nèi)蝿?wù)進(jìn)行分發(fā)，不同數(shù)據(jù)庫(kù)引擎執(zhí)行各自查詢?nèi)蝿?wù)，各數(shù)據(jù)庫(kù)引擎完成查詢后，將查詢結(jié)果全部返回給查詢執(zhí)行器，查詢執(zhí)行器完成全局的連接工作，得到最終的查詢結(jié)果，返回給客戶端。

從ENTIA 的架構(gòu)中能夠看出，該引擎主要從三方面來(lái)實(shí)現(xiàn)跨引擎的混合查詢：首先，查詢執(zhí)行模塊向上提供了統(tǒng)一的數(shù)據(jù)訪問(wèn)接口，從而屏蔽了存儲(chǔ)層數(shù)據(jù)存儲(chǔ)的不一致。一份完整的數(shù)據(jù)既可部分存儲(chǔ)在關(guān)系數(shù)據(jù)庫(kù)，部分存儲(chǔ)在NoSQL數(shù)據(jù)庫(kù)，也可以不同的結(jié)構(gòu)冗余存儲(chǔ)在多種數(shù)據(jù)庫(kù)中。無(wú)論采用怎樣的存儲(chǔ)策略，向上的訪問(wèn)接口是一致的。其次，混合查詢使用全局?jǐn)?shù)據(jù)模式和統(tǒng)一的查詢優(yōu)化器來(lái)保證查詢的正確性和性能。再次，向客戶端提供統(tǒng)一的查詢語(yǔ)言，在查詢表達(dá)層做到了統(tǒng)一和規(guī)范。

3.2 全局視圖設(shè)計(jì)

全局視圖的設(shè)計(jì)主要是為了解決底層各個(gè)數(shù)據(jù)庫(kù)引擎存儲(chǔ)模式之間的差異問(wèn)題。

全局視圖中，每一個(gè)數(shù)據(jù)元素都有兩個(gè)名稱：一個(gè)是該數(shù)據(jù)元素的“原始名稱”；另一個(gè)是該數(shù)據(jù)元素在全局視圖下的“語(yǔ)義名稱”?！罢Z(yǔ)義名稱”并不具有唯一性，不同的數(shù)據(jù)元素可能具有相同的“語(yǔ)義名稱”。針對(duì)“表”或者“集合”，全局視圖會(huì)給出“語(yǔ)義名稱”“數(shù)據(jù)源”“數(shù)據(jù)庫(kù)”“數(shù)據(jù)域”“主鍵”“外鍵”共六個(gè)屬性?！皵?shù)據(jù)源”為該表或集合的存儲(chǔ)引擎?！皵?shù)據(jù)庫(kù)”為該表或集合所屬的數(shù)據(jù)庫(kù)名稱?！皵?shù)據(jù)域”為該表所包含的字段或?qū)傩?。主、外鍵屬性用來(lái)完成多表之間的連接操作。針對(duì)數(shù)據(jù)庫(kù)元素中的“字段”或者“屬性”，全局視圖會(huì)給出“字段名稱”“語(yǔ)義名稱”和“數(shù)據(jù)類型”三個(gè)屬性。全局視圖由數(shù)據(jù)庫(kù)管理員生成，以JSON文件的形式保存在系統(tǒng)中。當(dāng)系統(tǒng)中任意一個(gè)數(shù)據(jù)庫(kù)引擎的數(shù)據(jù)模式發(fā)生變化時(shí)，需要更新JSON 文件來(lái)保持全局視圖與各個(gè)數(shù)據(jù)庫(kù)引擎之間的同步。ENTIA系統(tǒng)中的全局視圖設(shè)計(jì)示例如下所示：

3.3 查詢語(yǔ)言設(shè)計(jì)

本文中的研究?jī)?nèi)容暫時(shí)只支持?jǐn)?shù)據(jù)查詢語(yǔ)言（data query language，DQL）[16-17]。由于MongoDB 中沒(méi)有數(shù)據(jù)模式的概念，ENTIA 所支持的SQL 是基于全局視圖中的語(yǔ)義名稱來(lái)構(gòu)成。其基本語(yǔ)法如下：

SELECT[ALL|DISTINCT]<全局視圖-目標(biāo)列表達(dá)式>[,<全局視圖-目標(biāo)列表達(dá)式>]……

FROM<全局視圖-表名>[,<全局視圖-表名>]……

[WHERE <條件表達(dá)式>]

[GROUP BY<全局視圖-列名1>[HAVING<條件表達(dá)式>]]

[ORDER BY<全局視圖-列名2>[ASC|DESC]]

3.4 查詢實(shí)例

本節(jié)按照查詢處理的順序來(lái)介紹ENTIA對(duì)用戶的訪問(wèn)請(qǐng)求的處理流程。以查詢Q3.1為例：

其中，字段name、stars 存儲(chǔ)在PostgreSQL 中，屬性attribute存儲(chǔ)在MongoDB中。

ENTIA 收到查詢之后，首先會(huì)基于JSqlParser 對(duì)查詢進(jìn)行解析，生成一個(gè)代表該SQL 查詢的Java 對(duì)象ParseNode。

針對(duì)Q3.1，ENTIA 的查詢優(yōu)化模塊給出的邏輯查詢計(jì)劃如圖2所示。

Fig.2 Logical plan query diagram of Q3.1圖2 Q3.1邏輯計(jì)劃查詢圖

4 查詢優(yōu)化

4.1 查詢優(yōu)化概述

在跨引擎的混合查詢中，如何將計(jì)算任務(wù)合理地分配到每一個(gè)數(shù)據(jù)源直接決定了結(jié)果的正確性與查詢效率。本節(jié)中的查詢優(yōu)化的目標(biāo)就是基于優(yōu)化規(guī)則，把數(shù)據(jù)推向合適的計(jì)算引擎，將查詢?nèi)蝿?wù)盡量下推到各個(gè)數(shù)據(jù)庫(kù)引擎，而針對(duì)分離后的查詢子任務(wù)的更為具體的查詢計(jì)劃則是由各個(gè)數(shù)據(jù)庫(kù)引擎給出。查詢優(yōu)化的策略是由用戶查詢的特點(diǎn)與數(shù)據(jù)的存儲(chǔ)情況所共同決定的。

在混合存儲(chǔ)引擎系統(tǒng)中，數(shù)據(jù)的存儲(chǔ)情況在字段的粒度上可分為冗余存儲(chǔ)與非冗余存儲(chǔ)兩種情況。非冗余存儲(chǔ)是指，字段被唯一地存儲(chǔ)于眾多數(shù)據(jù)庫(kù)引擎當(dāng)中的某一個(gè)數(shù)據(jù)庫(kù)引擎中，該字段的數(shù)據(jù)僅此一份。冗余存儲(chǔ)是指，字段在至少兩個(gè)甚至多個(gè)數(shù)據(jù)庫(kù)引擎中都有所存儲(chǔ)，該字段擁有多份不同結(jié)構(gòu)類型的數(shù)據(jù)，雖然存儲(chǔ)形式不同，但所表達(dá)的語(yǔ)義相同。

用戶的查詢特點(diǎn)是查詢優(yōu)化中優(yōu)化策略的另一決定因素。經(jīng)前期實(shí)驗(yàn)測(cè)試：與PostgreSQL 相比，MongoDB在聚合操作與選擇全表掃描策略時(shí)的字段投影操作具有明顯的查詢優(yōu)勢(shì)，而在表連接的操作上，性能遠(yuǎn)不如PostgreSQL。此外，數(shù)據(jù)查詢語(yǔ)言DQL中，不相關(guān)子查詢是較為具有代表性、更容易解析與判斷的復(fù)雜查詢。因此基于前期的實(shí)驗(yàn)結(jié)論，當(dāng)用戶的查詢中具備上述特點(diǎn)時(shí)，ENTIA 可對(duì)此類查詢進(jìn)行優(yōu)化。

圖3 是ENTIA 查詢優(yōu)化模塊的工作流程圖。目前ENTIA能夠優(yōu)化的查詢?yōu)榘酆喜僮骰蛘呷頀呙璨僮鞯牟幌嚓P(guān)子查詢。ENTIA根據(jù)查詢解析之后的ParseNode以及數(shù)據(jù)存儲(chǔ)的元信息進(jìn)行判斷：用戶查詢的所有數(shù)據(jù)是否冗余存儲(chǔ)，若非冗余存儲(chǔ)，則進(jìn)一步判斷當(dāng)前查詢是否為跨引擎查詢。若數(shù)據(jù)全部存儲(chǔ)在某一引擎中，顯然該查詢會(huì)被完整地在該引擎中完成，若查詢是跨引擎的混合查詢，查詢模塊將分離原查詢中各個(gè)操作符，使得各引擎單獨(dú)完成分解之后的查詢，并保證各部分查詢之后返回的結(jié)果與用戶的原請(qǐng)求查詢等價(jià)。當(dāng)查詢數(shù)據(jù)被冗余存儲(chǔ)在不同結(jié)構(gòu)的數(shù)據(jù)庫(kù)引擎中時(shí)，需要進(jìn)一步判斷是否為可優(yōu)化的查詢。若不滿足可優(yōu)化規(guī)則，則ENTIA統(tǒng)一將查詢交由PostgreSQL來(lái)完成。若滿足優(yōu)化規(guī)則，再根據(jù)查詢中是否包含聚合操作，或者全表掃描操作來(lái)選擇對(duì)應(yīng)的規(guī)則進(jìn)行優(yōu)化。

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

4.2.1 聚合操作規(guī)則

規(guī)則1（聚合操作規(guī)則）由于MongoDB 中聚合操作采用管道流水線來(lái)處理管道中的一個(gè)個(gè)功能節(jié)點(diǎn)，大大提高了聚合操作的效率，其性能遠(yuǎn)遠(yuǎn)高于PostgreSQL。因此，聚合操作優(yōu)化規(guī)則是指當(dāng)查詢符合以下形式時(shí)：

即，如果整體查詢?yōu)椴幌嚓P(guān)子查詢，并且子查詢中包含聚合操作，那么該查詢會(huì)被分解成兩個(gè)子任務(wù)：子查詢被重寫(xiě)為MongoDB 查詢，外層查詢?nèi)匀挥蒔ostgreSQL 執(zhí)行，兩個(gè)子任務(wù)并行執(zhí)行，兩數(shù)據(jù)庫(kù)引擎返回各自查詢結(jié)果，最后連接兩部分查詢結(jié)果得到用戶原查詢的結(jié)果。其中，含有聚合操作的子查詢重寫(xiě)為MongoDB查詢的方式為：

Fig.3 Query optimization workflow of ENTIA圖3 ENTIA查詢優(yōu)化的工作流程圖

聚合操作優(yōu)化規(guī)則的偽代碼如算法1所示。

算法1聚合操作優(yōu)化規(guī)則

輸入：參數(shù)1，形式為包含聚合操作的不相關(guān)子查詢；參數(shù)2，保存全局視圖的JSON文件的路徑。

輸出：重寫(xiě)后的PostgreSQL查詢和MongoDB查詢。

4.2.2 全表掃描規(guī)則

經(jīng)過(guò)前期的實(shí)驗(yàn)測(cè)試，當(dāng)查詢請(qǐng)求的執(zhí)行計(jì)劃為全表掃描時(shí)，MongoDB 的查詢速度要遠(yuǎn)遠(yuǎn)快于PostgreSQL 的查詢速度。因?yàn)樵贛ongoDB 中，當(dāng)數(shù)據(jù)庫(kù)啟動(dòng)時(shí)，會(huì)將磁盤的數(shù)據(jù)加載到內(nèi)存中，充分利用系統(tǒng)的內(nèi)存資源，磁盤的I/O效率與內(nèi)存的查詢導(dǎo)致兩者查詢速度的差異自然十分明顯。全表掃描優(yōu)化規(guī)則是指，當(dāng)查詢符合以下形式時(shí)：

即整體查詢?yōu)椴幌嚓P(guān)子查詢，子查詢的查詢計(jì)劃是全表掃描操作時(shí)，該查詢可被進(jìn)一步優(yōu)化，原查詢被拆解成兩部分執(zhí)行，子查詢被重寫(xiě)為MongoDB 的查詢，外層查詢?nèi)匀唤唤oPostgreSQL來(lái)執(zhí)行，兩引擎并行執(zhí)行各自的查詢?nèi)蝿?wù)，最后將返回的兩部分查詢結(jié)果連接起來(lái)完成原來(lái)的查詢?nèi)蝿?wù)。其中子查詢被重寫(xiě)為MongoDB的查詢的形式為：

在MongoDB 中查詢條件是由多個(gè)鍵值對(duì)的形式來(lái)表達(dá)的，將多個(gè)查詢條件組合在一起，即完成了“條件1 AND 條件2 OR 條件3”的表達(dá)。鍵為列名、值為1的形式用來(lái)表示此列被投影出來(lái)，與SQL中的project語(yǔ)義相同。另外，在對(duì)當(dāng)前查詢判斷是否符合全表掃描優(yōu)化規(guī)則時(shí)，在程序中需要基于EXPLAIN SQL 來(lái)獲取該子查詢的查詢計(jì)劃，再進(jìn)一步判斷是否由全表掃描操作完成。全表操作優(yōu)化規(guī)則的偽代碼與算法1類似。

5 實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)說(shuō)明

5.1.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)在普通PC 機(jī)上進(jìn)行，基本的硬件配置如表1所示。

Table 1 Hardware configuration表1 硬件配置

5.1.2 實(shí)驗(yàn)數(shù)據(jù)集

本實(shí)驗(yàn)所使用的數(shù)據(jù)集是美國(guó)最大的點(diǎn)評(píng)網(wǎng)站Yelp 所公開(kāi)的內(nèi)部數(shù)據(jù)集。該數(shù)據(jù)集的內(nèi)容是Yelp所涵蓋的商家數(shù)據(jù)、用戶數(shù)據(jù)和點(diǎn)評(píng)數(shù)據(jù)的一個(gè)子集。目前Yelp 提供了這個(gè)數(shù)據(jù)集的JSON 文件。該數(shù)據(jù)集被廣泛用于自然語(yǔ)言處理和情感分析、數(shù)據(jù)庫(kù)、圖像挖掘等領(lǐng)域。本文將該數(shù)據(jù)集的JSON格式數(shù)據(jù)存儲(chǔ)于MongoDB 中，共有business、user 和rev-iew三個(gè)集合。利用該JSON文件生成結(jié)構(gòu)化的關(guān)系數(shù)據(jù)，存儲(chǔ)于PostgreSQL 數(shù)據(jù)庫(kù)中。三個(gè)集合（表）的數(shù)據(jù)量分別為20 萬(wàn)條、150 萬(wàn)條、600 萬(wàn)條記錄。為進(jìn)一步測(cè)試，根據(jù)原有數(shù)據(jù)，為每一個(gè)集合（表）又進(jìn)一步生成了兩倍數(shù)據(jù)和四倍數(shù)據(jù)。

5.2 前期實(shí)驗(yàn)

本節(jié)介紹優(yōu)化規(guī)則設(shè)定的前期實(shí)驗(yàn)，證明優(yōu)化規(guī)則設(shè)定的合理性。本節(jié)的實(shí)驗(yàn)從單字段查詢、表連接查詢、聚合操作查詢?nèi)矫妫瑢?duì)比關(guān)系數(shù)據(jù)庫(kù)PostgreSQL 和文檔數(shù)據(jù)庫(kù)MongoDB 在簡(jiǎn)單查詢上的查詢性能。

（1）單字段查詢

單字段查詢從整型、字符型、日期型、JSON 字符串類型四種數(shù)據(jù)類型測(cè)試。測(cè)試所使用的查詢實(shí)例如下：

PostgreSQL 與MongoDB 在以上查詢上的時(shí)間消耗與對(duì)比分別如表2 和圖4 所示。在單字段上的簡(jiǎn)單查詢以及聚合操作上，MongoDB 的性能遠(yuǎn)高于PostgreSQL，但是當(dāng)涉及到表連接操作時(shí)，哪怕是簡(jiǎn)單的兩表連接，PostgreSQL的查詢性能遠(yuǎn)高于Mongo-DB的查詢性能。

Table 2 Simple query time consumption of PostgreSQL and MongoDB表2 PostgreSQL 與MongoDB 簡(jiǎn)單查詢時(shí)間消耗

Fig.4 Comparison of simple query time between PostgreSQL and MongoDB圖4 PostgreSQL 與MongoDB 簡(jiǎn)單查詢時(shí)間對(duì)比

5.3 功能符合型測(cè)試

本實(shí)驗(yàn)的目的是測(cè)試執(zhí)行引擎ENTIA對(duì)既涉及MongoDB 又涉及PostgreSQL 的混合查詢的查詢處理的正確性，通過(guò)與傳統(tǒng)方法的查詢結(jié)果與查詢時(shí)間對(duì)比，證明ENTIA 對(duì)跨引擎查詢處理的可行性。本實(shí)驗(yàn)中采取的查詢實(shí)例為查詢Q3.1。針對(duì)Q3.1，傳統(tǒng)的解決思路是，程序員手動(dòng)分別寫(xiě)出PostgreSQL與MongoDB 兩個(gè)查詢，分別向兩個(gè)數(shù)據(jù)庫(kù)引擎發(fā)送查詢請(qǐng)求，獲取兩部分查詢結(jié)果之后，再手動(dòng)連接兩部分結(jié)果，得到最終的查詢結(jié)果。

將查詢Q3.1訪問(wèn)的表business以及集合business的元組（文檔）數(shù)量N分別設(shè)為20萬(wàn)、40萬(wàn)、80萬(wàn)組，對(duì)ENTIA 的執(zhí)行情況與傳統(tǒng)思路各測(cè)試10 次，記錄時(shí)間（單位為ms），并取平均值。ENTIA 與傳統(tǒng)方法分別使用ENTIA-U 與TRAN-U 表示，其查詢時(shí)間對(duì)比如表3所示。

Table 3 Query time comparison between ENTIA and traditional method表3 ENTIA與傳統(tǒng)方法查詢時(shí)間對(duì)比

從表3中可以看出，兩種方法的查詢時(shí)間幾乎相同。ENTIA由于要將混合查詢進(jìn)行解析、重寫(xiě)，進(jìn)而再分發(fā)給相應(yīng)的數(shù)據(jù)庫(kù)引擎查詢，因此在查詢時(shí)間上要略大于傳統(tǒng)思路的查詢時(shí)間，兩種方法性能差在0.15%左右，在可接受范圍之內(nèi)。但是ENTIA大大提高了程序開(kāi)發(fā)效率，降低了程序員對(duì)數(shù)據(jù)庫(kù)能力的要求，通過(guò)訪問(wèn)ENTIA的接口即可完成跨引擎查詢。

5.4 性能測(cè)試

本實(shí)驗(yàn)的目的是測(cè)試可優(yōu)化查詢?cè)赑ostgreSQL、MongoDB以及本文提出的基于啟發(fā)式規(guī)則的優(yōu)化方法的查詢時(shí)間，對(duì)比三種方法的性能，驗(yàn)證兩種優(yōu)化方法的正確性和效果。

將上述查詢實(shí)例訪問(wèn)的表（集合）business、user和review 的元組（文檔）數(shù)量N分別設(shè)為（20 萬(wàn)、150萬(wàn)、600萬(wàn)）、（40萬(wàn)、300萬(wàn)、1 200萬(wàn)）、（80萬(wàn)、600萬(wàn)、2 400 萬(wàn)）三組數(shù)據(jù)，對(duì)PostgreSQL、MongoDB、ENTIA 的執(zhí)行情況各測(cè)試十次，記錄時(shí)間（單位為ms），并取平均值?；诰酆喜僮鲀?yōu)化規(guī)則的性能對(duì)比結(jié)果如表4所示，基于全表掃描優(yōu)化規(guī)則的性能對(duì)比結(jié)果如表5所示。

Table 4 Performance comparison based on aggregation operation optimization rules表4 基于聚合操作優(yōu)化規(guī)則的性能對(duì)比結(jié)果

Table 5 Performance comparison based on full table scan optimization rules表5 基于全表掃描優(yōu)化規(guī)則的性能對(duì)比結(jié)果

圖5為基于聚合操作優(yōu)化規(guī)則下，可優(yōu)化查詢?cè)谌N引擎中的查詢性能對(duì)比圖。從圖5中可以看出，每個(gè)數(shù)量級(jí)下ENTIA的執(zhí)行均具有明顯的優(yōu)勢(shì)。其次，由于MongoDB 在聚合操作上的查詢性能較高，每個(gè)數(shù)量級(jí)下MongoDB 的查詢時(shí)間均少于Post-greSQL 中的查詢時(shí)間。重寫(xiě)后的查詢，充分利用MongoDB 聚合操作的查詢優(yōu)勢(shì)，各引擎并行執(zhí)行查詢?nèi)蝿?wù)，大大提高了查詢效率。

Fig.5 Performance comparison graph based on aggregation operation optimization rules圖5 基于聚合操作優(yōu)化規(guī)則的性能對(duì)比圖

圖6為基于聚合操作優(yōu)化規(guī)則下，ENTIA相對(duì)于PostgreSQL和MongoDB性能提升的趨勢(shì)圖。從圖6中可以看出，隨著數(shù)據(jù)量的增大，性能提升的效果越來(lái)越明顯。ENTIA使PostgreSQL避免了執(zhí)行聚合操作，使MongoDB避免了執(zhí)行NoSQL數(shù)據(jù)庫(kù)所不擅長(zhǎng)的連接操作。隨著數(shù)據(jù)量的增大，對(duì)于包含聚合操作的不相關(guān)子查詢而言，聚合操作所耗費(fèi)的時(shí)間要遠(yuǎn)遠(yuǎn)大于連接查詢所耗費(fèi)的時(shí)間，也因此，ENTIA相對(duì)于兩種數(shù)據(jù)庫(kù)引擎而言，性能提升越來(lái)越明顯，且相對(duì)PostgreSQL的性能提升要高于相對(duì)于MongoDB的性能提升。

Fig.6 Performance improvement trend graph based on aggregation operation optimization rules圖6 基于聚合操作優(yōu)化規(guī)則的性能提升趨勢(shì)圖

Fig.7 Performance comparison graph based on full table scan optimization rules圖7 基于全表掃描優(yōu)化規(guī)則的性能對(duì)比圖

圖7為基于全表掃描優(yōu)化規(guī)則下，可優(yōu)化查詢?cè)谌N引擎中的查詢性能對(duì)比圖。從圖7中可以看出，每個(gè)數(shù)量級(jí)下ENTIA的執(zhí)行均具有明顯的優(yōu)勢(shì)。分析可優(yōu)化查詢的查詢計(jì)劃，時(shí)間耗費(fèi)為子查詢中的全表掃描操作和兩表的Join 操作。當(dāng)執(zhí)行計(jì)劃為全表掃描時(shí)，其MongoDB 的查詢速度遠(yuǎn)遠(yuǎn)快于在PostgreSQL 中的查詢速度。因此，將子查詢重寫(xiě)為MongoDB的查詢，大大提高了整個(gè)查詢的速度。

圖8為基于全表掃描優(yōu)化規(guī)則下，ENTIA相對(duì)于PostgreSQL和MongoDB性能提升的趨勢(shì)圖。從圖8中可以看出，隨著數(shù)據(jù)量的增大，性能提升效果越來(lái)越明顯。ENTIA 避免了執(zhí)行MongoDB 所不擅長(zhǎng)的連接操作與PostgreSQL在大數(shù)據(jù)量下的全表掃描操作。由于表與表之間的連接操作所耗費(fèi)的時(shí)間性能的因素比單字段查詢所耗費(fèi)的時(shí)間性能因素更加明顯，導(dǎo)致ENTIA相對(duì)MongoDB的性能提升要高于相對(duì)于PostgreSQL的性能提升。

Fig.8 Performance improvement trend graph based on full table scan optimization rules圖8 基于全表掃描優(yōu)化規(guī)則的性能提升趨勢(shì)圖

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

本文基于關(guān)系數(shù)據(jù)庫(kù)PostgreSQL和文檔數(shù)據(jù)庫(kù)MongoDB 對(duì)查詢處理進(jìn)行探索研究，實(shí)現(xiàn)執(zhí)行引擎ENTIA，給出了混合查詢的查詢處理，并基于啟發(fā)式規(guī)則對(duì)混合引擎進(jìn)行查詢優(yōu)化，提高了查詢效率。在未來(lái)的研究工作中，希望進(jìn)行擴(kuò)展，加入更多NoSQL數(shù)據(jù)庫(kù)，使系統(tǒng)支持更加豐富的數(shù)據(jù)類型。

致謝本文工作得到國(guó)家電網(wǎng)有限公司科技項(xiàng)目（合同號(hào)：SGGSKY00FJJS1900296）的部分支持，也得到了中國(guó)人民大學(xué)信息技術(shù)與管理國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心的部分支持。感謝審稿專家們的寶貴修改意見(jiàn)和建議，同時(shí)感謝中國(guó)人民大學(xué)數(shù)據(jù)工程與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室人大行云云平臺(tái)為本論文項(xiàng)目提供的實(shí)驗(yàn)環(huán)境。