杜伍 陳琳

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

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）05-0003-02

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

1 概述

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

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

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

2 AsterixDB

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

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

下一層，基于Algebricks的查詢編譯器，用于并行查詢處理。該代數(shù)層從上層接收翻譯后的邏輯SQL++/AQL查詢計(jì)劃，并執(zhí)行基于規(guī)則的優(yōu)化。一個(gè)規(guī)則可以分配給多個(gè)規(guī)則集。根據(jù)規(guī)則集的配置，可以重復(fù)應(yīng)用每個(gè)規(guī)則，直到規(guī)則集中的任何規(guī)則都無法進(jìn)一步轉(zhuǎn)換計(jì)劃為止。對(duì)于邏輯計(jì)劃轉(zhuǎn)換，當(dāng)前有15個(gè)規(guī)則集和171個(gè)規(guī)則（包括將一個(gè)規(guī)則分配給不同的規(guī)則集）。邏輯優(yōu)化之后，Algebricks為計(jì)劃中的每個(gè)邏輯運(yùn)算符選擇物理運(yùn)算符。例如，對(duì)于邏輯聯(lián)接運(yù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存儲(chǔ)和管理的數(shù)據(jù)集的存儲(chǔ)工具，這些數(shù)據(jù)集是基于分區(qū)的基于LSM的B+樹，具有可選的基于LSM的二級(jí)索引。AsterixDB將計(jì)算任務(wù)轉(zhuǎn)換為運(yùn)算符和連接器的有向無環(huán)圖（DAG），并將其發(fā)送給Hyracks以便執(zhí)行。在Hyracks中，運(yùn)算符使用輸入數(shù)據(jù)的分區(qū)并產(chǎn)生輸出數(shù)據(jù)的分區(qū)。然后，將運(yùn)算符產(chǎn)生的輸出分區(qū)由連接器重新分區(qū)，以為下一個(gè)運(yùn)算符產(chǎn)生輸入分區(qū)。一個(gè)操作員具有一個(gè)或多個(gè)活動(dòng)（子步驟或階段），并且在某些操作員上的兩個(gè)活動(dòng)之間可能存在控制依賴性。使用此信息，創(chuàng)建一個(gè)或多個(gè)階段。一個(gè)階段包括可以共同安排的一組活動(dòng)（一個(gè)活動(dòng)集群）。因此，將逐級(jí)執(zhí)行作業(yè)。由于在此級(jí)別上將數(shù)據(jù)表示為字節(jié)元組，因此Hyracks是不可知的數(shù)據(jù)模型層。

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

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

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

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

3.1 倒排索引

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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