Multiversion two phase locking (MV2PL) provides online serializable queries without introducing the long blocking delays that can occur with conventional two phase locking (2PL). MV2PL requires indexing structures, however, that are capable of supporting multiple versions of data. We present several options for extending single version indexing schemes for use with MV2PL. These basic approaches are largely orthogonal to the underlying indexing structure (e.g., hashing or B+ trees). The options considered differ in where they place version selection information (i.e., references to individual versions); this information is placed either with the data or with the index entries of one or more of the indices. We also present the results from a performance study that show that placing the version selection information with the data is usually the best option, since it keeps the indices smaller and thus enables a larger fraction of the index pages to remain cached in the buffer pool.

The authors discuss a novel approach to multiversion concurrency control that allows high-performance transaction systems to support long-running queries. The approach extends the multiversion locking algorithm developed by Computer Corporation of America by using record-level versioning and reserving a portion of each data page for caching prior versions that are potentially needed for the serializable execution of queries; on-page caching also enables an efficient approach to garbage collection of old versions. In addition, view sharing is introduced, which has the potential for reducing the cost of versioning by grouping together queries to run against the same transaction-consistent view of the database. Results from a simulation study that indicate that the approach is a viable alternative to level-one and level-two consistency locking when the portion of each data reserved for prior versions is chosen appropriately are presented.>