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

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

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

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

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

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

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

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

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

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

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

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