Method and system for conducting reverse index scans

Details Method and system for conducting reverse index scans Method and system for conducting reverse index scans

2000-07-28

2003-06-10

Corrielus, Jean M. (Department: 2172)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

06578026

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to resource management systems, and more particularly to a method and system for reverse scanning of index key value ranges of records in resource management systems.
2. Description of the Related Art
A resource-management system is typically implemented using a computer or a network of computers and a server, having storage capability and appropriate software. A database management system is one type of resource-management system.
A typical database management system includes both database files and index files. The database files store data in the rows and columns of tables stored on data pages. In such a table, the rows may correspond to individual records while the columns of the table represent attributes of the records. For example, in a customer information table of a database management system, each row might represent a different customer, while each column represents different attributes of the customers such as the name of each customer, the amount owed by each customer and the cash receipts received from each customer.
Instead of providing for direct sorting and searching of the records in the tables, the database management system relies on the index files, which contain information or pointers about the location of the records in the tables stored in the database files. The index can be searched and sorted (scanned) much more rapidly than can the database files. An index is scanned through transactions in which criteria are stipulated for selecting records from a table. These criteria include keys, which are the attributes by which the database finds the desired record or records using the index. The actions of a transaction that cause changes to recoverable data objects are recorded in a log. Each log record is assigned a unique log sequence number (LSN) when the record is written to the log.
All data is stored in tables on a set of data pages that are separate from the indexes. All of the indexes for a table contain only the key values and record identifiers (RIDs) of records containing these key values. A RID consist of a data page ID concatenated with a sequence number unique within that range. One common type of index is a B-tree having N levels of nodes or pages. The starting node at the top of the tree is called the root node and defines the interval of key values that the B-tree index covers. In the successive lower levels of nodes before the lowest level of nodes, this key value interval is broken up into key value sub-intervals. Finally, the leaf nodes or pages in the lowest level of the tree contain the individual key values within the interval, together with the associated record (row) identifications (RIDs) that enable the records having those key values as attributes to be located in the tables of the database files. The leaf pages of an index contain entries (keys) each of which is conceptually a {key-value, RID} pair where the RID is treated as if it were an extra key field. A non-unique index is one that may contain more than one key with the same key value. In contrast, a unique index cannot contain more than one key with the same key value. Keys are maintained in an ascending collating order on all key fields, including the RID. Leaf pages alone contain next- and previous-page pointers so that ascending and descending range scans can be supported. Non-leaf pages contain child page pointers.
FIG. 17
shows a non-unique B-tree index.
Where a non-unique index contains duplicate instances of a key value, the key value is stored only once on each leaf page. This single value is followed by as many RIDs as would fit on that page—this is called a cluster of duplicates. On leaf page 3 of the B-tree of
FIG. 17
, the key value P is followed by the cluster of duplicates
12
and
13
. This cluster of duplicates
12
and
13
is notionally considered to be two keys: key <P,
12
> and key <P,
13
>.
Even if the actual data processor time required is very small, some transactions may require a considerable amount of time as data must be retrieved from storage facilities and must be input by the user requesting the transaction. Accordingly, it is important that the database management system permit the data processor to interleave different transactions. A set of transactions are interleaved when some transactions of the set are performed between separated operations of other transactions in the set as multiple users or application programs share common resources. This, however, may lead to problems, as the results that a transaction yields may depend on the way in which the transactions are interleaved, and may change if the transaction is re-executed for any reason.
Consider two transactions regarding the above-described customer information table. The two transactions have operations that are being interleaved. A payment has been received from a customer A and a first record-adjustment transaction is decreasing the accounts receivable attribute and increasing the cash receipts attribute for A by the amount of the payment. Concurrently, a second asset-totaling transaction is calculating the total assets of the company including both total accounts receivable and total cash receipts. Both of these transactions are performed though a number of interleaved operations. Depending on how the operations of the transactions are interleaved, the second transaction may sum the accounts receivable attribute column before the amount paid is removed from the row corresponding to A and may sum the cash receipts column after the amount paid has been added to such row, resulting in the amount aid being summed twice and the total assets of the company being overstated by the amount paid.
The degree to which the results provided by a transaction may differ depending on the manner in which different transactions are interleaved depends on the isolation level of the system. Interleaving different transactions may impact on the results returned by a transaction in the following ways:
Lost updates: Transactions T
1
and T
2
both read data from the same record (row) and both update the same attribute (column) of such record. If T
1
updates the attribute, and then T
2
subsequently updates the same attribute based on T
2
's read of the record prior to T
1
updating the attribute, then T
1
's update of the attribute will be lost.
Access to uncommitted data: Transaction T
1
updates a value in a database and Transaction T
2
reads that value before T
1
commits. Subsequently, T
1
rolls back. T
2
's calculations are based on data that is no longer recorded and is presumably invalid.
Nonrepeatable reads: Transaction T
1
reads a row, then performs other operations. After T
1
has read the row, Transaction T
2
changes the row. If T
1
subsequently tries to read this row again, a different result will be returned then from the first time.
Phantom Read: Transaction T
1
reads a set of rows based on some search criterion and then performs other operations. After T
1
has read the set of rows, Transaction T
2
updates existing rows or inserts new rows. T
1
subsequently repeats the search and returns results that differ from those originally returned.
Different isolation levels block some or all of these potential problems. Two such different isolation levels are cursor stability (CS) and repeatable read (RR). RR locks all rows an application references within a transaction. No other transactions can update, delete or insert a row that would affect the results of the transaction that requested and received the lock. Accordingly, at RR isolation levels none of the above-described problems can arise. In contrast, at CS isolation levels any row accessed by a transaction is locked while the cursor is positioned on that row. This lock remains in effect until the next row is fetched. However, if any data in the row is changed, then this lock is held until the change is committed. Accordingly, at both the CS and RR isolation levels, only committed data is returned to a s

Affiliated with

Also associated with

Rating

Method and system for conducting reverse index scans 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 and system for conducting reverse index scans, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for conducting reverse index scans will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3139360