大数据在2001年最早提出时有3个维度:volume(数据量)、velocity(数据产生和输出的速度)以及variety(不同数据类型和来源),2012年,Gartner更新了大数据的概念,其中一个重要的变化是high volume,high velocity, and/or high variety代替了原来的3个固有维度^[1],variety成为可选维度.这种变化表明:大数据已逐渐与各个领域相结合,而volume与velocity的结合则产生了大数据仓库需求,大数据上的OLAP正日益成为大数据分析的一个重要应用领域.与事务型数据库的查询相比,DW(data warehouse)的查询(OLAP查询)通常很复杂、涉及的元组属性较少,且主要是以读为主.通常,OLAP查询所需处理时间较长,而在大规模数据上的OLAP查询让这一矛盾显得更加突出.由于列存储数据库只访问与查询相关的数据,因此它能高效地利用内存带宽和高速缓存、减少磁盘I/O次数.这一特性使得列存储系统在应对海量数据上的OLAP查询带来的挑战时具有很大优势,C-store,SyBase IQ和MonetDB^{[2, 3]}等列存储系统都验证了列存储在应对读密集型应用的优越性能.为了改进OLAP查询的性能,微软也已将列存储加入到SQL Server 2012^[4]之中.随着内存容量的增大以及其价格的下降,涌现出一大批性能卓越的内存列存储数据库,MonetDB^{[2, 5]}就是其中的典型.SAP HANA数据库^{[6, 7]}是高性能的混合存储内存数据库.当处理分析型的工作负载时,它采用列存储的数据管理策略.这些系统的性能在特定工作负载下,尤其是在像DW中遇到的读密集型的工作负载情况下,比传统的行存储数据库要高出一个数量级以上.

为了克服OLAP查询中的多表连接和分组聚集的性能瓶颈,以应对大规模数据分析带来的挑战,本文介绍我们开发的一个内存列存储查询执行引擎:CDDTA-MMDB.我们的目标是进行实时的大规模数据分析,它能够以平均1.5s左右的时间完成对100GB的SSB(star schema benchmark)测试数据集的查询.此外,CDDTA-MMDB可以部署在分布式环境下,利用反转星型的处理模式^[8]轻松应对TB甚至是PB级的海量数据分析.这个系统是我们实验室在研究大数据背景下一系列研究成果^[8-10]之一,主要贡献体现在以下几个方面:

(1) 存储模型:CDDTA-MMDB采用分解存储模型(decomposed storage model,简称DSM),垂直划分关系表.我们扩展MonetDB的二元关联表(binary association table,简称BAT),维护一个三元组á代理键,关键字,值ñ或二元组集合的表.这种扩展的数据类型除了能更好地利用高速缓存块以外,也是轻量级物化的关键数据结构;

(2) 查询处理:CDDTA-MMDB运用分治策略处理OLAP查询.首先,将查询分解为作用在维表和事实表上的子查询;然后,根据子查询的特征改写子查询,以生成三元组或者二元组;最后,通过一趟扫描事实表,利用事实表的外键映射函数定位相应的三元组或者二元组,完成过滤、连接或者分组聚集操作;

(3) 列存储数据库的物化策略:在系统里提出一种新的物化策略,称为轻量级物化.轻量级物化与延迟物化都是将物化操作在查询计划里尽量推迟,但是轻量级物化能够减少内存的访问次数,加速OLAP查询中常见的分组聚集等操作;

(4) 实验:我们在SSB上使用标准测试数据和标准测试查询进行了全面的实验,测试系统在多核处理器环境下的扩展性;测试轻量级物化的性能;测试系统的总体性能.实验结果表明:CDDTA-MMDB基本上达到了线性加速比;在星型模型数据库仓库的标准测试数据集下,比MonetDB 5.5快2.5倍,比C-store的针对星型模型数据仓库的查询执行引擎(invisible join)快5倍.

本文第1节介绍相关工作.第2节介绍系统总体架构,包括存储管理、查询解析、查询处理以及优化.第3节是实验部分.最后一节是总结及未来的工作.

