Skew handling techniques in sort-merge join

ABSTRACT

Joins are among the most frequently executed operations. Several fast join algorithms have been developed and extensively studied; these can be categorized as sort-merge, hash-based, and index-based algorithms. While all three types of algorithms exhibit excellent performance over most data, ameliorating the performance degradation in the presence of skew has been investigated only for hash-based algorithms. However, for sort-merge join, even a small amount of skew present in realistic data can result in a significant performance hit on a commercial DBMS. This paper examines the negative ramifications of skew in sort-merge join and proposes several refinements that deal effectively with data skew. Experiments show that some of these algorithms also impose virtually no penalty in the absence of data skew and are thus suitable for replacing existing sort-merge implementations. We also show how sort-merge band join performance is significantly enhanced with these refinements.

REFERENCES

• 1: Structural Joins: A Primitive for Efficient XML Query Pattern Matching, Proceedings of the 18th International Conference on Data Engineering, p.141, February 26-March 01, 2002
• 2: David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider, An Evaluation of Non-Equijoin Algorithms, Proceedings of the 17th International Conference on Very Large Data Bases, p.443-452, September 03-06, 1991
• 3: 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
• 4: Hector Garcia-Molina , Jennifer Widom , Jeffrey D. Ullman, Database System Implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 5: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 6: Goetz Graefe, Sort-Merge-Join: An Idea Whose Time Has(h) Passed?, Proceedings of the Tenth International Conference on Data Engineering, p.406-417, February 14-18, 1994
• 7: G. Graefe , A. Linville , L. D. Shapiro, Sort vs. Hash Revisited, IEEE Transactions on Knowledge and Data Engineering, v.6 n.6, p.934-944, December 1994 [doi>10.1109/69.334883]
• 8: Himawan Gunadhi , Arie Segev, A framework for query optimization in temporal databases, Proceedings of the fifth international conference on Statistical and scientific database management, p.131-147, March 1990, Charlotte, North Carolina, United States
• 9: 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
• 10: M. Kitsuregawa , M. Nakayama , M. Takagi, The effect of bucket size tuning in the dynamic hybrid GRACE hash join method, Proceedings of the 15th international conference on Very large data bases, p.257-266, July 1989, Amsterdam, The Netherlands
• 11: Roger N. Kline and Michael D. Soo, "The TIMEIT Temporal Database Testbed," 1998. www.cs.auc.dk/TimeCenter/software.htm.
• 12: Robert Philip Kooi, The optimization of queries in relational databases, 1980
• 13: T. Y. Cliff Leung and Richard R. Muntz, "Generalized Data Stream Indexing and Temporal Query Processing," in International Workshop on Research Issues in Data Engineering: Transaction and Query Processing, Philip S. Yu (ed.), pp. 124-131, Tempe, AZ, February, 1992.
• 14: Quanzhong Li , Bongki Moon, Indexing and Querying XML Data for Regular Path Expressions, Proceedings of the 27th International Conference on Very Large Data Bases, p.361-370, September 11-14, 2001
• 15: Wei Li, Dengfeng Gao and Richard T. Snodgrass, "Skew Handling Techniques in Sort-Merge Join," 2001. http://www.cs.auc.dk/research/DP/tdb/TimeCenter/TimeCenterPublications/TR-62.pdf.
• 16: Priti Mishra , Margaret H. Eich, Join processing in relational databases, ACM Computing Surveys (CSUR), v.24 n.1, p.63-113, March 1992 [doi>10.1145/128762.128764]
• 17: Masaya Nakayama , Masaru Kitsuregawa , Mikio Takagi, Hash-Partitioned Join Method Using Dynamic Destaging Strategy, Proceedings of the 14th International Conference on Very Large Data Bases, p.468-478, August 29-September 01, 1988
• 18: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 19: Michael D. Soo , Richard Thomas Snodgrass , Christian S. Jensen, Efficient Evaluation of the Valid-Time Natural Join, Proceedings of the Tenth International Conference on Data Engineering, p.282-292, February 14-18, 1994
• 20: 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
• 21: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States
• 22: Thomas Zurek, Parallel Temporal Nested-Loop Joins, Ph.D. Dissertation, Dept. of Computer Science, Edinburgh University, 1996.

INDEX TERMS

Primary Classification:
  E. Data
  E.5 FILES
      Subjects: Sorting/searching

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Documentation, Theory