李軍　于靈凡　田斌　李犇　李曄　康海燕

摘? ?要：隨著基于數(shù)據(jù)流安全查詢（網(wǎng)絡(luò)流監(jiān)控、股票數(shù)據(jù)在線分析、物聯(lián)網(wǎng)中的分布式數(shù)據(jù)流查詢、云計(jì)算下的數(shù)據(jù)流處理等）為背景的應(yīng)用越來越普遍，學(xué)術(shù)界關(guān)于數(shù)據(jù)流上的安全分析、查詢、管理已經(jīng)成為當(dāng)前數(shù)據(jù)庫(kù)領(lǐng)域的一個(gè)很重要的研究熱點(diǎn)。在數(shù)據(jù)流應(yīng)用中，數(shù)據(jù)流的實(shí)時(shí)到達(dá)和元組的突變性使得數(shù)據(jù)流模型同傳統(tǒng)數(shù)據(jù)庫(kù)模型有本質(zhì)上的區(qū)別。因此，許多基于傳統(tǒng)數(shù)據(jù)庫(kù)模型下的查詢優(yōu)化技術(shù)無法適應(yīng)于數(shù)據(jù)流模型。以多媒體數(shù)據(jù)流安全檢測(cè)和查詢的視角，討論的核心內(nèi)容是數(shù)據(jù)流上的過濾器排序、數(shù)據(jù)流之間的連接計(jì)算以及自適應(yīng)優(yōu)化這三個(gè)子問題。文章針對(duì)以上子問題分別介紹了國(guó)際上關(guān)于數(shù)據(jù)流上自適應(yīng)查詢的一些主流研究思路和研究成果，并給出了下一步的研究思路。

關(guān)鍵詞：數(shù)據(jù)流;過濾器排序;自適應(yīng)查詢

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

Abstract： With the application of data flow security query （network flow monitoring， online analysis of stock data， distributed data stream query in the Internet of Things， data stream processing under cloud computing， etc.）， the application is more and more popular. Security analysis， query and management have become a very important research hotspot in the current database field. In data flow applications， the real-time arrival of data streams and the abruptness of tuples make the data flow model essentially different from traditional database models. Therefore， many query optimization techniques based on traditional database models cannot be adapted to the data flow model. From the perspective of multimedia data stream security detection and query， the core content of the discussion is the three sub-problems of filter sorting on the data stream， connection calculation between data streams and adaptive optimization. In view of the above sub-problems， some international research ideas and research results on adaptive query on data streams are introduced.

Key words： multimedia data Stream; adaptive query processing; filter ordering

1 引言

數(shù)據(jù)流作為數(shù)據(jù)庫(kù)發(fā)展的一個(gè)重要分支，在20世紀(jì)末作為一種新型的應(yīng)用的模式被提出，數(shù)據(jù)流具有廣泛的應(yīng)用前景，包括網(wǎng)絡(luò)流監(jiān)控、股票數(shù)據(jù)流分析、異常數(shù)據(jù)流挖掘和物聯(lián)網(wǎng)分布式數(shù)據(jù)流協(xié)同處理等。因此，數(shù)據(jù)流環(huán)境下的查詢[19， 1]、管理[3， 17]、過濾[1， 2]、挖掘[5， 6， 7]是當(dāng)前數(shù)據(jù)庫(kù)領(lǐng)域的研究熱點(diǎn)。數(shù)據(jù)流模型是區(qū)別于以往數(shù)據(jù)庫(kù)模型的新型數(shù)據(jù)應(yīng)用模式。主要區(qū)別為：（1）數(shù)據(jù)流模型中數(shù)據(jù)是實(shí)時(shí)到達(dá)的，查詢是相對(duì)“靜止”的。相反，在數(shù)據(jù)庫(kù)模型中，數(shù)據(jù)是相對(duì)“靜止”的，查詢是不斷的變化;（2）數(shù)據(jù)流模型中數(shù)據(jù)一旦被處理以后即丟棄。相反，數(shù)據(jù)庫(kù)模型中，查詢一旦被處理以后即丟棄。數(shù)據(jù)流模型中數(shù)據(jù)到達(dá)的速度和規(guī)模具有不可預(yù)測(cè)性。

以上是數(shù)據(jù)庫(kù)模型和數(shù)據(jù)流模型的本質(zhì)區(qū)別，使得數(shù)據(jù)流模型和數(shù)據(jù)庫(kù)模型對(duì)查詢的處理技術(shù)差別很大。主要體現(xiàn)在傳統(tǒng)數(shù)據(jù)庫(kù)模型中，查詢是不斷變化的，每次提交的查詢之間互不相關(guān)。查詢一旦執(zhí)行完畢就可以丟棄。在數(shù)據(jù)流模型中，查詢是常駐于系統(tǒng)，一旦注冊(cè)就要求一直“在線”，而數(shù)據(jù)是在不斷的變化。數(shù)據(jù)一旦處理完畢就可以丟棄。這兩種數(shù)據(jù)模型下對(duì)查詢處理模式的差異性導(dǎo)致了傳統(tǒng)數(shù)據(jù)庫(kù)模型的查詢處理技術(shù)已經(jīng)無法適用于數(shù)據(jù)流領(lǐng)域。同時(shí)，在數(shù)據(jù)流環(huán)境下，由于數(shù)據(jù)流的速率和規(guī)模的隨機(jī)性和不可預(yù)測(cè)性，自適應(yīng)變化的查詢處理策略變得更加重要。綜上，本文以一種基于數(shù)據(jù)流實(shí)時(shí)查詢的視角，重點(diǎn)關(guān)注了近年來對(duì)數(shù)據(jù)流安全計(jì)算尤其是流查詢的研究成果。