尽管将数据库关系表垂直划分以改进性能的概念很早就已经提出^[11],MonetDB和MonetDB/X100^{[2, 3, 5, 12]}是设计列存储系统和向量执行引擎的先驱.MonetDB和MonetDB/X100展示出:列存储由于CPU和高速缓存的有效利用能够在以读为主的应用场景中远优于传统的行数据库.MonetDB的设计、体系结构和实现都重新审视了传统数据库的各个部件,以充分挖掘现代计算机的潜能.它不仅采用列存储逻辑组织数据,而且提供全新的针对列存储的执行引擎,开发高速缓存敏感的数据结构和优化的算法,以最优地利用分级存储体系结构.MonetDB前端负责将用户的数据模型转换成二元关联表(binary association tables,简称BATs)和将用户输入的查询编译成MonetDB汇编语言(MonetDB assembly language,简称MAL)^[5].MonetDB将关系表垂直划分,每个BAT由形如ásurrogate,valueñ的二元组构成,二元组的value为定长数据值或者为变长数据的偏移量.一个具有k个属性的MonetDB关系表会被映射成k个BAT表.为了方便元组重构,元组t的所有属性都在BAT的同一位置.MAL的核心由作用在BAT上的底层关系代数构成.行关系代数查询执行计划被转换成BAT代数,并且被编译成MAL程序.这些MAL程序会被以“operator-at-a-time”的方式评估,也就是在激发后续的数据依赖的操作之前在整个输入数据集上评估这些操作.每个BAT算数操作符都会被映射成简单的MAL指令.每一个复杂的操作都被分解成一系列BAT代数操作符,每一个代数操作符在整列数据上执行简单的操作(“块处理”),减少了函数调用开销.

C-store^[13]是近些年来的另外一个列存储系统,它拥有许多与MonetDB/X100一样的特性,包括针对直接作用在压缩数据上的操作的优化.C-store支持标准的关系模型,其查询语言为SQL.在物理存储层,C-store没有采取传统行存储,也不像MonetDB那样对每个属性单独维护一个BAT,而是将一个逻辑表在一个或者多个属性上垂直投影(project).系统维护这些投影,以应对用户查询.利用连接索引,C-store可以将这些投影恢复成原来的表.例如,为了重构表T,只需从表的一个覆盖集T₁,T₂,...,T_k中找到一个连接路径即可.在查询优化方面,C-store采用基于代价的Selinger风格^[14]的优化,利用两阶段优化来限制查询计划搜索空间^[15].为了应对在海量数据上的OLAP查询,特别是针对星型模型的数据仓库的查询,C-store引进invisible join^[16]算法.Invisible join能够改进在列存储数据库上星型模型的表之间主键/外键模式的表连接性能.

MonetDB与C-Store都是列存储数据库,因此,它们不可避免地需要在查询计划的某个点将逻辑上属于同一元组的列值合并起来,这个过程就是物化.按照物化时机来分类,可以将物化策略分为早物化与延迟物化^[17], MonetDB/X100使用延迟物化策略^[2].然而,MonetDB中的位置描述符(也叫作选择向量)与列值分开存放,并且位于高速缓存的数据是以非压缩的形式存在的,这会损失直接在压缩数据上进行操作所带来的性能优化.C-store采用的是并行延迟物化策略,也就是并行物化前的操作,例如生成位置描述符.后来,C-store改进了物化策略,采用启发式算法来决定是采用早物化或者是延迟物化^[17].文献^{[18, 19]}深入对比了行存储与基于早物化的列存储.

受益于内存容量的快速增长与价格的进一步下降,不仅事务型数据库可以将大部分工作集加载到内存,而且分析型数据库也朝这个方向发展,产生了实时分析型数据仓库^{[2, 6, 7, 13]}.内存数据库消除了昂贵的磁盘I/O、数据页格式在内存与磁盘之间的转换操作以及复杂的缓冲区管理^{[20, 21]}.相比磁盘数据库,内存数据库在性能上有很大的提升.

