Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates.

C. Mohan, Inderpal Narang: Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates. SIGMOD Conference 1992: 361-370
  author    = {C. Mohan and
               Inderpal Narang},
  editor    = {Michael Stonebraker},
  title     = {Algorithms for Creating Indexes for Very Large Tables Without
               Quiescing Updates},
  booktitle = {Proceedings of the 1992 ACM SIGMOD International Conference on
               Management of Data, San Diego, California, June 2-5, 1992},
  publisher = {ACM Press},
  year      = {1992},
  pages     = {361-370},
  ee        = {, db/conf/sigmod/MohanN92.html},
  crossref  = {DBLP:conf/sigmod/92},
  bibsource = {DBLP,}


As relational DBMSs become more and more popular and as organizations grow, the sizes of individual tables are increasing dramatically. Unfortunately, current DBMSs do not allow updates to be performed on a table while an index (e.g., a B+-tree) is being built for that table, thereby decreasing the systems' availability. This paper describes two algorithms in order to relax this restriction. Our emphasis has been to maximize concurrency, minimize overheads and cover all aspects of the problem. Builds of both unique and nonunique indexes are handled correctly. We also describe techniques for making the index-build operation restartable, without loss of all work, in case a system failure were to interrupt the completion of the creation of the index. In this connection, we also present algorithms for making a long sort operation restartable. These include algorithms for the sort and merge phases of sorting.

Copyright © 1992 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 2, SIGMOD '75-'92" and ...

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

Printed Edition

Michael Stonebraker (Ed.): Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, San Diego, California, June 2-5, 1992. ACM Press 1992 BibTeX , SIGMOD Record 21(2), June 1992

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1279 KB]


Josephine M. Cheng, Donald J. Haderle, Richard Hedges, Balakrishna R. Iyer, Ted Messinger, C. Mohan, Yun Wang: An Efficient Hybrid Join Algorithm: A DB2 Prototype. ICDE 1991: 171-180 BibTeX
David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of Database Processing or a Passing Fad? SIGMOD Record 19(4): 104-112(1990) BibTeX
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, Peter M. Schwarz: ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM Trans. Database Syst. 17(1): 94-162(1992) BibTeX
C. Mohan: ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. VLDB 1990: 392-405 BibTeX
C. Mohan: Commit_LSN: A Novel and Simple Method for Reducing Locking and Latching in Transaction Processing Systems. VLDB 1990: 406-418 BibTeX
C. Mohan, Frank E. Levine: ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. SIGMOD Conference 1992: 371-380 BibTeX
C. Mohan, Hamid Pirahesh, Raymond A. Lorie: Efficient and Flexible Methods for Transient Versioning of Records to Avoid Locking by Read-Only Transactions. SIGMOD Conference 1992: 124-133 BibTeX
Hamid Pirahesh, C. Mohan, Josephine M. Cheng, T. S. Liu, Patricia G. Selinger: Parallelism in Relational Data Base Systems: Architectural Issues and Design Approaches. DPDS 1990: 4-29 BibTeX
Abraham Silberschatz, Michael Stonebraker, Jeffrey D. Ullman: Database Systems: Achievements and Opportunities. Commun. ACM 34(10): 110-120(1991) BibTeX
V. Srinivasan, Michael J. Carey: On-Line Index Construction Algorithms. HPTS 1991: 0- BibTeX
James Z. Teng, Robert A. Gumaer: Managing IBM Database 2 Buffers to Maximize Performance. IBM Systems Journal 23(2): 211-218(1984) BibTeX

Referenced by

  1. Mong-Li Lee, Masaru Kitsuregawa, Beng Chin Ooi, Kian-Lee Tan, Anirban Mondal: Towards Self-Tuning Data Placement in Parallel Database Systems. SIGMOD Conference 2000: 225-236
  2. Mohana Krishna Lakhamraju, Rajeev Rastogi, S. Seshadri, S. Sudarshan: On-line Reorganization in Object Databases. SIGMOD Conference 2000: 58-69
  3. Wilburt Labio, Janet L. Wiener, Hector Garcia-Molina, Vlad Gorelik: Efficient Resumption of Interrupted Warehouse Loads. SIGMOD Conference 2000: 46-57
  4. C. Mohan: Repeating History Beyond ARIES. VLDB 1999: 1-17
  5. Lauri Malmi, Eljas Soisalon-Soininen: Group Updates for Relaxed Height-Balanced Trees. PODS 1999: 358-367
  6. Chendong Zou, Betty Salzberg: Safely and Efficiently Updating References During On-line Reorganization. VLDB 1998: 512-522
  7. Kerttu Pollari-Malmi, Eljas Soisalon-Soininen, Tatu Ylönen: Concurrency Control in B-Trees with Batch Updates. IEEE Trans. Knowl. Data Eng. 8(6): 975-984(1996)
  8. Gary H. Sockut, Balakrishna R. Iyer: A Survey on Online Reorganization in IBM Products and Research. IEEE Data Eng. Bull. 19(2): 4-11(1996)
  9. Chendong Zou, Betty Salzberg: On-line Reorganization of Sparsely-populated B+trees. SIGMOD Conference 1996: 115-124
  10. 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
  11. Janet L. Wiener, Jeffrey F. Naughton: OODB Bulk Loading Revisited: The Partitioned-List Approach. VLDB 1995: 30-41
  12. Betty Salzberg, Allyn Dimock: Principles of Transaction-Based On-Line Reorganization. VLDB 1992: 511-520
  13. V. Srinivasan, Michael J. Carey: Compensation-Based On-Line Query Processing. SIGMOD Conference 1992: 331-340
  14. V. Srinivasan, Michael J. Carey: Performance of On-Line Index Construction Algorithms. EDBT 1992: 293-309
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:40:12 2009