第37卷 第12期2010年12月计算机科学Computer Science V ol.37No.12Dec 2010
到稿日期:2010 01 08 返修日期:2010 03 22 本文受国家863计划(编号2009AA01Z143)，铁道部 清华大学科技研究基金(编号:J2008X 009)资助。
李 超(1978-)，女，博士，讲师，主要研究方向为存储技术、数据库技术等,E mail:li chao@tsinghua.edu；张明博(1982-)，男，工程师，主要研究方向为W eb 信息管理、数据库技术等；邢春晓(1967-)，男，博士，教授，主要研究方向为数据库技术、数字图书馆等。
列存储数据库关键技术综述
李 超 张明博 邢春晓 胡劲松(清华大学信息技术研究院 北京100084)
摘 要 随着互联网技术的发展、硬件的不断更新、企业及政府信息化的不断深入，应用的复杂性要求越来越高，推动着数据存储技术向着海量数据、分析数据、智能数据的方向发展，以便为数据仓库、在线分析提供高效实时的技术支持。基于行存储的数据库技术面临新的问题，已经出现了技术瓶颈。近些年来，一种新的数据存储理念，即基于列存储的关系型数据库(简称列数据库，下同)应运而生。列数据库能够快速发展，主要原因是其复杂查询效率高，读磁盘少，存储空间少，以及由此带来的技术、管理和应用优势。对列数据库技术的基本现状、关键支撑技术以及应用优势进行了介绍和分析。
关键词 列数据库，列存储，数据压缩，延时物化，成组迭代，不可见连接，数据仓库，商业智能,T PCH 中图法分类号 T P391 文献标识码 A
Survey and Review on Key Technologies of C olumn Oriented Databa Systems
L I Chao ZH A N G M ing bo XIN G Chun x iao H U Jin song
(Rearch In stitute of Inform ation Techn ology,Tsin ghua U nivers ity,Beijing 100084,China)
Abstract Co lumn o riented databa is a kind of new databa sto rag e technolog y that sto res dat a acco rding t o column (not tr aditio nally ro w).T he databa pioneers such as Dr.M ichael Stonebr aker ar e advocating and ex plor ing the new theo ry and techno log y fo r co lumn o riented databa.T he main featur es o f it are g oo d query efficiency,less disk access,less st orag e,and significant impro vement o f databa perfo rmance.Column or iented dat aba is an ideal ar chit ecture fo r data w arehou nat ively,and thus sho ws a goo d potential in suppo rting hig hly eff icient business intellig ence applica t ions.T his new technolo gy is promising in both academic and business,ther efo re attracting lots of high tech co rpora t ions and rearch institutes to devote in it.T his paper intr oduced and analyd the main featur es,key techno log ies and cur rent R&D situat ions of column or iented databa.
Keywords Column or iented databa,Compressio n,Block it er atio n,L at e mater ialization,Invisible join,D ata w arehou,Business intellig ence,T PCH
1 引言
列数据库是基于列存储的、主要面向企业决策分析领域的关系型数据库。在SIGM O D85，论文 A Deco mpo sitio n St orag e M odel [1]提出了一种新的存储概念，简称DSM ，这就是列数据库的雏形，但是这种技术在当时并没有得到足够的重视。近些年来在以M ichael Stonebr aker ,Daniel J.Abadi,Peter Boncz 为首的一批专家的大力提倡下，列数据库相关技术及应用快速发展，在企业决策领域已经开辟了一条新道路(参考网址w w m)。这种技术的特点是复杂数据查询效率高，读磁盘少，存储空间少。这些特点使其成为构建数据仓库的理想架构，因而引起数据库学术前沿和相关高新科技企业投入大量的人力和物力研发。举办的英文
1.1 列数据库基本概念
列数据库是对应并区别于行数据库的概念。行数据库就
是我们所熟知的传统关系型数据库，即数据按记录存储，每一条记录的所有属性都存储在一起，如果要查询一条记录的一个属性值，需要先读取整条记录的数据。而列数据库是按数据库记录的列来组织
和存储数据的，数据库中每个表由一组页链的集合组成，每条页链对应表中的一个存储列，而该页链中每一页存储的是该列的一个或多个值。
1.2 列数据库的学术价值与应用价值
列数据库技术有它独有的学术价值，近些年来在国际一流的数据库会议上频频有关于这个领域的优秀论文出现[1 3,5 17]，他们主要围绕其商业价值以及主要关键技术，包括基于其主要存储原理的存储压缩、延时物化、成组叠代、查询优化、索引、及加密等进行研发。
列数据库的应用价值来自它对复杂查询的灵活快速以及压缩所带来的存储优势，这使其在数据仓库和商务智能方面具有良好的发展前景。已经有许多列数据库在企业决策分析
领域的成功案例。V ERT ICA已经在美国拥有了许多客户, SY BASE IQ更是已经进入了中国市场。
1.3 主要的开源列数据库和商业列数据库
1.3.1 C Store
C Sto re是一款开源的、运行于L inux系统的列数据库，是耶鲁大学、麻省理工大学、布朗大学等联合协作开发的软件，于2006年10月发布。它是一种适合做学术研究的列数据库，目前主要的学术研究都
是利用它来做的，在学术界比较流行。它同时是商业列数据库产品V ER T ICA的原型(ht t p://db.csail.mit.edu/pr ojects/csto re/#people)。
1.3.2 M onetDB
M onetDB是一款运行于L inux和Window s系统上的高性能开源列数据库(mo netdb.cwi.nl/)，同时是一款内存数据库。它可应用于数据挖掘、O L AP、G IS、XM L查询、文本和多媒体检索。它支持SQ L∀99,SQ L∀03核心标准，支持持久存储、触发器。用户可用C编写所需功能。它还支持OP EN G IS标准和SQ L/XM L的大部分标准。它基于内存文件存储，可对数据库进行升级，支持32位和64位平台，能对查询进行有效的优化[14]。
1.3.3 M onetDB/X100
M onetDB/X100同M onetDB都是一个组织开发的，主要区别是X100不是内存数据库，而其技术也更加成熟一些，查询效率也更加优秀。M o netDB/X100同样运行于L inux和Window s系统上，同样由C编写。
1.3.4 Rasdaman
Rasdaman是一款运行在L inux系统上的商业列数据库，由不莱梅大学和Rasdaman公司合作开发(ww
w.rasdaman. co m),2008年9月宣布开源版本(ww w.r asdaman.o rg)，全名为 raster data manag er。它是一款快速、灵活、价廉的列数据库，其开发语言是C/C++以及JA V A，支持大部分SQ L 标准。
1.3.5 Syba IQ
SY BASE IQ是Sy ba公司专为分析型应用与数据仓库而设计的，是唯一一个由传统基于行存储的关系型数据库厂商开发的列数据库产品。Syba IQ是拥有列式存储、专利索引、查询优化等技术的数据仓库引擎，带来的查询速度将比传统数据库提升10~100倍。
1.3.6 Par A ccel
Par Accel分析数据库PA DB是一个专门开发的数据仓库和分析型数据库管理系统,P arA ccel具有可扩展性、简单的数据仓库的安装和操作、成本可接受性、高效解析查询处理等特点。
除此之外，还有Ver tica,X100/Vecto rW i,K ickFire, SAP Business A ccelerato r,Info brig ht,Ex aso l等开源列数据库以及商业列数据库。
可以看到，列数据库已经从SIG M O D85上不为大众所关注的DSM雏形发展到了今天初具规模的局面。无论是在学术前沿研究、系统技术研发，还是在数据仓库、数据分析及决策支持等应用领域，列数据库都是一个蓬勃发展的热点和新的增长点。
本文从3个方面分析列数据库相对于行数据库的优势；然后介绍列数据库的几大关键技术，包括压缩、延时物化、成组迭代、不可见连接，这既是当前的一些研究前沿和热点，又是不同列数据库系统之间的主要技术区别所在；接下来，介绍用于评价数据库系统性能的T P CH测试，以为相关研究提供参考，并引用T PCH官方测试结果进一步说明列数据库的优势；最后总结全文。
2 列数据库的优势
列数据库在数据仓库、商务智能领域应用中有着先天的优势：独特的存储方式，能够迅速地执行复杂查询；列数据库的压缩技术，更是能为数据仓库、商务智能应用中巨大的数据量节约存储成本；列数据库先进的索引技术也大大提高了数据库的管理。
2.1 列数据库存储方式带来的技术优势
因为列数据库和行数据库都是关系型数据库，因此列数据库在逻辑上与行数据库没有区别，用户处理和操作的都是一行一行的记录、一个一个的表。两者的本质区别在于其物理存储是基于列存储还是基于行存储。列数据库按列存储的结构，便于在列上对数据进行轻量级的压缩，列上多个相同的值只需要存储一份。压缩能够大量地降低存储成本。
按列存储和压缩的特点，也为列数据库在查询方面带来先天优势，因为若能将更多的数据压缩在一起，
则在每次读取时就可以获得更多的数据。很显然，每次读取操作获取更多的数据就意味着更快的处理速度。同时，列数据库的存储特点有利于迅速查询所需要的列。行存储虽然可以比较轻松地添加修改记录，但是会增加许多不必要的读取；而列存储只需要读取相关数据，并且可以从多个入口写入数据。
六级听力mp3
2.2 列数据库在数据管理方面的便捷优势
在数据管理方面，行数据库采用的是稠密索引，即当数据库文件中的记录不按照关键码的顺序排列时(比如按照加入的顺序排列)，需要对每一个记录建立一个索引项。这有两方面的缺点：一是增加所用的存储空间，二是增加数据更新时的代价。正是由于这两方面的问题，在基于行存储的关系型数据库中，为表的所有列都建立索引就不太现实。这样就出现了下面的问题：如果一个查询语句是基于一个未加索引的列查询，系统就不得不做全表扫描，导致数据库的查询效率不高。因此，考虑在哪些列加索引并根据应用的需求适时调整，就成为数据库管理员的一项繁重工作。而列数据库因为各条记录在磁盘中是按照关键码值压缩顺序存放的，所以采用的是稀疏索引，即把连续的若干记录分成组(块)，对一组(块)记录建立一个索引项。列数据库可以为所有列建立稀疏索引，事实上也都是这么做的。这是因为每个列的值都已被压缩顺序存储，索引只需建立到数据块级，因此索引的存储空间很小，维护费用很低，使得可以以很小的代价给所有的列建立索引。当查询通过索引定位到某一数据块后，就可以使用二分法查找。这样，数据查询在任何情况下都不会导致全表扫描，从而提高了数据库的查询性
能。在列数据库中，后台程序默认地自动为所有的列维护稀疏索引，因此为数据库管理员卸下了建立、管理和维护索引的繁重工作。
此外，无论是在行数据库还是列数据库中，在删除一条记录时，都会出现一个物理存储空间上不连续的空洞。在行数据库中，随着一段时间的增删操作，这些空洞会越来越多，越来越大。这一方面会导致物理存储空间的闲置和浪费，另一
方面会使得访问数据库的效率下降。因此，行数据库管理员为了填补这些空洞、消除空洞带来的负面影响，经常在维护时要做的事情是把数据全部导出来，再重新导回去。而列数据库因为在每一列上都采用了轻量的稀疏索引，在插入删除数据时，利用这些索引可以把空洞尽量减小，免除了数据库管理员的大量导入、导出工作。
2.3 列数据库在数据挖掘领域的应用优势
数据挖掘应用有着数据量大、主要针对少数列进行复杂查询操作的特点。在列存储模式下，对于列的DM L (Data M anipulation L ang uage，数据操纵语言命令)操作，仅仅是对列所对应的数据库页链进行数据扫描，不会导致对全表的数据访问，可以有效降低DM L 操作的I/O 数量。由于数据按列存储，为调整数据模型所做的新增列、删除列操作不再会遇到数据碎片问题。这是因为在列存储中，由于数据存储以列为单元，列删除或者新增操作是将列所对应的数据库页链从表的页链集合中去除或者新增，
2009全美音乐奖
不涉及其他列对应的数据库页链。此外，列数据库中数据按列压缩的特点也同样能够减少挖掘时的I/O 量[2]。
3 列数据库的关键技术
3.1 压缩
随着信息化的不断发展，在数据仓库与商业智能领域中，数据量已经越来越大，企业不可能不间断地增加存储成本，所以数据压缩已经是目前IT 领域一个一定要面对的问题。列数据库的存储特点，决定了其在压缩方面的优势。
在SIGM O D06会议上,D aniel J.Abadi [3]通过在开源的列数据库C Store 上进行实验比较和理论分析指出，主要的压缩方法有以下几类:
1)行程编码算法(Run length Enco ding );2)词典编码算法(Dict ionary Encoding);3)位向量算法(Bit V ect or Encoding)。3.1.1 行程编码算法(Run leng th Encoding)
行程编码算法(见图1)是比较适合列数据库的压缩算法之一，即用一个三元组记录数据值、数据出现的起始位置和持续长度(即行程)，以代替具有相同值的若干连续原始数据，使三元组的存储长度少于原始数据的长度。
三元组描述为(X,Y ,Z):
X：数据的值,Y：起始位置,Z :
长度。
图1 行程编码算法
3.1.2 词典编码算法(Dictio nar y Enco ding )
词典编码就是生成一个 原始值 替代值 的对照词典。为了起到压缩的作用，替代值的长度小于原始值的长度。存储的时候，只存储替代值而不是原始值，从而压缩了存储空间。
算法描述如下:
T1：原始表(其中,T1有n 行)
DIC：词典表(关于表T 1的第k 列的词典) T2：压缩存储表
N：原始值 M ：替代压缩值For(1#i #n)Begin
扫描T 1中第k 列的第i 个值得到原始值N ; 查找DIC 中N 对应的压缩值M ;
将压缩值M 作为T 2中第k 列的第i 个值存储;En d.
如图2所示的例子中，简单的两位数字代替了原始的字符串,
缩短了所需的存储空间长度。
图2 词典编码算法
3.1.3 位向量编码算法(Bit V ector Encoding)
encore
位向量编码是为每一个不同的取值生成一个位向量，根据位向量(串)中不同的位置取值0或1来对应并确定不同的原始值。
算法描述如下:
T 1：原始表中的某一列(其中,T 1有n 行) V :T1的取值空间(无重复元素) M ：原始值
m:V 的模数(V 中的值的个数)
BV i(1#i #m):V 中不同取值对应的位向量For(1#i #n)Begin
扫描T 1中的第i 个值M ; 将M 加入取值空间V;En d;
计算V 的模m;For(1#i #m) 初始化位向量BV i;
//m 个位向量分别对应m 个不同的取值For(1#i #n)Begin
扫描T 1中的第i 个值M ; 确定M 对应的位向量BV x ; 将位向量BV x 的第i 位值置为1; For(1#j #m)
if (j <>x )th en 将位向量BV j 的第i 位值置为0;
En d.
图3中 产品ID 列的原始数据经过位向量算法压缩后，形成如图2所示的位向
量。
图3 位向量算法
3.1.4 3种压缩方法比较
Daniel J.A badi在文献[5]中介绍的3种压缩方法都是轻量级压缩算法。轻量级压缩最大的优点是能够在不解压的情况下直接对压缩状态的数据进行操作[19]。就目前的列数据库而言，行程编码是一种最容
易实现的压缩方法，但是有一定的局限性。表1是3种压缩方法的优缺点比较。
表1 压缩方法比较
算法名称行程编码算法词典编码算法位向量算法
数据列的共同特征a)适用于重复数据较多
b)不适用于重复数据较少
适用数据列的不同特征重复数据的排序
比较规则
取值空间较小取值空间较小
不适用的数
据列不同特
征排序不规则
a)取间空间较大
b)数据类型长度比词
典符号长度更小
取值空间较大
优点对于适用的数据
特征，有比较好
的压缩效果
a)对于数据类型要求
较低
b)对于数据排序要求
较低
a)对于数据类型要求
较低
cheerleaderb)对于数据排序要求
较低
c)在有些情况，查询
效率要比词典编码高
缺点对列值的重复性
以及排序要求较
高
需要创建一张词典
表，增加维护代价，如
果数据重复性不高,
词典表会过于巨大
用位置代表数据，如
取值空间较大，或重
复性较低，占用空间
会比较大
注：表中所谓 适用即采用了某一压缩算法可以起到减少存储空间的效果。
3.1.5 压缩优势的实例
对于列数据库主要应用的数据仓库领域，海量数据的有效压缩是一个十分重要的优势。几种开源和商业的列数据库系统都将良好的压缩率作为自己突出的优势。列数据库的领军厂家SYBA SE IQ就声称其压缩率可达到70%。
表2是2005年W inter Co rpor ation做的10大数据库评比。表中的数据仓库大小是建立两年后数据仓库
的大小，而原始数据大小是指数据仓库建立时的大小。N ieln M edia Rear ch是美国一家从事媒体收视率分析研究的公司，基于Syba IQ系统建立了数据仓库，原始大小是17.969T B。数据仓库建立两年后，大小是17.685T B。Y aho o点击流分析数据仓库(基于O racle系统)建立的时候数据量是17.014T B，而建立两年后，数据量大小为100.386T B。基于行数据库Or acle的Y aho o点击流分析数据仓库从约17T B扩张到了约100T B，大约扩张了6倍。而基于列数据库Syba IQ的Nieln M edia Rearch数据仓库却随着数据的积累被压缩得比原来还小。所以，从这个例子可以看出列数据库Syba IQ的压缩比是非常高的。
表2 对比表
公司、组织数据仓
库大小
(T B)
原始数
据大小
(TB)
数据
行数
数据
库
操作
系统
体系
结构
数据库
厂商
系统
厂商
存储
厂商
Y ahoo100.38617.0143853Oracle unix Centralized
/SMP
Oracle
Fujitsu
Siemens
short怎么读
EM C
N ieln
Med ia Rear ch 17.68517.9695024
S yba
IQ
unix
Centralized
/SMP
Syba
Fujitsu
Siemens
EM C
3.1.6 总结
在国内，已经有同行对压缩算法的性能分析做了很多工作[18]，但列数据库领域的压缩算法研究仍是
我们未来工作的重点之一。压缩技术不仅可以节约存储空间，而且是提高查询效率的关键因素。但是上述列数据库压缩方法都有其局限性，所以研发一个适用范围更加广泛、压缩以及解压的时间更加快速的压缩方法，必然是列数据库领域学术研究的一个热点。
3.2 延时物化
为了说明延时物化，先介绍元组物化的概念。元组物化，即将常用元组或可能会用到的逻辑元组从实际物理存储的状态生成为实体化的元组，也称为物化，存储在内存中。在随后查询时，直接读取已经物化的元组，以提高查询的效率。而元组物化有两种方案，分别是提前物化：在提交查询之前物化元组；延时物化：尽量推迟物化元组的时间，在查询中间的某个时刻物化元组。
对于列数据库来说，提前物化需要解压所有已经压缩的数据，其时间和空间的开销是很大的。同时，提前物化会涉及到很多不必要的列，有悖列数据库按列存储、按需取用的初衷。因此，在列数据库领域，提出了延时物化的思想。
3.2.1 延时物化形式化描述
假设有如下查询:
凯顿儿童美语s elect value1,value2,∃,value N,AGG1,AGG2,∃,AGG Q
from table1,table2,∃,table M
w herecondition1OP1conditon2OP2,∃,OP T condition P
LIST1,LIS T2,∃,LIST L
Value i(1#i#N)：查询直接要得到的值
AGG i(1#i#Q)：对于查询的值进行聚集计算的结果
table i(1#i#M)：查询所涉及到的表
con dition i(1#i#P)：查询的选择条件
三年级上册英语第一单元
OP i(1#i#T)：逻辑运算(与或非)
LIST i(1#i#L)：对结果进行排序处理指令
算法描述如下:
For(1#i#P)
Begin
对于condition i，生成标定符合条件的位向量h i;
En d;
初始化目标位向量H;
H:=h1;
For(1<i#P)
H=H OP i-1h i;
初始化目标物化结果空间为O;//O有(N+Q)个存储空间
For(1#i#(N+Q))
Begin
if(i#N)then O i=(Value i对应的列)AND H
el O i=(AGG i-N对应的列)AND H;
En d;
初始化最终查询结果空间为S;//S有(N+Q)个存储空间
For(1=<i<=(N+Q))
Begin
if(i<=N)then S i=O i
el S i=AGG i-N(O i);
En d;
输出结果时按照LI ST1,L IST2,∃,LI ST L的要求依次排序。
3.2.2 延时物化测试实例
以下面的查询为例:
S elect custID,SU M(price)From table w here
prodID =4an d s toreID=1gr ou p by prodID
如图4所示，如果采用提前物化，列数据库在执行查询时，会首先将列中数据解压，之后构建(物化)元组。这样的操作有3个缺点：一是需要解压所有数据；二是需要物化所有元组;
三是增加内存负担。
图4 提前物化
如果采用延时物化，列数据库则按过程执行查询。如图5所示，根据判定条件pro dID =4,stor eI D =1，将pr odID,sto reID
两列分别用位向量进行选择标定。
图5 延时物化第一步
之后将两个列对应的向量进行逻辑与运算，得到一个列向量，如图6
所示。
图6 延时物化第二步
通过上面得到的位向量，与相关两列进行逻辑与运算。在此刻将查询得到的元组进行物化，如图7
所示。
图7 延时物化第三步
最后通过物化的元组，得到所要查询的结果custID,SU M (price)，如图8
所示。
图8 延时物化第四步
ICD E2007会议上,Daniel J.A badi [7]在对延时物化和提前物化进行测试后得出了令人信服的定量化结论：在低选择性、中选择性和高选择性3类具有代表性的查询中，延时物化的表现始终要好于提前物化，如图9所示。
在对比测试中，即使在没有压缩的情况下，延时物化的表现仍然要比提前物化的好，如图10
所示。
图9
对比图
图10 对比图
3.2.3 总结
延时物化最主要的优点在于其高效的压缩传输数据开销：在执行计划中用位图(位向量)来标识行的位置，直到最后必须取属性值时再实际取相应列的值，尽可能地避免了不必要的实际数据传输开销。延时物化是一个比较实用的技术,
非常适合在列数据库中使用。单纯的列数据库是一列一列地把数据存储在磁盘上，如果离开列数据库，延时物化许多性能上的潜力得不到实现[7]。D aniel J.Abadi 在文献[7]中，利用开源列数据库平台C Sto re，详细介绍了两种物化方式的实验过程。另外,M onetDB/X100这个比较有影响力的开源列数据库也运用了延时物化技术。
3.3 成组迭代
要处理一系列记录，行数据库要对每个记录依次进行迭代，对于每一个记录通过单个记录的操作接口，从这些记录中
选取需要的属性或者执行函数的调用。这是一个成本很高的操作。所以IBM 的专家S.Padmanabhan 提出，可以成组地调用函数，这样就可以节约很多资源。
对于现代CPU 而言,CP U 在缓存中找到有用的数据被称为命中；当缓存中没有CPU 所需的数据时(未命中),CPU 才访问内存。所以,CPU 访问内存的频率越低(也称未命中频率)，查询的效率也就越高。列
式存储具有高度的可压缩性。假设对一列使用行程编码压缩，就像本文3.1节中提到的一样(值、起始位置、长度)，占10个字节。利用64字节的高速缓存行，可以将6个压缩的列值载入一个高速缓存行。这样，每次访问内存，读取的压缩列值是6个，而这些压缩的列值对应的实际数据就远远不止6个。
此外，如果列被设定为固定宽度，这些值可以直接对应为一个数组。把数据当作一个数组来操作，可以使单个记录处理代价最小化。所以，列数据库的存储方式可以大大提高CP U 吞吐量。随着CP U 性能的不断提高，运用成组迭代的列数据库在未来的表现将更加优秀[6]。
成组迭代的思想是针对行数据库提出的，所以成组迭代同样也适用行数据库。在这里也可以感觉到，列数据库作为关系型数据库，在许多方面是不得不借鉴行数据库已经成熟的技术。
3.4 不可见连接
这是Daniel J.A badi [3]提出的一种专门针对列数据库进行查询效率优化的技术。该方法将查询所涉及的各个表的属
性对于查询条件的符合情况采用位向量的方式来标定，之后对这些位向量进行逻辑与或运算，得到最终可用于标定结果的位向量。整个过程没有属性或列之间直接的值连接操作，这些直接的操作被位向量直接的逻辑与或运算替代，因此被称为 不可见连接 。不可见连接的目的是尽量避免原始数据
传输、处理和缓存的开销，而充分利用按列存储的便利，采用位向量的方式来标定和连接符合条件的中间结果。该方法适用于星状结构的数据库。
3.4.1 不可见连接形式化描述
假设有如下查询:
lect valu e1,valu e2,∃,value N,AGG1,AGG2,∃,AGG Q
from tab le1,table2,∃,table M
w h ere
condition1OP1conditon2OP2∃OP T condition P
L IS T1,LIST2,∃,LIST L
Valu e i(1#i#N)：查询直接要得到的值
AGG i(1#i#Q)：对于查询的值进行聚集计算的结果
table i(1#i#M)：查询所涉及到的表
condition i(1#i#P)：查询的选择条件
OP i(1#i#T)：逻辑运算(与或非)
L IS T i(1#i#L)：对结果进行排序处理指令
算法描述如下:
count=0;//count用于记录选择性查询条件的个数
For(1#i#P)
Begin
if(condition i是选择性条件而非连接条件)
th en
Begin
对于condition i，生成标定符合条件的位向量h i;
cou nt=count+1;
end;
E nd;
初始化目标位向量H;
H:=h1;
For(1<i#P)
if(condition i是选择性条件而非连接条件)
th en H=H OP i-1h i;
初始化中间物化结果空间O;
//O有(P count)个存储空间将被物化中间结果填充
For(1#i#P)
Begin
if(condition i是连接条件而非选择性条件)
th en O i=(condition i对应的事实表的列)AND H
E nd;
初始化最终连接结果空间为R
//R有(P coun t)个存储空间将被最终连接结果空间填充
For(1#i#P)
Begin
if(O i存储的是中间物化结果而非初始化值)
th en
Begin
condition i对应的维表与O i在对应列作连接;
R i=选取连接结果中与Value i(1#i#N)或者AGG i(1# i#Q)关联的列;
En d;
E nd;
初始化最终查询结果空间为S//S有(N+Q)个存储空间
For(1#i#(N+Q))
Begin
if(i#N)then S i=R i
els e S i=AGG i-N(R i);
E nd;
输出结果时按照LI ST1,L IST2,∃,LI ST L的要求依次排序。
3.4.2 不可见连接测试实例
以下面的查询为例:
s elect c_nation,s_nation,d_year,venu e)as revenu e
from customer AS c,lineorder AS lo,sup plier AS s,dw date AS d
w here lo_cu stkey=c_custk ey
and lo_suppk ey=s_s uppkey
and lo_orderdate=d_datekey
and c_region=%ASIA∀
and s_region=%ASIA∀
and d_year&1992and d_year#1997
grou p by c_nation,s_nation,d_year
order b y d_year asc,revenu e desc;
首先我们按照这个顺序来执行w her e子句,lineor der, customer(reg ion=Asia),supplier(reg ion=Asia),date(y ear betw een1992and1997)。
从表3中，根据判定条件r egio n=Asia，得到custkey为1和3的记录符合条件。
表3 客户表
cust key reg ion nat ion
garage怎么读
1A SIA CH INA
2EUROPE FRA NCE
3A SIA INDIA
在表4中，根据判定条件reg ion=A sia，得到suppkey为1的记录符合条件。
表4 供应商表
suppkey reg ion nat ion
1A SIA RUSSIA
2EUROPE SPAIN
在表5中，根据判定条件(d_y ear&1992and d_y ear# 1997),3条记录都符合条件。
表5 日期表
dat ei d yea r
010*********
010*********
010*********
之后在lineo rder表(fact table)(见表6)中根据上述判定条件进行符合条件的连接。
表6 事实表
o rderkey custkey suppkey o rderdat e revenue 1310101199743256
2320101199733333
mbt3210102199712121
4110102199723233
5220102199745456
6120103199743251
7320103199734235
如图11所示，根据对表3-表5的选择判定，将表6中custkey,suppkey,orderdate这3个用于连接的列分别用位向量进行选择标定，之后将这3个列对应的向量进行逻辑与运算，得到一个用于传递实际选择条件和连接结果的列向量，如图12所示。