CDDTA-MMDB是一个内存列存储数据库查询执行引擎,是针对星型模型数据仓库上的OLAP而提出来的解决方案.它基于三元组改进了列存储中的物化方式,避免了早物化与延迟物化的缺点(早物化会构建无用元组而延迟物化需要重复读取数据块);并且,CDDTA-MMDB改进了invisible join算法,能够一趟扫描事实表完成表连接.其查询解析算法是基于分解的思想.

CDDTA-MMDB是一个内存列存储数据库执行引擎,其主要模块如图 1所示.应用程序和用户发送查询请求到系统;查询解析模块将查询分解成作用在维表与事实表上的一系列子查询,这些子查询所涉及的表互不相交.查询解析算法采用分治策略的主要原因是,维表上的子查询与事实表上的子查询需要以不同的方式处理:维表上的操作主要是提供过滤器和分组值,作用在维表上改写后的子查询由系统动态地生成三元组或者是二元组,如图 1中虚线矩形所示;而事实表上的查询信息会被系统解析、存储,利用这些信息,查询执行器知道需要访问事实表上哪些列.目前,查询解析模块的语义检查只是简单地查找系统目录,确定查询中出现的每个属性是否合法.查询优化器生成查询执行计划,这个查询执行计划的生成,依赖于维表与事实表上的过滤条件.查询执行器的主要操作是表扫描.在星型模型数据库仓库上,事实表与维表存在主外键关系,且表连接操作主要是在它们之间进行.根据这个特点,CDDTA-MMDB将表连接操作转换成事实表上外键的内存定位操作.扫描一趟事实表,即可完成表连接、过滤,聚集操作.数据文件在系统启动的时候被加载到内存.下面详细地介绍系统的各个模块.

Fig. 1 CDDTA-MMDB architecture overview图 1 CDDTA-MMDB总体架构

2.1 维表/事实表的管理

如上所述,系统将查询分解为作用在事实表和维表上的子查询.作用在维表上的子查询会被重写,以产生三元组ásurrogate,key,valueñ或者是二元组ásurrogate,Boolean_valueñ(当子查询只有过滤作用的时候,系统将为整个子查询产生二元组).在三元组中,一个key会对应多个value,亦即key与value是一对多的关系.MonetDB的二元关联表中,value要么为定长数据,要么为变长数据的偏移量.本文扩展了MonetDB的二元组中value的含义,使它包含过滤信息(我们的系统中,三元组的surrogate与MonetDB二元组中的surrogate都不实际存储).在CDDTA-MMDB中,key的作用类似于MonetDB中二元组的value,它具有两层含义:

① 系统通过它可以知道在该位置上的元组是否满足过滤条件;

② 它是该属性的某个数据的ID,系统可以在后续的查询计划,例如聚集、排序操作中直接利用这个ID.

这个设计是实现系统轻量级物化的关键.系统将三元组的key存放于地址连续的内存空间,称为key vector.key可以是其对应value的哈希值,也可以是value的内存地址,因此,三元组的key可以看成是其对应维表列值的一种轻量级数据压缩形式.系统在查询执行中直接对以整型存在的key进行操作,而不需要处理变长数据与复杂数据类型,从而加速查询执行操作,提高系统响应时间.同时,我们在key值上加入过滤信息,使得满足过滤条件的key值不为0.三元组的设计可以使得CDDTA-MMDB的物化策略避免延迟物化需要重复读取数据块的缺点与维护中间数据结构的代价.三元组的value属性只在输出结果时才会被使用.此外,可以通过事实表外键的映射函数直接定位维表相应元组,如同定位数组元素的操作.三元组或者是二元组与其对应的维表元组一一对应,因此可以通过一趟扫描事实表完成过滤、连接和分组聚集操作.图 2给出了三元组的一个示例:假如某个维表的一个非主属性列包含4个属性值{Sam,Bob,Bob,John},满足某个查询条件的属性值只有{Sam,Bob},则满足过滤条件的属性值相应的key值不为0.注意,key vector中元素的位置与维表中元组的位置一一对应.系统可以在查询计划的各个阶段直接利用该key值,完成过滤、聚集等操作.

