列存储Word文档格式.docx
《列存储Word文档格式.docx》由会员分享，可在线阅读，更多相关《列存储Word文档格式.docx（23页珍藏版）》请在冰点文库上搜索。
Sybase的数据仓库方法从根本上不同于其他的关系型数据库提供商。
Sybase认为，传统的关系型方法以及ROLAP方法效率很低，要想获得足够的性能，必须通过高额的成本，在额外的硬件、软件、资源、钱、时间上进行大量投资，否则不可能达到。
因此Sybase已经开发了一个新的关系型数据库——逆向关系型数据库可能是对此最好的解释，它使用一个传统的关系型结构以及类似的非常熟悉的术语，但是却是基于列的，而非基于行的。
我们开始审视SybaseIQ时，我们正是从此点开始，Sybase对其使用列方法的好处所作的论述“相当令人信服”。
然而，通过对数据仓库不断增加需求、迅猛增长的来自Web的数据与用户所带来的分析和报表（更不必提即将到来的RFID应用），以及客户的经验等等，我们现在可以证明，SybaseIQ提供了一个远比那些传统的关系型供应商更优越的方法。
2.1列存储
不同于传统的关系型数据库，其数据在表中是按行存储的，SybaseIQ是通过表中的列来存储与访问数据的。
尽管这种方式很明显的不太适合于交易环境，在交易环境中，一个事务与一行数据有效对应，而在查询进程环境中，很显然，查询是基于特定的列来选择的。
列方式所带来的重要好处之一就是，由于查询中的选择规则是通过列来定义的，因此整个数据库是自动索引化的。
事实上，情况并不象上述的这样简单，SybaseIQ有各种方法支持基于列的索引，我们将在下面就此讨论。
使用列方法的另一个结果就是，SybaseIQ在压缩方面比传统的关系型数据库更加有效（根据Sybase所称，效果可达5倍之好）。
这个原因，无疑说，是由于同一列中的所有数据域有相同的数据类型。
因此，每一列都可以为优化的效率与检索进行压缩。
相比来讲，基于行的存储，各个不同的域拥有各不相同的数据类型，这非常适合于交易进程。
在这样的环境中，不断变换理想的压缩算法是不可行的，这意味着任何压缩都将可能是一种最低通用的规则。
基于列的方法的另一个重要优势完全基于所有读出的数据量。
无论何时你从传统的数据库中访问数据，你需要读出完整的每一行，而不管你实际所感兴趣的是哪些域。
实际上，这可能意味着读300个字节的数据仅仅检索20个字符的数据。
但是，基于列来读取数据，你仅仅需要读出你想要了解的数据。
当然，读取一条单独的记录时，性能上的不同可以忽略，但是许多查询需要进行全表扫描。
当读取数百万行数据时，性能的不同就会非常显著。
Sybase认为，SybaseIQ的列存储天然的比普通的ROLAP方法提供更佳的性能，IQ不需要象多数竞争对手或者SybaseAdaptiveServerEnterprise（ASE）一样支持硬件的并行处理。
尤其是，Sybase指出，与数据分区相关的问题就是需要支持硬件的并行机制。
显而易见，不论如何进行分区，分区都会带来很多问题（更不必说额外的维护了），不过，它打开了性能改进的实质性途径。
然而，Sybase进一步阐述道，这仅仅是对基于行的方法所与生俱来的糟糕性能的一种补偿机制。
Sybase有很多事实支持它的论断，但这并不意味着Sybase避免任何形式的数据分区。
然而，不同于水平分区，SybaseIQ实施的是垂直分区，也就是说分区是按照列而不是按照行进行的。
该方法的优势之一是分区从来不会变得不均衡，这是由于每个表中的每列都有相同数量的域。
这大大降低了管理分区的维护需求，同时消除了数据库的重新组织，而在分区变得不均衡从而开始影响性能的时候，数据库重新组织是必需进行的。
最后，需要注意的是，SybaseIQ并没有避免使用OLAP。
对于那些希望在聚合层次下以一个相对预先定义的方式进行查询的用户来讲，OLAP具有明显的优势。
基于此，Sybase支持OLAP功能属性如排列、百分比、平均。
2.2数据压缩
传统的数据库引擎不能以一种通用的方式进行数据压缩，主要是由于存在以下三个问题：
1.按行存储的数据存储方式不利于压缩。
这是因为数据（大多为二进制数据）在以这种方式存储时重复并不多。
我们发现，按行存储的数据，最多能有5-10%的压缩比例；
2.对于许多2K和4K的二进制数据页来说，为压缩和解压缩而增加的开销太大；
3.在OLTP环境中，大量读取和更新混杂在一起。
每一次更新需要进行压缩操作，而读取只需解压缩操作，大多数的数据压缩算法在压缩时比解压缩时慢4倍。
这一开销将明显降低OLTP数据库引擎的事务处理效率而使得数据压缩的代价昂贵到几乎不能忍受。
在数据仓库应用中，数据压缩可以用小得多的代价换取更大好处。
其中包括减少对于存储量的要求；
增大数据吞吐量，这相当于减少查询响应时间。
SybaseIQ使用了数据压缩。
这是由于数据按列存储，相邻接的字段值具有相同的数据类型，其二进制值的范围通常也要小得多，所以压缩更容易，压缩比更高。
SybaseIQ对按列存储的数据通常能得到大于50%的压缩。
更大的压缩比例，加上大页面I/O，使得SybaseIQ在获得查询的优良性能的同时，减少了对于存储空间的需求。
在传统的数据库中，为提高查询性能所建立的索引占用的磁盘空间往往需要比数据本身需要的磁盘空间多出3-10倍。
而SybaseIQ存储数据所占用的磁盘空间通常只是原数据文件的40%-60%，是传统数据库所占用空间的几分之一。
SybaseIQ与传统数据库在数据压缩方面的典型对比
智能压缩技术，与精巧的索引结构和列存储结合，给了IQ比其他数据库引擎高的多的存储效果。
这将获得更低的存储成本与更高的性能（因为系统仅需很少的磁盘I/O读取或写入任何给定的数据库块）。
2.3索引
SybaseIQ的秘密在于其索引。
随着Sybase客户发现了新的分析需求，Sybase可以简捷地建立新的索引以满足这些需求。
这种方法的奇妙之处在于为数据仓库增加新的索引几乎不会（即使有也是微乎其微）影响数据仓库的架构或使用仓库的分析型应用。
在实时企业与闭环应用领域，Sybase将索引视为在TB数量级（将来）甚至PB数量级数据仓库中获得更高查询性能的关键。
今天，Sybase实际上已使用了如下几种种索引机制：
2.3.1LowFast索引这些是低基数索引，它使用一个被称之为“代号化”的进程。
使用该进程，数据被转换为代号，然后存储这些代号而不是数据。
这对于减少冗余数据的数量尤其有用。
例如，在整个英国拥有大量客户群的公司，将需要存储客户的地址。
这将意味着巨大数量的重复的郡的名称。
因此，不是保存大量的“班夫郡”的实例，例如，Sybase将会用一个数字代替每个郡的名称。
因此，由于班夫郡按照拼音排列在英国是第5个郡（排在Aberdeen,Armagh,Avon与Ayrshire之后）因此，它可能就会被设值为5。
如果一个列包含一个数字值，该值自身可以用于代号化的基础。
一旦建立了代号（这是一个自动进行的进程），一个位图索引将被建立以表示这些代号。
代号化典型地应用于列数据存在有限数量的可能取值。
这也是为什么Sybase称之为低基数索引的原因，典型的，它仅用于不同的取值个数在1500以内的域。
2.3.2Bit-Wise索引
对于高基数的域，那些取值个数超过1500个（如金额值），Sybase使用其专利的被称之为Bit-Wise索引.这在你希望在范围搜索的时候同时进行计算的情况下，尤为有用，例如，查找销售价格低于50欧元的货品数量及总收入。
如同位图的其他变量，该方法的优势之一就是计数（count）查询可以直接通过读取索引获得答案，而无需读取数据。
2.3.3HighGroup索引
实际上，它是B-树索引。
然而，此处的原则是，用户仅仅在几个列有可能作为一个组来使用的情况下，尤其是高基数与低基数的联合搜索时，才定义这些索引。
比如可能有这样的例子，按照商店（低基数）查询产品销售清单与价格（高基数）。
2.3.4FastProjection索引
该索引类型（缺省的）就是列存储本身。
如果用户总是打算检索整个列的数据，则列存储事实上意味着列可以直接映射到表或查询中，而无需显式的定义任何索引。
这非常有用，例如在“Where”从句中。
2.3.5Word索引
这是一个文本索引。
它基于关键词或短语字符串搜索。
这种类型的索引，历史上一直没有用于数据仓库中。
然而，它有着大量重要的市场，在这些市场上，能够联合定量与定性的分析非常重要。
例如，在医疗横业，医生的诊断通常就是：
笔记。
为了获取信息，例如发病率，因此可能必须访问这种非结构化的数据。
2.3.6Compare索引
这个索引技术允许数据列的比较，从效果上讲，类似于“if…then…else”表达式。
例如，“if支出大于收入，then…”。
该类型的索引对于在Web应用中实时比较尤其有用。
2.3.7Join索引
正如索引的名称所示，它是为消除表连接的需要而设计的。
正象大多支持索引的情况，它可能在预先已知的查询需求下更为有用。
2.3.8TimeAnalytic索引
这为基于日期、时间、日期与时间建立索引提供了选项。
需要注意的是，对于传统的关系型数据库，处理基于时间的查询尤为困难。
大量扩展工具用以支持在各种情况下使用这些索引。
这包括为减少硬盘（或内存——位图可能存在缓冲中）需求的索引压缩，联合使用不同类型索引的能力，以及使用布尔操作如AND与OR过滤比特队列等。
这些特性表明，SybaseIQ克服了传统的位图的缺陷，即不适合于表连接或数据聚合。
SybaseIQ在最近发布的版本中增加了一个索引顾问（IndexAdvisor），这一点尤其令人欢欣：
这将建议管理员何时应该增加新的索引以及增加那种类型的索引。
三、行列存储比较
将表放入存储系统中有两种方法，而我们绝大部分是采用行存储的。
行存储法是将各行放入连续的物理位置，这很像传统的记录和文件系统。
然后由数据库引擎根据每个查询提取需要的列。
列存储法是将数据按照列存储到数据库中，与行存储类似；
3.1基于行的储存
基于行的存储是将数据组织成多个行，这样就能在一个操作中找到所有的列。
这种做法的缺点是必须每次处理一整行，而不是只处理自己需要的列。
不过，这样在处理相同实体的两个或多个列的查询时能够取得更快的速度，而且可以提高更新、插入和删除操作的速度。
基于行的存储系统可以进行并行处理，并且不需要模仿顺序文件系统，尽管有许多产品仍然在这样做。
这种做法的缺点是，一旦确定了这种体系结构，那么使用的代码就不仅仅是“老式代码”，甚至比像“家族的诅咒”那样的代码还要难懂。
Teradata是一种非常流行的数据仓库产品，它使用了散列处理，并且从一开始就具有并行处理机制。
最开始的时候它是一种数据库机，不过当前版本采用的是在标准硬件上建立虚拟机的方式。
它从设计上就总是采用并行处理方式。
各结点根据实际需要彼此交谈，而不是由一个中央点来控制。
万维网就是采用了这种工作方式，因此对程序员而言，这种模型应该不会太陌生。
（结点）数量将数据值尽可能均匀地分散到硬件存储设备中。
如果结点数改变了，那么系统会重新分布这些数据。
由于采用逻辑地址代替了人们在传统索引模型中使用的物理地址，因此用户根本不会看到这些过程。
故障结点会对其数据进行重新定位，并将自身从系统中删除。
新结点则会从现有结点将数据传送到其本地存储区，刀片服务器上使用了一种建立在内存中的模型。
这里没有索引；
数据都是尽可能多地保存在主存储器中，并在这里进行扫描。
3.2基于列的存储
基于列的访问存在的缺点是载入速度通常比较慢，因为源数据在外部来源中是以行或者记录的形式表示的。
这样做的优点是针对某个列中的值进行简单查询的速度非常快，需要的内部存储资源最少。
这表示对某个列中特定值的搜索可以直接进入该列的存储区，而不需要扫描整行的数据。
这样也使得数据压缩变得更容易，因为一个列中的数据通常具有相同的数据类型。
这种体系结构在处理数据仓库使用的海量数据时没有问题，但不适合需要进行大量以行的方式进行访问和更新操作的联机事物处理。
就是这种数据库之一。
在由一万亿行组成的测试数据集中，输入数据共很明显，这是一种适合数据仓库的技术。
这种技术虽然在压缩和快速访问方面有优势，但也存在插入操作复杂的缺点。
引擎也采用了一种基于列的处理方式，但是它还对值进行标记，以获得更高的速度和更好的数据压缩效果。
它们使用一种专用的位向量方案，可以在压缩的状态下进行搜索。
这种技术非常适合档案处理，但是必须将标记恢复成其原始数据值才能显示，以及在表达式内使用。
不过，在压缩方面鼓励将一个数据列分解成更多更详细的列。
四、列存储数据查询中的连接策略选择方法
4.1引言
随着计算机技术的快速发展以及数据库系统的深入研究和广泛应用,人们在期望获得巨大
数据存储容量的同时,对数据的检索效率,尤其是即席查询和决策分析提出了更高的要求。
列存储系统将同一列数据连续存储,能避免在查询中访问无关列带来的性能损失,使查询操作更有效率,迅速成为数据库领域的研究热点。
不少列存储系统如C-Store[1]、Sybase[2]、MonetDB[3]等,都证实了列存储技术在读优先系统上的优越性。
同时研究也发现,列存储查询虽然可以避免操作无关列,但还需连接相关列并将其组织成记录返回给用户。
查询相关的列越多,列之间的连接操作就越复杂。
面对海量的复杂查询,如何使列存储技术扬长避短,充分利用其查询优势,成为了当今列存储领域的研究重点。
查询优化在数据库领域一直占有重要的地位。
现有的列存储系统通过在存储上做改进来减少查询中的连接开销,如C-Store的“投影（projection）”技术[4−5]将属于同表的几列存储在一起;
MonetDB的“饼干图（crackermap）”[6]技术在查询时建立相关列的映射关系;
PAX[7−8]将同一元组的属性存储在一个磁盘页上,以此来加速同表之间的列连接。
可以看出,列存储技术虽然在存储方面已有很多研究成果,在查询处理层的优化研究还相当少。
这是由于列存储的处理对象缩小到“列”,使得候选查询计划集合规模增大,从而增加了查询优化本身的代价,影响查询的性能。
然而对连接用单一的处理方式,也无法达到查询执行的最优效果。
针对上述问题,本文提出一种连接策略选择方法,首先通过简单规则重写查询,排除代价过大的计划,生成候选计划树。
进而提出动态优化树算法,修改候选计划树中节点的执行顺序,得到可被转化为最优计划的查询树。
根据列存储的特点,查询树中连接节点的连接策略可归纳为两种：
串行连接与并行连接。
在此基础上构建代价估计模型进行代价估计和策略选择,不仅有效减少了代价估计的开销,也增加了列存储查询处理的灵活性。
经分析,本文提出的连接策略选择方法能有效优化查询,使得查询效率显著提高。
4.2相关工作
列存储的概念可以追溯到20世纪70年代,1976年加拿大统计局开发实现了列存储数据库
管理系统RAPID[9],并在80年代广泛应用。
随着企业对分析型查询需求的快速增长,对列存储的研究在近十年得到了提升。
早期的列存储模型有分解存储模型（DSM）[10]、PAX等。
新的列存储系统包括MonetDB/X100[11]、C-Store等。
研究表明,列存储数据库系统在分析型业务中的性能比行存储数据库系统性能超出多个数量级[5]。
查询优化在数据库领域占有重要地位。
目前较为成熟的优化方法有两类：
基于规则的优化方法（rulebasedoptimization,RBO）以及基于代价的优化方法（costbasedoptimization,CBO）[12−14]。
基于规则的优化方法根据指定的规则或定义路径的优先级对逻辑计划进行优化。
基于代价的优化方法通过统计信息和存取路径评估所有候选计划的代价,选择代价最小的一个。
通常优化器选择结合这两种方法来进行优化[14]。
然而,在列存储系统中的优化却相当少,目前的列存储查询处理,都将重点放在物理存储的改变上,没有统一的规则或代价的权衡。
C-Store是开源列存储系统,它将每列单独存储,多列保存在一个投影（projection）中,按照其中一列排序[1,4−5]。
因此C-Store查询经常基于一个投影,或者含有公共排序列的不同投影,以此减少列的连接代价。
连接操作首先根据对排序列的筛选,得到position列表并用它过滤其他列。
因此需要通过索引检索position的第一个值来定位其他列的起始查找位置[4]。
position是基于排序列的,若执行的谓词列在任何投影中都没有排序,则需对其进行全列扫描,这样代价很大。
MonetDB以（key,value）形式存储数据,利用“饼干图（crackermap）”来连接列。
在多选择列之间,选择某一列作为基列（左列）,跟其他相关列两两绑定在一起。
根据左列的筛选条件进行分区,并建立该分区的索引,重新存储为M（crackermap）。
由于基列一样,使用位图向量之间的位与来连接列[6]。
此方法在第一次查询的时候需要消耗大量的内存,对列进行范围的划分以及索引的建立。
在以后的查询中,如果基于该列的谓词发生变化,需重新划分范围并修改索引。
该方法内存消耗巨大,仅适用于内存数据库MonetDB,却无法在列存储系统上通用。
上述两个系统,C-Store的查询执行器相当完善,但是查询优化器却未实现[4]。
MonetDB的查询处理中,执行计划并不通过代价模型评估,仅是通过启发式规则来重写计划[15]。
可见现有的列存储系统连接策略单一且局限,在查询优化方向的研究非常少。
本文结合简单规则和动态Huffman算法,建立基于代价的连接策略选择模型,针对不同情况处理列之间的连接。
4.3定义
定义1（空间）列存储数据的查询处理对象为列,属于一张表的列属于同一个空间。
定义2（rowid）为了重组一行数据,每一列都附加一个伪列rowid,形如<
rowid,value>
如图
1．每一列在rowid上都存在B树索引。
定义3（连接）同空间内由and连接的两个操作、两个列的比较操作称为同空间列的连接;
不同空间两列间的操作称为不同空间列的连接。
定义4（串行连接）一个连接操作的对象有两个孩子操作,用一个操作的结果通过连接条件去过滤另一个操作的方法称为串行连接,如图2。
定义5（并行连接）先分别执行两个相关操作,再通过连接条件得到结果的方法称为并行连接,如图3。
定义6（驱动列）连接操作中,两个处理对象中较少行数的列为驱动列。
它可以是原始数据,
李静等：
列存储数据查询中的连接策略选择方法853也可以是中间结果中的列。
定义7（被探测列）当从驱动列得到了一项数据以后,在该探测列中查找符合条件的数据。
对于SQL：
selectmfromA,BwhereA.m=B.n其中m为驱动列,则连接策略如图2和图3。
4.4连接策略选择方法
本文重点研究如下形式的查询：
selectAfromTwhereΛ（P1,P2,...,Pm）
（1）
T是查询引用的关系集合;
A是引用关系T的属性集;
（P1,P2,...,Pm）是由and连接的谓词。
对于列存储而言,该查询可转化为如下形式：
Ci是查询相关的列,如果Ck上不存在选择谓词,设σ（Ck）为true。
Fij是连接条件,如果Ci、Cj上不存在连接谓词,设Fij为true。
对于n个节点的查询树来说,列之间连接方法有
种。
基于代价的优化连接策略就是从中选择一个I/O最小的计划,然而数据按列存储后,n往往很大,这使得从中选择一个理想计划十分困难,因此需要首先根据简单的规则削减计划的选择范围。
4.4.1简单下推规则
根据启发式原理：
由于关系越小,所需读写的I/O也就越少,因此中间结果之和较小的计划
很可能是较好的计划[12]。
本文根据关系代数表达式的下推规则来执行不同空间的谓词下推;
并使用列的级联规则合并同列选择谓词[12];
最后处理列间的连接谓词。
通过以上规则得出式
（2）中where子句的形式：
定义选择空间T,连接空间J：
查询计划如图4,用于连接的左深树能和连接算法很好地交互,有利于形成有效的计划[12]。
4.4.2动态优化树
对左深连接树而言,应该选用估计数值较小的节点作为左变元[12]。
本文结合动态Huffman
树[16]思想提出动态优化树算法,改进查询执行顺序,保证执行该树的代价尽可能最小,如图5。
（1）利用动态Huffman树原理修改空间之间的连接顺序。
设Tout为每个空间根节点的输出元组数,查询计划中的选择空间根节点Ti∈{T1,T2,…,Tn}的权值为Tiout。
若存在某空间与多空间连接,将该空间作为最左空间,根据动态Huffman树原理修改该空间与其他空间的连接顺序。
若不存在这样的空间,则修改所有空间的连接顺序。
（2）利用动态Huffman树原理,修改空间内的连接顺序。
优先处理选择性较好的谓词可以尽早减少需处理的元组数目,从而避免I/O的浪费[12]。
设
C.ff
升级会员 