An efficient parallel join algorithm based on hypercube-partitioning

Many parallel join algorithms have been proposed so far but most of which are developed focused on minimizing the disk I/O and CPU costs. The communication cost, however, is also an important factor that can significantly affect the join processing performance in multiprocessor systems. We propose a...

Full description

Saved in:
Bibliographic Details
Main Authors: Hwan Ik Choi, Byoung Mo Im, Myoung Ho Kim, Yoon-Joon Lee
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Broadcasting
Central Processing Unit
Computer science
Costs
Hypercubes
Multiprocessing systems
Parallel processing
Relational databases
Robustness
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Many parallel join algorithms have been proposed so far but most of which are developed focused on minimizing the disk I/O and CPU costs. The communication cost, however, is also an important factor that can significantly affect the join processing performance in multiprocessor systems. We propose an efficient parallel join algorithm, called Cube-Robust, for hypercube multicomputers. The proposed algorithm is developed based on the observation that the size ratio of two relations to be joined is the dominant factor in the communication cost. We develop the analytic cost model for the proposed join algorithm. The performance comparisons show that the Cube-Robust join algorithm works better than others proposed earlier in a wide range of size ratios.< >
DOI:10.1109/PDIS.1994.331733