Fig. 2 An example of triplets图 2 三元组示例

2.2 查询分解与三元组的生成

在CDDTA-MMDB中,采用分治策略处理用户的查询.在系统中,查询被划分成独立的子查询,这些子查询所涉及的表互不相交.根据用户查询的目标属性和过滤条件,这些子查询会被改写以产生三元组.下面详细介绍查询分解和查询改写算法.

查询分解算法首先由文献^{[22, 23]}提出,它是为数据库系统INGRES的查询语言QUEL而开发的,给出INGRES中处理多参数查询的策略.INGRES将查询分解成一系列单参数的做法是:

a) 归约:将查询的各个部分分解成包含单个参数的子查询;

b) 元组替换:每次用元组替换多参数查询中的某个参数.

算法的不足是,当表之间出现“链接”信息时,分解的原子语句会包含两个变量.在我们的应用场景中,表之间的“链接”信息可以通过主键/外键的对应关系消解.因此,我们的分解算法不会出现包含两个变量的子查询的情况.我们设计的查询分解算法流程如下:首先扫描select句子的目标属性列表;同时,通过查找系统目录确定属性列表的各个变量所属的表;下一步,抽取在各个表上的过滤条件,并记录“链接”信息.“链接”信息在扫描事实表时确定哪些维表需要访问.图 3给出了SSB中Q4.1(查询4.1)的SQL部件,它可以划分为select句子目标属性列表(target list)、链接信息(link information)、过滤条件(qualification)和分组器(grouper)等.以Q4.1为例,扫描目标属性列表之后通过查找系统目录,可以获得以下信息:

d_yearÎdwdate,c_nationÎcustomer,(lo_revenue,lo_suppcost)Îlineorder.

Fig. 3 SQL query components in Q4.1图 3 Q4.1的SQL查询部件

我们利用有限状态自动机(deterministic finite automaton,简称DFA)分解过滤条件.如图 3所示,在星型模型中,事实表和维表通过主键/外键关联起来.因此,事实表中的外键可以作为连接索引直接定位维表的元组.在这种情况下,维表与事实表的“链接”可以消解.取而代之的是,只需让系统记录扫描事实表时需要访问哪些维表.因此,本文的查询分解算法能够保证在这个应用场景下只有单变量的子查询.在获取目标属性列表和分解作用在各个表上的过滤条件之后,就可以改写子查询了.改写子查询需要分3种情况分别加以考虑:

Fig. 3 SQL query components in Q4.1图 3 Q4.1的SQL查询部件

1) 存在作用在表上的过滤条件,但是该表的属性没有出现在select目标属性列表(target list)中.

这种情况下,系统只需为该改写后的SQL语句产生布尔值.因此,改写后的查询语句与下面类似:

RQ1:SELECT CASE WHEN (p_mfgr=‘MFGR#1’ or p_mfgr=‘MFGR#2’) THEN 1 ELSE 0 END FROM part

RQ2:SELECT CASE WHEN s_nation=‘AMERICA’ THEN 1 ELSE 0END FROM supplier

2) 存在作用在表上的过滤条件,同时,该表的属性也出现在目标属性列表中.

这时候,需要返回满足过滤条件的元组.对于不符合条件的元组,返回0,同时标记该位置上的元组不符合过滤条件.改写后的SQL语句类似以下的结构:

RQ3:SELECT CASE WHEN c_region=‘AMERICA’ THEN c_nation ELSE 0 END FROM customer

3) 没有作用在该表上的SQL上限值条件,但是该表的某些属性出现在目标属性列表中.

如果出现了这种情况,则需要返回表上该属性的所有数据.改写后的SQL语句类似以下结构:

RQ4: SELECT CASE WHEN TRUE THEN d_year ELSE 0 END FROM dwdate

例程tripletProducer给出了产生三元组的算法:

· 首先把游标定位在将要处理的维表的第1条记录,如果记录不符合过滤条件,则直接将key值赋为0,并把key加入key vector;

