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

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

基于列存储的MapReduce分布式Hash连接算法

大数据具有规模大、深度大、宽度大、处理时间短、硬件系统普通化、软件系统开源化的特点。传统关系型数据库在对大数据进行操作时存在系统性能严重下降、计算效率提升有限以及可扩展性差等问题,因此引入MapReduce并行计算模型,提出一种大数据上基于列存储的MapReduce分布式Hash连接算法。首先,设计面向大数据的分布式计算模型,在设计的分片聚集并行连接的基础上,利用Hash连接以及动态探测方法优化了数据并行连接处理效率;然后,针对该算法开发了基于Hadoop的原型系统。通过实验证明,在大数据分析处理中,所提算法在执行时间和负载能力上都有很好的性能表现,也能提供良好的可扩展性。

基于DSVM的并行Hash连接算法及其性能评价

提出了一个基于分布式共享虚拟存储器技术（ＤＳＶＭ）的并行Ｈａｓｈ 连接算法，然后设计了一个并行连接算法的测试评价基准，并评价和分析了该算法在均匀数据分布情况下３ 种不同负载的性能比较和Ｚｉｐｆ倾斜数据分布情况下两种调度策略的算法性能．

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

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

基于丛生树的多流水线并行Hash连接的处理机分配算法

本文介绍了并行数据库中实现多流水线Ｈａｓｈ连接的处理机分配算法。

阵列众核结构上的一种多层分区Hash连接算法

连接是数据查询处理中最耗时、使用最频繁的操作之一,对提高连接操作的速率具有重要意义。阵列众核处理器是一类重要的众核处理器,具有强大的并行能力,可用来加速并行计算。基于阵列众核处理器的结构,设计和优化了一种高效的多层分区Hash连接算法。该算法通过多层划分的策略大大降低了主存访问次数,通过分区重排方法有效消除了数据倾斜的影响,获得了很高的性能。在异构融合阵列众核处理器DFMC(Deeply-Fused Many Core)原型系统上的实验结果表明,DFMC上多层分区Hash连接算法的性能是CPU-GPU耦合结构上最快的连接算法的8.0倍,表明利用阵列众核处理器加速数据查询应用具有优势。

抗数据偏斜的高效并行join运算算法研究

通过分析ABJ＋算法和Hybrid hash join算法，并对两个算法进行了结合和改进，提出了一种能克服各种数据偏斜的并行二元连接运算算法，可在不同的数据偏斜情况下启动不同的模块，克服数据偏斜造成的负载不平衡现象。

一种利用固态盘特性的散列连接改进算法

随着新一代存储设备固态盘的发展,如何发挥新存储设施的性能成为近年来的一个研究热点.将固态盘作为"黑盒",通过观察固态盘I/O外部特性,即考察访问粒度与访问队列深度与固态盘性能之间的关系,得出算法设计应遵循的原则,并应用到数据库散列连接算法的设计中.提出了并行化Grace散列连接设计方法,以及根据访问粒度、队列深度计算各阶段缓冲区大小的优化分配方法.一系列实验结果表明本文提出的并行散列连接方法能够充分发挥固态盘性能,优化的缓存分配方案可保证固态盘性能充分发挥而不浪费内存资源.

基于DSVM和消息传递的并行哈希连接算法的性能分析

基于分布式共享虚拟存储器（ＤＳＶＭ） 的软件设计方法是运行在网络工作站（ＮＯＷ） 上的支持并行计算与分布处理的新途径，它与传统的消息传递的编程方法不同·描述了在面向对象的分布式数据库系统ＳｈｕｓｓｅＵｏ 上，用ＤＳＶＭ 和消息传递两种方式分别实现并行哈希连接操作的３种算法；设计了测试数据库和３ 种不同的负载；并分析了ＤＳＶＭ 和消息传递这两种设计方法的性能·大量的测试结果表明，基于ＤＳＶＭ 的算法的性能比传统的消息传递的算法稍差，但ＤＳＶＭ 具有易编程等优点，因此在并行处理上仍是一项很有研究和开发价值的技术·

抗偏斜的并行二元连接算法研究

在分析了数据偏斜特点的基础上，提出了一种抗静态和动态数据偏斜的ＨｙｂｒｉｄＳｋｅｗ算法以及代价分析模型．应用本模型对ＨｙｂｒｉｄＳｋｅｗ算法进行分析，结果表明，本算法在网络传输率和磁盘传输率较低的系统和半连接选择率较小、有偏斜的情况下。

并行数据库系统PAROII连接算法

介绍PAROII采用的哈希轮转 (Hash -Round -Robin)数据划分方法以及基于该划分方法的并行RDBn树 ,着重、详细地讨论了基于该树的并行连接算法 ,该算法充分利用了数据的已有分布、Bn 树的特性、叶结合点有序连接、哈希轮转划分的特性 ,这些特性减少了系统的额外消耗 。

无共享多处理机系统的并行连接算法

在并行数据库中,各种关系操作,特别是连接(Join)操作的并行化一直是一个研究热点。一般认为,无共享(Shared-Nothing)结构是最适于超大规模并行数据库的并行体系结构。因此,本文主要介绍2种基于无共享多处理机系统的并行连接算法,对它们的性能作了比较,并指出在该领域仍存在的一些主要问题。

基于Spark的高维K近邻连接算法

为解决数据量日益增长和数据维度不断增高,通过单机运行K近邻连接算法得出结果时间过长无法满足时效要求的问题,提出一种基于Spark的使用位置敏感哈希函数对数据预处理后再进行查询的算法。利用位置敏感哈希函数对训练集数据降维并进行分桶索引,进行近邻查找,有效利用Spark基于内存的高性能并行计算能力。实验结果表明,该算法对高维大数据具有较高的准确性和查询效率。