Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-12-14
2003-11-11
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06647386
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method, system, and program for performing a reverse index scan and, in particular, serializing access to an index when performing a reverse index scan.
2. Description of the Related Art
Data records in a relational database management system (RDBMS) are maintained in tables, which are a collection of rows all having the same columns. Each column maintains information on a particular type of data for the data records which comprise the rows. One or more indexes may be associated with each table. An index is an ordered set of pointers to data records in the table based on the data in one or more columns of the table. An index is comprised of rows or index entries which include an index key and a pointer to a database record in the table having the key column values of the index entry key. An index key is comprised of key columns that provide an ordering to records in a table. The index key columns are comprised of the columns of the table, and may include any of the values that are possible for that particular column. Columns that are used frequently to access a table may be used as key columns.
Index entries are often stored in a B-tree data structure. A B-tree consists of a single root page and a number of leaf and non-leaf pages. The leaf pages store the index entries. Each index entry consists of key values and the physical address or identifier of the row or record, i.e., a RID, in the data base table which has the key value in its key columns. A non-leaf page stores key values and pointers to other index pages. An index may be searched for matching key values by an index scan. A scan of the index traverses from the root page down to the leaf page looking for the index entries that have the matching keys. The pages which store the index entries are maintained in a storage device, such as a hard disk drive or other non-volatile memory accessible to the database program.
A query can be made against an index to retrieve one or more index keys using a search key that includes values for each of the key columns. The search locates the first index entry that has a key value that matches the search key, i.e., the values in the key columns in the search key match the values for the key columns in the index entry.
A reverse index scan is a scan that moves backwards through the index keys in the pages at the leaf node level of a B-tree index. The co-pending and commonly assigned patent application entitled “Method and System for Conducting Reverse Index Scans”, to Leslie Anne Cranston, Catherine S. McArthur, and Matthew Albert Huras, having U.S. application Ser. No. 09/628,600 and filed on Jul. 28, 2000, describes an implementation for reverse index scans. This Canadian patent application is incorporated herein by reference in its entirety. One problem that arises in reverse index scanning, which is addressed in the above incorporated Canadian patent application, is deadlocking. For example, deadlocking occurs when a reverse index scan holds a read or non-exclusive shared latch (“s-latch”) for a page, e.g., page n, and seeks an s-latch for the previous page (n−1). At the same time, another index update transaction holds an exclusive latch (“x-latch”) on page (n−1) and seeks an x-latch on page n in order to split the page n. In such a situation a deadlock would occur because the update transaction needs a latch on page n, but cannot obtain such latch to proceed because the reverse scan transaction holds the s-latch for page n. Likewise, the reverse scan transaction cannot obtain the s-latch needed on page (n−1) to proceed because the update transaction holds the x-latch to page (n−1). Thus, both transactions are waiting for the other to release the latch, thereby resulting in a deadlock.
There is a need in the art for improved techniques for handling reverse scanning in a manner that prevents a deadlock from occurring and, at the same time, optimizes system performance during reverse index scans.
SUMMARY OF THE PREFERRED EMBODIMENTS
Preferred embodiments disclose a system, method, and program for performing a reverse scan of an index implemented as a tree of pages. Each leaf page includes one or more ordered index keys and previous and next pointers to the previous and next pages, respectively. The scan is searching for keys in the leaf pages that satisfy the search criteria. If a current index key is a first key on a current page, then a request is made for a conditional shared latch on a previous page prior to the current page. If the requested conditional shared latch is not granted, then the latch on the current page is released and a request is made for unconditional latches on the previous page and the current page. After receiving the latches on the previous and current pages, a determination is made of whether the current index key is on the current page if the current page was modified since the unconditional latch was requested. The current index key is located on the current page if the current index key is still on the current page. A determination is then made of whether the located current index key satisfies the search criteria.
Still further, a determination is made of whether the previous page was involved in a structural modification if the current page was not modified. If the previous page was not involved in a structural modification, then a last key on the previous page is accessed. In such case, the accessed previous page becomes the current page and the accessed last key becomes the current key in continuing the reverse index scan.
Yet further, if the previous page was involved in a structural modification, then the current index key is saved and a request is made for a tree latch to prevent another process from performing a subsequent structural modification to the tree. After receiving the tree latch, a determination is made of a prior non-leaf page that includes the saved current index key. A forward traversal is made from the determined non-leaf node to a leaf page including the saved current index key.
In yet further embodiments, when initially traversing the tree to access the current page, page stack information on the non-leaf pages traversed is saved including key bounds of the non-leaf pages. A relationship of the non-leaf pages can be determined from the page stack. In such case, determining the prior non-leaf node that includes the current index key comprises using the page stack to determine a closest non-leaf page including the saved current index.
Preferred embodiments provide an algorithm and data structures for performing reverse index scans that avoids a deadlock from occurring with a transaction structurally modifying the arrangement of pages in the tree. In the preferred embodiments, the reverse scan transaction releases a shared latch on the current page to allow a structural modification to the tree affecting the current page to complete the update. Further, preferred embodiments use a tree latch system to prevent subsequent tree structure modifying transactions from starving the reverse index scan. To prevent starvation, the reverse index scan is provided a latch on the entire tree after any preexisting structure modifying transactions complete modifying the arrangement of pages in the tree. This latch prevents subsequent structure modifying transactions from blocking the reverse index scan. After the reverse index scan moves to the key prior to the current key, it may then release the tree latch to allow structure modifying transactions access to the tree.
REFERENCES:
patent: 5123104 (1992-06-01), Levine et al.
patent: 5574902 (1996-11-01), Josten et al.
patent: 5594899 (1997-01-01), Knudsen et al.
patent: 5717918 (1998-02-01), Takayama et al.
patent: 5717919 (1998-02-01), Kodavalla et al.
patent: 5758146 (1998-05-01), Schiefer et al.
patent: 5826253 (1998-10-01), Bredenberg
patent: 5832484 (1998-11-01), Sankaran et al.
patent: 5835904 (1998-11-01), Vicik et al.
patent: 5918224 (1999-06-01), Bredenberg
patent: 6363387 (200
Hollines, III Robert J.
Lee Christina Marie
Levish David L.
Shadduck Michael R.
Wang Yufen
Konrad Raynes & Victor & Mann LLP
Metjahic Safet
Nguyen Cam Linh
Victor David W.
LandOfFree
Method, system, and program for reverse index scanning does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method, system, and program for reverse index scanning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system, and program for reverse index scanning will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3119763