基于硬件預(yù)處理的數(shù)據(jù)流并發(fā)連接查詢優(yōu)化算法

周虹+富春巖+支援+劉越+于占龍+薛佳楣+韋韞韜+王超+張立銘+李微娜

摘要：目前在金融、移動數(shù)據(jù)、網(wǎng)絡(luò)監(jiān)控及物聯(lián)網(wǎng)等領(lǐng)域中，經(jīng)常會需要處理一些海量的、實(shí)時的、需要快速響應(yīng)的數(shù)據(jù)流。為了對這些數(shù)據(jù)流進(jìn)行有效的管理，提出了基于硬件預(yù)處理的數(shù)據(jù)流管理系統(tǒng)，并對相應(yīng)的數(shù)據(jù)流并發(fā)連接算法進(jìn)行了優(yōu)化，以得到數(shù)據(jù)流預(yù)處理器所需的控制信息。

關(guān)鍵詞：數(shù)據(jù)流管理系統(tǒng)；連續(xù)查詢；查詢優(yōu)化

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）33-0025-02

數(shù)據(jù)流的特點(diǎn)是：數(shù)據(jù)具有實(shí)時性，需要即時響應(yīng)；數(shù)據(jù)量大，而且無界；它還具有不可預(yù)知性，不可預(yù)期、無法控制數(shù)據(jù)流中元素的到達(dá)次序。以上這些特點(diǎn)都決定了，對數(shù)據(jù)流的查詢只能近似實(shí)時。而且，目前大多數(shù)基于軟件實(shí)現(xiàn)的數(shù)據(jù)流管理系統(tǒng)的處理速度都是有一定限制的。當(dāng)數(shù)據(jù)流的流速達(dá)到一定的速度之后，就會出現(xiàn)瓶頸，利用軟件就難以實(shí)現(xiàn)了。目前看來，比較可行的方法是來設(shè)計(jì)專門的硬件進(jìn)行預(yù)處理來解決這個問題，即將數(shù)據(jù)流處理的某些操作利用硬件來實(shí)現(xiàn)。

提高對數(shù)據(jù)流連接操作的處理效率，是解決數(shù)據(jù)流管理系統(tǒng)中，如何提高處理速度的關(guān)鍵問題。利用多條數(shù)據(jù)流并發(fā)執(zhí)行連接理論上可以提高處理效率，但是如何處理連接順序又在很大程度上影響了系統(tǒng)的速度。因此，如何優(yōu)化數(shù)據(jù)流并發(fā)連接查詢算法則成為了研究數(shù)據(jù)流管理系統(tǒng)的關(guān)鍵技術(shù)之一。

1 基于硬件預(yù)處理的數(shù)據(jù)流管理系統(tǒng)

目前基于硬件預(yù)處理的數(shù)據(jù)流管理系統(tǒng)主要由兩部分組成，包括：位于前端的預(yù)處理器和位于后端的數(shù)據(jù)引擎部分。位于前端的預(yù)處理器主要功能是完成對數(shù)據(jù)流的預(yù)處理操作?？梢詫蠖藗鬏斶^來的一些控制命令進(jìn)行初始化處理，還可以對數(shù)據(jù)流中的數(shù)據(jù)進(jìn)行濾波、壓縮和加標(biāo)記等處理工作。這種位于前端的預(yù)處理器，采用的是軟、硬件協(xié)同的方式進(jìn)行工作的，可以大大提高數(shù)據(jù)的處理速度。經(jīng)過前端預(yù)處理之后的數(shù)據(jù)通過網(wǎng)絡(luò)被傳輸?shù)胶蠖说臄?shù)據(jù)引擎部分。

系統(tǒng)后端的數(shù)據(jù)引擎主要的功能是進(jìn)行連續(xù)查詢的語法分析、生成要進(jìn)行并行查詢的計(jì)劃、將經(jīng)過預(yù)處理的元組分到相應(yīng)的數(shù)據(jù)緩存中，將通過并行處理后得到的查詢結(jié)果再進(jìn)行組裝分發(fā)，后端數(shù)據(jù)引擎還負(fù)責(zé)負(fù)載的均衡、服務(wù)質(zhì)量的監(jiān)控等功能。用戶提交的查詢要經(jīng)過詞法及語義的分析、要進(jìn)行查詢優(yōu)化才能得到所需的查詢抽象語法樹，在后端要對生成的抽象語法樹用相應(yīng)的算法進(jìn)行處理，得到所需控制信息，再將這些控制信息，經(jīng)過查詢輸出控制器交給前端的硬件查詢處理模塊進(jìn)行相應(yīng)的處理。

2 基于硬件預(yù)處理的數(shù)據(jù)流連續(xù)查詢語言X-SQL

在傳統(tǒng)的關(guān)系數(shù)據(jù)庫中，常用的查詢語言是SQL，它不能用于數(shù)據(jù)流查詢中，不支持?jǐn)?shù)據(jù)流中的連續(xù)查詢語義。為了處理數(shù)據(jù)流中的數(shù)據(jù)，就需要使用專門處理數(shù)據(jù)流查詢的語言。目前，用于數(shù)據(jù)流研究的查詢語言主要有：基于關(guān)系的、基于對象的和基于過程的這三種語言[1]。