如圖1所示，數(shù)據(jù)流系統(tǒng)通常注冊(cè)大量“在線”的查詢來完成數(shù)據(jù)流的實(shí)時(shí)查詢處理。每個(gè)查詢是多個(gè)過濾器（謂詞）的“與”運(yùn)算。每個(gè)過濾器的計(jì)算開銷通常是比較昂貴的，特別是在日益普遍的多媒體數(shù)據(jù)流環(huán)境中。因此，數(shù)據(jù)流查詢的目標(biāo)就是通過計(jì)算盡可能少的過濾器來決定所有查詢的結(jié)果。例如，假設(shè)在當(dāng)前數(shù)據(jù)流上注冊(cè)了四個(gè)查詢，這些查詢間共享的過濾器的數(shù)量是四個(gè)。對(duì)于當(dāng)前數(shù)據(jù)流元組e，過濾器最優(yōu)排序順序A = F1;F2;F3;F4。也就是說順序A的開銷可能遠(yuǎn)遠(yuǎn)小于其他排序順序如B = F2;F4;F1;F3。由于數(shù)據(jù)流上元組存在突變性，對(duì)于下一個(gè)數(shù)據(jù)流元組e，排序順序B 的開銷可能就優(yōu)于排序順序A。因此，在不斷變化的數(shù)據(jù)流環(huán)境中，如何自適應(yīng)的調(diào)整過濾器的排序順序是關(guān)鍵問題。

近年來，數(shù)據(jù)流上的處理技術(shù)發(fā)展很快，主要側(cè)重于數(shù)據(jù)流查詢的處理和數(shù)據(jù)流上的深度內(nèi)容挖掘技術(shù)。也出現(xiàn)了很多數(shù)據(jù)流管理系統(tǒng)，例如Tapestry[9]是構(gòu)建在只支持添加模式的數(shù)據(jù)庫(kù)系統(tǒng)上面的在線查詢處理引擎，用來完成基于內(nèi)容的過濾。這個(gè)系統(tǒng)可以說是數(shù)據(jù)流系統(tǒng)的雛形。

XFilter[11]將不同用戶對(duì)XML 文檔的“偏好”注冊(cè)到系統(tǒng)中，將這些“偏好”作為查詢以XPath[12]語言的形式來表示，進(jìn)而實(shí)現(xiàn)了基于內(nèi)容的過濾系統(tǒng)。Xyleme[13]是一個(gè)和XFilter[11]很類似的基于內(nèi)容的過濾系統(tǒng)，只是使用的規(guī)則描述語言不同而已。Tribeca[14]系統(tǒng)是真正意義上的數(shù)據(jù)流管理系統(tǒng)，用來完成對(duì)網(wǎng)絡(luò)數(shù)據(jù)流的在線查詢，只不過提供查詢的能力非常有限。OpenCQ[15]和NiagaraCQ[16]系統(tǒng)都是監(jiān)視Web數(shù)據(jù)流的數(shù)據(jù)流管理系統(tǒng)。支持側(cè)重點(diǎn)不太相同：OpenCQ[15]重點(diǎn)關(guān)注查詢處理的算法。NiagaraCQ[16]側(cè)重于支持的查詢數(shù)量規(guī)模。Telegraph[19， 18， 20， 50]是比較有特點(diǎn)的數(shù)據(jù)流管理系統(tǒng)，具有較好的擴(kuò)展性和移植性。其最大的特點(diǎn)是設(shè)計(jì)了一種稱為Eddy[19]的機(jī)制，通過這個(gè)機(jī)制來完成對(duì)每個(gè)元組的自適應(yīng)路由。Madden[20]重點(diǎn)討論了在傳感器網(wǎng)絡(luò)環(huán)境中Telegraph[19]系統(tǒng)的查詢執(zhí)行策略。Madden[20]主要討論了在Telegraph系統(tǒng)中如何自適應(yīng)的處理多查詢。Aurora[21]系統(tǒng)是側(cè)重于網(wǎng)絡(luò)管理應(yīng)用的數(shù)據(jù)流管理系統(tǒng)，Aurora的核心是由操作符組成的觸發(fā)器網(wǎng)絡(luò)。每個(gè)觸發(fā)器是由一個(gè)或者多個(gè)操作符組成的有向無環(huán)圖。

對(duì)于每個(gè)使用了Aurora[21]系統(tǒng)的數(shù)據(jù)流管理應(yīng)用中，管理員只需要?jiǎng)?chuàng)建一個(gè)或者多個(gè)觸發(fā)器，并將這些觸發(fā)器添加到Aurora觸發(fā)器網(wǎng)絡(luò)中。Aurora在執(zhí)行計(jì)劃編譯時(shí)和運(yùn)行時(shí)都進(jìn)行了優(yōu)化，Aurara在系統(tǒng)運(yùn)行時(shí)通過檢測(cè)資源負(fù)載情況結(jié)合注冊(cè)服務(wù)的QoS進(jìn)行“甩負(fù)荷”。STREAM[3]是一種基于關(guān)系模型的數(shù)據(jù)流管理系統(tǒng)。提出了一種數(shù)據(jù)流查詢語言CQL[38]。所有操作算子和算子的優(yōu)化都是在同一個(gè)進(jìn)程中，調(diào)度算法按照時(shí)間片進(jìn)行簡(jiǎn)單切割。STREAM 系統(tǒng)對(duì)查詢的優(yōu)化也非常有限，只是對(duì)單查詢進(jìn)行了選擇下推，對(duì)多查詢只是在數(shù)據(jù)共享方面做了一些優(yōu)化工作。STREAM 基于關(guān)系模型進(jìn)行數(shù)據(jù)流建模，給出了數(shù)據(jù)流環(huán)境下查詢的較完備的形式化定義。另外還有其他一些數(shù)據(jù)流項(xiàng)目，例如COUGAR[22]是Cornell大學(xué)的一個(gè)傳感器網(wǎng)絡(luò)環(huán)境中的數(shù)據(jù)庫(kù)項(xiàng)目，支持一種面向?qū)ο蟮牟樵冋Z言，將傳感器產(chǎn)生的數(shù)據(jù)定義為一個(gè)抽象數(shù)據(jù)類型，這樣傳感器輸出的就是一個(gè)時(shí)間序列的數(shù)據(jù)流。StatStream[23]是紐約大學(xué)的跨多個(gè)數(shù)據(jù)流計(jì)算統(tǒng)計(jì)值的實(shí)時(shí)數(shù)據(jù)流統(tǒng)計(jì)系統(tǒng)。

