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

doi:10.3778/j.issn.1673-9418.2010.05.002

计算机科学与探索 ›› 2010, Vol. 4 ›› Issue (5): 401-409.DOI: 10.3778/j.issn.1673-9418.2010.05.002

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

梁智超;周大; 孟小峰⁺

中国人民大学信息学院, 北京 100872

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-05-11 发布日期:2010-05-11
通讯作者: 孟小峰

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

LIANG Zhichao;ZHOU Da; MENG Xiaofeng⁺

Information School, Renmin University of China, Beijing 100872, China

Received:1900-01-01 Revised:1900-01-01 Online:2010-05-11 Published:2010-05-11
Contact: MENG Xiaofeng

摘要/Abstract

摘要： 固态硬盘具有高速的随机读取速度、低功耗、体积小等特点, 被认为将取代磁盘成为新一代的数据存储设备。但是闪存数据库的查询性能的提高却远小于固态硬盘相比于磁盘I/O性能的提高, 其原因在于现有的数据库是基于磁盘设计的, 不能充分发挥固态硬盘的高速性能。提出一种名为子连接(Sub-Join)的连接算法。首先将数据表的连接列和主键投影为新的子表, 然后对子表进行接连操作, 最后根据子表的连接结果再从原始数据表中回取查询结果。通过和开源数据库Oracle Berkeley DB的比较实验, 结果表明子连接算法比原有算法的性能提高了40%~100%, 充分说明了它的优越性。

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

Abstract: Compared with hard drive disk (HDD), solid state disk (SSD) has a lot of advantages, such as high ran-dom read performance, low power consumption and lightweight form. Therefore it is envisioned to be next genera-tion 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 pro-jects the column of join and primary key as Sub-Table, and then executes join operations on Sub-Tables. Finally re-sults 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.

Key words: solid state disk (SSD), flash memory, flash-based database, query optimization, Sub-Join

中图分类号:

TP311

梁智超;周大; 孟小峰+ . Sub-Join:面向闪存数据库的查询优化算法*[J]. 计算机科学与探索, 2010, 4(5): 401-409.

LIANG Zhichao;ZHOU Da; MENG Xiaofeng⁺. Sub-Join: Query Optimization Algorithm for Flash-Based Database*[J]. Journal of Frontiers of Computer Science and Technology, 2010, 4(5): 401-409.

[1]	曾祥伟, 邓玉辉. 利用页面重构与数据温度识别的闪存缓存算法[J]. 计算机科学与探索, 2021, 15(1): 84-95.
[2]	马志程，袁海峰，谷洋，刘亚茹，张孝. 文档-关系数据查询执行技术研究与实现[J]. 计算机科学与探索, 2020, 14(8): 1315-1326.
[3]	宋雨萌，谷峪，李芳芳，于戈. 人工智能赋能的查询处理与优化新技术研究综述[J]. 计算机科学与探索, 2020, 14(7): 1081-1103.
[4]	唐琪，王吉磊，柴云鹏. 面向SSD寿命优化的访问序列折叠缓存替换算法[J]. 计算机科学与探索, 2019, 13(1): 35-44.
[5]	郭云格，陈明宇，蒋德钧. 通过差值和压缩减少SSD的擦除次数[J]. 计算机科学与探索, 2019, 13(1): 45-55.
[6]	李宇珺，彭智勇，吴瑕，兰海，彭煜玮. IPI：灵活高效的对象代理数据库索引结构[J]. 计算机科学与探索, 2018, 12(8): 1191-1201.
[7]	黄达，闫宏飞. 复杂布尔查询下的文档收集打分策略的优化[J]. 计算机科学与探索, 2017, 11(1): 106-113.
[8]	金铮，刘梦赤，胡婕. 信息网数据库管理系统的查询优化[J]. 计算机科学与探索, 2015, 9(3): 300-309.
[9]	李瑞轩，廖东杰，辜希武，文坤梅，赵铄乂，董新华. YARN平台上的并行主题标引算法[J]. 计算机科学与探索, 2014, 8(12): 1409-1421.
[10]	朱青，李红. 时序图上动态子图查询优化算法[J]. 计算机科学与探索, 2014, 8(11): 1324-1333.
[11]	陆戌辰，王梅，乐嘉锦. 列存储中的OLAP多查询优化方法[J]. 计算机科学与探索, 2012, 6(9): 852-864.
[12]	李伏，朱青. 混合MapReduce环境下大数据划分的查询优化[J]. 计算机科学与探索, 2012, 6(10): 877-887.
[13]	陈恺萌，卢科，岳丽华. PostgreSQL闪存缓冲区置换算法扩展与性能验证[J]. 计算机科学与探索, 2012, 6(10): 888-894.
[14]	韩旭, 曹巍, 孟小峰. 使用固态硬盘管理主存KV数据库的虚拟内存[J]. 计算机科学与探索, 2011, 5(8): 686-694.
[15]	李静+ ;孙莉; 王梅 . 列存储数据查询中的连接策略选择方法*[J]. 计算机科学与探索, 2010, 4(9): 850-858.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics