Handling data skew in parallel joins in shared-nothing systems

ABSTRACT

Parallel processing continues to be important in large data warehouses. The processing requirements continue to expand in multiple dimensions. These include greater volumes, increasing number of concurrent users, more complex queries, and more applications which define complex logical, semantic, and physical data models. Shared nothing parallel database management systems [16] can scale up "horizontally" by adding more nodes. Most parallel algorithms, however, do not take into account data skew. Data skew occurs naturally in many applications. A query processing skewed data not only slows down its response time, but generates hot nodes, which become a bottleneck throttling the overall system performance. Motivated by real business problems, we propose a new join geography called PRPD (Partial Redistribution & Partial Duplication) to improve the performance and scalability of parallel joins in the presence of data skew in a shared-nothing system. Our experimental results show that PRPD significantly speeds up query elapsed time in the presence of data skew. Our experience shows that eliminating system bottlenecks caused by data skew improves the throughput of the whole system which is important in parallel data warehouses that often run high concurrency workloads.

REFERENCES

• 1: TPC Benchmark H (decision support) standard specification http://www.tpc.org.
• 2: K. Alsabti , S. Ranka, Skew-Insensitive Parallel Algorithms for Relational Join, Proceedings of the Fifth International Conference on High Performance Computing, p.367, December 17-20, 1998
• 3: Mostafa Bamha , Gaétan Hains, Frequency-adaptive join for shared nothing machines, Progress in computer research, Nova Science Publishers, Inc., Commack, NY, 2001
• 4: J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18:143--154, 1979.
• 5: Hasanat M. Dewan , Kui W. Mok , Mauricio Hernández , Salvatore J. Stolfo, Predictive dynamic load balancing of parallel hash-joins over heterogeneous processors in the presence of data skew, Proceedings of the third international conference on on Parallel and distributed information systems, p.40-49, October 1994, Autin, Texas, United States
• 6: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• 7: David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider , S. Seshadri, Practical Skew Handling in Parallel Joins, Proceedings of the 18th International Conference on Very Large Data Bases, p.27-40, August 23-27, 1992
• 8: FrankǎOlken and DoronǎRotem. Random sampling from databases: a survey. Statistics and Computing, 5(1):25--42, 1995.
• 9: R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17(2):416--429, 1969.
• 10: Lilian Harada , Masaru Kitsuregawa, Dynamic Join Product Skew Handling for Hash-Joins in Shared-Nothing Database Systems, Proceedings of the 4th International Conference on Database Systems for Advanced Applications (DASFAA), p.246-255, April 11-13, 1995
• 11: Kien A. Hua , Chiang Lee, Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning, Proceedings of the 17th International Conference on Very Large Data Bases, p.525-535, September 03-06, 1991
• 12: E. G. C. Jr., M. R. Garey, and D. S. Johnson. An application of bin-packing to multiprocessor scheduling. SIAM J. Comput., 7(1):1--17, 1978.
• 13: Masaru Kitsuregawa , Yasushi Ogawa, Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC), Proceedings of the 16th International Conference on Very Large Data Bases, p.210-221, August 13-16, 1990
• 14: M. S. Lakshmi , P. S. Yu, Effectiveness of Parallel Joins, IEEE Transactions on Knowledge and Data Engineering, v.2 n.4, p.410-424, December 1990 [doi>10.1109/69.63253]
• 15: Ambuj Shatdal , Jeffrey F. Naughton, Using shared virtual memory for parallel join processing, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.119-128, May 25-28, 1993, Washington, D.C., United States
• 16: M. Stonebraker. The case for shared nothing. IEEE Database Eng. Bull., 9(1):4--9, 1986.
• 17: Christopher B. Walton , Alfred G. Dale , Roy M. Jenevein, A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins, Proceedings of the 17th International Conference on Very Large Data Bases, p.537-548, September 03-06, 1991
• 18: J. L. Wolf , D. M. Dias , P. S. Yu, A Parallel Sort Merge Join Algorithm for Managing Data Skew, IEEE Transactions on Parallel and Distributed Systems, v.4 n.1, p.70-86, January 1993 [doi>10.1109/71.205654]
• 19: Joel L. Wolf , Daniel M. Dias , Philip S. Yu , John Turek, An Effective Algorithm for Parallelizing Hash Joins in the Presence of Data Skew, Proceedings of the Seventh International Conference on Data Engineering, p.200-209, April 08-12, 1991
• 20: J. L. Wolf , D. M. Dias , P. S. Yu , J. Turek, New Algorithms for Parallelizing Relational Database Joins in the Presence of Data Skew, IEEE Transactions on Knowledge and Data Engineering, v.6 n.6, p.990-997, December 1994 [doi>10.1109/69.334888]
• 21: X. Zhou and M. E. Orlowska. Handling data skew in parallel hash join computation using two-phase scheduling. In IEEE 1st International Conference on Algorithm and Architecture for Parallel Processing, pages 527--536 vol.2, 1995.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Parallel databases

General Terms:
Algorithms

Keywords:
data skew, parallel joins, shared nothing