« aalto.fi « www.tkk.fi « CSE

Skip to main content


Database Research Group

Research topics (index structures)

Concurrency Control and Recovery

The classical theory of concurrency control and recovery defines transactions as strings of abstract read and write operations. In our model, the logical database is assumed to consist of records with unique keys taken from a totally ordered domain. This implies that insertions and deletions of records, and thus dynamic index structures, can be treated in the theory of transactions. We have shown how to implement effcient concurrency control and recovery algorithms within this model, when the underlying index structure is a Blink-tree. We present a new technique to implement a small structure modification such as a page split or a page merge as an atomic action, so that interrupted structure modifications are never rolled back (undone). This is in contrast to the previous algorithms, in which an interrupted tree-structure modification always has to be rolled back during restart recovery or when transaction aborts during normal processing. Our transaction model has also been extended to page-shipping client-server database systems, in which the physical database is organized as a sparse B-tree index; and to the multiversion B+-tree, an asymptotically optimal multiversion index structure.

Publications:


Multiversion indexes

Current database systems require access to past database states, in addition to the current state. Efficient indexing of such historical data requires a multiversion index structure. We have based our work on the multiversion B+-tree (MVBT) of Becker et al (Bruno Becker , Stephan Gschwind , Thomas Ohler , Bernhard Seeger , Peter Widmayer: An asymptotically optimal multiversion B-tree. VLDB J. 5(4): 264-275 (1996)). The MVBT is asymptotically optimal, so that queries targeting any version of the database are as efficient as queries in a single-version B+-tree that only indexes the entries that are part of the targeted version; but the MVBT follows a single-update model, and the update cannot be rolled back. We have extended the MVBT by redesigning the structure-modification algorithms so that a single updating transaction can execute on the index concurrently with multiple read-only transactions, and we have further developed a combined index structure, the concurrent multiversion B+-tree (CMVBT), that is composed of a transactional MVBT and a separate main-memory-resident versioned B+-tree structure used to hold the updates of active transactions.

Our CMVBT index is an efficient multiversion index structure that allows the indexing of a single linear history of data evolution. We have analytically shown that the underlying transactional multiversion B+-tree index is asymptotically optimal, and thus remains optimal even in the presence of key deletions. Even though deletions in multiversion indexes must not physically remove the data history from the index, searches and range scans in later versions (after deletions) can be more efficient, if the index structure merges pages.

Publications:


Bulk operations and adaptive sorting

Another interesting question would be to allow a richer set of basic operations for the indexes. For example, bulk insertion and bulk deletion are obvious candidates for additional operations. The efficient implementation of these operations for main memory search trees have been studied in the Ph.D. Thesis by Riku Saikkonen with the application of adaptive tree sorting . We have shown how to treat online bulk deletes from large warehouse tables in the context of general transactions. The new features are a new multiple-granularity locking protocol and the use of our general concurrency control and recovery technique.

Publications: