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 the 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 paralel database system is contingent on the physical layout of data across the processors of the system. If the data is not declustered properly, the execution of an operator might waste resources, reducing the overall processing capability of the system. With earlier, single attribute declustering strategies, such as those found in Tandem, Teradata, Gamma, and Bubba parallel database systems, a selection query including a range predicate on any attribute other than the partitioning attribute must be sent to all processors containing tuples of the relation. By directing a query with minimal resource requirements to processors that contain no relevant tuples, the system wastes CPU cycles, communication bandwidth, and I/O bandwidth, reducing its overall processing capability. As a solution, several multi-attribute declustering strategies have been proposed. However, the performance of these declustering techniques have not previously been compared to one another nor with a single attribute partitioning strategy. This paper, compares the performance of Multi-Attribute GrId deClustering (MAGIC) strategy and Bubba's Extended Range Declustering (BERD) strategy with one another and with the range partitioning strategy. Our results indicate that MAGIC outperforms both range and BERD in all experiments conducted in this study.

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BAC+90	H. Boral , W. Alexander , L. Clay , G. Copeland , S. Danforth , M. Franklin , B. Hart , M. Smith , P. Valduriez, Prototyping Bubba, A Highly Parallel Database System, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.4-24, March 1990  [doi>10.1109/69.50903 ]
	BDC83	Dina Bitton , David J. DeWitt , Carolyn Turbyfill, Benchmarking Database Systems A Systematic Approach, Proceedings of the 9th International Conference on Very Large Data Bases, p.8-19, October 31-November 02, 1983
	CABK88	George Copeland , William Alexander , Ellen Boughter , Tom Keller, Data placement in Bubba, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.99-108, June 01-03, 1988, Chicago, Illinois, United States
	DGS+90	D. J. Dewitt , S. Ghandeharizadeh , D. A. Schneider , A. Bricker , H. -I. Hsiao , R. Rasmussen, The Gamma Database Machine Project, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.44-62, March 1990  [doi>10.1109/69.50905 ]
	GD90	Shahram Ghandeharizadeh , David J. DeWitt, A Multiuser Performance Analysis of Alternative Declustering Strategies, Proceedings of the Sixth International Conference on Data Engineering, p.466-475, February 05-09, 1990
	Gha90	Shahram Ghandeharizadeh , David J. Dewitt, Physical database design in multiprocessor database systems, 1990
	GMSY90	S. Ghandeharizadeh, 1~. 1~ Meyer, G. L. Schultz, and J. Yackel. Optimal balance partitions and a parallel database application. Computer sciences technical report, UW-Madison, December 1990. To appear in Operation Research Society of America (ORSA) Journal of Computing.
	Gra89	G. Graefe. Volcano: An extensible and parallel dataflow query processing system. Computer science technical report, Oregon Graduate Center, Beaverton, OR, june 1989.
	Hsi90	Hui Hsiao. A vailibility in Multiprocessor Database machines. PhD thesis, University of Wisconsin- Madison, 1990.
	Liv88	M. Livny. DeNet User's Guide. Computer Sciences Department, University of Wisconsin, Madison, 1988.
	LKB87	Miron Livny , Setrag Khoshafian , Haran Boral, Multi-disk management algorithms, Proceedings of the 1987 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.69-77, May 11-14, 1987, Banff, Alberta, Canada
	NHS84	J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984  [doi>10.1145/348.318586]
	RE78	D. Ries and R. Epstein. Evaluation of distribution criteria for distributed database systems. UCB/ERL Technical Report M78/22, UC Berkeley, May 1978.
	Sch90	Donovan Alfred Schneider , David J. Dewitt, Complex query processing in multiprocessor database machines, 1990
	SPO88	Michael Stonebraker , Randy H. Katz , David A. Patterson , John K. Ousterhout, The Design of XPRS, Proceedings of the 14th International Conference on Very Large Data Bases, p.318-330, August 29-September 01, 1988
	Tan88	CORPORATE Tandem Performance Group, A benchmark of non-stop SQL on the debit credit transaction, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.337-341, June 01-03, 1988, Chicago, Illinois, United States
	Ter85	Teradata Corp. DBC/IOI2 Data Base Computer System Manual, November 1985. Teredata Corp. Document No. C10-0001- 02, Release 2.0.
	TP72	Toby J. Teorey , Tad B. Pinkerton, A comparative analysis of disk scheduling policies, Communications of the ACM, v.15 n.3, p.177-184, March 1972  [doi>10.1145/361268.361278]

• Constructing reality Proceedings of the 11th annual international conference on Systems documentation
  Douglas A. Powell ,  Norman R. Ball ,  Mansel W. Griffiths
  
  
• Data structures for quadtree approximation and compression Communications of the ACM   28, 9
  Hanan Samet
  
  
• A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
  Kim S. Lee ,  Huizhu Lu ,  D. D. Fisher
  
  
• An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
  Gwo-Dong Chen ,  Daniel D. Gajski
  
  
• The GemStone object database management system Communications of the ACM   34, 10
  Paul Butterworth ,  Allen Otis ,  Jacob Stein
  
  

• ACM SIGMOD Record
  Volume 21 ,  Issue 2   June 1, 1992