結(jié)合上述研究成果，對(duì)提出的問題進(jìn)行分析和總結(jié)。本文試圖克服以上文獻(xiàn)中的片面性，以一種全新的數(shù)據(jù)流實(shí)時(shí)處理的視角來重點(diǎn)介紹數(shù)據(jù)流查詢領(lǐng)域的重點(diǎn)研究問題和解決辦法。傳統(tǒng)數(shù)據(jù)庫(kù)模型對(duì)查詢的精度、準(zhǔn)確性有較高的要求，相反數(shù)據(jù)流模型對(duì)詢計(jì)劃執(zhí)行的實(shí)時(shí)性和自適應(yīng)調(diào)整這兩個(gè)方面要求比較高。正是基于數(shù)據(jù)流模型和數(shù)據(jù)庫(kù)模型在數(shù)據(jù)流查詢領(lǐng)域的差異性，引出了三個(gè)重要子問題。

（1）在越來越多的數(shù)據(jù)流應(yīng)用場(chǎng)景中，數(shù)據(jù)模態(tài)越來越多，例如文本、圖片、音頻、視頻等。針對(duì)不同數(shù)據(jù)模態(tài)下的“操作算子”的屬性也千差萬別。將針對(duì)不同數(shù)據(jù)模態(tài)下的“操作算子”稱為過濾器。這樣，在數(shù)據(jù)流環(huán)境下的各種過濾器的屬性（開銷，選擇性……）就各不相同，如果將開銷較小的過濾器優(yōu)先計(jì)算，那么對(duì)同一個(gè)元組的處理速度就要比其他策略要快。這就是過濾器的排序問題。過濾器排序問題是數(shù)據(jù)流處理領(lǐng)域最重要的問題之一。

（2）在很多數(shù)據(jù)流應(yīng)用場(chǎng)景中，由于數(shù)據(jù)流之間的相關(guān)性越來越大，不同數(shù)據(jù)流之間通過各種屬性（如網(wǎng)絡(luò)流中四元組、時(shí)間戳、模態(tài)內(nèi)容相似性）進(jìn)行關(guān)聯(lián)，這樣就需要跨多個(gè)數(shù)據(jù)流進(jìn)行融合過濾、分析、查詢、管理，將這個(gè)問題稱為多數(shù)據(jù)流融合計(jì)算。多數(shù)據(jù)流融合計(jì)算問題的核心是設(shè)計(jì)高效的多數(shù)據(jù)流之間的連接算子（Join operator）。多數(shù)據(jù)流的連接算子的設(shè)計(jì)是數(shù)據(jù)流領(lǐng)域的熱點(diǎn)問題之一。

（3）自適應(yīng)查詢優(yōu)化在數(shù)據(jù)流查詢系統(tǒng)中，執(zhí)行引擎通常將查詢解析成執(zhí)行計(jì)劃，執(zhí)行計(jì)劃的單元是操作算子[1]。隨著數(shù)據(jù)流中數(shù)據(jù)時(shí)刻變化，同一個(gè)操作算子在不同時(shí)刻所需要的資源也是時(shí)刻變化，在有限存儲(chǔ)計(jì)算資源的情況下，如何自適應(yīng)的優(yōu)化執(zhí)行計(jì)劃以高效的處理實(shí)時(shí)數(shù)據(jù)流是數(shù)據(jù)流查詢領(lǐng)域中一個(gè)很重要的研究熱點(diǎn)。這個(gè)問題稱為自適應(yīng)查詢優(yōu)化[33]。

在余下的章節(jié)，按照以上列出的數(shù)據(jù)流查詢領(lǐng)域的主要問題分別進(jìn)行具體介紹：第二部分主要介紹共享過濾器排序問題;第三部分主要介紹數(shù)據(jù)流領(lǐng)域的主要連接算子研究進(jìn)展情況;第四部分主要介紹自適應(yīng)查詢優(yōu)化問題以及目前的進(jìn)展，最后對(duì)本文工作進(jìn)行總結(jié)。

2 共享過濾器排序

為了有效地過濾數(shù)據(jù)流中特定信息，人們常常在數(shù)據(jù)流上注冊(cè)大量的查詢，同時(shí)訓(xùn)練大量的過濾器。在數(shù)據(jù)流環(huán)境中，查詢和過濾器常常是一種“多對(duì)多”的連接，也就是說對(duì)于單個(gè)過濾器的判斷可能會(huì)同時(shí)給出多個(gè)查詢的結(jié)果。在這種情況下，如何排序所有的過濾器來獲得最小的過濾代價(jià)變得非常重要。對(duì)于過濾器的排序一般依賴于三個(gè)指標(biāo)：過濾器本身的執(zhí)行代價(jià)（c）、過濾器連接的查詢數(shù)目（p）以及過濾器對(duì)于隨機(jī)樣本判斷為真的概率（s）。針對(duì)過濾器的排序問題一般分為相關(guān)過濾器排序和獨(dú)立過濾器排序兩個(gè)子問題。其中，相關(guān)過濾器排序是指過濾器之間存在概率關(guān)系的情況下對(duì)過濾器進(jìn)行排序。相反，獨(dú)立過濾器排序問題則是相對(duì)比較理想的情況下，假設(shè)所有的過濾器都是相互獨(dú)立。后者在數(shù)據(jù)流領(lǐng)域被廣泛關(guān)注。

2.1 獨(dú)立共享過濾器排序問題

