Browse Prior Art Database

Index Mini-Pages

IP.com Disclosure Number: IPCOM000045518D
Original Publication Date: 1983-Apr-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 4 page(s) / 71K

Publishing Venue

IBM

Related People

Crus, RA: AUTHOR [+3]

Abstract

This article describes a method for operating a computing apparatus to control access to index records to assure that (a) a user requesting a repeatable read will not obtain a different set of records from an original read because another user has been permitted to modify the index within the first user's key range prior to the first user's commit point, and that (b) a user accessing an index key range will not see changes to the index resulting from an uncommitted update to the index caused by an update to an indexed record.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 41% of the total text.

Page 1 of 4

Index Mini-Pages

This article describes a method for operating a computing apparatus to control access to index records to assure that (a) a user requesting a repeatable read will not obtain a different set of records from an original read because another user has been permitted to modify the index within the first user's key range prior to the first user's commit point, and that (b) a user accessing an index key range will not see changes to the index resulting from an uncommitted update to the index caused by an update to an indexed record. The method comprises the steps of organizing the index into physical pages representing a unit of I/O transfer, each physical page including a plurality of index mini-pages; locking an index mini-page exclusive whenever a record within the mini-page is to be updated; locking an index mini-page shared whenever a record within the mini page is to be read; releasing shared locks selectively upon commit of a repeatable read operation or, otherwise, upon the user releasing position in that index mini-page; and releasing exclusive locks to index mini-pages upon commit, thereby achieving finer granularity to reduce contention for index records.

A table in an illustrative subsystem can have one or more indexes defined on it, each of which is an ordering of parts (keys) of the row of the table and is used to access certain rows when the keys are known.

An index is implemented with a "tree" structure consisting of leaf pages and non-leaf pages. A page is a physical unit of transfer between main storage and secondary storage (DASD). In the illustrative subsystem, a page in an index is always 4096 bytes in size.

A non-leaf page contains a list of page numbers of other index pages, along with the highest key values for those pages: see original In the above example, any key that is large than "Highest key of page 7" can be found in page 10.

A leaf Page is the lowest level in the index tree. It consists of keys and their associated row addresses (pointers to the rows in the table that have the given key value).

A user of such a subsystem can use a command of the type CREATE INDEX to make an index available to the subsystem. The subsystem then controls when and how that index is used, and maintains the index. The user has no control over when an index is used to service any given request.

Multiple tasks can access the same index at the same time. Tasks that are reading data can share all parts of the index. Tasks that update a leaf page in the index must lock out all other tasks from that leaf page, including read-only tasks. Normally this is done by locking leaf pages in the "Exclusive" state. Readers lock pages in the "Shared" state. If someone already holds an exclusive page lock, no one else is allowed to acquire an exclusive or shared lock on that page until the exclusive lock is released. If someone already holds a shared page lock, anyone requesting an exclusive lock on that page will wait until all...