Skew handling strategies for pipelined processing of multi-join queries in shared-nothing systems

Abstract

This paper looks at how to effectively exploit pipelining for multi-join queries in shared-nothing systems. A promising technique that has appeared in the literature uses an iterative approach to process a multi-join query. In each iteration, several relations are selected, and are joined in a pipelined fashion. However, optimization algorithms that are based on this approach have traditionally assumed that the relations are uniformly distributed or lowly skewed. When this assumption is relaxed, that is when the data is skewed, the performance of the system may degenerate drastically. We propose four skew handling techniques to deal with data skew for multi-join queries. An analytical model is presented and used to compare the performance of each technique. Our results show that the nested-loops technique performs worst, while the hybrid technique is superior in most cases.