獨(dú)立共享過濾器排序是指所有數(shù)據(jù)流系統(tǒng)中所有過濾器之間都是相互獨(dú)立的，一個(gè)過濾器的計(jì)算結(jié)果不會(huì)對(duì)其他過濾器的計(jì)算結(jié)果產(chǎn)生任何影響。在數(shù)據(jù)流環(huán)境中，查詢和過濾器常常是一種“多對(duì)多”的連接，即一條查詢中包含多個(gè)過濾器，一個(gè)過濾器可以同時(shí)出現(xiàn)在多條查詢中，這樣對(duì)于單個(gè)過濾器的判斷可能會(huì)同時(shí)給出多個(gè)查詢的結(jié)果。也就是說，查詢間有共享的過濾器，每個(gè)查詢都是過濾器的“聚合”，過濾器之間是“與”關(guān)系。在每個(gè)過濾器計(jì)算開銷已知的情況下，如何排序所有的過濾器來獲得最小的過濾代價(jià)變得非常重要。尤其是在多數(shù)據(jù)流環(huán)境中，能否自適應(yīng)的調(diào)整計(jì)算順序來使得代價(jià)最小化。這就是本文關(guān)注的“獨(dú)立共享過濾”問題。下面給出共享過濾問題的描述。如圖1所示，用Q1;Q2;Q3;Q4來表示注冊(cè)的四條查詢。用F1;F2;F3;F4 來表示連接的過濾器。目標(biāo)就是以最小的代價(jià)來完成所有查詢的計(jì)算。在圖 1 中如果F2返回為“假”，那么Q1和Q2的結(jié)果就是“假”。其他相關(guān)的過濾器就不需要再計(jì)算，只需要去關(guān)注與Q3相關(guān)的過濾器即可。這個(gè)問題就是共享過濾問題。最先由文獻(xiàn)[1]提出。

解決共享過濾問題需要考慮的因素如下：過濾器本身的執(zhí)行代價(jià)（c），過濾器連接的查詢數(shù)目（p）以及過濾器對(duì)于隨機(jī)樣本判斷為“真”的概率（s）。一般來講，s 越小的過濾器計(jì)算次序越應(yīng)該靠前，因?yàn)閟 越小，表示其返回為“假”的概率越大，一旦這個(gè)過濾器返回為“假”，能排除所有包含這個(gè)過濾器的查詢。同樣，p 越大的過濾器越應(yīng)該首先被計(jì)算，如果這個(gè)過濾器的計(jì)算結(jié)果為“假”，由于包含它的查詢數(shù)量較多，這樣就能排除較多的查詢。同樣，也應(yīng)該首先計(jì)算c 值較小的過濾器。綜上，共享過濾問題的復(fù)雜性就在于如何以一種統(tǒng)一的策略來綜合考慮三個(gè)因素來實(shí)現(xiàn)計(jì)算開銷最小化的目標(biāo)，以自適應(yīng)的調(diào)整計(jì)算次序來處理實(shí)時(shí)的數(shù)據(jù)流。共享過濾問題是由A. Kemper[24]最先提出。他們不僅證明了這是NP難問題。這實(shí)質(zhì)上暗示著在多項(xiàng)式時(shí)間解決這類問題的有效算法不存在，如何在多項(xiàng)式時(shí)間內(nèi)得到這類問題的近似解是努力的方向。Liuzhen[8] 提出了近優(yōu)算法來解決共享過濾問題并從理論證明了相似解的可求性，同時(shí)他們通過實(shí)驗(yàn)結(jié)果論證了近優(yōu)算法的性能提升。以上工作都是結(jié)合先驗(yàn)知識(shí)來固定過濾器的參數(shù)s 顯然無法適應(yīng)網(wǎng)絡(luò)數(shù)據(jù)流內(nèi)容不斷變化的環(huán)境，同時(shí)以前的工作只是簡(jiǎn)單的將三個(gè)指標(biāo)融合成一個(gè)代價(jià)函數(shù)進(jìn)行排序，而沒有深入分析各個(gè)指標(biāo)之間的關(guān)系。

2.2 相關(guān)過濾器排序問題

相關(guān)過濾器排序問題一直是過濾器排序問題中的難點(diǎn)。相關(guān)共享過濾器排序的問題更加貼近于真實(shí)的數(shù)據(jù)流過濾情況。相關(guān)共享過濾器排序同樣是NP難問題。國(guó)外對(duì)相關(guān)過濾器排序的研究進(jìn)展情況為：文獻(xiàn)[25] 嘗試用一種全面搜索來選擇下一個(gè)要計(jì)算的過濾器。文獻(xiàn)[26] 則提出了一種啟發(fā)式算法。文獻(xiàn)[27， 28， 29] 則提出了一些近似算法來解決這個(gè)問題。文獻(xiàn)[1] 將共享過濾器排序映射為并行集合覆蓋問題。在文獻(xiàn)[29] 中提出了線性規(guī)劃框架作為共享集合覆蓋問題的近似解決辦法。文獻(xiàn)[8] 所做的工作都是在假設(shè)所有過濾器都是相互獨(dú)立的情況下開展，論文不止一次提到相關(guān)過濾器的排序是非常有挑戰(zhàn)性的工作。

3 數(shù)據(jù)流上的連接運(yùn)算

傳統(tǒng)的數(shù)據(jù)庫(kù)引擎主要側(cè)重基于磁盤IO的優(yōu)化，這樣可以支持高速率的數(shù)據(jù)讀寫。數(shù)據(jù)庫(kù)查詢操作通常有多層嵌套的循環(huán)節(jié)點(diǎn)比較操作實(shí)現(xiàn)，所以數(shù)據(jù)庫(kù)優(yōu)化的目標(biāo)是盡量減少查詢操作中的循環(huán)次數(shù)。這種優(yōu)化目標(biāo)顯然不適應(yīng)于較新的數(shù)據(jù)流領(lǐng)域。本文主要是介紹數(shù)據(jù)流領(lǐng)域的查詢優(yōu)化，所以在這部分重點(diǎn)介紹了三個(gè)比較重要的連接操作算子（Join operator）。在3.1節(jié)中重點(diǎn)介紹對(duì)稱哈希連接算子。實(shí)現(xiàn)對(duì)兩個(gè)數(shù)據(jù)流的并行連接運(yùn)算。在3.2節(jié)中重點(diǎn)介紹多數(shù)據(jù)流（大約等于2）上的連接算子—多路連接（M-join[36]）。

3.1 對(duì)稱哈希連接

