【摘要】：新型非易失性存儲器(NVM),如相變存儲器(Phase Change Memory,PCM),因具有功耗低、存儲密度大、讀寫速度可與DRAM達到同一個級別、可字節(jié)尋址等特性而在工業(yè)和學(xué)術(shù)屆備受關(guān)注,它也有望替代DRAM,從而構(gòu)建一個以NVM為主存的新系統(tǒng)架構(gòu)。當然,NVM(以PCM為例)存在眾多優(yōu)點的同時還有一定的缺陷,比如寫容忍度有限、讀寫速度不對稱等。新型非易失性存儲器的出現(xiàn)使得我們可以將數(shù)據(jù)庫直接存放在NVM上,從而構(gòu)建出基于NVM的內(nèi)存數(shù)據(jù)庫系統(tǒng)架構(gòu)。多表連接操作是數(shù)據(jù)庫中常用而又重要的一項操作,其中會產(chǎn)生大量的中間表,對存儲設(shè)備造成大量的寫操作。傳統(tǒng)的多表連接優(yōu)化算法并沒有考慮到NVM寫耐受度有限、可字節(jié)尋址等特征,所以并不適用于這一全新的架構(gòu)。為此,本文針對基于NVM的內(nèi)存數(shù)據(jù)庫提出了“NVM友好”的多表連接算法,目的是充分利用NVM的優(yōu)勢,并盡可能減少NVM上的寫操作,從而延長NVM的壽命。本文首先提出了優(yōu)化多表連接順序的NVjoin算法,該算法通過解析表與表之間的關(guān)聯(lián)性,抽樣估算中間結(jié)果大小來優(yōu)化連接順序,從而盡可能減少NVM上的寫操作。其次,本文提出了一個輕量級的組織中間結(jié)果的數(shù)據(jù)結(jié)構(gòu),稱為LWTab,該結(jié)構(gòu)充分利用了NVM可字節(jié)尋址的特性,進一步減少多表連接過程中中間結(jié)果所產(chǎn)生的NVM寫操作。將這兩個技術(shù)相結(jié)合,可以得到NVjoin+LWTab算法。為了確定算法中抽樣估計的概率,本文將測試數(shù)據(jù)分為Zipf分布、正太分布、均勻分布分別進行大量實驗,最終確定算法的抽樣概率為0.1。最后,通過不同連接方式的對比實驗衡量NVjoin+LWTab算法是否可以在減少NVM寫操作和提升運行時間兩方面都取得顯著效果。從實驗結(jié)果的分析可得出兩點結(jié)論:1)一個適當?shù)某闃痈怕什坏兄讷@取較優(yōu)的連接順序,且不會影響整體連接的運行時間;2)笛卡爾積對連接過程中產(chǎn)生的中間結(jié)果總大小和整體運行時間都有很大的影響。而正因為NVjoin+LWTab充分考慮了表之間的關(guān)聯(lián)性、盡可能地減少不必要的笛卡爾積操作、避免大量冗余數(shù)據(jù)的拷貝等特點,使得其可以在保證性能的同時盡可能減少NVM上的寫操作。實驗結(jié)果表明,與MySQL所提供的連接順序相比,NVjoin可以減少104.21倍的NVM寫操作。除此之外,LWTab可以在NVjoin的基礎(chǔ)上,更進一步減少16.74倍的NVM寫操作。從運行時間來講,NVjoin+LWTab平均比MySQL連接方法提升87.24%。
【學(xué)位授予單位】：重慶大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：TP311.13;TP333

【參考文獻】

相關(guān)期刊論文 前4條

1 郭聰莉;朱莉;李向;;基于蟻群算法的多連接查詢優(yōu)化方法[J];計算機工程;2009年10期

2 徐署華;江文;黃志剛;;基于貪心算法的Web Services查詢優(yōu)化方案[J];計算機工程;2008年05期

3 雷宏偉,王魁生,屈展;基于SQL的關(guān)系數(shù)據(jù)查詢優(yōu)化策略[J];北京電子科技學(xué)院學(xué)報;2004年02期

4 游榮彥;Zipf定律與漢字字頻分布[J];中文信息學(xué)報;2000年03期

相關(guān)碩士學(xué)位論文 前8條

1 李健;非易失性存儲器的能耗研究[D];重慶大學(xué);2015年

2 李雷;大數(shù)據(jù)環(huán)境下數(shù)據(jù)存儲與查詢的研究[D];哈爾濱工業(yè)大學(xué);2014年

3 馬翠;面向相變存儲器測試的精密電流源設(shè)計[D];華中科技大學(xué);2012年

4 蔡金武;面向數(shù)據(jù)庫多表查詢的遺傳算法的改進[D];東北石油大學(xué);2011年

5 宋麗娜;基于遺傳退火算法的數(shù)據(jù)庫多連接查詢優(yōu)化研究與應(yīng)用[D];長春理工大學(xué);2009年

6 孫輝;MySQL查詢優(yōu)化的研究和改進[D];華中科技大學(xué);2007年

7 程平;基于免疫遺傳算法的數(shù)據(jù)倉庫查詢優(yōu)化研究[D];重慶大學(xué);2006年

8 周敏;遺傳算法的若干改進及應(yīng)用[D];中國科學(xué)院軟件研究所;2001年

，

本文編號：2667650