海量數(shù)據(jù)查詢處理算法的研究.pdf

1、時(shí)至今日,海量數(shù)據(jù)時(shí)代的來(lái)臨已經(jīng)毋庸置疑。高速計(jì)算技術(shù)和先進(jìn)的自動(dòng)感應(yīng)技術(shù)使得產(chǎn)生和收集大量數(shù)據(jù)成為可能,各行業(yè)獲得數(shù)據(jù)量呈指數(shù)增長(zhǎng)趨勢(shì)。在最近的20年里,全球總的數(shù)據(jù)量以每年25.3％的速度增長(zhǎng)。各行業(yè)可以利用海量數(shù)據(jù)的數(shù)據(jù)分析結(jié)果獲得巨大的收益,這也充分說(shuō)明了海量數(shù)據(jù)查詢計(jì)算的價(jià)值。在海量數(shù)據(jù)的查詢處理中,磁盤I/O操作費(fèi)用是其執(zhí)行操作的主要費(fèi)用。在過(guò)去的20年間,主流單硬盤的容量增長(zhǎng)了50000倍,與之對(duì)應(yīng)的,在同一時(shí)期,磁盤的數(shù)

2、據(jù)傳輸速率則只提高了375倍。在用戶的角度看來(lái),因?yàn)閿?shù)據(jù)庫(kù)系統(tǒng)需要存儲(chǔ)和處理更多的數(shù)據(jù),查詢處理操作的時(shí)間增加了。現(xiàn)有的數(shù)據(jù)庫(kù)查詢技術(shù)只適用于中小規(guī)模的數(shù)據(jù)集,當(dāng)處理海量數(shù)據(jù)時(shí),現(xiàn)有數(shù)據(jù)庫(kù)系統(tǒng)無(wú)法提供高效的數(shù)據(jù)操作算法和查詢處理技術(shù)。面對(duì)目前的海量數(shù)據(jù)集,如何有效地執(zhí)行數(shù)據(jù)分析來(lái)支持決策及科學(xué)探索是一個(gè)非常具有挑戰(zhàn)性的問(wèn)題,并且具有較大的學(xué)術(shù)和實(shí)用價(jià)值。本文的研究工作主要集中于海量數(shù)據(jù)的查詢處理算法,因此本文將對(duì)一些常用的查詢操作提出新

3、的更加高效的并且適用于海量數(shù)據(jù)的查詢算法,包括:連接查詢、連接聚集查詢、top-k查詢和top-k join查詢。本文的主要研究成果包括如下幾個(gè)方面:
　　首先,本文研究海量數(shù)據(jù)連接查詢處理問(wèn)題。連接查詢是數(shù)據(jù)庫(kù)系統(tǒng)中的一個(gè)重要而又昂貴的操作,其性能直接影響著數(shù)據(jù)庫(kù)的整體性能。在海量數(shù)據(jù)上執(zhí)行時(shí),現(xiàn)有連接算法不但需要耗費(fèi)大量時(shí)間和計(jì)算資源,而且在不同選擇度下需要處理同樣數(shù)量的數(shù)據(jù)。本文分析了現(xiàn)有連接算法在海量數(shù)據(jù)上執(zhí)行時(shí)的性能問(wèn)題

4、,提出了一種新的基于磁盤的連接算法PI-Join,該算法可以有效地處理海量數(shù)據(jù)上的連接查詢。本文提出了連接位置索引對(duì)表(JPIPT:Join Positional Index Pair Table)的概念,用來(lái)表示每個(gè)連接元組在各自數(shù)據(jù)表中的位置索引對(duì)。PI-Join的執(zhí)行包括兩個(gè)階段:JPIPT構(gòu)建階段和結(jié)果輸出階段。JPIPT構(gòu)建階段對(duì)列存儲(chǔ)化的連接屬性執(zhí)行高速緩存敏感的算法來(lái)構(gòu)建連接位置索引對(duì)表。利用獲得的JPIPT,結(jié)果輸出階段

5、只需要對(duì)數(shù)據(jù)表執(zhí)行一遍順序掃描就可以獲得結(jié)果。本文提供了算法的正確性證明和費(fèi)用分析。實(shí)驗(yàn)表明,和傳統(tǒng)磁盤連接算法相比,PI-Join算法可以獲得達(dá)到一個(gè)數(shù)量級(jí)的加速比。
　　第二,本文研究海量數(shù)據(jù)近似連接聚集查詢處理問(wèn)題。連接聚集查詢是數(shù)據(jù)庫(kù)中的一個(gè)常用的操作,它可以返回兩個(gè)或者多個(gè)表的連接結(jié)果的統(tǒng)計(jì)信息。在某些場(chǎng)合下,近似連接聚集操作可以在少得多的響應(yīng)時(shí)間內(nèi)返回滿足置信區(qū)間要求的近似結(jié)果,從而更受用戶的歡迎。不過(guò),現(xiàn)有方法無(wú)法以

