Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases.

Kiran J. Achyutuni, Edward Omiecinski, Shamkant B. Navathe: Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases. SIGMOD Conference 1996: 125-136

@inproceedings{DBLP:conf/sigmod/AchyutuniON96,
  author    = {Kiran J. Achyutuni and
               Edward Omiecinski and
               Shamkant B. Navathe},
  editor    = {H. V. Jagadish and
               Inderpal Singh Mumick},
  title     = {Two Techniques for On-Line Index Modification in Shared Nothing
               Parallel Databases},
  booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
               Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
  publisher = {ACM Press},
  year      = {1996},
  pages     = {125-136},
  ee        = {http://doi.acm.org/10.1145/233269.233326, db/conf/sigmod/AchyutuniON96.html},
  crossref  = {DBLP:conf/sigmod/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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), wheras 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 that 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.

Copyright © 1996 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod9397 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

H. V. Jagadish, Inderpal Singh Mumick (Eds.): Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, June 4-6, 1996. ACM Press 1996

, SIGMOD Record 25(2), June 1996
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1233 KB]

References

[Ach95]: ...
[DB92]: David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35(6): 85-98(1992)
[IFMX]: ...
[LDJ86]: Sheau-Dong Lang, James R. Driscoll, Jiann H. Jou: Batch Insertion for Tree Structured File Organizations - Improving Differential Database Reprensentation. Inf. Syst. 11(2): 167-175(1986)
[MN92]: C. Mohan, Inderpal Narang: Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates. SIGMOD Conference 1992: 361-370
[Moh90]: C. Mohan: ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. VLDB 1990: 392-405
[OLS94]: Edward Omiecinski, Liehuey Lee, Peter Scheuermann: Performance Analysis of a Concurrent File Reorganization Algorithm for Record Clustering. IEEE Trans. Knowl. Data Eng. 6(2): 248-257(1994)
[Omi85]: Edward Omiecinski: Incremental File Reorganization Schemes. VLDB 1985: 346-357
[Omi89]: Edward Omiecinski: Concurrent file conversion between B+-tree and linear hash files. Inf. Syst. 14(5): 371-383(1989)
[OS90]: Edward Omiecinski, Peter Scheuermann: A Parallel Algorithm for Record Clustering. ACM Trans. Database Syst. 15(4): 599-624(1990)
[SC91]: V. Srinivasan, Michael J. Carey: On-Line Index Construction Algorithms. HPTS 1991: 0-
[SD92]: Betty Salzberg, Allyn Dimock: Principles of Transaction-Based On-Line Reorganization. VLDB 1992: 511-520
[SG79]: Gary H. Sockut, Robert P. Goldberg: Database Reorganization - Principles and Practice. ACM Comput. Surv. 11(4): 371-395(1979)
[SI93]: ...
[Smi90]: ...
[SWZ92]: ...
[SWZ94]: Peter Scheuermann, Gerhard Weikum, Peter Zabback: ``Disk Cooling'' in Parallel Disk Systems. IEEE Data Eng. Bull. 17(3): 29-40(1994)
[Tro94]: ...
[Val93]: Patrick Valduriez: Parallel Database Systems: Open Problems and New Issues. Distributed and Parallel Databases 1(2): 137-165(1993)
[WZS91]: Gerhard Weikum, Peter Zabback, Peter Scheuermann: Dynamic File Allocation in Disk Arrays. SIGMOD Conference 1991: 406-415