在研究過程中，我們數(shù)據(jù)流管理系統(tǒng)使用的是基于硬件預(yù)處理的數(shù)據(jù)流連續(xù)流查詢語言X-SQL。它是一種基于關(guān)系查詢語言，具有類SQL 的句法規(guī)則，它還可以提供對窗口以及對排序的支持。通過基于關(guān)系的流語言，用戶即可指定查詢的語義，也定義數(shù)據(jù)流的采樣率。

X-SQL是用滑動窗口來實(shí)現(xiàn)連續(xù)查詢中的抽象語義的。我們可在系統(tǒng)后端進(jìn)行X-SQL連續(xù)查詢的輸入，再進(jìn)行交叉編譯得出相應(yīng)的一些查詢指令和信息，再通過網(wǎng)絡(luò)傳輸，將這些指令和數(shù)據(jù)輸送到硬件的預(yù)處理器中，即可進(jìn)行對數(shù)據(jù)流的各種查詢。

X-SQL由數(shù)據(jù)流定義語言和數(shù)據(jù)流查詢語言兩種語言構(gòu)成。其中，數(shù)據(jù)流定義語言是用來給數(shù)據(jù)流管理系統(tǒng)輸入元數(shù)據(jù)信息的，而數(shù)據(jù)流查詢語言則是實(shí)現(xiàn)對數(shù)據(jù)流進(jìn)行查詢的。

在X-SQL語言中，也是用SELECT語句來實(shí)現(xiàn)查詢功能的。只不過除了像傳統(tǒng)SQL語言一樣給出要返回的屬性選擇列表、要檢索數(shù)據(jù)的流的流列表和條件外，還有窗口聲明部分。窗口聲明部分是用來聲明相應(yīng)的滑動窗口大小的。語法如下所示：

X-SQL查詢語句通過WINDOW子句就可以實(shí)現(xiàn)對滑動窗口查詢，也就可以實(shí)現(xiàn)對數(shù)據(jù)流的連續(xù)查詢操作。

3 并發(fā)連接查詢的優(yōu)化算法

在基于硬件預(yù)處理的數(shù)據(jù)流管理系統(tǒng)中，當(dāng)用戶提交了查詢，該查詢首先要經(jīng)過編譯器的詞法分析、語法分析和語義分析。在進(jìn)行了這些分析之后，才能得一棵語義正確的查詢語法樹。然后再依據(jù)這棵語意正確的語法樹生成相應(yīng)的目標(biāo)代碼。但是，只是可以生成目標(biāo)代碼，用這種方法生成的代碼執(zhí)行效率并不高，我們?yōu)榱颂岣卟樵兿到y(tǒng)的工作效率，就需要對一些查詢進(jìn)行優(yōu)化。

3.1 對謂詞進(jìn)行化簡的優(yōu)化算法

對謂詞進(jìn)行化簡就是利用應(yīng)用邏輯運(yùn)算的相應(yīng)規(guī)則，將用到的謂詞表達(dá)式，等價(jià)地置換成更簡單的式子。謂詞化簡的邏輯運(yùn)算規(guī)則如下表1所示：

根據(jù)規(guī)則，我們設(shè)計(jì)出謂詞化簡算法，如下所示：

3.2 對謂詞進(jìn)行規(guī)范化優(yōu)化算法

除了可以對謂詞進(jìn)行化簡，我們還可以在X-SQL查詢中對謂詞的規(guī)則進(jìn)行規(guī)范化優(yōu)化，規(guī)謂詞范化優(yōu)化算法如下所示：

4 結(jié)論

目前來看，大多數(shù)的數(shù)據(jù)流管理系統(tǒng)基本還是基于軟件系統(tǒng)來實(shí)現(xiàn)管理的。那么，當(dāng)數(shù)據(jù)流速過快時，處理速度就出現(xiàn)問題。為了能提高數(shù)據(jù)流的處理速度，我們采用了基于硬件預(yù)處理的數(shù)據(jù)流管理系統(tǒng)。并對數(shù)據(jù)流查詢語言X-SQL進(jìn)行了優(yōu)化。通過查詢優(yōu)化，可得到查詢語法樹，再對相應(yīng)的語法樹進(jìn)行處理，即可生成基于硬件預(yù)處理的數(shù)據(jù)流管理系統(tǒng)所需的優(yōu)化的控制信息。

參考文獻(xiàn)：

[1] Qian Jiang-bo， Xu Hong-bing， Dong Yi-sheng， et al. FPGA Acceleration window Joins over Multiple Data Stream， Journal of Circuits， Systems， and Computers， 2012，14（4）：813-830.

[2] Babcock B， Babu S， Datar M， et al. Models and Issues in Data Stream Systems [J]. In Proc. of the 2014 ACM Symp， In Principles of Database Systems， 2014：12-16.