Robust and Skew-resistant Parallel Joins in Shared-Nothing Systems
Open Access
- 3 November 2014
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1399-1408
Abstract
The performance of joins in parallel database management systems is critical for data intensive operations such as querying. Since data skew is common in many applications, poorly engineered join operations result in load imbalance and performance bottlenecks. State-of-the-art methods designed to handle this problem offer significant improvements over naive implementations. However, performance could be further improved by removing the dependency on global skew knowledge and broadcasting. In this paper, we propose PRPQ (partial redistribution & partial query), an efficient and robust join algorithm for processing large-scale joins over distributed systems. We present the detailed implementation and a quantitative evaluation of our method. The experimental results demonstrate that the proposed PRPQ algorithm is indeed robust and scalable under a wide range of skew conditions. Specifically, compared to the state-of-art PRPD method, we achieve 16% - 167% performance improvement and 24% - 54% less network communication under different join workloads.Keywords
Funding Information
- International Business Machines Corporation
- Irish Research Council
This publication has 22 references indexed in Scilit:
- Robust and Efficient Large-Large Table Outer Joins on Distributed InfrastructuresLecture Notes in Computer Science, 2014
- Massively parallel sort-merge joins in main memory multi-core database systemsProceedings of the VLDB Endowment, 2012
- GPU join processing revisited2012
- The data cyclotron query processing schemeACM Transactions on Database Systems, 2011
- Sort vs. Hash revisitedProceedings of the VLDB Endowment, 2009
- Peer-to-peer management of XML dataACM SIGMOD Record, 2005
- An adaptive hash join algorithm on a network of workstations2002
- The state of the art in distributed query processingACM Computing Surveys, 2000
- Parallel database systemsCommunications of the ACM, 1992
- A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environmentACM SIGMOD Record, 1989