首先解釋了傳統(tǒng)哈希連接不適用于自適應(yīng)查詢[33]的原因。傳統(tǒng)的哈希連接運(yùn)算可以簡(jiǎn)單分為兩個(gè)過程：構(gòu)建（Build）和探測(cè)（Probe）。這兩個(gè)過程不能并行，必須構(gòu)建過程完成后才能開始探測(cè)過程，這顯然不適用于數(shù)據(jù)流連接運(yùn)算。由于，在數(shù)據(jù)流環(huán)境下元組并不是全部達(dá)到的，同時(shí)傳統(tǒng)的哈希連接也不適用于分布式數(shù)據(jù)源處理的場(chǎng)景中，當(dāng)數(shù)據(jù)源分布在異處的情況下，是不可以一次性獲取到所有元組的。在數(shù)據(jù)流領(lǐng)域中，元組是持續(xù)到來的，優(yōu)先想持續(xù)獲得元組的計(jì)算結(jié)果。文獻(xiàn)[30，31]首先引入了對(duì)稱哈希連接這個(gè)概念。

如圖2所示，當(dāng)數(shù)據(jù)流A或者數(shù)據(jù)流B中任意一個(gè)元組進(jìn)入對(duì)稱哈希連接算子以后，會(huì)存儲(chǔ)到對(duì)應(yīng)的哈希表中，這個(gè)過程相當(dāng)于原來的構(gòu)建過程，然后去探測(cè)對(duì)稱的哈希表。算法 1 詳細(xì)描述了對(duì)稱哈希連接的處理邏輯?；趯?duì)稱哈希連接處理數(shù)據(jù)流的思想，后來出現(xiàn)了很多類似的連接算子：文獻(xiàn)[32]提出了XJoin主要是在原來對(duì)稱哈希連接的基礎(chǔ)上解決了內(nèi)存有限的情況，將數(shù)據(jù)緩存到磁盤。文獻(xiàn)[34]將連接算子移植到一個(gè)多線程框架中，將數(shù)據(jù)流處理看成是一種生產(chǎn)者——消費(fèi)者模型，同時(shí)也考慮了當(dāng)內(nèi)存空間不足的情況下將溢出流緩存到磁盤中的情況。

3.2 多路連接運(yùn)算

將多路連接（M-join[36]）看成是對(duì)稱哈希連接向多數(shù)據(jù)流的自然擴(kuò)展。文獻(xiàn)[35， 36] 首先提出了多路連接的概念：將對(duì)稱哈希連接推廣到多數(shù)據(jù)流（大于2）的情況，允許數(shù)據(jù)流中的元組按照任意順序到達(dá)。同時(shí)，文獻(xiàn)[35， 36] 說明了多路連接比由二叉連接算子構(gòu)建的樹結(jié)構(gòu)具有的優(yōu)勢(shì)，并證明了多路連接非常適合于數(shù)據(jù)流處理和自適應(yīng)查詢，如圖4所示。圖3是一個(gè)典型的三路連接算子實(shí)例。多路連接算子通過在每個(gè)連接相關(guān)屬性上構(gòu)建哈希索引。如圖 3 所示，基于表B 的兩個(gè)哈希索引共享著數(shù)據(jù)流B上的元組。其他數(shù)據(jù)流表A，C 上分別構(gòu)建了一個(gè)哈希索引。路由器作為一個(gè)輕量級(jí)的調(diào)度算子，完成所有數(shù)據(jù)流上元組的調(diào)度，這個(gè)調(diào)度算子和Eddy框架[35]中的調(diào)度算子非常類似。當(dāng)任意一個(gè)數(shù)據(jù)流中有元組到達(dá)時(shí)，首先是要將該元組插入到所屬的哈希表中，然后按照一種特定的順序去依次探測(cè)其他的相關(guān)數(shù)據(jù)流，探測(cè)順序的選擇和共享過濾器排序問題非常相似，可用相同的思路來解決。

4 查詢優(yōu)化

查詢優(yōu)化的過程就是自適應(yīng)查詢處理的過程。在傳統(tǒng)的數(shù)據(jù)庫(kù)領(lǐng)域，查詢的處理策略是：先計(jì)劃，再執(zhí)行。也就是，查詢引擎首先決策出一個(gè)開銷最小的查詢執(zhí)行計(jì)劃，然后查詢執(zhí)行器來完成計(jì)劃的執(zhí)行。鑒于數(shù)據(jù)流查詢中，數(shù)據(jù)流在速度和內(nèi)容上具有不可預(yù)測(cè)性。因此，數(shù)據(jù)元組突變性可能會(huì)使得優(yōu)化本次選擇的執(zhí)行計(jì)劃在下一個(gè)數(shù)據(jù)元組的查詢中會(huì)引起性能驟降[50， 37]，這樣就使得自適應(yīng)查詢處理在數(shù)據(jù)流領(lǐng)域被廣泛關(guān)注[38]。自適應(yīng)查詢的主要研究動(dòng)機(jī)是：

（1）由于數(shù)據(jù)流的突變，可能會(huì)導(dǎo)致本次的最優(yōu)查詢計(jì)劃在下一次元組處理中的開銷增加。自適應(yīng)查詢處理需要及時(shí)發(fā)現(xiàn)這種不適應(yīng)并采取一些糾正措施;

（2）自適應(yīng)查詢處理可以及時(shí)探知數(shù)據(jù)源的未知屬性并選擇最優(yōu)查詢計(jì)劃;

（3）鑒于數(shù)據(jù)流系統(tǒng)的資源限制條件，自適應(yīng)查詢處理要能夠及時(shí)的根據(jù)當(dāng)前系統(tǒng)資源和輸入條件的限制做出最優(yōu)計(jì)劃的決策。

自適應(yīng)的查詢處理可以避免因?yàn)樗腊宓牟樵冇?jì)劃帶來的性能抖動(dòng)，使得數(shù)據(jù)流系統(tǒng)的查詢性能趨于穩(wěn)定[45， 37]。在自適應(yīng)的查詢處理模型中，查詢的執(zhí)行被嚴(yán)格的劃分為優(yōu)化階段和執(zhí)行階段。這兩個(gè)階段相互獨(dú)立。這樣可以使得查詢的處理過程中可以及時(shí)的糾正因?yàn)閮?yōu)化策略帶來的性能顛簸。自適應(yīng)查詢處理在過去幾年中的進(jìn)展情況為：

（1）所有自適應(yīng)查詢處理的工作集中在最近的十年內(nèi);

