二次分级连接排序算法

近年来,人们提出了不少排序运算量为O(N)的新算法。但对这些算法分析研究的结果表明,普遍存在着以下两点不足:(1)附加空间开销大;(2)排序效率过分依赖于键值的均匀分布。对此,本文提出了一个新的排序算法——二次分级连接排序法。该方法保证排序时间在最坏情况下为O(N)的基础上,仅需附加空间开销N+(ΔM)^(1/2)+2。这里,ΔM为键值的变化范围。

面向DRAM和NVM异构混合内存架构的排序连接算法优化

随着计算机技术的高速发展,数据的应用规模也在不断扩大,各行各业对于数据存取速度的要求也越来越高。为了满足这种需求,内存数据库的思想被提出,然而传统的内存存储器DRAM由于密度和能耗的限制无法大规模集成和扩展。与此同时,非易失内存(NVM)以其性能高、密度高、能耗低的优势弥补了DRAM的不足。DRAM和NVM结合在一起组成的混合内存系统能够发挥出更高的性能和更强的扩展能力,同时也更加经济高效。在这种新的混合内存架构下,传统的算法面临着巨大的挑战,因为它们必须要对新的架构进行优化。故从数据库系统常用的排序连接算法出发,探索其在混合内存系统上的更优使用方式,提出了键值分离的排序连接算法,并在此基础上提出了3种不同的C-Join算法。实验结果表明,提出的方案达到了预期的目标,不仅减少了DRAM的使用,同时也提高了算法的时间性能。

分布式数据库下基于剪枝的并行合并连接策略

排序合并连接是数据库系统一种重要的连接实现方式,比哈希连接有更广泛的应用.分布式环境下,数据分片、分布存储,面对昂贵的网络代价,进行高效排序合并连接的挑战巨大.传统策略首先针对连接数据进行排序,然后基于排好序的数据执行合并连接.这两部分操作均基于原始数据进行操作,通常情况下,原始连接数据存在无用数据块,这些数据块无需连接,但会增加额外开销,包括网络开销.随着数据量的增多,出现无用数据块的概率增大,额外开销随之增多.传统策略没有预先处理这些无用数据块.针对这个问题,提出一种分布式环境下基于剪枝的并行排序合并连接策略(parallel sort-merge join based on prune,简称Pr_PSMJ).其特点是,连接发生之前高效完成对连接对象无用数据块的剪枝处理,提高整体连接效率.基本思想是,根据连接对象对应的连接分区数据统计信息,构造一种双边邻接表(bilateral adjacency list,简称BAL),用来对连接数据中无用数据块进行剪枝,并保证最终连接结果的正确性;剪枝完成后,利用BAL计算出各个最佳本地连接执行点,并指导分区数据的迁移,使数据移动量最小;在连接阶段,由于BAL保证本地连接执行节点的独立性,因此能够轻松并行执行整个连接过程,并在每个连接点本地利用多核环境完成局部并行排序合并连接;最后,将局部结果合并成最终结果.由于Pr_PSMJ中的高效剪枝策略是在连接执行之前完成的,因此几乎适合任何合并连接操作,并且对于其他连接策略也有借鉴作用.给出了基于Pr_PSMJ的算法的正确性、效率性以及适应性分析,并且给出实验验证,证明了在分布式大数据量排序合并连接情况下,Pr_PSMJ相对于其他策略能够有效减少网络开销,并提高连接效率.

集成CPU-GPU架构上的列存储连接优化技术研究

集成多核CPU-GPU架构已经成为计算机处理器芯片的发展方向。利用这种架构的并行计算能力进行数据处理已经成为了数据库领域的研究热点。为了提高列存储系统的查询性能,首先改进了已有协处理机制中的负载分配策略,通过监测数据库系统CPU占用率,动态地为处理器提供合理的数据划分;然后,针对集成多核CPU-GPU架构上的数据预取机制,提出了一种确定预取数据大小的模型,同时,针对GPU访存的特点,进行了GPU访存优化;最后,使用OpenCL作为编程语言,实现了一种集成多核CPU-GPU架构上的列存储排序归并连接算法,并采用提出的方法对连接处理进行优化。实验证明,所提优化策略可以使列存储系统排序归并连接性能提升33%。

基线与增量数据分离架构下的分布式连接算法

在大数据背景下,数据库系统表连接操作的效率急需优化,尤其对于基线与增量数据分离的数据库系统来说,其连接操作更是成为其性能的主要瓶颈.为了有效提升事务处理的性能,在基线与增量数据分离的数据库系统架构中,通常将基线数据存储于磁盘中,增量数据存储于内存中,进而获得较高的事务处理吞吐量和可扩展性.Hbase、BigTable、OceanBase等系统是典型的基线与增量数据分离的数据库管理系统,但是他们的表连接效率较低,其主要原因包括:每次表连接前必须先合并基线数据和增量数据;数据存储模式更为复杂,导致过大的网络开销.该文提出了一种基线与增量数据分离架构下的排序归并连接优化算法.该算法对连接属性做范围切分,在多个节点上并行做排序归并连接.该算法无需在连接前合并基线数据和增量数据,进而实现对基线和增量数据并行处理,同时也避免了大量非连接结果集数据的基线与增量合并操作.并在开源的数据库OceanBase上实现了该算法,通过一系列实验证明,该算法可以极大提高OceanBase数据库的表连接处理性能.

适应度二次选择的QPSO和SA协同搜索大规模离散优化算法

针对大规模离散工程优化问题,提出一种改进的离散量子粒子群优化算法(IDQPSO-SA)。首先,提出一种适应度的二次选择更新平均最优位置策略,使QPSO能够适用离散空间的优化问题。其次,引入二次切割与连接(DCJ)排序策略加速搜索进程。最后,在QPSO并行搜索基础上,引进模拟退火(SA)的概率突跳性,协同进行全局搜索。在大规模、高维离散工程优化问题上进行了测试,并同已有算法进行比较,结果表明,IDQPSO-SA进一步提高了面向大规模离散优化问题时的搜索效率,并有效提升了算法的性能。

数据库外基于多模型的学习式查询优化方法

对于AI与数据库优化问题,现有技术均须改动数据库底层,影响研究成果的应用且缺乏可扩展性.提出一种非嵌入数据库的学习式查询优化方法.在基数估计阶段,使用多模型的方法,对特定的子查询建立神经网络,独立训练不同的子模型,解决需要训练集过多且可扩展性差的问题;在连接优化阶段,应用基于代价的强化学习方法,提高查询优化性能.针对每个查询,从基数估计到连接排序的优化过程都在数据库外执行,按照得到的优化策略对查询重写,并将重写结果返回到数据库中,通过设置参数使该查询按照指定的计划执行.在包含8个表的数据集上进行实验验证,与未进行优化的查询进行比较,非嵌入数据库的优化方法具有良好的优化效果.