基于NVM的内存数据库多表连接操作的设计与优化

发布时间：2020-05-17 01:00

【摘要】：新型非易失性存储器(NVM),如相变存储器(Phase Change Memory,PCM),因具有功耗低、存储密度大、读写速度可与DRAM达到同一个级别、可字节寻址等特性而在工业和学术届备受关注,它也有望替代DRAM,从而构建一个以NVM为主存的新系统架构。当然,NVM(以PCM为例)存在众多优点的同时还有一定的缺陷,比如写容忍度有限、读写速度不对称等。新型非易失性存储器的出现使得我们可以将数据库直接存放在NVM上,从而构建出基于NVM的内存数据库系统架构。多表连接操作是数据库中常用而又重要的一项操作,其中会产生大量的中间表,对存储设备造成大量的写操作。传统的多表连接优化算法并没有考虑到NVM写耐受度有限、可字节寻址等特征,所以并不适用于这一全新的架构。为此,本文针对基于NVM的内存数据库提出了“NVM友好”的多表连接算法,目的是充分利用NVM的优势,并尽可能减少NVM上的写操作,从而延长NVM的寿命。本文首先提出了优化多表连接顺序的NVjoin算法,该算法通过解析表与表之间的关联性,抽样估算中间结果大小来优化连接顺序,从而尽可能减少NVM上的写操作。其次,本文提出了一个轻量级的组织中间结果的数据结构,称为LWTab,该结构充分利用了NVM可字节寻址的特性,进一步减少多表连接过程中中间结果所产生的NVM写操作。将这两个技术相结合,可以得到NVjoin+LWTab算法。为了确定算法中抽样估计的概率,本文将测试数据分为Zipf分布、正太分布、均匀分布分别进行大量实验,最终确定算法的抽样概率为0.1。最后,通过不同连接方式的对比实验衡量NVjoin+LWTab算法是否可以在减少NVM写操作和提升运行时间两方面都取得显著效果。从实验结果的分析可得出两点结论:1)一个适当的抽样概率不但有助于获取较优的连接顺序,且不会影响整体连接的运行时间;2)笛卡尔积对连接过程中产生的中间结果总大小和整体运行时间都有很大的影响。而正因为NVjoin+LWTab充分考虑了表之间的关联性、尽可能地减少不必要的笛卡尔积操作、避免大量冗余数据的拷贝等特点,使得其可以在保证性能的同时尽可能减少NVM上的写操作。实验结果表明,与MySQL所提供的连接顺序相比,NVjoin可以减少104.21倍的NVM写操作。除此之外,LWTab可以在NVjoin的基础上,更进一步减少16.74倍的NVM写操作。从运行时间来讲,NVjoin+LWTab平均比MySQL连接方法提升87.24%。
【学位授予单位】：重庆大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP311.13;TP333

【参考文献】

相关期刊论文 前4条

1 郭聪莉;朱莉;李向;;基于蚁群算法的多连接查询优化方法[J];计算机工程;2009年10期

2 徐署华;江文;黄志刚;;基于贪心算法的Web Services查询优化方案[J];计算机工程;2008年05期

3 雷宏伟,王魁生,屈展;基于SQL的关系数据查询优化策略[J];北京电子科技学院学报;2004年02期

4 游荣彦;Zipf定律与汉字字频分布[J];中文信息学报;2000年03期

相关硕士学位论文 前8条

1 李健;非易失性存储器的能耗研究[D];重庆大学;2015年

2 李雷;大数据环境下数据存储与查询的研究[D];哈尔滨工业大学;2014年

3 马翠;面向相变存储器测试的精密电流源设计[D];华中科技大学;2012年

4 蔡金武;面向数据库多表查询的遗传算法的改进[D];东北石油大学;2011年

5 宋丽娜;基于遗传退火算法的数据库多连接查询优化研究与应用[D];长春理工大学;2009年

6 孙辉;MySQL查询优化的研究和改进[D];华中科技大学;2007年

7 程平;基于免疫遗传算法的数据仓库查询优化研究[D];重庆大学;2006年

8 周敏;遗传算法的若干改进及应用[D];中国科学院软件研究所;2001年

，

本文编号：2667650