————————————
基金项目
基金项目基金项目
基金项目:
::
:国家自然科学基金资助项目(61070031, 61070032, 61103046);“核高基”重大专项(2010ZX01042-001-003-004);上海市自然科学基
金资助项目(11ZR1401200)
作者简介
作者简介作者简介
作者简介:
::
:王 梅(1980-),女,副教授、博士后,主研方向:数据库技术,多媒体信息检索;杨思箫,硕士研究生;乐嘉锦,教授
收稿日期
收稿日期收稿日期
收稿日期:
::
:2011-12-07 修回日期
修回日期修回日期
修回日期:
::
:2012-01-15 E-mail:
::
:wangmei@dhu.edu.cn
列存储
列存储列存储
列存储数
数数
数据库
据库据库
据库中压缩位图
中压缩位图中压缩位图
中压缩位图索引
索引索引
索引技术
技术技术
技术
王
王王
王
梅
梅梅
梅,
,,
,杨思箫
杨思箫杨思箫
杨思箫,
,,
,乐嘉锦
乐嘉锦乐嘉锦
乐嘉锦
(东华大学计算机科学与技术学院,上海 201620)
摘
摘摘
摘 要
要要
要:
::
:为提高压缩码的利用率,提出一种适用于列存储数据库的压缩位图索引技术。定义反转、合并等操作,将所有计算的输入值与输
出值格式化为位向量形式。通过活跃度衡量索引中位向量的复杂度,并对压缩位向量进行直接计算,优化 where 子句和 group by 子句在查
询执行过程中的数据提取。在 SSB 数据集上的实验结果证明,该技术能提高 29.7%~38.9%的压缩位图索引性能。
关键词
关键词关键词
关键词:
::
:列存储数据库;位图索引;活跃度;SSB 数据集;聚集查询
Compressed Bitmap Index Technology
in Column-oriented Database
WANG Mei, YANG Si-xiao, LE Jia-jin
(School of Computer Science and Technology, Donghua University, Shanghai 201620, China)
【
【【
【Abstract】
】】
】In order to improve the compression code utilization, this paper presents a compressed bitmap index technology in column-oriented
database. It defines the inversion and merges operations to transform the input and output of all calculation to the bitmap vector. By using a vitality
to describe the complexity of each bitmap vector and directly operating on the compressed bitmap vector, the technology optimizes the data
extraction in query execution process of where and group by clauses. Experimental research on SSB dataset shows that the technology improves
29.7%~38.9% of the index performance on compressed bitmap.
【
【【
【Key words】
】】
】column-oriented database; bitmap index; vitality; Star Schema Benchmark(SSB) dataset; aggregation query
DOI: 10.3969/j.issn.1000-3428.2012.18.007
计 算 机 工 程
Computer Engineering
第 38 卷 第 18 期
Vol.38 No.18
2012 年 9 月
September 2012
·
··
·软件技术与数据库
软件技术与数据库软件技术与数据库
软件技术与数据库·
··
·
文章编号
文章编号文章编号
文章编号:
::
:1000—
——
—3428(2012)18—
——
—0026—
——
—04
文献标识码
文献标识码文献标识码
文献标识码:
::
:A
中图分类号
中图分类号中图分类号
中图分类号:
::
:TP311.13
1
概述
概述概述
概述
随着计算机技术的快速发展以及数据库系统
[1]
的深入
研究和广泛应用,人们在期望获得巨大数据存储容量的同
时,对数据的检索效率提出更高的要求。在面向列存储
[2]
的分析型查询环境下,位图索引
[3]
可以非常有效地提高低
基数数据
(
集中在非数值型数据
)
的查询效率。但是,随着
基数的增长,索引大小也随之增长,开销增加、实用性降
低。据分析,建立在
50
个基数的
10 000 000
行上的低基
数位图索引需要
62.5 MB
的磁盘空间,当基数上升至
500
时,所需的磁盘空间增到
625 MB
[4]
。
为减少存储空间,位图索引通常使用分段长度码生成
压缩位图
[5]
。压缩位图索引上的查询操作通常需要“解压
-
运算
-
压缩”
3
个步骤实现,过程中存在大量不必要的“解
压”和“再次压缩”的计算开销。
如何提高压缩位图上的查询执行效率是查询优化的
重要内容。
CBFrag-Cubing
[6]
算法通过引入首尾有效指针
压缩位图进行存储,以减少解压范围来获得
bit-AND
运算
速度的加快以及内存消耗的降低;压缩位图索引
[7]
以存储
空间的消耗来换取查询性能的提升。但是,这
2
类方法都
没有从本质上提高压缩码的利用率。
针对上述问题,本文提出了一种基于压缩级别位图索
引
[8-9]
的 直 接 应 用 技 术
CBT(Compressed Bitmap Index
Based Execution Technology)
,通过
CBT
研究实现列存储
系统中的聚集和分组查询,并提高列存储
DBMS
查询的
执行效率。
2
列存储
列存储列存储
列存储
在列存储体系中,关系表依据列分开存储。假设现有
表
T
,
T
共有
N
条属性,
T
i
为第
i
条属性的属性名称,
i
∈
[1,
N
]
。在每个
T
i
上做投影操作,
Π
T
i
的值与新生成的
id
号重组,依次读入存储数据块。
如图
1
所示,原始表中有
3
列属性
ID
、
Name
和
Sex
,
对各列做投影操作后,将获取的列值与自动生成的
ID
号
进行重组,存入磁盘空间。列存储模式极大提高了分析型
查询的效率。