杜伍 陳琳

摘要：在許多應(yīng)用程序中，例如數(shù)據(jù)清理，記錄鏈接，Web搜索和文檔分析，相似性查詢處理變得越來越重要。該方法使用現(xiàn)有的運行時運算符來實現(xiàn)這種復(fù)雜的聯(lián)接算法，而無須重新發(fā)明輪子。這樣可以使系統(tǒng)自動受益于這些操作員的未來改進。該方法包括一種技術(shù)，該技術(shù)通過使用很大程度上以系統(tǒng)用戶級查詢語言表示的模板，在查詢優(yōu)化期間將相似性聯(lián)接計劃轉(zhuǎn)換為基于操作員的有效物理計劃;這項技術(shù)大大簡化了這種轉(zhuǎn)換規(guī)則的規(guī)范。我們使用并行大數(shù)據(jù)管理系統(tǒng)Apache AsterixDB來說明和驗證我們的技術(shù)。我們使用并行計算集群上的幾個大型真實數(shù)據(jù)集進行了一項實驗研究，以評估相似性查詢支持。

關(guān)鍵詞：大數(shù)據(jù)管理系統(tǒng);Apache AsterixDB;相似性查詢;并行數(shù)據(jù)庫;優(yōu)化

中圖分類號：TP391 文獻標識碼：A

文章編號：1009-3044（2020）05-0003-02

開放科學(xué)（資源服務(wù)）標{o碼cOSID）：

1 概述

相似性查詢會計算滿足不完全匹配但近似的匹配條件的答案。支持相似性查詢的問題在許多應(yīng)用中變得越來越重要，包括搜索，記錄鏈，數(shù)據(jù)清理和社交媒體分析。例如，在與客戶進行實時電話交談期間，呼叫中心代表可能希望通過鍵入序列號立即識別客戶購買的產(chǎn)品。即使在搜索號碼中出現(xiàn)錯別字，系統(tǒng)也應(yīng)找到產(chǎn)品。社交媒體分析師可能希望找到共享共同愛好或社交朋友的用戶賬戶。醫(yī)學(xué)研究人員可能希望搜索標題與特定文章相似的論文。在這些示例的每一個中，查詢都包括具有特定于域的相似度函數(shù)的匹配條件，例如關(guān)鍵詞的編輯距離或興趣組的Jaccard。

相似性查詢有兩種基本類型。一種是search或selection，它查找與給定記錄相似的記錄。另一個是Jom，它計算彼此相似的記錄對。關(guān)于這兩種類型的查詢已有許多研究。已經(jīng)開發(fā)了許多數(shù)據(jù)結(jié)構(gòu)，分區(qū)方案和算法，以在大型數(shù)據(jù)集上有效地支持相似性查詢。當(dāng)計算超出一臺計算機的限制時，也將有并行解決方案支持跨集群中多個節(jié)點的查詢。

由于在許多應(yīng)用程序中數(shù)據(jù)都駐留在數(shù)據(jù)庫中，所以一個自然的問題是如何在這樣的數(shù)據(jù)庫系統(tǒng)上采用這些現(xiàn)有技術(shù)來支持相似性查詢。一種方法是在數(shù)據(jù)庫。也就是說，我們開發(fā)了一個獨立的應(yīng)用程序?qū)?，該層從?shù)據(jù)庫中檢索數(shù)據(jù)，并在此應(yīng)用程序中部署這些索引結(jié)構(gòu)和算法以支持相似性查詢。這種方法的一個優(yōu)點是它在實現(xiàn)中具有很大的靈活性。同時，它也有幾個主要缺點。首先，數(shù)據(jù)本質(zhì)上具有兩個副本，一個副本在數(shù)據(jù)庫中，一個在應(yīng)用程序中。其次，需要付出額外的努力來將應(yīng)用程序中的數(shù)據(jù)與數(shù)據(jù)庫中的數(shù)據(jù)同步，以便將最新結(jié)果返回給用戶查詢。第三，沒有充分利用數(shù)據(jù)庫的內(nèi)部功能，包括存儲，索引和查詢執(zhí)行。另一種方法是將這些技術(shù)完全集成到內(nèi)部數(shù)據(jù)庫，從而可以克服所有上述限制。特別是，不必將數(shù)據(jù)復(fù)制到單獨的層中，并且可以利用數(shù)據(jù)庫系統(tǒng)的內(nèi)置功能直接對數(shù)據(jù)進行查詢。

2 AsterixDB

2.1 體系結(jié)構(gòu)

AsterixDB由幾個軟件層組成，如圖1所示。最頂層提供了完整，靈活的數(shù)據(jù)模型（ADM）和查詢語言（SQL++和AQL），用于描述，查詢和分析數(shù)據(jù)。AQL是AsterixDB的初始查詢語言。SQL++現(xiàn)在是用戶首選的語言。

下一層，基于Algebricks的查詢編譯器，用于并行查詢處理。該代數(shù)層從上層接收翻譯后的邏輯SQL++/AQL查詢計劃，并執(zhí)行基于規(guī)則的優(yōu)化。一個規(guī)則可以分配給多個規(guī)則集。根據(jù)規(guī)則集的配置，可以重復(fù)應(yīng)用每個規(guī)則，直到規(guī)則集中的任何規(guī)則都無法進一步轉(zhuǎn)換計劃為止。對于邏輯計劃轉(zhuǎn)換，當(dāng)前有15個規(guī)則集和171個規(guī)則（包括將一個規(guī)則分配給不同的規(guī)則集）。邏輯優(yōu)化之后，Algebricks為計劃中的每個邏輯運算符選擇物理運算符。例如，對于邏輯聯(lián)接運算符，可以基于聯(lián)接謂詞選擇混合哈希聯(lián)接或嵌套循環(huán)聯(lián)接。之后，物理優(yōu)化階段開始。在邏輯和物理優(yōu)化期間，有許多順序應(yīng)用的規(guī)則集。物理優(yōu)化階段有3條規(guī)則集和30條規(guī)則。物理優(yōu)化過程完成后，Algebricks層將生成Hyracks作業(yè)，以在ra層。

Hyracks層包括由AsterixDB存儲和管理的數(shù)據(jù)集的存儲工具，這些數(shù)據(jù)集是基于分區(qū)的基于LSM的B+樹，具有可選的基于LSM的二級索引。AsterixDB將計算任務(wù)轉(zhuǎn)換為運算符和連接器的有向無環(huán)圖（DAG），并將其發(fā)送給Hyracks以便執(zhí)行。在Hyracks中，運算符使用輸入數(shù)據(jù)的分區(qū)并產(chǎn)生輸出數(shù)據(jù)的分區(qū)。然后，將運算符產(chǎn)生的輸出分區(qū)由連接器重新分區(qū)，以為下一個運算符產(chǎn)生輸入分區(qū)。一個操作員具有一個或多個活動（子步驟或階段），并且在某些操作員上的兩個活動之間可能存在控制依賴性。使用此信息，創(chuàng)建一個或多個階段。一個階段包括可以共同安排的一組活動（一個活動集群）。因此，將逐級執(zhí)行作業(yè)。由于在此級別上將數(shù)據(jù)表示為字節(jié)元組，因此Hyracks是不可知的數(shù)據(jù)模型層。

2.2 數(shù)據(jù)模型

AsterixDB定義了自己的針對半結(jié)構(gòu)化數(shù)據(jù)的數(shù)據(jù)模型（ADM）。ADM是JSON的超集，支持包，嵌套類型和各種原始類型。圖2顯示了一些示例ADM DDL。AmazonReviewType被定義為開放類型，這意味著其實例必須具有所有指定的字段，但可能還包含因?qū)嵗惖念~外字段。

AsterixDB數(shù)據(jù)集中的每個記錄都由唯一的主鍵標識，并且記錄將基于其主鍵在集群的節(jié)點之間進行哈希分區(qū)。數(shù)據(jù)集中的每個記錄必須符合其關(guān)聯(lián)的數(shù)據(jù)類型。圖5還包括用于創(chuàng)建Amazon評論數(shù)據(jù)集的SQL語句。每個分區(qū)都通過LSMB+樹中的主鍵（也稱為主索引）在本地建立索引，并駐留在其節(jié)點的本地存儲中。AsterixDB還支持二級索引，包括B+樹，R樹和反向索引選項。索引是本地的，即，它們以與主索引相同的方式進行分區(qū)。像主索引一樣，每個輔助索引也采用基于LSM的結(jié)構(gòu)。在AsterixDB存儲管理文件中可以找到AsterixDB中基于LSM的索引結(jié)構(gòu)的更多詳細信息。