· 否则,判断与该条记录相同的值是否存在:如果存在,则首先获取该属性的key值,并把key加入key vector;如果不存在,则将该记录放入哈希表,增加key值并把它放入key vector.

算法1. tripletProducer.

输入:查询涉及的维表、改写后的SQL;

输出:三元组或者二元组.

begin

for each dimension table involved in query and corresponding rewritten SQL on it do {

locate the cursor on the first record according to rewritten SQL;

while cursor is not to end do {

get attribute from result set;

If attribute is FALSE according to rewritten SQL { //维表上该位置的属性值不满足过滤条件,

assign 0 to key; //该属性对应的key值为0

push back key into the key vecotor;

cursor moves to next record; continue;

}//end if

use the attribute to probe the hash table;

if attribute not in the hash table { //维表上该属性满足过滤条件

increment key; //且目标属性尚且不在哈希表中,生成不同的key值

insert the attribute into hash table;

}else { //维表上该属性满足过滤条件,且目标属性已在哈希表中,返回已经存在的key值即可

get the key of the attribute;

}//end if

push back key into the key vector; //将对应目标属性key值存放于key值向量中

cursor moves to next record;

}//end while

} //end for

end tripletProducer

以下符号按照文献^[24]来定义:

· s:选择操作,对应SQL语句WHERE条件;

· p:投影操作,对应SQL语句SELECT语句;

· g:分组聚集操作,对应SQL语句GROUP BY.

另外,增加如下操作:

:列存储中列拼接操作,拼接关系R的列a与列b;

:扫描三元组操作,如果key不为0,返回true.>_a扫描列a上产生的三元组;

Q:扫描位图操作,对于位置位图为1,返回true.Q_a扫描列a上的位图.

列存储是对数据库物理层面的修改,在逻辑层和视图上,它等同于行存储.涉及到数据库的应用程序,无论数据库采用行存储还是列存储,都将接口视为面向行的接口.因此,列存储数据库必须在查询计划的某个点将逻辑上属于同一记录的各个属性值粘连起来,这个过程就叫作物化,它是投影的逆操作.根据物化的时机,可将物化操作分为两类:早物化(early materialization,简称EM)和延迟物化(late materialization,简称LM).每当在操作中需要某个列值时,这个列值就会被读入CPU,并且添加在元组的中间表示上,这种物化方式称为早物化.由于早物化会导致CPU执行一些无用的工作,所以它并不总是最有效的^[17].考虑以下场景:一个列存储数据库将一个表的各个列保存在单独的数据文件中,它们按相同的方式排序.假如一个查询在列R.a和R.b上有选择操作s₁和s₂(s₁有较高的选择率)以及在R.a上有GROUP BY操作g.在早物化的策略下,如图 4(a)所示,数据库执行的操作一般如下所示:读入列R.a,R.b的数据块,合并列R.a与R.b().然后,将选择操作符s₁和s₂依次作用在这些元组上.符合过滤条件的元组进行投影操作p,最后进行分组聚集操作g.不难看出,合并不满足过滤条件的属性是没有必要的操作.当选择率较低的时候,合并属性的大部分操作是无效的.处理该查询的一个更为高效的操作是保留两个中间位置列表;扫描列R.a和R.b的数据块,同时判断它们是否满足过滤条件s₁和s₂.对于满足过滤条件的元组,则在其位置列表相同的位置上标记为1,否则为0.之后,对两个位置列表进行“与”操作(Ä)形成最终位图.然后扫描最终位图(Q),决定是否获取相应位置上的元组进行分组聚集操作g.该操作过程如图 4(b)所示.随着硬件技术的发展,内存数据库的瓶颈所在已经从磁盘数据库的内存-磁盘转移到CPU-内存上.CDDTA- MMDB得益于三元组的设计,可以进一步减少物化中内存访问和维护中间数据结构所带来的开销,我们称其为轻量级物化.轻量级物化与延迟物化的理念一致,即将物化操作尽可能地推迟,但是轻量级物化将过滤信息编码加入三元组,使得在存在过滤条件的情况下系统无需生成过滤位图,然后根据位图决定是否再次访问内存.如图4(c)所示,在轻量级物化的策略下,为了处理查询Q,系统只需扫描三元组>,符合条件的key直接以流水线方式输送到分组聚集操作符p.

