We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
PIPELINING A SKEW-INSENSITIVE PARALLEL JOIN ALGORITHM.
- Authors
Bamha, M.; Exbrayat, M.
- Abstract
Most standard parallel join algorithms try to overcome data skews with a relatively static approach. The way they distribute data (and then computation) over nodes depends on a data re-distribution algorithm (hashing or range partitioning) that is determined before the actual join begins. On the contrary, our approach consists in pre-scanning data in order to choose an efficient join method for each given value of the join attribute. This approach has already proved to be efficient both theoretically and practically in our previous papers. In this paper we introduce a new pipelined version of our frequency adaptive join algorithm. The use of pipelining offers flexible strategies for resource allocation while avoiding unnecessary disk input/output of intermediate join results when computing multi-join queries. We present a detailed version of the algorithm and a cost analysis based on the BSP (Bulk Synchronous Parallel) model, showing that our pipelined algorithm achieves noticeable improvements compared to the sequential parallel version for multi-join queries while guaranteeing perfect balancing properties.
- Subjects
PARALLEL programming; ALGORITHMS; COMPUTER software; RESOURCE allocation; DATABASE management
- Publication
Parallel Processing Letters, 2003, Vol 13, Issue 3, p317
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626403001306