C. Mohan
Inderpal Narang
ABSTRACT
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 operations 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 of operation restartable. These include algorithms for the sort and merge phases of sorting.
- CHHIM91.Cheng, J., Haderle, D., Hedges, R., lyer, B., Messinger, T., Mohan, C., Wang, Y. An Efficient Hybrid Join Algorithm: o 9BZ Prototype, Proc. 7th International Conference on Data Engineering, Kobe, April 1991. An expanded version of this paper is available as IBM Research Report RJ7884, IBM Almaden Research Center, December 1990. Google Scholar
Digital Library
- DeGr90.DeWitt, D., Gray, J. PorolZel Dotobase Systems: The Future of Dotabose Processing or o Possing Fad?, ACM SIGMOD Record, Volume 19, Number 4, Decemeber 1990. Google ScholarDigital Library
- Gray78.Gray, J. Notes on Doto Bose Operoting Systems, In Operating Systems - An Advanced Course, R. Bayer, R. Graham, and G. Seegmuller (Eds.), LNCS Volume 60, Springer-Verlag, 1978. Google ScholarDigital Library
- Knut73.Knuth, D. The Art of Computer Programming: Volume 3, Addison-Wesley Publishing Co., 1973. Google ScholarDigital Library
- MHLPS92.Mohan, C., Haderle, D., Llndsay, B., Pirahesh, H., Schwarz, P. ARIES: A Tronsoct ion Recovery Method Supporting Fine-6ronulority Locking ond Portiol Rol Zbocks Using Write-Aheod Logging, ACM Transactions on Database Systems, Vol. 17, No. 1, March 1992. Also available as IBM Research Report RJ6649, IBM Almaden Research Center, January 1989. Google ScholarDigital Library
- Moha90a.Mohan, C.ARIE$/KVL: A Key-VoZue Locking Hethod for Concurrency ControZ of HuZ t ioction Tronsoct ions Operating on B-Tree Indexes, Proc. 16th International Conference on Very Large Data Bases, Brisbane, August 1990. A different version ot this paper is available as IBM Research Report RJ7008, IBM Almaden Research Center, September 1989. Google ScholarDigital Library
- Moha90b.Mohan, C. Commit LSN: A Novel ond SimpZe Hethod for Reducing Locking ond Lotching in Tronsoction Processing Systems, Proc. 16t1~ International Conference on Very Large Data Bases, Brisbane, August 1990. Also available as IBM Research Report RJ7344, IBM Almaden Research Center, February 1990. Google ScholarDigital Library
- Moha92.Mohan, C. Supporting Very Lorge TobZes, Proc. 7th Brazilian Symposium on Database Systems, Porto Alegre, May 1992.Google Scholar
- MoLe92.Mol~an, C., Levine, F. ARIES~IN: An Efficient ond High Concurrency Index Honogement Method Us ing Write-Aheod Logging, Proc. ACM SlGMOD International Conference on Management of Data, San Diego, June 1992. A longer version ot this paper is available as IBM Research Report RJ6846, IBM Almaden Research Center, August 1989. Google ScholarDigital Library
- MoPL92.Mohan, C., Pirahesh, H., Lorle, R. Efficient end FZexibZe Hethods for Tronsient Versioning of Records to Avoid Locking by Reod-Only Tronsocttons, Pro~. ACM SlOMOD International Conference on Management of Data, San Diego, June 1992. Google ScholarDigital Library
- Ober80.Obermarck, R. IHS/V5 Progrom isolotion Feoture, IBM Research Report RJ2879, IBM San Jose Research Laboratory, July 1980.Google Scholar
- PMCLS90.Ptrahesh, H., Mohan, C., Cheng, J., Llu, T.S., Sellnger, P. PurolleZtsm in ReZotionol Ooto Bose Systems: Architecturol Issues ond Design Approoches, Proc. 2nd International Symposium on Databases in Parallel and Distributed Systems, Dublin, July 1990. An expanOeO version of this paper Is available as IBM Research Report RJ7724, IBM Almaden Research Center, October 1990. Google ScholarDigital Library
- SiSU91.Silberschatz, A., Stonebraker, M., UIIman, J. (Eds.) Ootobose Systems: Achievements ond Opportunities, Communications of the ACM, Vol. 34, No. 10, October 1991. Google ScholarDigital Library
- SrCa91.Srinivasan, V., Carey, M. On-Line Index Construction Algorithms, Proc. 4th International Workshop on High Performance Transaction Systems, Asllomar, September 1991.Google Scholar
- TeGu84.Teng, J., Gumaer, R. Honogtng IBH Dotobose 2 Buffers to Hoximize Performonce, IBM Systems Journal, Vol. 23, No. 2, 1984.Google ScholarDigital Library
Index Terms
- Algorithms for creating indexes for very large tables without quiescing updates
Recommendations
Algorithms for creating indexes for very large tables without quiescing updates
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 ...
Updates for structure indexes
VLDB '02: Proceedings of the 28th international conference on Very Large Data BasesThe problem of indexing path queries in semistructured/XML databases has received considerable attention recently, and several proposals have advocated the use of structure indexes as supporting data structures for this problem. In this paper, we ...
Inverted indexes vs. bitmap indexes in decision support systems
CIKM '09: Proceedings of the 18th ACM conference on Information and knowledge managementBitmap indexes are widely used in Decision Support Systems (DSSs) to improve query performance. In this paper, we evaluate the use of compressed inverted indexes with adapted query processing strategies from Information Retrieval as an alternative. In a ...
Comments