Fig. 4 The three kinds of materialization strategy图 4 3种物化策略

2.4 查询执行器

OLAP上的查询分析操作一般表现为在事实表和维表之间连接操作的基础上对结果集上进行分组聚集等操作,因此,表连接和分组聚集操作是ROLAP(relational OLAP)性能的两个重要决定因素.我们着重优化查询执行中的表连接算法,本文提出的查询执行算法能够以一趟扫描完成表连接、过滤与聚集等操作.本节给出朴素的轻量级物化下的表连接算法——LWMJoin(light-weight materialization join)及其优化.

LWMJoin算法是invisible join^[16]的改进.invisible join是针对星型模型的数据仓库而提出来的表连接算法,它分为3个阶段:

首先,将维表上的谓词条件作用在相应维表上,抽取符合过滤条件的元组的关键字构建哈希表;

然后,扫描事实表,并利用事实表外键探测维表上的哈希表,这一阶段确定了事实表上的过滤位图;

最后,根据过滤位图确定是否访问事实表相应位置上的元组构建结果集.如果过滤位图第i个位置上的值为1,则需要检索事实表的第i条记录;否则,应舍弃事实表的第i条记录.

根据以上分析,invisible join所耗费时间可以表达为

t₀+(2+1/e)t₁,

扫描最终过滤位图所需时间约为t₁/e,因此,invisible join所耗费的时间也可以用以下式子表达:

t₀+(2+1/e)t₁.

与invisible join相比,LWMJoin利用第1阶段产生的三元组,可以避免扫描事实表 2次.以下是算法过程:

· 首先,维表上的子查询产生三元组ásurrogate,key,valueñ,如果子查询只有过滤作用,例如RQ1,那么产生过滤位图即可;

· 然后,顺序扫描事实表,利用事实表外键映射函数定位相应维表的三元组.如果这些三元组中的key值存在为false,那么该条元组应被舍弃;否则,将key值与事实表度量属性拼接成一条元组,并将该元组以流水线的方式输送到下一个操作.

LWMJoin避免谓词判断以后又需要再次访问内存,在invisible join的基础上进一步减少随机内存访问(随机内存访问会造成高速缓存命中缺失,内存数据库应当尽量避免此类操作).图 5演示了CDDTA-MMDB处理查询Q4.1(如图 3所示)的步骤:首先,将查询分解并改写为RQ1,RQ2,RQ3和RQ4这4个子查询;之后,在相应维表上产生三元组或者是过滤位图(虚线的surrogate数组不作实际存储).第2阶段扫描事实表获取外键探测key数组,图 5中虚线框所示为Q4.1中的分组器.对于满足过滤条件的元组,直接将分组器中相应的值以流水线的方式传送给下一个操作符.在这个例子中,事实表有4条元组(位置1、位置3、位置5、位置6)满足条件,结果集有两组.LWMJoin所耗费的时间由产生三元组的t₀(与invisible join第1阶段时间相同)和一趟扫描事实表时间t₁组成,因此, LWMJoin所耗费时间大约是invisible join的2+1/e之一.由于轻量级物化的结果,LWMJoin实际所耗时间比invisible join在理论上分析的还要少,后面的实验验证了这一点.图 6给出了算法流程图步骤:首先初始化变量,将游标置于事实表第1条元组.根据SQL解析的信息,获取查询相关外键值探测key vector.如果某个key值不符合条件,则转而处理下一条元组;如果根据事实表外键所访问的三元组key值都大于0,则构造物理元组并将元组以流水线方式输送到下一操作符.

Fig. 5 Query execution process example图 5 查询执行流程示例

Fig. 6 The naive LWMJoin algorithm flow chart图 6 朴素LWMJoin算法流程图

事实上,选择外键探测key vector的顺序是很重要的.如果事实表上有过滤条件,也应当把这个因素考虑进来.我们倾向于优先探测具有最低选择率的key vector,依次按选择率执行谓词过滤判断.这个优化的原则是很简单的:尽量减少内存访问.一旦某个key的值为false,即可停止访问内存获取key vector元素的操作,转而执行下一跳记录.我们通过建立统计直方图,利用selinger风格来评估选择率.例如,有3个维表(t₁,t₂,t₃),3个等值选择操作s_A=a,s_B=b和s_C=c分别作用在这3个维表上.如果下面的关系成立:

(1)

CDDTA-MMDB是一个内存列存储数据库查询执行引擎,是针对星型模型数据仓库上的OLAP而提出的解决方案.我们将采用星型模型测试基准^{[25, 26]}(star schema benchmark,简称SSB)来评估执行引擎的性能.SSB是标准化的TPC-H,与TPC-H不同的是,SSB只有一个事实表LINEORDER.这个事实表是通过合并TPC-H的LINEITEM和ORDERS表而得到的,有17个属性.事实表记录个人的订单信息.LINEORDER的主键是组合键,包含ORDERKEY和LINENUMBER属性.事实表的其他属性包含指向CUSTOMER,PART,SUPPLIER和DATE表的4个外键以及订单的其他信息,例如优先级、价格、折扣和发货日期等.SSB包含4个维表:CUSTOMER, PART,SUPPLIER和DATE表.如同TPC-H,SSB也有一个扩展因子(scale factor),用来定义测试基准集的大小.各个表的大小都是相对这个扩展因子来确定的.本文的实验中使用的扩展因子为1,10,50以及100.此外,SSB有13个查询,分为4组.更多关于SSB的细节可参考文献^{[25, 26]}.

加载到内存的数据包括事实表中与实验相关的属性、所有的维表.实验环境如下:48GB的内存、两路Intel® xeon® E5645处理器2.4GHZ(每个处理器有6个超标量的处理核心,每个核心支持2个并发的物理线程)、1TB磁盘空间、64位Ubuntu 10.10操作系统.我们的关注点是轻量级物化所带来的性能优化、CDDTA-MMDB的整体性能以及系统在多核环境下的扩展性.

这个实验中扩展因子SF=100,忽略没有GROUP BY操作的查询Q1.x.我们模拟延迟物化根据最终位图访问维表操作,强制性地让LWMJoin在谓词判断以后访问维表,以获取数据进行聚集操作(称为CDDTA- LMJoin,late materialization join).同时,测试轻量级物化下这个阶段所耗费的时间.令我们感到意外的是Q3.1,如图 7所示,Q3.1中分组聚集所用时间占据了总时间的61%,超过了事实表扫描的时间.Q4.1,Q2.1和Q4.2中分组聚集所用时间占总时间的百分比分别是35%,21%和17%.相比之下,在上述4个查询中,LWMJoin已经将这个阶段耗费的时间所占百分比下降到28%,13%,8%和5%.在参与实验的其余查询中,LWMJoin在扫描事实表后的阶段所耗费时间基本上也比CDDTA-LMJoin要少.这个差别就在于扫描事实表以后,如果该条元组满足过滤条件,则CDDTA-LMJoin需要再次访问内存获取数据以进行下一步操作,而这种随机内存访问模式容易造成高速缓存命中缺失.所以,CDDTA-LMJion所耗费的时间比采用轻量级物化的LWMJoin时间要长,尤其是当选择率较高的情况下,例如Q2.1,Q3.1,Q4.1.

Fig. 7 CDDTA-LWMJoin and CDDTA-LMJoin time-consuming comparison in aggregation and grouping图 7 CDDTA-LWMJoin与CDDTA-LMJoin在分组聚集时间所耗费时间对比

3.2 CDDTA-MMDB总体性能评估