（2）在自適應(yīng)查詢處理領(lǐng)域的主要研究工作具有很大的差異性，這些差異性主要體現(xiàn)在查詢語義的不同，不同的數(shù)據(jù)源，開銷度量方式的差異，優(yōu)化框架的差異以及不同的自適應(yīng)定義;

（3）自適應(yīng)查詢處理的框架主要包括三個(gè)重要的組成部分。

1）優(yōu)化器：選擇一種開銷最小的執(zhí)行計(jì)劃;

2）執(zhí)行器：按照當(dāng)前選擇的執(zhí)行計(jì)劃來完成查詢的執(zhí)行操作;

3）統(tǒng)計(jì)跟蹤器：統(tǒng)計(jì)在查詢執(zhí)行過程中的系統(tǒng)資源信息，查詢開銷信息等。以供優(yōu)化器在優(yōu)化過程中使用。

文獻(xiàn)[38]第一次對(duì)數(shù)據(jù)流系統(tǒng)按照查詢執(zhí)行策略進(jìn)行了分類并對(duì)系統(tǒng)的性能表現(xiàn)進(jìn)行了詳細(xì)的對(duì)比。對(duì)主流的數(shù)據(jù)流系統(tǒng)按照查詢執(zhí)行的策略分為三類。

（1）基于計(jì)劃的系統(tǒng)：傳統(tǒng)“先計(jì)劃，再執(zhí)行”的查詢執(zhí)行模式的擴(kuò)展。主要的擴(kuò)展體現(xiàn)在增加了統(tǒng)計(jì)跟蹤器、自適應(yīng)查詢，如圖5所示。統(tǒng)計(jì)跟蹤器用來收集查詢執(zhí)行過程中的系統(tǒng)信息來作為優(yōu)化器重新優(yōu)化的重要數(shù)據(jù)參考。

（2）基于路由的系統(tǒng)：以Eddy[19]和River[39]作為這個(gè)分支的經(jīng)典代表。核心思想是將數(shù)據(jù)流上的元組的查詢過程看成一個(gè)個(gè)的數(shù)據(jù)包在操作算子間的路由。因此，所有的優(yōu)化策略都是基于數(shù)據(jù)流元組級(jí)別。自適應(yīng)查詢處理的流程如圖6所示。

（3）基于持續(xù)查詢的系統(tǒng)：以CAPE[17]、NiagaraCQ[40]、StreaMon[49]作為這個(gè)分支的經(jīng)典代表，是數(shù)據(jù)流領(lǐng)域查詢處理的主要模型。重點(diǎn)考慮大量查詢?cè)诰€注冊(cè)的情況下，將查詢和數(shù)據(jù)流元組的變化常態(tài)化，重點(diǎn)關(guān)注優(yōu)化器自適應(yīng)的調(diào)整操作算子的順序來完成查詢的執(zhí)行過程。自適應(yīng)查詢處理的流程如圖 7 所示。

依據(jù)上面的分類，對(duì)近年來主流的數(shù)據(jù)查詢處理系統(tǒng)進(jìn)行簡(jiǎn)單的歸類和簡(jiǎn)單說明，如表1所示。

5 結(jié)束語

本文回顧了數(shù)據(jù)流領(lǐng)域的國(guó)內(nèi)和國(guó)際上在該領(lǐng)域的主要研究成果，從數(shù)據(jù)流過濾的視角重新審視自適應(yīng)查詢的問題，綜述了在數(shù)據(jù)流模型中自適應(yīng)查詢出現(xiàn)的主要問題（過濾器排序、數(shù)據(jù)流連接、查詢優(yōu)化），并結(jié)合大規(guī)模數(shù)據(jù)流安全檢測(cè)背景，形成了下一步的研究思路。

（1）過濾器排序：在數(shù)據(jù)流環(huán)境下的各種過濾器的屬性（開銷、選擇性、窗口等）差異較大，以往工作均是結(jié)合自身過濾器屬性構(gòu)建簡(jiǎn)單的排序算法，普遍不具備自適應(yīng)調(diào)整能力。下一步的工作重點(diǎn)是普適性的過濾器度量模型和自適應(yīng)排序算法。

（2）數(shù)據(jù)流連接：隨著大數(shù)據(jù)和高通量計(jì)算需求日益旺盛，跨多數(shù)據(jù)流進(jìn)行融合過濾、分析、查詢、管理歸類為多流融合計(jì)算問題。多流融合計(jì)算問題的關(guān)鍵是設(shè)計(jì)高效的多數(shù)據(jù)流間的連接算法和環(huán)境感知關(guān)聯(lián)模型。通過研究發(fā)現(xiàn)，當(dāng)前工作中對(duì)連接算法普遍采用數(shù)據(jù)庫(kù)連接計(jì)算方法，缺乏對(duì)數(shù)據(jù)流和大數(shù)據(jù)環(huán)境下的環(huán)境感知能力，下一步重點(diǎn)考慮構(gòu)建具備環(huán)境感知能力的數(shù)據(jù)流關(guān)聯(lián)計(jì)算模型。

基金項(xiàng)目：

1.國(guó)家自然科學(xué)基金聯(lián)合基金（項(xiàng)目編號(hào)：U1936111）;

2.北京信息科技大學(xué)?；痦?xiàng)目（項(xiàng)目編號(hào)：5221910933）。

參考文獻(xiàn)

[1] S. Babu， R. Motwani， K. Munagala， I. Nishizawa， and J. Widom：Adaptive ordering of pipelined stream filters. In SIGMOD04： Proceedings of the ACM SIGMOD International Conference on Management of Data， pp. 407-418 （ 2004）

[2] Chris Olston ， Jing Jiang ， Jennifer Widom， Adaptive filters for continuous queries over distributed data streams， Proceedings of the 2003 ACM SIGMOD international conference on Management of data， June 09-12， 2003， San Diego， California

[3] A. Arasu， B. Babcock， S. Babu， M. Datar， K. Ito， I. Nishizawa， J. Rosenstein， J. Widom. STREAM： the stanford stream data manager， in： Proceedings of the SIGMOD， 2003， p. 665.

