列存储系统面向列的连接顺序优化研究

连接操作是影响列存储数据查询效率的重要操作之一,对于列存储系统中的连接操作优化,以往的研究工作大多专注于对数据组织结构的优化以及辅助物理结构的建立上,极少涉及逻辑层特别是早期的连接策略优化.为此,根据列存储数据的特点和分析型查询需求的特征,提出了一种新的列存储连接优化方法.该方法采用提早优化的策略,使用“事实表下推”的优化规则,并在多事实表查询条件下引入浓密树进行连接顺序决策,以较小的时空复杂度获得“最优”的连接执行顺序.使用代价估计模型对提出的连接策略优化方法进行了理论验证.同时,在大规模数据仓库基准数据集SSB上通过实验验证了提旱优化机制及下推规则的有效性.     

以目标节点为导向的XML路径查询处理

XML查询语言将复杂路径表达式作为核心内容.为了加速路径表达式处理,基于路径分解和结构连接操作的处理策略需要更深入的研究.以目标节点为导向的XML路径查询处理框架被提了出来.该方法利用了扩展基本操作来减少连接操作的数目.在路径分解和查询计划选择的过程中,利用查询树中的目标节点来避免中间结果的传递.除了分解规则和策略以外,提出了一组扩展的基本操作和实现算法.初步的实验结果显示,该方法具有良好的性能.它为路径查询处理提供了更多的选择.     

一个基于三元组存储的列式OLAP查询执行引擎

大数据与传统的数据仓库技术相结合产生了大数据实时分析处理需要（volume+velocity）,它要求大数据背景下的数据仓库不能过多地依赖物化、索引等高存储代价的优化技术,而要提高实时处理能力来应对大数据分析中数据量大、查询分析复杂等特点.这些查询分析操作一般表现为在事实表和维表之间连接操作的基础上对结果集上进行分组聚集等操作.因此,表连接和分组聚集操作是ROLAP（relational OLAP）性能的两个重要决定因素.研究了新硬件平台下针对大规模数据的OLAP查询的性能,设计新的列存储OLAP查询执行引擎CDDTA-MMDB（columnar direct dimensional tuple access-main memory databasequeryexecutionengine,直接维表元组访问的内存数据库查询执行引擎）.基于三元组的物化策略,使得CDDTA-MMDB能够减少内存列存储模型上表连接操作访问基表和中间数据结构的次数.首先,CDDTA-MMDB将查询分解为作用在维表和事实表上的子查询,如果只涉及过滤操作,子查询将生成<代理键,布尔值>二元组;否则,子查询生成<代理键,关键字,值>三元组.然后,只需一趟扫描事实表,利用事实表的外键映射函数直接定位相应三元组或者二元组,完成相应的过滤、连接或聚集操作.CDDTA-MMDB充分考虑了内存列存储数据库的设计原则,尽量减少随机内存访问.实验结果表明：CDDTA-MMDB是高效的,与具代表性的列存储数据库相比,比MonetDB 5.5快2.5倍,比C-store的invisible join快5倍;并且,CDDTA-MMDB在多核处理器上具有线性加速比.     

列存储数据查询中的连接策略选择方法

列的连接策略优化是列存储数据查询中的重要问题。现有的列存储系统中,列的连接存在策略单一,缺少优化处理,无法满足复杂查询等缺陷。针对这些问题,提出一种连接策略选择方法。该方法首先定义简单规则过滤代价过大的查询计划,生成候选查询计划树。进而根据动态Huffman树原理提出动态优化树算法,对候选查询计划树中的查询执行顺序进行改进。根据列存储数据的特点,候选计划中每个连接节点的执行策略被归纳为两种:串行连接和并行连接。在此基础上构建代价估计模型,集中针对这两种连接策略进行代价估计和策略选择,从而以较小的时间复杂度获得优化的查询执行策略。     

RB+树——一种列存储数据的树型索引结构

