Improving the robustness and performance of parallel joins over distributed systems

High-performance data processing systems typically utilize numerous servers with large amounts of memory. An essential operation in such environment is the parallel join, the performance of which is critical for data intensive operations. In many real-world workloads, data skew is omnipresent. Techniques that do not cater for the possibility of data skew often suffer from performance failures and memory problems. State-of-the-art methods designed to handle data skew propose new ways to distribute computation that avoid hotspots. However, this comes at the expense of global collection of statistics, redundant computation, duplication of data or increased network communication. In this light, performance could be further improved by removing the dependency on global skew knowledge and broadcasting. In this paper, we propose a new method called PRPQ (partial redistribution & partial query), with targets for efficient and robust joins with large datasets over high performance clusters. We present the detailed implementation of our approach and compare its performance with current implementations. The experimental results demonstrate that the proposed algorithm is scalable and robust and can also outperform the state-of-the-art approach with less network communication, figures that confirm our theoretical analysis.