MAGIC: a multiattribute declustering mechanism for multiprocessor database machines

During the past decade, parallel database systems have gained increased popularity due to their high performance, scalability, and availability characteristics. With the predicted future database sizes and complexity of queries, the scalability of these systems to hundreds and thousands of processors is essential for satisfying the projected demand. Several studies have repeatedly demonstrated that both the performance and scalability of a parallel database system are contingent on the physical layout of the data across the processors of the system. If the data are not declustered appropriately, the execution of an operation might waste system resources, reducing the overall processing capability of the system. With earlier, single-attribute partitioning mechanisms such as those found in the Tandem, Teradata, Gamma, and Bubba parallel database systems, range selections on any attribute other than the partitioning attribute must be sent to all processors containing tuples of the relation, while range selections on the partitioning attribute can be directed to only a subset of the processors. Although using all the processors for an operation is reasonable for resource intensive operations, directing a query with minimal resource requirements to processors that contain no relevant tuples wastes CPU cycles, communication bandwidth, and I/O bandwidth. As a solution, this paper describes a new partitioning strategy, multiattribute grid declustering (MAGIC), which can use two or more attributes of a relation to decluster its tuples across multiple processors and disks. In addition, MAGIC declustering, unlike other multiattribute partitioning mechanisms that have been proposed, is able to support range selections as well as exact match selections on each of the partitioning attributes. This capability enables a greater variety of selection operations to be directed to a restricted subset of the processors in the system. Finally, MAGIC partitions each relation based on the resource requirements of the queries that constitute the workload for the relation and the processing capacity of the system in order to ensure that the proper number of processors are used to execute queries that reference the relation