索引技术是提高海量数据查询效率的关键技术之一.传统索引如B+树等在更新事务环境中具有较好的性能,然而在面向列存储的分析型数据仓库查询环境下,时间空间代价较大.根据列存储数据仓库查询环境的特点,提出一种新型树型索引--RB+树(reduced B+-tree).该索引对传统B+树结构进行了改进,并结合自底向上创建索引树的方法,使得索引的空间利用率、创建和查找效率得到显著的提高.进一步将RB+树应用于列存储数据仓库中,建立了行号索引、列值索引,特别地为解决星型模型中多表连接问题提出连接索引,有效地提高了列存储数据仓库中元组重构与多表连接的效率.在数据仓库基准数据集SSB上的实验验证了方法的有效性.     

列存储数据查询中的连接策略优化方法

列存储数据查询优化的重点是列的连接策略.现有的列存储系统通过存储的改变来简化列的连接,致使列的连接缺少查询优化处理,策略单一且无法满足复杂查询.在剖析现有连接选择策略的基础上,提出一种新的连接策略优化方法,即首先利用基于规则的优化方法为列存储数据查询制定优化规则,过滤不可能产生最优计划的候选计划;然后设计了基于代价的优化算法,根据动态Huffman树和左深连接树原理对查询执行顺序进行改进,进一步减少候选计划的规模;根据列存储数据的特点将候选计划中每个连接节点的执行策略归纳为串行连接和并行连接两类,并在此基础上提出代价估计模型,进而可针对这两种连接策略进行代价估计和策略选择.最后在SSB数据集上通过实验证明了方法在列存储数据查询中的有效性.     

一种对象代理数据库的跨类查询优化方法

对象代理数据库中跨类查询可以充分发挥对象代理模型的灵活性,为用户提供个性化数据服务,其执行效率十分重要。然而在处理多个跨类属性查询时,现有基于路径表达式的跨类查询实现存在对公共路径节点对象进行重复获取的情形,执行效率较低。针对跨类查询中加快获取终点对象的问题,优化核心思想是减少对路径上节点对象的重复与不必要的遍历,包括两个关键策略:首先是将路径节点整体作为虚拟路径视图统一获取节点对象,避免了多跨类属性查询下公共路径节点的冗余遍历;其次是针对路径复杂过长的跨类查询,依据代价估计策略选择物化查询涉及起点与终点对象,利用缓存减少执行时路径上中间节点的遍历。分别在属性数目与结果集规模两方面进行了对比实验,实验结果表明了优化方法的有效性。     

对查询优化重写QRA算法的一种改进

数据仓库系统中利用物化视图可以提高查询效率,但是,过分使用物化视图重写查询有时不一定能起到提高查询性能这一预期目的.针对QRA算法的不足并结合左深度处理树技术提出一种改进算法,通过实验结果表明由改进算法优化后查询的性能更优.     

基于遗传算法的物化视图优化方法

物化视图是提高数据仓库执行效率的有力方法,但是物化视图的保存会占用存储空间。本文把查询需要扫描的物化视图或事实表的空间大小作为查询时间开销,以查询的时间开销和物化视图的存储开销作为衡量标准建立代价估算模型,设计基于遗传算法的物化视图优化算法。目的是使系统在物化视图方面的存储开销和查询时间开销的和最小。试验结果表明算法可行。     

基于分布式文件系统的MPP数据库扫描调度研究

基于分布式文件系统的MPP（大规模并行处理）数据库是目前的研究热点,为改善其执行查询扫描操作前调度执行单元读取数据块的过程,提出一种基于节点负载的调度策略NLS。这种策略同时结合数据本地性和节点负载,通过本地读分配保证调度结果满足良好的数据本地性,基于节点的实时工作负载对中间调度结果进行重分配调整,以达到减少数据扫描操作完成时间的目标。实验结果表明,相比连续性调度策略FCS,NLS在保持90%以上数据本地性的同时,在完成时间上的优化最多达到32%,在测试的9种情况中平均优化25%。