排序合并Join算法的新结果

Ｊｏｉｎ操作是数据库中最昂贵和最常用的操作．排序合并Ｊｏｉｎ算法是实现Ｊｏｉｎ操作的重要算法，得到了普遍接受并广为应用．在重新研究了排序合并Ｊｏｉｎ算法后发现，同时对两个Ｊｏｉｎ关系进行外排序是不必要的，会带来很大的额外开销．针对这个问题，提出了一种基于单关系外排序的分治Ｊｏｉｎ算法，并在该算法的基础上提出了基于单关系外排序的并行分治Ｊｏｉｎ算法．理论和实验结果证明，基于单关系排序的分治Ｊｏｉｎ算法高于排序合并Ｊｏｉｎ算法．特别是在并行计算环境下，基于单关系排序的并行分治Ｊｏｉｎ算法的效率远远高于排序合并Ｊｏｉｎ算法的并行版本．

并行数据库上的并行CMD-Join算法

并行数据库在多处理机之间的分布方法（简称数据分布方法）对并行数据操作算法的性能影响很大．如果在设计并行数据操作算法时充分利用数据分布方法的特点，可以得到十分有效的并行算法．本文研究如何充分利用数据分布方法的特点，设计并行数据操作算法的问题，提出了基于ＣＭＤ多维数据分布方法的并行ＣＭＤ－Ｊｏｉｎ算法．理论分析和实验结果表明。

基于并行B^+-树的并行Join算法的设计、分析与实现

B＋-树是一种有效的数据库存储结构，被普遍应用于各种关系数据库系统．把B＋-树并行化，使之用于并行数据库系统显然是一项很有意义的重要工作．本文研究了适用于并行数据库的并行B＋-树存储结构，提出两类基于并行B＋-树的并行Join算法．理论和实验结果表明，这些算法效率高于其它并行Join算法．

一个基于Semijoin的并行join算法SBABJ

本文在并行ｊｏｉｎ算法ＡＢＪ＋的基础上提出了一个基于Ｓｅｍｉｊｏｉｎ的改进算法ＳＢＡＢＪ＋。我们在多台Ｓｕｎ工作站上实现了该算法，并对ＡＢＪ十和ＳＢＡＢＪ十进行了性能测试。算法分析和实验结果表明了并行ｊｏｉｎ算法ＳＢＡＢＪ＋优于ＡＢＪ＋算法。

并行数据库中JOIN运算的并行算法

JOIN运算的并行算法一直是并行数据库领域中研究的热点问题,先后出现了一系列并行JOIN算法或改进算法,但它们都存在着通信效率较低、负载调度频繁等问题。本文针对这些问题,在分析比较前人工作的基础上对SABJ+算法与ABJ+算法加以改进,得到了效率更高的并行JOIN算法ABJ++。

同构环境中Join任务图的一个调度算法

任务调度问题是一个NP完全问题。Join结构是一种并行处理的基本结构,虽然许多算法对Join任务图能产生最优调度,但大多都忽略了节省处理机个数和最小化程序总的完成时间等问题。因此,专门针对Join任务图,提出一个能产生最优调度的同构贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为O(v2),其中,v表示任务集中任务的个数。实验结果表明,相比其他算法,该算法具有较短的调度长度、较短的完成时间,使用的处理机数较少。

调度Fork-Join任务图的贪心算法

任务调度算法的目标是把组成并行程序的一组任务分配到多个处理器以使得程序的完成时间最短,这是一个NP完全问题。虽然许多算法在任务满足某些条件时能产生最优调度,但大多都忽略了节省处理器个数和最小化程序总的完成时间等问题。Fork-Join结构是一种并行处理的基本结构。因此,专门针对Fork-Join任务图,提出了一个能产生最优调度的新的贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为2,其中,表示任务集中任务的个数。实验结果表明,相比其它算法,该算法具有较短的调度长度、较短的完成时间,使用的处理器数较少。

基于HRR划分的并行RDB^n树Join算法

