Browse Prior Art Database

Mass Delete of Index Structures

IP.com Disclosure Number: IPCOM000036049D
Original Publication Date: 1989-Aug-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Haderle, DJ: AUTHOR [+2]

Abstract

An algorithm is disclosed for the deletion of all entries in a data base management system index structure. The algorithm minimizes the system resources required for the delete operation and assures the atomicity of the change through the selective deferral of normally required logging.

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

Page 1 of 2

Mass Delete of Index Structures

An algorithm is disclosed for the deletion of all entries in a data base management system index structure. The algorithm minimizes the system resources required for the delete operation and assures the atomicity of the change through the selective deferral of normally required logging.

Data base management systems (DBMSs) typically include special protocols which assure that all updates (transactions) appear atomic to the user. That is, they either occur completely or, if catastrophic system failure prevents the completion of the transaction, the update is backed out. The write-ahead log protocol is such a protocol 1.

If all of the records in a table (file) are to be deleted, then all corresponding entries in all accompanying indexes must be deleted as well. Normally, this would require that each index entry be individually accessed, logged (assuming write-ahead log protocol), and deleted.

If the write-ahead log protocol is observed, the following algorithm can be used for the deletion of all entries in an index structure. The algorithm is described in terms of a tree-structured index [2,3], but is applicable to other index structures as well. (1) Mark in memory the occurrence of the mass delete

of the index.

(2) Mark all index pages (except the root page) as

unallocated in an availability/occupancy space map

assigned to the index.

(3) Reformat the root page of the index so it will

appear empty.

(4) At commit time, unmark (in memory) the mass

deletion of the index.

(5) Whenever index pages are to be allocated and if

the index is marked in memory as having been the

subject of a mass delete, then first log (saving

the former contents of) the page before it is

reformatted for use.

This method ensures that the former contents (data) of the index are available until commit. This data is available in either the index pages (if no other activity followed the mass delete but preceded the transaction commit) or in the log (if the page was reused).

The significant attributes of this method are:

(1) While observing the write-ahead lo...