Database processing on a cube-connected multicomputer
Ophir Frieder · Deep Blue (University of Michigan) · 1987
A boolean cube-connected relational database machine is developed. Strategies for performing the basic relational database operations are presented. The strategies are termed "dynamic" and are novel in that they account for the non-uniform data distribution across parallel paths by redistributing the data as part of the database algorithms. Obtaining uniform data distributions is important in parallel architectures in order to attain close to optimal performance. The cube interconnection scheme employed subsumes many other interconnection structures such as the tree, ring, etc. This property is exploited in order to efficiently support the various database operations such as Select, Aggregate, Join, and Project. Results from a simulation which was developed demonstrate the improvement in the performance of the costly join operation achieved via the two main data redistribution operations viz., tuple balancing and merging. For the four database operations considered, it is shown that each can be represented in terms of a few "basic" operations and the set of all "basic" operations is identified. Within the proposed architecture, an overall query processing approach using these algorithms and a flexible "cube controlling a cube" control structure are presented. The scheduling method used groups that needed database operations to reduce scheduling complexity, while still supporting intra- and inter-query concurrency and minimizing communcation delay. Besides being novel by "dynamically" redistributing data resulting from intermediate calculations, this research demonstrates the possibility of implementing fast database operations on a general, multi-purpose multicomputer system with lower response times than special purpose database architectures.