文章首先介绍了PDBMS采用的Hash-Round-Robin(HRR)数据划分方法以及基于该划分方法的并行RDBn树,最后着重、详细地给出了基于该树的并行Join算法,分析了该算法的效率。

一个机群环境下抗数据偏斜的JOIN算法

提出了一种计算机机群环境下JOIN算法,防止数据偏斜对机群执行效率的影响.给出了数据分布树的形式化定义,构造了基于数据分布树的数据均衡分布机制、抗数据偏斜的JOIN算法.分析和实验表明,该算法适合于海量数据查询并能有效地解决机群并行环境下数据偏斜所造成的查询性能低下的问题.

并行JOIN算法的优化子集合调整方法

子集合调整是克服数据偏斜影响的并行ＨＡＳＨ－ＪＯＩＮ算法的关键组成部分，现有的克服数据偏斜影响的ＨＡＳＨ－ＪＯＩＮ算法都没有很好地解决这个问题。作者深入地研究了子集合调整问题，提出了四种子集合调整算法。理论分析和实验结果都证明，这四种算法都能够很好地解决子集合调整问题，特别是启发式优化算法ＯＰ－ＡＤＪＵＳＴ在多数情况下都能给出优化解。

广义Fork-Join任务图的调度问题研究

Fork-Join结构是一种并行处理的基本结构。为处理传统方法难以解决的复杂和非线性问题,缩短整个程序的总完成时间,针对广义Fork-Join任务图提出了基于遗传算法的调度算法,该算法将遗传算法和任务复制相结合,有效地缩短了得到最优结果的时间。实验结果表明,与其他算法相比,该算法具有较短的调度长度。

一种改进的并行连接算法Diag-Join及其性能分析

介绍了一种改进的并行连接算法:Diag-Join算法,并将它运用到并行环境中。实验表明,Diag-Join算法在内存足够时可以取得最好的性能,即使在内存较小的情况下,仍能得到令人满意的效果。

计算机机群并行环境下的并行非等值JOIN算法

研究在计算机机群环境下并行非等值ＪＯＩＮ算法的设计与实现问题，提出了两个相关的算法和实现的具体技术，实验结果表明，这些算法都是实用和有效的。

异构环境中Fork-Join任务图的调度算法

目前已有的Fork-Join任务图的调度算法大多假定处理机为同构的,而没有考虑实际应用中处理机的异构性以及节省处理机的问题,导致算法在具体应用中效率较低。因此,对Fork-Join任务图的调度问题进行研究,提出了一个基于异构环境的贪心调度算法,该算法具有高的加速比和总体效率,其时间复杂度为2,其中,表示任务集中任务的个数。实验结果表明,相比其它算法,该算法具有较短的调度长度、较短的完成时间,使用的处理机数较少,具有更强的实用性。

DBCC-Join:一种新的高速缓存敏感的磁盘连接算法

随着CPU和内存的性能差距越来越大,系统设计者在CPU寄存器和内存之间插入高速缓存来弥补这个差距.高速缓存的数据存取速度远高于内存,所以数据库操作要获得更好的性能就必须考虑充分利用高速缓存.基于磁盘的连接操作是一种常用并且耗时的数据库查询操作,可是大多数传统的连接算法在设计时都没有考虑高速缓存的使用,从而使得这些连接算法无法充分利用CPU的能力.文中分析了传统的连接算法在高速缓存利用方面的问题,并且提出了一种新的可以充分利用高速缓存的磁盘连接算法DBCC-Join.连接位置索引对表JPIPT是用到的数据结构,说明了每个连接结果元组在各自表中的位置索引对.DBCC-Join的执行包括两个阶段:JPIPT构建阶段和结果输出阶段.JPIPT构建阶段对列存储化的连接属性执行高速缓存敏感的算法来构建连接位置索引对表.利用获得的JPIPT,结果输出阶段只需要对数据表执行一遍顺序扫描就可以获得结果.该文是第一篇提出利用高速缓存的磁盘连接算法的文章.实验表明,和传统磁盘连接算法相比,DBCC-Join算法可以获得一个数量级的加速比.

