Browse Prior Art Database

Online Algorithms for Load Balancing the Join Operation

IP.com Disclosure Number: IPCOM000122632D
Original Publication Date: 1991-Dec-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 3 page(s) / 125K

Publishing Venue

IBM

Related People

Swami, AN: AUTHOR [+2]

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 for the join operation. Disclosed are two algorithms for handling the skew in a parallel join. The balancing algorithms are presented with two histograms over the same set of distinct values. An interval is a consecutive set of values in the histogram where an interval could be single-valued or multi-valued. The join work can be computed for each interval. Also, a single-valued interval can be split so that its work can be distributed over multiple processors.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Online Algorithms for Load Balancing the Join Operation

      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 for the join operation.  Disclosed
are two algorithms for handling the skew in a parallel join.  The
balancing algorithms are presented with two histograms over the same
set of distinct values.  An interval is a consecutive set of values
in the histogram where an interval could be single-valued or
multi-valued.  The join work can be computed for each interval.
Also, a single-valued interval can be split so that its work can be
distributed over multiple processors.

      Let p denote the number of processors available to perform the
join (join processors).  Let Wt denote the total join work including
CPU and IO, and let Wp = Wt/p denote the join work per processor if
perfectly balanced.  Then, Wt = pWp .  Let w denote the permissible
tolerance in the load balancing.  For the perfectly balanced case, w
= 0.  Then it is required that the load balancing algorithm assign
the join work so that no processor is assigned work exceeding (1 +
w)Wp .

      The first algorithm is called the pure online algorithm PO.
Let Wseen denote the join work seen (and assigned) so far by
algorithm PO.  Initially Wseen is zero.  Let I be the work in the
next interval to be assigned.  Let Wi denote the work on processor i
before I is assigned, and W'i the work on the same processor after I
is assigned.  In PO, it is ensured that

      First, PO tries to assign I to a single processor, i.e.,
without splitting, so that Equation 1 holds.  If such an assignment
is not possible, I needs to be split.  It is easy to see that
splitting each interval into p fragments will always work.  However,
this may lead to excessive communication overhead.  Hence, PO
computes the smallest number of splits of I required and assigns
these fragments of I to the appropriate processors.  Clearly, when PO
terminates after processing the complete histogram, the load balance
criterion is satisfied since then Wseen = Wt and I = 0.  Thus, all
the intervals are processed as they are generated, and the algorithm
is a pure online algorithm.

      The other algorithm is called the online/offline algorithm OO.
It consists of two phases, an online phase and an offline phase.  In
the online phase, two auxiliary lists are used: an offline list of
maximum length p, and a combining list.  Also, Ua denotes the average
work currently assigned to the join processors, and Oa denotes the
average work currently assigned to the offline list.  Initially, both
the offline list and the combining list are empty, and Ua = Oa = 0.
At any point the processor to which the next interval can be assigned
is called...