A parallel sort merge join algorithm for managing data skew

A parallel sort-merge-join algorithm which uses a divide-and-conquer approach to address the data skew problem is proposed. The proposed algorithm adds an extra, low-cost scheduling phase to the usual sort, transfer, and join phases. During the scheduling phase, a parallelizable optimization algorithm, using the output of the sort phase, attempts to balance the load across the multiple processors in the subsequent join phase. The algorithm naturally identifies the largest skew elements, and assigns each of them to an optimal number of processors. Assuming a Zipf-like distribution of data skew, the algorithm is demonstrated to achieve very good load balancing for the join phase, and is shown to be very robust relative, among other things, to the degree of data skew and the total number of processors     

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

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

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

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

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

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

Effectiveness of parallel joins

The effectiveness of parallel processing of relational join operations is examined. The skew in the distribution of join attribute values and the stochastic nature of the task processing times are identified as the major factors that can affect the effective exploitation of parallelism. Expressions for the execution time of parallel hash join and semijoin are derived and their effectiveness analyzed. When many small processors are used in the parallel architecture, the skew can result in some processors becoming sources of bottleneck while other processors are being underutilized. Even in the absence of skew, the variations in the processing times of the parallel tasks belonging to a query can lead to high task synchronization delay and impact the maximum speedup achievable through parallel execution. For example, when the task processing time on each processor is exponential with the same mean, the speedup is proportional to P/ln(P) where P is the number of processors. Other factors such as memory size, communication bandwidth, etc., can lead to even lower speedup. These are quantified using analytical models     

一种避免数据偏斜的动态Hash连接方法

本文提出了一种新的动态Hash连接方法──DHJ（dynamichash　join），以解决并行数据库连接操作中的数据偏斜现象.为避免目前某些算法提出的预处理中隐含的高额费用，该方法在划分阶段通过增添附加桶的方法来平衡输出，然后依据计算确认哪些附加桶被映射到处理器上并确定处理器分配，在最后阶段完成连接.本文最后给出了该算法的性能分析.     

Dynamic load balancing in multicomputer database systems usingpartition tuning

Shared nothing multiprocessor architecture is known to be more scalable to support very large databases. Compared to other join strategies, a hash-based join algorithm is particularly efficient and easily parallelized for this computation model. However, this hardware structure is very sensitive to the skew in tuple distribution. Unless the parallel hash join algorithm includes some dynamic load balancing mechanism, the skew effect can severely deteriorate the system performance. In this paper, we investigate this issue. In particular, three parallel hash join algorithms are presented. We implement a simulator to study the effectiveness of these schemes. The simulation model is validated by comparing the simulation results to those produced by the actual implementation of the algorithms running on a multiprocessor system. Our performance study indicates that a naive approach is not able to provide tangible savings. However, the carefully designed strategies can offer substantial improvement over conventional techniques for a wide range of skew conditions     

An Adaptive Parallel Distributive Join Algorithm on a Cluster of Workstations

In this paper, we present an adaptive version of the parallel Distributive Join (DJ) algorithm that we proposed in [5]. The adaptive parallel DJ algorithm can handle the data skew in operand relations efficiently. We implemented the original and adaptive parallel DJ algorithms on a network of Alpha workstations using the Parallel Virtual Machine (PVM). We analyzed the performance of the algorithms, and compared it with that of the parallel Hybrid-Hash (HH) join algorithms. Our results show that the parallel DJ algorithms perform comparably with the parallel HH join algorithms over the entire range of the number of processors used and for different join selectivities. A significant advantage of the parallel DJ algorithms is that they can easily support non-equijoin operations.     

Using intrinsic data skew to improve hash join performance

Hash join is used to join large, unordered relations and operates independently of the data distributions of the join relations. Real-world data sets are not uniformly distributed and often contain significant skew. Although partition skew has been studied for hash joins, no prior work has examined how exploiting data skew can improve the performance of hash join. In this paper, we present histojoin, a join algorithm that uses histograms to identify data skew and improve join performance. Experimental results show that for skewed data sets histojoin performs significantly fewer I/O operations and is faster by 10–60% than hybrid hash join.     

Distributed load balancing for parallel main memory hash join

Parallel joins have been widely studied during the past decade and a number of efficient algorithms were presented. While it is known that the performance of these algorithms may suffer greatly in the presence of skewed input data, the work on load balancing schemes for parallel join has been limited. The main contribution of this paper is the development and analysis of a new distributed data structure and an effective load balancing scheme for parallel main memory hash join on NUMA architecture. Multiprocessors based on this architecture are scalable in both size of main memory and number of processors, and provide very high memory bandwidth. The load balancing scheme is based on random probing to avoid the hot spot problems caused by probing sequentially. We have modeled this load balancing scheme both analytically and experimentally. The experiments were run on a BBN TC2000 multiprocessor system     

Task scheduling algorithm using minimized duplications in homogeneous systems

For fine grain task graphs, duplication-based scheduling algorithms are generally more efficient than list and cluster-based algorithms. However, most duplication-based heuristics try to duplicate all possible ancestor nodes of a given join node, in order to reduce the earliest start time (EST) of the join node, even though these ancestor nodes have already been allocated in previous steps. Thus, these duplication heuristics inevitably induce redundant duplications, which lead to the superfluous consumption of resources and generally deteriorate the scheduling result in the case of a bounded number of processors. When scheduling algorithms are used on an unbounded number of processors, the required number of processors grows excessively with the size of the task graph, thereby limiting the practicality of these algorithms for large task graphs. In this paper, we propose a novel algorithm designed to allocate join nodes without redundant duplications. In the proposed algorithm, if the ancestor nodes of a join node are duplicated when scheduling the join node, the original allocations of these ancestor nodes are removed using a very efficient method. The performance of the proposed algorithm, in terms of its normalized schedule length and efficiency, is compared with that of some of the recently proposed algorithms. The proposed algorithm generates better or comparable schedules with minimized duplication. Specifically, the simulation results show that it is most useful on a bounded number of processors.     

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