降序加权join半概念格快速挖掘算法

通过分析Eclat算法,对完全概念格按照支持度进行了裁减,得到了一个向下封闭的降序join半概念格,在构造半概念格的同时计算出每一个项集的支持度作为其权值,最后基于降序加权join半概念格对Eclat算法进行了改进,裁减了概念格中大量的冗余的连接,给出了一个快速的关联规则挖掘算法。经过分析,该算法与Eclat算法相比,效率更高。

基于Fermi架构的Join算法

在列数据库中,连接操作依然是最核心和最耗时的操作,GPU强大的计算能力可为此提供新的优化手段。基于Fermi架构,提出了新的Hash Join算法和Sort-merge Join算法,其基本思想是充分利用该架构新增的缓存结构来减少连接操作的cache缺失率。与CUDA stream技术相结合,新算法在输出结果较多时可以有效地隐藏主存与显存间数据传输带来的延迟,进一步提升其执行效率。实验结果证实了基于Fermi架构的Hash Join算法处理偏斜数据的高效性及Sort-merge Join算法的稳定性,并且通过比较表明,这两种算法的性能全面优于基于多核CPU充分优化的Join算法,最大加速2.4倍,在外键分布高偏斜时新的Hash Join算法的执行速度甚至达到每秒217M元组。

一种改进的闪存数据库Sort-Merge-Join算法

在对传统的Sort-Merge-Join算法进一步研究的基础上,提出了一种改进的闪存数据库Sort-Merge-Join算法。该算法只对小关系进行外排序,避免了大关系的外排序,节省了大量时间,同时最小化了中间临时表,达到了少写闪存、减小擦除代价的目的。通过理论分析和与传统Sort-Merge-Join算法在闪存上的比较实验,证明了该算法的优越性。

一种关系式JOIN算法的研究与实践

关系式数据库管理系统中经常使用Join运算,因其常常耗费系统的大量资源,是研究关系式运算及其性能方面的聚焦点之一[1～4]。通过分析Merge-Join算法[4,7,8]和SDC算法[1],提出一种在处理速度上更快的Join算法,并在算法复杂性和处理性能上进行了比较,结果表明所给出的Join算法能够使Join性能明显改进。

CPU和DRAM加速任务划分方法:大数据处理中Hash Joins的加速实例

硬件加速器能够有效地提高当前计算机系统的能效.然而,传统的硬件加速器(如GPU,FPGA和定制的加速器)和内存是相互分离的,加速器和内存之间的数据移动难以避免,这使得如何降低加速器和内存之间数据移动的开销成为极具挑战性的问题.随着靠近数据的处理技术(near-dataprocessing)和3D堆叠DRAM的出现,我们能够将硬件加速器集成到3D堆叠DRAM中,使得数据移动的开销大大降低.然而,由于3D堆叠DRAM对面积、功耗和散热具有严格的限制,所以不可能将一个功能复杂的硬件加速器完整地集成到DRAM中.因此,在设计内存端的硬件加速器时,应该考虑将加速任务在CPU和加速器之间合理地进行划分.以加速大数据系统中的一个关键操作hash joins为例子,阐述了CPU和内存端加速任务划分的设计思想.以减少数据移动为出发点,设计了一个包含内存端定制加速器和处理器端SIMD加速单元的混合加速系统,并对应用进行分析,将加速任务划分到不同的加速器.其中,内存端的加速器用于加速数据移动受限的执行阶段,而处理器端SIMD加速单元则用于加速数据移动开销较低成本的执行阶段.实验结果表明:与英特尔的Haswell处理器和Xeon Phi相比,设计的混合加速系统的能效分别提升了47.52倍和19.81倍.此外,提出的以数据移动为驱动的方法很容易扩展于指导其他应用的加速设计.