Sub-Join:面向闪存数据库的查询优化算法  

Sub-Join:Query Optimization Algorithm for Flash-Based Database

作　　者：梁智超[1] 周大[1] 孟小峰[1] 

机构地区：[1]中国人民大学信息学院,北京100872

出　　处：《计算机科学与探索》2010年第5期401-409,共9页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金No.60833005;60573091;国家高技术研究发展计划(863)No.2007AA01Z155;2009AA011904;国家教育部博士点基金No.200800020002~~

摘　　要：固态硬盘具有高速的随机读取速度、低功耗、体积小等特点,被认为将取代磁盘成为新一代的数据存储设备。但是闪存数据库的查询性能的提高却远小于固态硬盘相比于磁盘I/O性能的提高,其原因在于现有的数据库是基于磁盘设计的,不能充分发挥固态硬盘的高速性能。提出一种名为子连接(Sub-Join)的连接算法。首先将数据表的连接列和主键投影为新的子表,然后对子表进行接连操作,最后根据子表的连接结果再从原始数据表中回取查询结果。通过和开源数据库Oracle Berkeley DB的比较实验,结果表明子连接算法比原有算法的性能提高了40%～100%,充分说明了它的优越性。Compared with hard drive disk （HDD）,solid state disk （SSD） has a lot of advantages,such as high random read performance,low power consumption and lightweight form. Therefore it is envisioned to be next generation data storage instead of HDD. However,the enhancement of query performance for flash-based database is not the same as the I/O ratio of SSD to HDD. The reason is existing databases which are designed for HDD can not take full advantage of high I/O performance of SSD. A new join algorithm,Sub-Join,is proposed. Sub-Join firstly projects the column of join and primary key as Sub-Table,and then executes join operations on Sub-Tables. Finally results are gotten from original table according to the result of join on Sub-Tables. The compared experiments with Oracle Berkeley DB show Sub-Join outperforms original indexed nested-loop join at the ratio of about 40%～100%,which shows the high efficiency of this method.

关 键 词：固态硬盘 闪存 闪存数据库 查询优化 子连接 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]