提出了一个基于分布式共享虚拟存储器技术的并行Ｈａｓｈ连接算法,然后设计了一个并行连接算法的测试评价基准,并评价和分析了该算法在均匀情况下３个不同负载的性能比较和Ｚｉｐｆ顺斜数据分布情况下两种度策略的算法性能。同时与其它并行连接算法进行性能比较与分析。     

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

本文提出了一种能克服各种数据偏斜、高效的、并行二元连接运算算法,可在不同的数据偏斜情况下启动不同的模块,克服数据偏斜造成的负载不平衡现象。     

Utilizing page-level join index for optimization in parallel joinexecution

This paper presents a methodology for the optimization of parallel join execution. Past research on parallel join methods mostly focused on the design of algorithms for partitioning (e.g. hash) relations and distributing data buckets as evenly as possible to the processors. Once data is distributed to the processors, it assumes that all processors will complete their tasks at about the same time. We stress that this is true if no further information such as page-level join index is available. Otherwise, the join execution can be further optimized and the workload in the processors may still be unbalanced. We study such problems that may incur in a shared-nothing architecture environment and propose algorithms for the problems. Also, a simulation study is performed to understand the characteristics of the proposed method     

基于Hadoop 的高效连接查询处理算法CHMJ

提出了一种并行连接查询处理算法CoLocationHashMapJoin(CHMJ).首先,设计了多副本一致性哈希算法,将具有连接关系的表根据其连接属性的哈希值在机群中进行分布,在提升了连接查询处理中数据本地性的同时,保证了数据的可用性;其次,基于多副本一致性哈希数据分布,提出了HashMapJoin并行连接查询处理算法,有效地提高了连接查询的处理效率.CHMJ算法在腾讯公司的数据仓库系统中进行了应用,结果表明,CHMJ连接查询的处理效率比Hive系统提高了近5倍.     

On-line scheduling of scalable real-time tasks on multiprocessor systems

The computation time of scalable tasks depends on the number of processors allocated to them in multiprocessor systems. As more processors are allocated to a scalable task, the overall computation time of the task decreases but the total amount of processors’ time devoted to the execution of the task, called workload, increases due to parallel execution overhead. In this paper, we propose a task scheduling algorithm that utilizes the property of scalable tasks for on-line and real-time scheduling. In the proposed algorithm, the total workload of all scheduled tasks is reduced by managing processors allocated to the tasks as few as possible without missing their deadlines. As a result, the processors in the system have less load to execute the scheduled tasks and can execute more newly arriving tasks before their deadlines. Simulation results show that the proposed algorithm performs significantly better than the conventional algorithm based on a fixed number of processors to execute each task.     

A parallel distributive join algorithm for cube-connectedmultiprocessors

This paper presents a parallel distributive join algorithm for cube-connected multiprocessors. The performance analysis shows that the proposed algorithm has an almost linear speedup over the sequential distributive join algorithm as the number of processors increases, and its performance is comparable to that of the parallel hybrid-hash join algorithm. A big advantage of the proposed algorithm over hash-based join algorithms is that it does not have the bucket overflow problem caused by nonuniform hashing of the smaller operand relation. Moreover, the proposed algorithm can easily support the nonequijoin operation, which is very hard to implement by using hash-based join algorithms     

基于共享Cache多核处理器的Hash连接优化

针对目前主流的多核处理器,研究了基于共享缓存多核处理器环境下的数据库Hash连接优化.首先提出基于Radix-Join算法的Hash连接多线程执行框架,通过实例分析了影响多线程Radix-Join算法性能的因素.在此基础上,优化了Hash连接多线程执行框架中的各种线程及其访问共享Cache的性能,优化了聚集连接时Hash连接算法的内存访问,并分析了多线程聚集划分的加速比.基于开源数据库INGRES和EaseDB,实现了所提出的连接多线程执行框架,在实验中测试了多线程Hash连接框架的性能.实验结果表明,该算法可以有效解决Hash连接执行时共享Cache在多线程条件下的访问冲突和处理器负载均衡问题,极大地提高了Hash连接性能.     

一个有效的Join任务图的调度算法

已有的Join任务图的调度算法大多不是基于通信竞争的环境而开发,且未考虑节省处理机的问题,使算法的应用效果不佳.因此,针对Join任务图,提出一个通信竞争环境的调度算法,该算法因串行通信边而改善其调度效率,时间复杂度为O(vlogv),其中,v为图中任务的个数.实验结果表明,与其他算法相比,该算法的调度长度较短且使用的...     

On exploiting task duplication in parallel program scheduling

One of the main obstacles in obtaining high performance from message-passing multicomputer systems is the inevitable communication overhead which is incurred when tasks executing on different processors exchange data. Given a task graph, duplication-based scheduling can mitigate this overhead by allocating some of the tasks redundantly on more than one processor. In this paper, we focus on the problem of using duplication in static scheduling of task graphs on parallel and distributed systems. We discuss five previously proposed algorithms and examine their merits and demerits. We describe some of the essential principles for exploiting duplication in a more useful manner and, based on these principles, propose an algorithm which outperforms the previous algorithms. The proposed algorithm generates optimal solutions for a number of task graphs. The algorithm assumes an unbounded number of processors. For scheduling on a bounded number of processors, we propose a second algorithm which controls the degree of duplication according to the number of available processors. The proposed algorithms are analytically and experimentally evaluated and are also compared with the previous algorithms