Whenever data is moved across nodes in the parallel database system, the indexes need to be modified too. Index modification overhead can be quite severe because there can be a large number of indexes on a relation. In this paper, we study two alternatives to index modification, namely OAT (One-At-a-Time page movement) and BULK (bulk page movement). OAT and BULK are two extremes on the spectrum of the granularity of data movement. OAT and BULK differ in two respects: first, OAT uses very little additional disk space (at most one extra page), whereas BULK uses a large amount of disk space. Second, BULK uses sequential prefetch I/O to optimize on the number of I/Os during index modification, while OAT does not. Using an experimental testbed, we show that BULK is an order of magnitude faster than OAT. In terms of the impact on transaction performance during reorganization, BULK and OAT perform differently: when the number of indexes to be modified is either one or two, OAT has a lesser impact on the transaction performance degradation. However, when the number of indexes is greater than two, both techniques have the same impact on transaction performance.

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.

	Ach95	Kiran Jyotsna Achyutuni , Shamkant B. Navathe , Edward Omiecenski, On-line tuning of data placement in parallel databases, 1995
	DG92	David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992  [doi>10.1145/129888.129894]
	IFMX	Inform,x Software Inc. Informix Manuals, release 7 1 edition, December 1994-
	LDJ86	S D Lang , J R Driscoll , J H Jou, Batch insertion for tree structured file organizations—improving differential database representation, Information Systems, v.11 n.2, p.167-175, 1986  [doi>10.1016/0306-4379(86)90005-0]
	MN92	C. Mohan , Inderpal Narang, Algorithms for creating indexes for very large tables without quiescing updates, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.361-370, June 02-05, 1992, San Diego, California, United States
	Moh90	C. Mohan, ARIES/KVL: a key-value locking method for concurrency control of multiaction transactions operating on B-tree indexes, Proceedings of the sixteenth international conference on Very large databases, p.392-405, September 1990, Brisbane, Australia
	OLS94	E. Omiecinski , L. Lee , P. Scheuermann, Performance Analysis of a Concurrent File Reorganization Algorithm for Record Clustering, IEEE Transactions on Knowledge and Data Engineering, v.6 n.2, p.248-257, April 1994  [doi>10.1109/69.277769 ]
	Omi85	E, Omtecinskl Incremental flie reorgan~zat,on schemes In Proc, l lth Intl Conf Very Large Data Bases, pages pp 346-35T, Sac Marco, CA, Aug. 1985 Morgan Kaufmann Publishers
	Omi89	E. Omiecinski, Concurrent file conversion between B+-tree and linear hash files, Information Systems, v.14 n.5, p.371-383, 1989  [doi>10.1016/0306-4379(89)90002-1]
	OS90	Edward Omiecinski , Peter Scheuermann, A parallel algorithm for record clustering, ACM Transactions on Database Systems (TODS), v.15 n.4, p.599-624, Dec. 1990  [doi>10.1145/99935.99947]
	SC91	V Srinivasan and M Carey. On-line index construction a{gor,thms In Proc. 4th Internatlon Workshop on High Performance Transaction Systems, Asilomar, September 1991
	SD92	Betty Salzberg , Allyn Dimock, Principles of Transaction-Based On-Line Reorganization, Proceedings of the 18th International Conference on Very Large Data Bases, p.511-520, August 23-27, 1992
	SG79	Gary H. Sockut , Robert P. Goldberg, Database Reorganization—Principles and Practice, ACM Computing Surveys (CSUR), v.11 n.4, p.371-395, Dec. 1979  [doi>10.1145/356789.356796]
	SI93	O H Sockut and B I% lyer l~eorganizing databases concurrently with usage' A survey. Technlcal Report T16 0;5 488, IBM, Santa Teresa Laboratory, San Jose, CA, June 199;5
	Smi90	G S Smith Onllne reorgan,zat}on of key-sequenced tables and files Tandem System Review, 6(2).pp 52-59, Oct 1990.
	SWZ92	P. Scheuermann, G Welkum, and P Zabback Autornatlc tuning of data placement and load balancing in disk arrays. Technical 16eport DBS-92-91, ETH-Zurlch, Department of Computer Sc,ence, ETH-Zentrum, CH-8092 Zur*ch~ Sw,tzerland, 1992
	SWZ94	P. Scheuermann, O. Weikum, and P Zabback Disk coollng ,n parallel disk systems. Bulletin of the Technlcal Committee on Data I~ng{neering, 17(3),29-40, September 1994.
	Tro94	J Tro~si NonStop ava,lab~llty and database configuration operatKons Tandem Systems 16evlew, 10(;5)'18-2;5, July 1994
	Val93	Patrick Valduriez, Parallel database systems: open problems and new issues, Distributed and Parallel Databases, v.1 n.2, p.137-165, April 1993  [doi>10.1007/BF01264049]
	wzs91	Gerhard Weikum , Peter Zabback , Peter Scheuermann, Dynamic file allocation in disk arrays, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.406-415, May 29-31, 1991, Denver, Colorado, United States

• 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
  
  
• The GemStone object database management system Communications of the ACM   34, 10
  Paul Butterworth ,  Allen Otis ,  Jacob Stein
  
  
• Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM   34, 12
  Ellen Francik ,  Susan Ehrlich Rudman ,  Donna Cooper ,  Stephen Levine
  
  
• An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
  Gwo-Dong Chen ,  Daniel D. Gajski
  
  

• ACM SIGMOD Record
  Volume 25 ,  Issue 2   June 1996