3 執(zhí)行相關(guān)查詢

3.1 倒排索引

AsterixDB中的反向索引是基于LSM的二級索引，它由可變的內(nèi)存中組件和多個不可變的磁盤上組件組成。之所以選擇這種設(shè)計來支持高頻插入，因為基于LSM的索引通過在將更新寫入磁盤之前合并內(nèi)存中的更新來攤銷寫入成本。內(nèi)存中的組件由兩棵B+樹組成，一棵用于內(nèi)存中反向索引，另一棵用于存儲已刪除記錄的主鍵。磁盤上的組件是不可變的，因此AsterixDB使用此B+表示磁盤上組件的已刪除記錄。-tree，而不是從反向索引本身中刪除它們。

3.2 執(zhí)行相似性選擇

AsterixDB用于選擇查詢的執(zhí)行策略。我們使用圖3的示例查詢來解釋執(zhí)行流程。此SQL++查詢計算名為Reddit的數(shù)據(jù)集的字段標題與edit-distance-threshold為2的恒定搜索鍵良好競爭之間的編輯距離。然后再分別給予索引的搜索執(zhí)行和基于非索引的搜索執(zhí)行分別將結(jié)果返回給協(xié)調(diào)器。

3.3 執(zhí)行相似聯(lián)接

相似聯(lián)接運算符具有兩個分支作為其輸入。我們稱第一個為外部分支，第二個為內(nèi)部分支。例如，在圖3，SQL++別名一種[R指外部分支，并且[R指內(nèi)部分支。該查詢基于閾值為0.5的Jaccard連接條件從每個數(shù)據(jù)集中獲取三個字段。再分別基于索引的聯(lián)接執(zhí)行和非索引的聯(lián)接執(zhí)行，再次將結(jié)果發(fā)送給協(xié)調(diào)器進行合并。

3.4 優(yōu)化相似性查詢

AsterixDB使用基于規(guī)則的優(yōu)化方法。根據(jù)給定的查詢構(gòu)造一個初始邏輯計劃，然后對該計劃嘗試每個優(yōu)化規(guī)則。如果有規(guī)則適用，則計劃將被轉(zhuǎn)換。涉及數(shù)據(jù)集的邏輯計劃始終以PRIMARY-INDEX-SCAN運算符開頭，如果存在一個或多個條件，則以SELECT運算符開頭。對于相似性查詢，首先要構(gòu)建非索引相似性查詢計劃，并且可以在優(yōu)化過程中引入基于索引的轉(zhuǎn)換或三階段相似性聯(lián)接。 4 結(jié)論

在本文中，我們描述了一種為并行大數(shù)據(jù)管理系統(tǒng)中的相似性查詢提供集成支持的方法。我們使用Apache AsterixDB來說明和驗證我們的方法。我們描述了系統(tǒng)中相似性查詢的整個生命周期，包括查詢語言，索引，執(zhí)行計劃和計劃重寫以優(yōu)化查詢執(zhí)行。我們的相似性搜索解決方案利用了并行數(shù)據(jù)管理系統(tǒng)的現(xiàn)有基礎(chǔ)架構(gòu)，包括其運算符，查詢引擎和基于規(guī)則的優(yōu)化器。我們希望其他尋求將搜索功能集成到通用并行數(shù)據(jù)管理環(huán)境中的人會發(fā)現(xiàn)我們的工作結(jié)果很有用。

參考文獻：

[1]克里斯汀.P.數(shù)據(jù)匹配一記錄鏈接，實體解析和重復(fù)檢測的概念和技術(shù)，以數(shù)據(jù)為中心的系統(tǒng)和應(yīng)用，谷歌學(xué)術(shù)，2012.

[2]拉姆E.待辦事項H.H.數(shù)據(jù)清理中存在的問題和當(dāng)前的方法[J]lEEE數(shù)據(jù)工程師公牛，2000，23（4）：3-13.

[3] Borgatti S.P，Mehra A.，Brass D.J.社會科學(xué)中的網(wǎng)絡(luò)分析科學(xué)，2009：892-895.

[4]蔣翠清，疏得友，段銳.基于用戶時空相似性的位置推薦算法[J].計算機工程，2018（7）.

[5]米琳.基于q-gram的字符串相似性查詢研究.現(xiàn)代計算機：專業(yè)版，2014（6）.

【通聯(lián)編輯：梁書】