連續(xù)查詢硬處理器及相關(guān)算法研究.pdf

1、數(shù)據(jù)流的高速性和無限性以及計(jì)算機(jī)資源的有限性使得提高數(shù)據(jù)處理的速度成為數(shù)據(jù)流管理系統(tǒng)的關(guān)鍵。目前已有的數(shù)據(jù)流管理原型系統(tǒng)都是從查詢優(yōu)化、系統(tǒng)調(diào)度等方面來提高速度，在高速數(shù)據(jù)流環(huán)境下都存在明顯的不足。降載策略是解決高速數(shù)據(jù)流處理的一個方法，但也有局限性，如可用于聚集計(jì)算，但不能應(yīng)用于連接操作。本文基于數(shù)據(jù)管理技術(shù)發(fā)展的前瞻性考慮，以高速數(shù)據(jù)流為處理對象，．不局限于通過查詢優(yōu)化、系統(tǒng)調(diào)度等方法來提高數(shù)據(jù)流的處理速度，而是考慮采用一種全新的體

2、系結(jié)構(gòu)來加速數(shù)據(jù)處理。國內(nèi)外尚沒有這方面的研究報道，具有較高的創(chuàng)新性。本文內(nèi)容涉及多個研究領(lǐng)域，除數(shù)據(jù)庫技術(shù)外，還涉及具體的機(jī)器指令設(shè)計(jì)、便處理器設(shè)計(jì)利編澤技術(shù)等。本文的主要研究工作有以下幾方面： 1．在深入研究國際上先進(jìn)的數(shù)據(jù)流管理原型系統(tǒng)基礎(chǔ)上，提出了一種適合數(shù)據(jù)流并發(fā)連接處理的方法M3Join。該方法充分考慮數(shù)據(jù)的“流”特性，體現(xiàn)數(shù)據(jù)驅(qū)動特點(diǎn)，以多線程并行和類似路由器的處理方式保證數(shù)據(jù)的高速處理，同時注重查詢間和查詢內(nèi)的并

3、行。M3Join可用于硬件實(shí)現(xiàn)，為更高速度地處理數(shù)據(jù)流提供了可能。實(shí)驗(yàn)結(jié)果表明，M3Join具有良好的性能，能夠滿足多流多窗口的并發(fā)連接查詢的需要。 2．提出適合數(shù)據(jù)流連續(xù)查詢處理的架構(gòu)SeuStreams。在傳統(tǒng)數(shù)據(jù)庫中，由于需求是即時查詢而不是連續(xù)查詢，岡此通常不考慮并發(fā)查詢處理。一般處理原則是盡可能將選擇、投影操作移向查詢樹的葉節(jié)點(diǎn)。而在連續(xù)查詢中，由于存在大量并發(fā)查詢，如果先執(zhí)行選擇將破壞對于連接結(jié)果的共享性，而恰恰此時

4、的連接操作是最耗時的。本文深入研究了適合SeuStreams查詢處理的二種可共享連接結(jié)果的策略：Shared PushDown、PullUp和Filtered PulIUp。通過理論分析和實(shí)驗(yàn)證明，在數(shù)據(jù)流的連續(xù)查詢處理中，PullUp策略性能較低，而Filtered PullUp和SharedPushDown策略各有優(yōu)勢。由于Filtered PullUp處理簡單，消耗內(nèi)存相對較少，因此一般情況下Filtered PullUp是適合S

5、euStreams的最佳方案。 3．為進(jìn)一步提高系統(tǒng)處理的效率，我們也對并發(fā)連接查詢的優(yōu)化算法作了深入研究，提出數(shù)據(jù)流窗口迎接的近似優(yōu)化算法SQFGS。在并發(fā)查詢條件下，一條查詢的優(yōu)化可能會牽涉劍其它許多的查詢，迫使它們的修正正在執(zhí)行的查詢計(jì)劃。而查詢計(jì)劃的調(diào)整是非常復(fù)雜和耗資源的。我們提山的sQFGS優(yōu)化策略簡單易行，對一條查詢的優(yōu)化不會牽涉到其它查詢，理論和實(shí)驗(yàn)證明其性能在可接受的范圍內(nèi)。SQFGS策略尤其適用于硬件處理的查

6、詢計(jì)劃生成，當(dāng)然，SQFGS策略也適合丁杏詢更新頻率很高的系統(tǒng)。 4．絕人多數(shù)連續(xù)查詢處理算法是用軟件實(shí)現(xiàn)的，我們提出了用硬件加速數(shù)據(jù)流連接處理的方法，極人地提高了處理的速度。為了處理不同的連接條件，我們設(shè)計(jì)并實(shí)現(xiàn)了用于數(shù)據(jù)流連接的處理器WJSP及其指令系統(tǒng)WJSI，并提出集成方法以提高WJSP的擴(kuò)展性和并行性，同時也提高處理的速度。我們將WJSP與STREAM原型作了比較，結(jié)果顯示wJSP比STREAM的速度提高20多倍，說明