Dynamic load balancing in very large shared-nothing hypercube database computers
- 1 January 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 42 (12) , 1425-1439
- https://doi.org/10.1109/12.260633
Abstract
Two relational join strategies, broadcast-based join and bucket-based join, have been recently proposed for the hypercube interconnection topology. The first strategy, however, incurs many unnecessary comparisons of pairs of tuples of the two relations. Although the second technique compares only tuples of the relevant buckets, it may suffer from potential load imbalance, which is most critical to the performance of a shared-nothing system. To address these issues, a join algorithm for hypercube computers which includes dynamic load balancing capabilities to minimize the effect of skewness in tuple distribution is proposed. Simulation results indicate that the scheme provides significant improvement over the bucket-based join strategy. In fact, the technique is consistently superior even when the skew condition is very mild.Keywords
This publication has 19 references indexed in Scilit:
- A benchmark of NonStop SQL release 2 demonstrating near-linear speedup and scaleup on large databasesACM SIGMETRICS Performance Evaluation Review, 1990
- The Gamma database machine projectIEEE Transactions on Knowledge and Data Engineering, 1990
- Prototyping Bubba, a highly parallel database systemIEEE Transactions on Knowledge and Data Engineering, 1990
- Hash-based and index-based join algorithms for cube and ring connected multicomputersIEEE Transactions on Knowledge and Data Engineering, 1989
- Database operations in a cube-connected multicomputer systemIEEE Transactions on Computers, 1989
- A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environmentACM SIGMOD Record, 1989
- A hash-based join algorithm for a cube-connected parallel computerInformation Processing Letters, 1989
- Fragmentation: a technique for efficient query processingACM Transactions on Database Systems, 1986
- Implementation techniques for main memory database systemsPublished by Association for Computing Machinery (ACM) ,1984
- Application of hash to data base machine and its architectureNew Generation Computing, 1983