[4] H.-H. Lee， E.-W. Yun and W.-S. Lee， Attribute-based evaluation of multiple continuous queries for filtering incoming tuples of a data stream， Information Sciences 178 （11） （2008）， pp. 2416–2432

[5] Moses Charikar ， Kevin Chen ， Martin Farach-Colton， Finding Frequent Items in Data Streams， Pro-ceedings of the 29th International Colloquium on Automata， Languages and Programming， p.693-703， July 08-13， 2002

[6] J. Feigenbaum ， S. Kannan ， M. Strauss ， M. Viswanathan， An Approximate L1-Di?erence Algorithm for Massive Data Streams， Proceedings of the 40th Annual Symposium on Foundations of Computer Science， p.501， October 17-18， 1999

[7] Anna C. Gilbert ， Yannis Kotidis ， S. Muthukrishnan ， Martin Strauss， Surfing Wavelets on Streams： One-Pass Summaries for Approximate Aggregate Queries， Proceedings of the 27th International Conference on Very Large Data Bases， p.79-88， September 11-14， 2001

[8] Zhen Liu ， Srinivasan Parthasarathy ， Anand Ranganathan ， Hao Yang， Near-optimal algorithms for shared filter evaluation in data stream systems， Proceedings of the 2008 ACM SIGMOD international conference on Management of data （2008）

[9] D. Terry， D. Goldberg， D. Nichols， and B. Oki. Continuous queries over append-only databases. In Proc. of the 1992 ACM SIGMOD Intl. Conf. on Management of Data， pages321–330， June 1992.

[10] M. Altinel and M. J. Franklin. E?cient filtering of XML documents for selective dissemination of information. In Proc. of the 2000 Intl. Conf. on Very Large Data Bases，pages 53–64， Sept. 2000.

[11] Xml path language （XPath） version 1.0， Nov. 1999.W3C Recommendation available at http：//www.w3.org/TR/xpath.

[12] B. Nguyen， S. Abiteboul， G. Cobena， andM. Preda.Monitoring XML data on the web. In Proc. of the 2001 ACM SIGMOD Intl. Conf. on Management of Data， pages437–448，May 2001.

[13] M. Sullivan. Tribeca： A stream databasemanager for network tra?c analysis. In Proc. of the 1996 Intl. Conf. on Very Large Data Bases， page 594， Sept. 1996.

[14] L. Liu， C. Pu， andW. Tang. Continual queries for internet scale event-driven information delivery. IEEE Trans. on Knowledge and Data Engineering， 11（4）：583–590， Aug.1999.

[15] J. Chen， D. J. DeWitt， F. Tian， and Y. Wang. NiagraCQ： A scalable continuous query system for internet databases. In Proc. of the 2000 ACM SIGMOD Intl. Conf. on Management of Data， pages 379–390，May 2000.

[16] S. Babu and J. Widom：Continuous queries over data streams. SIGMODRec.， vol. 30， no. 3， pp. 109–120， 2001.

[17] J. Hellerstein， M. Franklin， et al. Adaptive query processing： Technology in evolution. IEEE Data Engineering Bulletin， 23（2）：7–18， June 2000.

[18] R. Avnur and J. Hellerstein. Eddies： Continuously adaptive query processing. In Proc. of the 2000 ACM SIGMOD Intl. Conf. on Management of Data， pages 261–272，May 2000.

[19] S. Madden andM. J. Franklin. Fjording the stream： An architecture for queries over streaming sensor data. In Proc. of the 2002 Intl. Conf. on Data Engineering， Feb. 2002. （To appear）.

[20] D. Carney， U. Cetinternel， M. Cherniack， C. Convey， S. Lee， G. Seidman，M. Stonebraker，N. Tatbul， and S. Zdonik. Monitoring streams –a new class of dbms applications. Technical Report CS-02-01， Department of Computer Science， Brown University， Feb. 2002.

[21] P. Bonnet， J. Gehrke， P. Seshadri. Towards Sensor Database System. In Proc. Int. Conf. On Mobile Data Management， 2001， pages 3-14.

[22] Y. Zhu， D. Shasha. StatStream： Statistical Monitoring of Thousands of Data Streams in Real Time. In Proc. Int. Conf. On Very Large Data Bases， 2002， pp. 358-369.

[23] K. Munagala， U. Srivastava， and J. Widom.Optimization of continuous queries with shared expensive filters. In PODS07： Proceedings of the 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems， pp. 215-224 （2007）

[24] A. Kemper， G. Moerkotte， and M. Steinbrunn. Optimizing boolean expressions in object-bases. In Proc. of the 1992 Intl. Conf. on Very Large Data Bases， pages 79–90， Aug. 1992.

[25] K. Ross. Conjunctive selection conditions in main memory. In Proc. of the 2002 ACM Symp. on Prin-ciples of Database Systems， June 2002.

[26] E. Cohen， A. Fiat， and H. Kaplan. E?cient sequences of trials. In Proc. of the 2003 Annual ACM-SIAM Symp. on Discrete Algorithms， Jan. 2003.

[27] U. Feige， L. Lov′asz， and P. Tetali. Approximating min-sum set cover. In Proc. of the 5th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization （APPROX）， Sept. 2002.

[28] K. Munagala， S. Babu， R. Motwani， and J. Widom. The pipelined set cover problem. Technical report， Stanford University Database Group， Oct. 2003. Available at http：//dbpubs.stanford.edu/pub/2003-65.

[29] L. Raschid and S. Y. W. Su， “A parallel processing strategy for evaluating recursive queries，”in VLDB 86： Proceedings of the 12th International ConReferences ference on Very Large Data Bases， pp. 412–419， Morgan Kaufmann Publishers Inc.， 1986.

[30] A. N. Wilschut and P. M. G. Apers， “Dataflow query execution in a parallel main-memory environ-ment，”in PDIS 91： Proceedings of the First International Conference on Parallel and Distributed Information Systems， Fontainebleu Hilton Resort， Miami Beach， FL， pp. 68–77， IEEE Computer Soci-ety， 1991.

