Extreme Skew Handling in Right-Deep Multi-Joins

概要

論文の詳細を見る
Execution of relational operations on a shared nothing system is susceptible to various forms of skew due to the partitioning of tuples amongst the processing nodes. This skew reduces the overall efficiency of the multi-join operation. In this paper, we present an algorithm for dynamically handling skew in a right-deep hash multi-join. In the right-deep hash multi-join, a right-deep query execution plan is used to schedule the order in which the pair-wise hash joins should be performed. The right-deep query allows the multi-join to proceed in a pipelined manner. When this pipeline is partitioned amongst the processors, skew affects the flow of tuples through the processors, allowing some processors to finish reading all of the tuples on their local disks much faster than others. Once all of the disk tuples have been read, the processor will become periodically idle while it waits for probe tuples to arrive from another processor. As the skew in the disk read completion times increases, processor utilization efficiency decreases which leads to a longer response time for the multi-join. Our algorithm makes use of a control processor, called the foreman, to make decisions about how hash lines should be migrated in order to balance the disk completion times, where a hash line consists of the set of build relation tuples of a particular pair-wise join which map to the same hash entry in the hash table. A hash line is a natural unit of migration, since it assures that all build relation tuples with the same attribute value are located on the same processor. Load balancing occurs in two phases, the first phase balances the pipeline flow for each processor, and the second phase balances the disk completion times.
一般社団法人情報処理学会の論文
1996-09-04

Extreme Skew Handling in Right-Deep Multi-Joins

スポンサーリンク

概要

著者

関連論文

スポンサーリンク