6、既高效又滿足任意置信區(qū)間的方式來(lái)處理近似連接聚集。本文提出一種新的近似連接聚集查詢算法pε-AJA((p,ε)-Approximate Join Aggregation)來(lái)有效地返回滿足任意置信區(qū)間的近似連接聚集結(jié)果。本文提出且預(yù)計(jì)算兩個(gè)數(shù)據(jù)結(jié)構(gòu):連接隨機(jī)樣本(JRS)和連接位置索引對(duì)表(JPIPT)。利用JRS,pε-AJA向用戶返回近似結(jié)果的快速響應(yīng)。如果利用JRS得到的近似結(jié)果沒(méi)有滿足給定的置信區(qū)間,pε-AJA利用JPIPT獲得

7、更多的隨機(jī)連接元組。本文提出一種采樣算法來(lái)獲得給定數(shù)量的JPIPT樣本,并且利用獲得的JPIPT樣本,本文提出算法通過(guò)對(duì)連接表的一遍順序掃描獲得連接元組。本文還提供了JPIPT和JRS有效的構(gòu)建和維護(hù)算法。實(shí)驗(yàn)結(jié)果表明,pε-AJA可以獲得相對(duì)于現(xiàn)有近似連接聚集算法3倍到2個(gè)數(shù)量級(jí)的加速比,可以獲得相對(duì)于準(zhǔn)確查詢1到4個(gè)數(shù)量級(jí)的加速比,并且可以有效地完成JPIPT和JRS的構(gòu)建和維護(hù)操作。
　　第三,本文研究海量數(shù)據(jù)top-k查詢

8、處理問(wèn)題。在海量數(shù)據(jù)上執(zhí)行top-k查詢時(shí),隨機(jī)讀操作是受限的,NRA算法被用來(lái)處理只支持順序讀的top-k查詢。NRA算法的執(zhí)行分為兩個(gè)階段:增長(zhǎng)階段(不斷累積top-k候選元組直到找到top-k結(jié)果的閾值)和收縮階段(不斷剪切候選元組直到獲得最終top-k結(jié)果)。隨著涉及的屬性數(shù)量、元組數(shù)量和返回的結(jié)果數(shù)量的增大,NRA算法的增長(zhǎng)階段需要維護(hù)的候選元組也越來(lái)越多,其維護(hù)費(fèi)用也越來(lái)越大。本文詳細(xì)地分析了NRA算法的執(zhí)行行為,確定了增長(zhǎng)

9、階段和收縮階段中每個(gè)文件需要掃描的元組個(gè)數(shù)。基于分析結(jié)果,本文提出一種新的海量數(shù)據(jù)top-k查詢算法TKEP(Top-K with Early Pruning),該算法在查詢處理的增長(zhǎng)階段就執(zhí)行早剪切,從而大大減少增長(zhǎng)階段需要維護(hù)的候選元組。本文給出了早剪切操作的數(shù)學(xué)分析,確定了早剪切操作的理論和實(shí)際剪切效果。實(shí)驗(yàn)結(jié)果表明,和傳統(tǒng)的NRA算法相比, TKEP算法在增長(zhǎng)階段維護(hù)的元組數(shù)量可以減少3個(gè)數(shù)量級(jí),TKEP算法可以獲得1個(gè)數(shù)量級(jí)的

10、加速比。
　　第四,本文研究海量數(shù)據(jù)top-k join查詢處理問(wèn)題。PBRJ算法是一個(gè)概括了已有top-k join算法的模板,每個(gè)實(shí)例化的PBRJ算法需要拉策略P(確定從哪個(gè)連接表讀取下一個(gè)元組)和界限模式B(確定PBRJ算法的閾值)。在海量數(shù)據(jù)上執(zhí)行時(shí),PBRJ算法需要掃描和維護(hù)大量候選元組,這將導(dǎo)致較大的執(zhí)行費(fèi)用。本文提出了一種新的海量數(shù)據(jù)top-k join算法TJJE(Top-k Join with JPIPT and

11、 EGRIT)。通過(guò)預(yù)計(jì)算的數(shù)據(jù)結(jié)構(gòu)(EGRIT:Exponential Gap Range Information Table),TJJE算法首先估計(jì)要返回top-k join的結(jié)果需要在每個(gè)連接表中掃描的元組數(shù)量。接著,利用數(shù)據(jù)結(jié)構(gòu)JPIPT(Join Positional Index Pair Table),TJJE算法確定包含最終top-k join結(jié)果的連接位置索引對(duì)元組。TJJE算法保證只需要對(duì)連接表的一遍掃描就可以獲得JP