Browse Prior Art Database

Recoverable Method for Creating an Index Which Minimizes Logging

IP.com Disclosure Number: IPCOM000036742D
Original Publication Date: 1989-Oct-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Allan, AL: AUTHOR [+4]

Abstract

Background The algorithm described here is used to create a B-tree index on a table in a relational database management system. It must allow the index creation operation to be rolled back and must provide for recovery of the index if a system crash occurs after the operation is committed.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 72% of the total text.

Page 1 of 1

Recoverable Method for Creating an Index Which Minimizes Logging

Background The algorithm described here is used to create a B-tree index on a table in a relational database management system. It must allow the index creation operation to be rolled back and must provide for recovery of the index if a system crash occurs after the operation is committed.

To create an index, the entire table must be scanned, row by row. For each row, a key is formed from the fields in the row which are part of the key. The key is then added to the index.

To provide for rollback and recovery, the straightforward approach is to log each key as it is inserted into the index, just as it would be logged when a new row is inserted into the table. The allocation of new nodes of the B-tree index must also be logged. Two problems result from this approach:
1. Performance is degraded

because writing log records for each key

is time-consuming.
2. The volume of data can flood the log. Index node

splits during key inserts, in particular, can consume

considerable log space.

The Improved Algorithm: It is not necessary to log each individual key insertion to provide atomicity of the index creation operation. An improved algorithm is as follows:
1. Lock the table exclusively and hold the lock until the

end of transaction.
2. Scan each row of the table and add a key to the index

for each record. The key insertion and node splits are

not logged. Physical page allocations continue to be

logged.
3. For...