Algorithms for creating indexes for very large tables without quiescing updates

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 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.