Online algorithms for handling skew in parallel joins

Abstract

When the work involved in a join is partitioned among multiple processors in the parallel join, the skew in the operand relations can result in significant imbalance in the work assigned to the different processors. This imbalance can cause significant degradation in the response time lor the join operation. In this paper, we present two new algorithms, the pure online PO and the online/offline algorithm OO, for handling skew in parallel join evaluation. Lsing the histogram data of the operand relations, the skew handling algorithms can achieve any permissible tolerance in the join work imbalance among the processors. Unlike previous work on handling skew in parallel joins, the algorithms are online in the sense that they process most (or all) of the histogram data as it is generated. We compare these algorithms and their variations experimentally and find that a particular variation of algorithm OO is usually the algorithm of choice.