在这一节中,我们测试系统CDDTA-MMDB的总体性能.在不同的数据量下(SF分别为1,10,50,100),将系统与MonetDB以及C-Store的invisible join算法进行比较.CDDTA-MMDB与invisible join能够检测系统配置,将事实表根据CPU参数(支持的物理线程数)水平均匀划分,然后将划分后的表赋予各个物理线程.在这个实验中使用的MonetDB是支持多核多线程环境下的版本.我们还比较了朴素LWJoin与过滤顺序优化的LWMJoin.图 8给出了SF=100的情况下,朴素的LWMJoin以及带过滤顺序优化的LWMJoin的性能对比.查询Q1.x有两个过滤条件:一个作用在维表dwdate上,另一个作用在事实表上.如果先判断事实表上的谓词条件,那么系统所用查询时间会大幅度提升.在其余的查询中,带优化规则的系统也有较好的性能.图 9是在SF=1,10,50,100的情况下,CDDTA-MMDB与MonetDB(v11.7.9)以及invisible join的比较.

Fig. 8 Naive LWMJoin and optimized LWMJoin with filter order图 8 朴素LWMJoin与过滤顺序优化规则的LWMJoin

Fig. 9 CDDTA-MMDB vs. MonetDB vs. Invisible join time-consuming under different SF图 9 不同SF下,CDDTA-MMDB vs. MonetDB vs. invisible join所耗费时间对比

我们让进行比较的系统在数据集上重复运行若干次,使得实验是在“热”数据上进行,以消除I/O影响.在这个实验中,CDDTA-MMDB具有最优性能.总体而言,C-Store的invisible join比CDDTA-MMDB耗费的时间多5倍左右,这基本符合第2.4.1节的算法分析.在不同的SF下,MonetDB处理Q2.x,Q3.x以及Q4.3所需时间基本上比其他查询要少,这主要是因为查询Q2.x以及Q3.x需要处理的维表数据较小以及Q4.3的选择率很低.MonetDB的基数聚集表连接算法(radix cluster join)是高速缓存敏感的.当数据集能够全部放入高速缓存时,MonetDB具有如下很好的性能:

1) SF=50,100.CDDTA-MMDB与MonetDB在处理Q2.x,Q3.x所需时间相差不大,MonetDB甚至要略优于我们的系统;

2) SF=1,10.key vector能够全部放入高速缓存,我们的查询处理算法的简单性占据了优势,从而在这几个查询上,CDDTA-MMDB的性能要全部优于MonetDB;

3) SF=1,10,50,100.在其余的查询中(Q1.x,Q4.x),我们的系统都要明显优于MonetDB.在SF=100的情况下,CDDTA-MMDB处理实验中的13查询所用总时间为19 920ms,平均每个查询耗时1.5s左右,而MonetDB为50 311ms,平均每个查询耗时约3.8s.

我们的另外一个关注点是系统在多核平台上的扩展性,将处理线程个数从1增加到12,测试CDDTA- MMDB的加速比.选取Q1.1,Q2.1,Q3.1和Q4.1进行实验.纵轴是一个线程执行任务的时间除以n个线程处理任务的时间的比率.如图 10所示,CDDTA-MMDB基本上接近线性加速比.

Fig. 10 CDDTA-MMDB scalability on multi-core platform图 10 CDDTA-MMDB在多核平台上的扩展性

4 总 结

本文的主要贡献在于在新硬件平台下,针对大规模数据的OLAP查询所开发的一个新的查询执行引擎CDDTA-MMDB.这个查询执行引擎引进了一种新的表连接算法——LWMJoin,该算法能够消除传统的数据库中多表连接的性能瓶颈.另外,我们在CDDTA-MMDB中使用了一种新的物化策略——轻量级物化.轻量级物化具有延迟物化的优点,能够避免CPU产生额外的无用工作.与延迟物化相比,它又能减少内存访问和中间数据结构的产生.实验结果表明,CDDTA-MMDB是高效的,且具有较好的扩展性.这个查询引擎部署在集群系统中,利用反转星型模型^[8]的处理模式,可以轻松地应对TB级甚至是PB级的海量数据分析.未来的工作是把轻量级物化策略加入到开源的数据库系统,例如MonetDB,以及在CDDTA-MMDB中加入并发控制.