[31] T. Urhan and M. J. Franklin， “XJoin： a reactively-scheduled pipelined join operator，”IEEE Data Engineering Bulletin， vol. 23， no. 2， pp. 27–33， 2000.

[32] Amol Deshpande ， Zachary Ives ， Vijayshankar Raman， Adaptive query processing， Foundations and Trends in Databases， v.1 n.1， p.1-140， January 2007

[33] Z. G. Ives， D. Florescu， M. Friedman， A. Levy， and D. S. Weld， “An adaptive query execution system for data integration，”in SIGMOD 99： Proceedings of the 1999 ACM SIGMOD international conference on Management of data， （New York， NY， USA）， pp. 299–310， ACM Press， 1999.

[34] V. Raman， A. Deshpande， and J. M. Hellerstein， “Using state modules for adaptive query process-ing.，”in ICDE 03： Proceedings of the 19th International Conference on Data Engineering， Bangalore， India， pp. 353–364， 2003.

[35] S. Viglas， J. F. Naughton， and J. Burger， “Maximizing the output rate of multi-way join queries over streaming information sources，”in VLDB 03： Proceedings of the 29th International Conference on Very Large Data Bases， Berlin， Germany： Morgan Kaufmann， September 9–12 2003.

[36] R. Avnur and J. M. Hellerstein， “Eddies： continuously adaptive query processing，”in SIGMOD 00： Proceedings of the 2000 ACM SIGMOD international conference on Management of data， （New York， NY， USA）， pp. 261–272， ACM Press， 2000.

[37] S. Babu and P. Bizarro， ”Adaptive query processing in the looking glass，” in CIDR 05： Second Biennial Conference on Innovative Data Systems Research， pp. 238-249， Asilomar， CA， 2005.

[38] N. Kabra and D. DeWitt. E?cient mid-query reoptimization of sub-optimal query execution plans. In Proc. of the 1998 ACM SIGMOD Intl. Conf. on Management of Data， pages 106–117， June 1998.

[39] R. Arpaci-Dusseau. Run-time adaptation in river[J]. ACM Trans. on Computer Systems， 21（1）：36–86， 2003.

[40] J. Chen， D. DeWitt， F. Tian， and Y. Wang. NiagaraCQ： A scalable continuous query system for internet databases. In Proc. of the 2000 ACM SIGMOD Intl. Conf. on Management of Data， pages 379–390， May 2000.

[41] Z. Ives， D. Florescu， M. Friedman， A. Levy， and D. Weld. An adaptive query execution system for data integration. In Proc. of the 1999 ACM SIGMOD Intl. Conf. on Management of Data， pages 299–310， June 1999.

[42] [45] K. Ng， Z. Wang， R. Muntz， and S. Nittel. Dynamic query re-optimization. In Proc. of the 1999 Intl. Conf. on Scientific and Statistical Database Management， pages 264–273， July 1999.

[43] B. Dageville and M. Zait. SQL memory management in Oracle9i. In Proc. of the 2002 Intl. Conf. on Very Large Data Bases， pages 962–973， Aug. 2002.

[44] E. Wong and K. Youssefi. Decomposition - a strategy for query processing[J]. ACM Trans. on Database Systems， 1（3）， 1976.

[45] A. Deshpande and J. Hellerstein. Lifting the burden of history from adpative query processing. In Proc. of the 2004 Intl. Conf. on Very Large Data Bases， Aug. 2004.

[46] S. Madden， M. Shah， J. Hellerstein， and V. Raman. Continuously adaptive continuous queries over streams. In Proc. of the 2002 ACM SIGMOD Intl. Conf. on Management of Data， pages 49–60， June 2002.

[47] V. Raman， A. Deshpande， and J. Hellerstein. Using state modules for adaptive query processing. In Proc. of the 2003 Intl. Conf. on Data Engineering， Mar. 2003.

[48] S. Babu， K. Munagala， J.Widom， and R. Motwani. Adaptive caching for continuous queries. In Proc. of the 2005 Intl. Conf. on Data Engineering， 2005. （To appear）.

[49] S. Babu and J. Widom. StreaMon： An adaptive engine for stream query processing. In Proc. of the 2004 ACM SIGMOD Intl. Conf. on Management of Data， June 2004. Demonstration proposal.

[50] S. Christodoulakis. Implications of certain assumptions in database performance evaluation[J]. ACM Trans. on Database Systems， 9（2）：163–186， 1984.

[51] 孟小峰， 周龍?bào)J， 王珊. 數(shù)據(jù)庫(kù)技術(shù)發(fā)展趨勢(shì)[J]. 軟件學(xué)報(bào)， 2004（12）：74-88

作者簡(jiǎn)介：

李軍（1983-），男，漢族， 山東滕州人，北京郵電大學(xué)，博士， 高級(jí)工程師，北京信息科技大學(xué)，教師;主要研究方向和關(guān)注領(lǐng)域：網(wǎng)絡(luò)信息安全、數(shù)據(jù)挖掘。

于靈凡（1998-），女，漢族，北京信息科技大學(xué)，本科;主要研究方向和關(guān)注領(lǐng)域：網(wǎng)絡(luò)流挖掘和管理。

田斌（1983-），男，漢族，北京郵電大學(xué)，博士，中國(guó)信息安全測(cè)評(píng)中心，高級(jí)工程師;主要研究方向和關(guān)注領(lǐng)域：網(wǎng)絡(luò)空間安全。

李犇（1986-），男，漢族，山東濟(jì)寧人，中國(guó)科學(xué)院大學(xué)，碩士，北京市公安局朝陽分局，副科級(jí)警察;主要研究方向和關(guān)注領(lǐng)域：網(wǎng)絡(luò)空間安全。

李曄（1986-），男，漢族，河北保定人，北京郵電大學(xué)，碩士，河北移動(dòng)網(wǎng)絡(luò)管理中心，工程師;主要研究方向和關(guān)注領(lǐng)域：網(wǎng)絡(luò)安全和管理。

康海燕（1971-），男，漢族，河北石家莊人，北京理工大學(xué)，博士，教授，北京信息科技大學(xué)，副院長(zhǎng);主要研究方向和關(guān)注領(lǐng)域：網(wǎng)絡(luò)空間安全。