Database system providing methodology for optimizing latching/copying costs in index scans on data-only locked tables

[0002] The present application claims the benefit of priority from and is related to the following commonly-owned U.S. provisional application: application Ser. No. 60/105,034, filed Oct. 20, 1998. The disclosure of the foregoing application is hereby incorporated by reference in its entirety, including any appendices or attachments thereof, for all purposes.

[0003] A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

[0004] The present invention relates generally to information processing environments and, more particularly, to retrieval and processing of information stored in a data processing system, such as a Database Management System (DBMS).

[0005] Computers are very powerful tools for storing and providing access to vast amounts of information. Computer databases are a common mechanism for storing information on computer systems while providing easy access to users. A typical database is an organized collection of related information stored as “records” having “fields” of information. As an example, a database of employees may have a record for each employee where each record contains fields designating specifics about the employee, such as name, home address, salary, and the like.

[0006] Between the actual physical database itself (i.e., the data actually stored on a storage device) and the users of the system, a database management system or DBMS is typically provided as a software cushion or layer. In essence, the DBMS shields the database user from knowing or even caring about underlying hardware-level details. Typically, all requests from users for access to the data are processed by the DBMS. For example, information may be added or removed from data files, information retrieved from or updated in such files, and so forth, all without user knowledge of underlying system implementation. In this manner, the DBMS provides users with a conceptual view of the database that is removed from the hardware level. The general construction and operation of a database management system is known in the art. See e.g., Date, C., An Introduction to Database Systems, Volume I and II, Addison Wesley, 1990; the disclosure of which is hereby incorporated by reference.

[0007] DBMS systems have long since moved from a centralized mainframe environment to a de-centralized or distributed environment. One or more PC “client” systems, for instance, may be connected via a network to one or more server-based database systems (SQL database server). Commercial examples of these “client/server” systems include Powersoft™ clients connected to one or more Sybase Adaptive Server™ database servers. Both Powersoft™ and Sybase Adaptive Server™ are available from Sybase, Inc. of Emeryville, Calif.

[0008] As the migration to client/server continues, each day more and more businesses are run from mission-critical systems which store information on server-based SQL database systems, such as Sybase Adaptive Server™. As a result, increasingly higher demands are being placed on server-based SQL database systems to provide enterprise-wide decision support. Accordingly, there is much interest in improving the performance of such system, particularly in terms of execution speed and reliability.

[0009] The present invention provides a methodology for using look ahead lists to significantly reduce latching costs associated with index pages in non-covered index scans, without the necessity of using a shadow page. (For covered queries, the datarow is not retrieved; all columns needed by the queryproc (query processing module) are provided from the index row.) In many cases, the copying costs are eliminated too.

[0010] In database systems, a “B+-tree” is a common indexing scheme that is employed. A primary B+-tree has data records at the leaf row, while a secondary B+-tree has index keys, where a key consists of a key value and a ROWID of the data record. The index manager of a database system typically provides the following interface methods to facilitate scans:

[0011] (1) startscan( ): to start a scan on an index, optionally with some search arguments (or SARGs), which are simple conditions that can be expressed in the form of column <relop> value, where relop can be <, >, <=, >=, !=or =and column is a column in the index. If the index is on ‘name’ column of an Employee table, name=“Joe” is an example of a SARG.

[0012] (2) getnext( ): to retrieve ROWID from the next qualifying index key. This ROWID is used by the system's data layer to retrieve the data record.

[0013] (3) endscan( ): to terminate the scan and clean up resources.

[0014] A conventional approach for implementing getnext( ) would be as follows:

[0015] However, in the above approach, there is a latch/unlatch operation for every qualifying key. If there are 100 qualifying keys on a page, the latched/unlatched cycle occurs 100 times.

[0016] Some systems solve this problem by using a shadow page. In that scheme, when a page is latched, all qualifying keys are copied to shadow page. Subsequently, the rows are returned from shadow page, avoiding the latch requests on the original page. However, the shadow page is a memory overhead. The present invention, in contrast, provides a methodology that solves this problem without using a shadow page. In addition, it also saves the cost of copying qualifying keys in some cases.

[0017] The preferred approach may be summarized as follows.

[0018] (1) The database system uses a “look ahead” list (LA) to save up to a preset number (e.g., 60) of ROWIDs (row identifiers) from the qualifying index keys. Since a ROWID is typically small (e.g., about 6 bytes), the space needed to store 60 ROWIDs is typically much smaller than the underlying page size (which typically range from 2K to 32K in systems). Thus, in step 3 above, instead of finding just one next qualifying key, up to a selected number (e.g., 60) of qualifying keys on the current page are found and the ROWIDs from them are stored in the look ahead list.

[0019] (2) In addition to space needed for look ahead list, the approach uses space to store one index key.

[0020] The scan is considered to be in NOCOPY mode if it satisfies the following conditions:

[0021] 1. The scan is not for a cursor statement, AND

[0022] 2. The scan is required to hold a lock on its current row, AND

[0023] 3. The scan is not for an update statement which is modifying one of the index columns.

[0024] Otherwise, it is considered to be in DCOPY mode.

[0025] If the scan is in NOCOPY mode, then copying every qualifying key is not needed. In such a case, STEP 5 is not needed. If a restart is needed, i.e., in STEP 2A, the index key is built from the data record which corresponds to last ROWID returned. On the other hand, if the scan is in DCOPY mode, then STEP 5 is omitted if latch is not being held on the index page. Instead, the index key is built from the data record and copied while holding the latch on data page. If the data layer finds that the data record does not qualify, then there is no need to build or copy the index key.

[0026] The following definitions are provided for purposes of illustration.

[0027] FIG. 1A is a block diagram illustrating a computer system in which the present invention may be embodied.

[0028] FIG. 1B is a block diagram illustrating a software subsystem for controlling the operation of the computer system of FIG. 1A.

[0029] FIG. 2 is a block diagram of a client/server system in which the present invention is preferably embodied.

[0030] FIG. 3 is a block diagram of a leaf page of an index, for illustrating ICOPY mode.

[0031] FIGS. 4A-B are block diagrams illustrating shadow buffers for the ICOPY mode for both a SR (serializability isolation level) scan and a non-SR scan.

[0032] The following description will focus on the presently preferred embodiment of the present invention, which is operative in a network environment executing client/server database applications. The present invention, however, is not limited to any particular application or environment. Instead, those skilled in the art will find that the present invention may be advantageously applied to any application or environment requiring optimization of information retrieval. The description of the exemplary embodiments which follows is, therefore, for the purpose of illustration and not limitation.

[0033] Standalone System Hardware

[0034] The invention may be embodied on a computer system such as the system 100 of FIG. 1A, which comprises a central processor 101, a main memory 102, an input/output controller 103, a keyboard 104, a pointing device 105 (e.g., mouse, track ball, pen device, or the like), a screen display device 106, and a mass storage 107 (e.g., hard or fixed disk, optical disk, magneto-optical disk, or flash memory). Processor 101 includes or is coupled to a cache memory 109 for storing frequently accessed information; memory 109 may be an on-chip cache or external cache (as shown). Additional output device(s) 108, such as a printing device, may be included in the system 100 as desired. As shown, the various components of the system 100 communicate through a system bus 110 or similar architecture. In a preferred embodiment, the system 100 includes an IBM-compatible personal computer system, available from a variety of vendors (including IBM of Armonk, N.Y.).

[0035] Standalone System Software

[0036] Illustrated in FIG. 1B, a computer software system 150 is provided for directing the operation of the computer system 100. Software system 150, which is stored in system memory 102 and on disk memory 107, includes a kernel or operating system (OS) 140 and a window-based or graphical user interface shell 145. One or more application programs, such as application software 155, may be “loaded” (i.e., transferred from storage 107 into memory 102) for execution by the system 100. The system also includes a user interface 160 for receiving user commands as input and displaying user data as output.

[0037] Also shown, the software system 150 includes a Relational Database Management System (RDBMS) front-end or client 170. The RDBMS front-end 170 may comprise any one of a number of database front-ends, including PowerBuilder™, dBASE®, Paradox®, Microsoft® Access, or the like. In an exemplary embodiment, the front-end will include SQL access drivers (e.g., Borland SQL Links, or Microsoft ODBC drivers) for accessing SQL database server tables in a Client/Server environment.

[0038] Client/Server Database Management System

[0039] While the present invention may operate within a single (standalone) computer (e.g., system 100 of FIG. 1A), the present invention is preferably embodied in a multi-user computer system, such as a client/server system. FIG. 2 illustrates the general structure of a Client/Server Database System 200 suitable for implementing the present invention. As shown, the system 200 comprises one or more Client(s) 210 connected to a Server 230 via a Network 220. Specifically, the Client(s) 210 comprise one or more standalone Terminals 211 connected to a Database Server System 240 using a conventional network. In an exemplary embodiment, the Terminals 211 may themselves comprise a plurality of standalone workstations, dumb terminals, or the like, or comprise personal computers (PCs) such as the above-described system 100. Typically, such units would operate under a client operating system, such as Microsoft Windows for PC clients.

[0040] The Database Server System 240, which comprises Sybase Adaptive Server™ (Sybase of Emeryville, Calif.) in an exemplary embodiment, generally operates as an independent process (i.e., independently of the clients), running under a server operating system such as Microsoft Windows NT (Microsoft Corp. of Redmond, Wash.), NetWare (Novell of Provo, Utah), or UNIX (Novell). The Network 220 may be any one of a number of conventional network systems, including a Local Area Network (LAN) or Wide Area Network (WAN), as is known in the art (e.g., using Ethernet, IBM Token Ring, or the like). The Network includes functionality for packaging client SQL calls and its parameters into a format (of one or more packets) suitable for transmission across a cable or wire, for delivery to the Database Server 240.

[0041] Client/server environments, database servers, and networks are well documented in the technical, trade, and patent literature. For a general discussion of database servers and client/server environments, see, e.g., Nath, A., The Guide to SQL Server, Second Edition, Addison-Wesley Publishing Company, 1995. For a general introduction to a Local Area Network operating under NetWare, see Freed, L. et al., PC Magazine Guide to Using NetWare, Ziff-Davis Press, 1991. A more detailed discussion is available in NetWare 3.x and 4.x and accompanying documentation, which is available from Novell of Provo, Utah. The disclosures of each of the foregoing are hereby incorporated by reference.

[0042] In operation, the Client(s) 210 store data in or retrieve data from one or more database tables 250, shown in FIG. 2. Typically resident on the Server 230, each table itself comprises one or more horizontal rows or records (tuples); each record comprises columns or fields of information. A database record, therefore, includes information which is most conveniently represented as a single unit. A record for an employee, for example, may include information about the employee's ID Number, Last Name and First Initial, Position, Date Hired, Social Security Number, and Salary. Thus, a typical record includes several categories or fields of information about an individual person, place, or thing. Each of these categories, in turn, represents a database field. In the foregoing employee table, for example, Position is one field, Date Hired is another, and so on. With this format, tables are easy for users to understand and use. Moreover, the flexibility of tables permits a user to define relationships between various items of data, as needed.

[0043] In operation, the Clients issue one or more SQL commands to the Server. SQL commands may specify, for instance, a query for retrieving particular data (i.e., data records meeting the query condition) from the table 250. The syntax of SQL (Structured Query Language) is well documented; see, e.g., the abovementioned An Introduction to Database Systems. In addition to retrieving the data from Database Server tables, the Clients also include the ability to insert new rows of data records into the table; Clients can also modify and/or delete existing records in the table.

[0044] For enhancing the speed in which the Database Server stores, retrieves, and processes particular data records, the Server maintains one or more database indexes 245 on the table. A database index, typically maintained as a B-Tree data structure, allows the records of a table to be organized in many different ways, depending on a particular user's needs. An index may be constructed as a single disk file storing index key values together with unique record numbers. The former is a data quantity composed of one or more fields from a record; the values are used to arrange (logically) the database file records by some desired order (index expression). The latter are unique pointers or identifiers to the actual storage location of each record in the database file. Both are referred to internally by the system for locating and displaying records in a database file.

[0045] As clients insert more and more data into the table 250, the index 245 continues to grow. Two parts of the Database Server System 240 play a central role in the accessing and managing tables and indexes: Access Methods 241 and Page Manager 243. For example, when a request from a client to insert a new row (i.e., record) into the table occurs in the system, the Access Methods 241 employ the index 245 for determining on which of the leaf-level pages (e.g., clustered index) a particular row should be inserted. If sufficient space exists on the particular page located, then the Access Methods do not require the assistance of the Page Manager. The row is simply inserted into the located page, at the appropriate storage space or “slot” available at that page. The process may continue in this manner until a row arrives for insertion which cannot fit on the existing page. Here, the Access Methods seek assistance from the Page Manager for allocating a new page (which is now needed, at this point, for the table). As the client continues to add more and more rows, the table continues to grow and the process repeats. This operation occurs very frequently in practically all on-line transaction processing (OLTP) systems. The following discussion focuses on modifications to the system 200, for providing improved query execution performance.

[0046] Optimizing Latching/Copying Costs in Index Scans on Data-Only Locked Tables

[0047] A. Overview

[0048] In database systems, a “B+-tree” is a common indexing scheme that is employed. A primary B+-tree has data records at the leaf row, while a secondary B+-tree has index keys, where a key consists of a key value and a ROWID of the data record. The index manager of a database system typically provides the following interface methods to facilitate scans:

[0049] (1) startscan( ): to start a scan on an index, optionally with some search arguments (or SARGs), which are simple conditions that can be expressed in the form of column <relop> value, where relop can be <, >, <=, >=, !=or =and column is a column in the index. If the index is on ‘name’ column of an Employee table, name=“Joe” is an example of a SARG.

[0050] (2) getnext( ): to retrieve ROWID from the next qualifying index key. This ROWID is used by the system's data layer to retrieve the data record.

[0051] (3) endscan( ): to terminate the scan and clean up resources.

[0052] A conventional algorithm for getnext( ) would be as follows:

[0053] However, in the above approach, there is a latch/unlatch operation for every qualifying key. If there are 100 qualifying keys on a page, the latched/unlatched cycle occurs 100 times.

[0054] Some systems solve this problem by using a shadow page. In that scheme, when a page is latched, all qualifying keys are copied to shadow page. Subsequently, the rows are returned from shadow page, avoiding the latch requests on the original page. However, the shadow page is a memory overhead. The present invention, in contrast, provides a methodology that solves this problem without using a shadow page. In addition, it also saves the cost of copying qualifying keys in some cases.

[0055] The preferred approach may be summarized as follows.

[0056] (1) The database system uses a “look ahead” list (LA) to save up to a preset number (e.g., 60) ROWIDs (row identifiers) from the qualifying index keys. Since a ROWID is typically small (e.g., about 6 bytes), the space needed to store 60 ROWIDs is typically much smaller than the underlying page size (which typically range from 2K to 32K in systems). Thus, in step 3 above, instead of finding just one next qualifying key, up to a selected number (e.g., 60) of qualifying keys on the current page are found and the ROWIDs from them are stored in the look ahead list.

[0057] (2) In addition to space needed for look ahead list, the approach uses space to store one index key.

[0058] The scan is considered to be in NOCOPY mode if it satisfies the following conditions:

[0059] 1. The scan is not for a cursor statement, AND

[0060] 2. The scan is required to hold a lock on its current row, AND

[0061] 3. The scan is not for an update statement which is modifying one of the index columns.

[0062] Otherwise, it is considered to be in DCOPY mode.

[0063] If the scan is in NOCOPY mode, then copying every qualifying key is not needed. In such a case, STEP 5 is not needed. If a restart is needed, i.e., in STEP 2A, the index key is built from the data record which corresponds to last ROWID returned. On the other hand, if the scan is in DCOPY mode, then STEP 5 is omitted if latch is not being held on the index page. Instead, the index key is built from the data record and copied while holding the latch on data page. If the data layer finds that the data record does not qualify, then there is no need to build or copy the index key.

[0064] B. General Scan Design

[0065] Note that scan code (e.g., in the context of a table or index scan) is considered separate from traversal code. Scan is a client of traversal just as insert/delete/split/shrink is also. Of course, to do an index scan, one needs to traverse the index tree to locate the starting leaf page. But when one describes scans, traversal module is considered as a black box which is just invoked from scans. Also note that RID is the pageid (page identifier) and rownum (row number) of data row. A RID is never used to refer to pageid, rownum of an index row, however.

[0066] Recall that an index row has a key value with one or more RIDs associated with it. The physical position of an index key on an index page is specified by specifying the slot#, which gives the index into an offset table and rid#, which is the position in the RID list associated with the row specified by the slot#. The following discussion focuses on the index manager part of the index scan.

[0067] 1. Latching

[0068] No logical locks are held on index pages of Data-only Locking (DOL) tables. Instead, latching is used to achieve physical consistency. With latching, the system's latch manager does not perform deadlock detection. Thus, the scan releases any latches held before blocking on a logical/address lock. Similarly, a latch also needs to be released before returning a row to the system's data layer. This is because the data layer may want to latch data pages and it is not desirable to latch data pages while holding latch on index page. One exception to this latching rule is that, if an index scan just wants to check if the page timestamp has changed, it may not latch the page. Accordingly, it is assumed that it is alright to read a page-timestamp without a latch. Note that this is very different from an allpage locked tables. There, the scan holds a lock on the current page until it is done with it and has moved to next page. Dirty reads are an exception; they use buffer manager primitives bufpredirty/bufdirty so that page is protected from writers.

[0069] 2. Repositioning

[0070] A latch an on index page needs to be released whenever the scan needs to return a row or block on a logical lock or address lock. When the scan re-acquires the latch, it may find that the page has changed. Inserts or deletes may have happened or the page may have been split or deallocated.

[0071] If the scan were to remember only the physical position on the index page, it will not be possible to resume the scan correctly. Logical position of the scan in the index i.e., key value and RID, are needed to continue the scan. If the key is known, the index can be searched to locate the key and the scan can continue from there. This process of locating the current scan position in the index is called “repositioning.” Repositioning is also done on allpage locked tables for dirty reads but a different approach, “sarg reduction” is used.

[0072] 3. Copying Issues Related to Repositioning

[0073] An index scan needs a key to do repositioning. One possible way of making a key available is to copy the current key before returning a row or blocking on a logical/address lock. When the latch is reacquired, if the page has changed, the saved key can be used to do repositioning. While it can be argued that blocking on logical/addresslock is a rare event, returning a row is not. Therefore, the act of copying a key whenever a row needs to be returned, just to handle repositionings, which are rare, incurs too much overhead. The index manager therefore just remembers the RID that was returned. When repositioning is needed, the appropriate index key is built from the corresponding data row. Note that in some cases, such as dirty reads or the like, this optimization is not possible.

[0074] 4. Other Copying Issues

[0075] For covered queries, the datarow is not retrieved. All columns needed by the queryproc (query processing module) are provided from the index row. Since the page is unlatched before returning the row, pointers to columns on the page cannot be provided to queryproc. Therefore, the index scan copies the index key and returns that to the data layer which returns it to queryproc. For non-covered queries, the queryproc takes all the columns that it needs from the datarow. The index manager just needs to return the RID to the data layer. In this case any copying that is done is just for the purpose of repositioning. Note that on allpage locked tables, dirty readers do copying. In other cases, a page lock allows the scan to directly return pointers to the columns in the page to queryproc.

[0076] 5. Latching Optimization and Look Ahead (LA) List

[0077] A simple approach to performing a scan would be latch the index page, find the next qualifying row and return the row after unlatching the page. However, this means that if the scan needs to return N rows, N latch/unlatch operations are needed, even if there are no contention at all on the index.

[0078] To optimize this, the scan maintains a look ahead list of RIDs (LA) which can hold upto BT_SIZEOFLA(defined as 60) RIDs. When the index page is latched, multiple keys are qualified and the RIDs from keys of interest are cached in LA. The first RID is returned after un-latching the page. Subsequently, while there are more RIDs to be returned in LA, if the index page timestamp has not changed, the next RID in LA can be returned without latching index page. If the index page has changed, however, the LA needs to be discarded and the scan needs to reposition itself. So, in the best case, this can reduce latching on index page by a factor of BT_SIZEOFLA, since the index page needs to be latched once for every batch of BT_SIZEOFLA qualifying keys.

[0079] 6. Serializability Issues: Range Locks

[0080] Suppose that two consecutive keys of an index are (11, R11) and (15, R15), where Rk is used to denote RID associated with key value k. A RANGE lock on R15 prevents inserts (by other transactions) between 11 and 15. This is because the inserter (module) checks for presence of RANGE lock on the key following the position of insert and blocks on it, if any. A serializability scan requests the lock manager to mark the locks requested by it as RANGE locks. Note that RANGEness is just an attribute of lock and should not be confused with type of lock i.e., shared/exclusive/update. The two are independent. It is possible to have a shared range lock or exclusive range lock or update range lock. The term SR is sometimes used for brevity to denote a scan at serializability isolation level.

[0081] 7. Other Serializability Issues

[0082] On allpage locked tables, the difference between serializability and read committed isolation levels is only in releasing locks; this is handled in access routines that release locks. At level 1, the lock is actually released while at serializability; the lock is just transferred to level 3 lock chain. It actually gets released only when the transaction commits, so the difference is transparent to the index manager. However, it is not so transparent to DOL tables.

[0083] A scan at serializability isolation level does “next key” locking for phantom protection. Therefore, in addition to the rows in the range of interest, the next row is also locked. Also, not only the qualifying rows are locked but also any intervening non-qualifying rows are locked. For example, consider a scan on a unique index on one column x looking for x>=10 and x<=20 and x!=15. Suppose that index has (11, R11), (15, R15), (19, R19), (21, R21) where Rk is used to denote RID associated with key value k. Next key locking requirement means R21 needs to be locked. This prevents inserts between 19 and 21. Row R15, which corresponds to intervening non-qualifying row, is also locked. This is needed to prevent inserts between 11 and 15. queryproc tells the index manager what type of locks need to be acquired i.e., SHARED/UPDATE or EXCLUSIVE. However, the locks on next key and intervening non-qualifying rows are always acquired in shared mode. They are needed just for phantom protection, and hence do not need to be locked in update or exclusive mode, even if the scan is for a range update or delete statement. The blocking/restart logic is also more complicated for serializability isolation level.

[0084] C. SCANS: High Level Design

[0085] The following description will discuss scan basics, including how a scan is started, what is its qualification, and how the scan is terminated. Various isolation levels and locking behaviors supported are also discussed. Next, the interaction between scans and splits/shrinks and repositionings are described, together with latching and copying issues and how they affect repositioning. Finally, index “look aside” optimization and multi-column range scan optimization are described.

[0086] 1. Scan Basics

[0087] Consider the query: select * from T where x>=10 and x<=20 and y=40. Assume that an index I(x,y) exists and is chosen by the optimizer to do the scan. The low bound for the scan is formed by putting together the low values for individual columns, if any. Low value for x is “>=10” and low value for y is “=40”. So in this example, the bound (>=10, =40) is the low bound for the scan and is passed to the traversal module. The traversal module uses the low bound to locate the starting position for the scan in the index i.e., leaf page, slot# and rid# of the index row on which scan needs to start.

[0088] Depending upon what predicates have been specified by the user, low values may or may not exist for an index column. If no low value exists for an index column, the low values of any subsequent index columns cannot be used in the low bound. If the predicate x>=10 were not there, the low value for y cannot be used in low bound. If there is no low value for the major column of the index itself, there is no low bound for the scan. In such cases, scan needs to be started on first leaf page. The high bound for the scan is formed by putting together the high values for the individual index columns, if any. In the above example, the high bound for the scan is (<=20, =40). If there is no high value for an index column, any high values for the subsequent index columns cannot be used in high bound for the scan. The high bound is used to decide when the scan can be terminated.

[0089] Once the traversal has located the starting index row for the scan, the scan starts qualifying the index rows from that point onwards until the high bound of the scan has reached 1. Qualification involves applying all the sargs 2 on index columns. In a B1 server, it also includes performing B1 MAC checks. In parallel scans, it also includes checking if the RID maps to the thread. Note that sargs on index columns that could not be used in low bound or high bound of the scan are also considered while qualifying (for example, sargs with !=operator, and the like).

[0090] Now, consider how the high bound of the scan is used to decide when to terminate the scan. In the above example, assume that the index has the following (only the key values are shown, RID is omitted for brevity).

[0091] . . . . . . . . .

[0092] [10, 40] ----------- starting point for the scan

[0093] [15, 40]

[0094] [17, 38]

[0095] [18, 40]

[0096] [19, 100]

[0097] [20, 30]

[0098] [20, 50]

[0099] . . . . . . .

[0100] Can the scan be stopped at [17, 38]? Although that row is not a qualifying row, the scan cannot be stopped because neither high value on x (i.e., 20) nor the high value on y has been reached. Can the scan be stopped at [19, 100]. No, because high value on x has not been reached. The scan cannot be stopped at [20, 30] because although high value on x has been reached, and the high value on y has not been reached. The scan can be stopped at [20, 50], because high value on x has been reached and the high value has been exceeded. There cannot possibly be more qualifying rows beyond this point.

[0101] 2. Repositionings (Restarts)

[0102] The following discusses why restarts happen and how restarts would be handled if one were not using look ahead lists and the index manager always copied the key before returning RID. This is followed by a discussion of LA, copying optimizations, and how they affect restarts.

[0103] Two new terms are introduced: “RESTART_AT” and “RESTART_AFTER”. To RESTART_AFTER some key, say [“bob”, 80.2], means traversal (module) is called to locate [“bob”, 80.2]; even if the key is found in the index, the scan skips [“bob”, 80.2] and starts qualifying from the next key in the index. On the other hand, to RESTART_AT [“bob”, 80.2] means that if the key if found in the index, the scan qualifies keys starting at [“bob”, 80.2], i.e., [“bob”, 80.2] is qualified too. Note that if traversal does not find [“bob”, 80.2] in the index, it automatically positions the scan on the next logical key in the index. Here, the scan would start qualifying at the key on which traversal positioned it and, consequently, both RESTART_AT and RESTART_AFTER would behave the same way.

[0104] (1) The Path Saved in Scan Context

[0105] During an index scan, a “scan context” data structure keeps track of current scan page i.e., pageid, pagets at the time of last latched access to the page and buffer holding current scan page. In addition, whenever the scan calls traversal (module), the level 1 index page that was searched is also remembered in the scan context. For the level 1 page, only pageid and pagets are remembered but not the buffer holding the page. Whenever the scan needs to do repositioning, it passes the saved path i.e., current scan page and the level 1 page that the scan encountered during it last traversal and their timestamps to traversal. It is traversal's responsibility to check if those pages are valid and, if so, use them for optimizing the search in the index and discard them otherwise. The following focuses on what is the restart key that the scan passes to traversal to do the repositioning.

[0106] Restarts are due to three reasons. These will now be discussed in turn.

[0107] (a) Restart W/O Lock Waits (Abbrev. R1)

[0108] All latches must be dropped before index manager returns a row to data layer. There are two cases of restart without lock wait.

[0109] A) When the data layer calls the index manager to retrieve the next row, the index manager may find that page has changed. Suppose that last row returned by the index manager was [“bob”, 80.2]. Then it needs to RESTART_AFTER [“bob”, 80.2].

[0110] B) If the index manager did not return the row locked, and if the data layer finds that the index page has changed by the time it read and latched data page, the data layer calls index manager to retrieve same row again. Suppose that the last row returned by the index manager is [“bob”, 80.2], then it needs to RESTART_AT [“bob”, 80.2].

[0111] (b) Restart with Address Lock Wait(Abbrev. R2)

[0112] When an index scan is crossing page boundaries, if the next page is undergoing shrink or if it is an SR and next page is undergoing split, it needs to block. On wakeup, if page has changed, it needs to restart. In addition, when the scan is crossing a page boundary, it may decide to deallocate the current page if it is full of committed deletes. After deallocating the page, it restarts. Although no lock wait is involved in this case, saving the key value and the repositioning is very similar to case where scan needs to block on a page being shrunk by another xact. Suppose that [“bob”, 80.2] was the last row returned by the scan and [“larry”, 90.6] is the first index key on the page being split/shrink by another xact (or the page which the scan it-self is planning to shrink). Note that [“larry”, 90.6] could be a committed deleted key. For non-SRs, the scan can RESTART_AT [“larry”, 90.6].

[0113] For SRs, however, the scan cannot RESTART_AT [“larry, 90.6]. This is because another xact (transaction) could insert an index key between [“bob”, 80.2] and [“larry”, 90.6], and that would be considered a phantom for SR. This is because SR would skip it now but would return it if the same scan were done again by the user initiating SR scan. Can the SR RESTART_AFTER [“bob”, 80.2]? There are two issues here. The first issue is as follows. If [“bob”, 80.2] were the last row returned by the scan, their still could be an arbitrarily large number of non-qualifying index keys between [“bob”, 80.2] and [“larry”, 90.6]. Since they did not qualify, they were not returned by the index manager and the keys were not copied. If the index manager were to RESTART_AFTER [“bob”, 80.2], it needs to rescan all those keys. Restarting at a point arbitrarily behind the current scan position is not acceptable since it could potentially cause starvation and infinite loops. Note, however, that SR would have locked all those intervening non-qualifying keys. So it can build index key from last locked datarow and RESTART_AFTER that key. So an SR needs to maintain RID that was last locked and use that to get restart key to avoid restarting arbitrarily behind the current scan position. This is referred to as rid_lastlock.

[0114] As a second issue, one does not want to read data page corresponding to a non-qualifying key just to get a restart key. This could mean an extra physical I/O just to do re-start. Also, if the scan is a covered query, it is not a good idea to read data page for the purpose of restart. So whenever rid_lastlock corresponds to a non-qualifying key, the system also maintains the slot# of that key on the index page and refer to it as slot_lastlock. This way, when one needs the key value corresponding to rid_lastlock, if it is a non-qualifying key, the key value can be copied from slot_lastlock slot on the index page rather than reading the data page. The slot_lastlock is tracked until the latch on that index page needs to be released. In case the scan needs to unlatch the index page before it gets its next lock (for example, because the next key is not on the current page and the next page is undergoing split or shrink and the scan needs to block on addresslock), the key value is copied from slot_lastlock and then the index page is unlatched. On the other hand, if the next lock is acquired before the latch is dropped, then rid_lastlock can be set to the RID on which the new lock was obtained. If the new lock were obtained on a non-qualifying key, slot_lastlock is also set. Otherwise, slot_lastlock is set to BT_INVALID_SLOTNUM and is not looked into. Note that rid_lastlock cannot correspond to a committed delete key. A committed deleted key can get garbage collected at any time and would not guarantee any protection against phantoms. On the other hand, a range lock on a key that is not a committed delete would block inserts between that key and preceding (non committed deleted) key.

[0115] (c) Restart with Logical Lock Wait (Abbrev. as R3)

[0116] Whenever an index scan requests a lock, if it does not get it and if SKIP_IF_NOLOCK has not been specified (i.e., it is not doing “read past” locking), then scan needs to drop all latches and sleep for the lock. On wakeup, it may find that page has changed and it needs to re-start. Suppose that [“larry”, 90.6] is the key on which the scan failed to get a lock. For non-SRs, scan can copy the key [“larry”, 90.6] and then sleep on the lock. After wakeup, if the page has changed, it can RESTART_AT [“larry”, 90.6].

[0117] For SRs, copying [“larry”, 90.6] and doing RESTART_AT that the key would not work. The reason is as follows. Suppose that the previous key locked by SR was [“bob”, 80.2], then, while the SR is sleeping on lock for 90.6, another xact (transaction) inserted a new key between these two keys. It would become a phantom for SR. So, SR again relies on rid_lastlock as in case of retsart with addresslock wait. In this example it is 80.2. If rid_lastlock corresponds to a qualifying key, when the scan returned that RID, it would have copied the key into the scan context and so there is no need to copy anything now. On the other hand, if rid_lastlock corresponds to a non-qualifying key, the key is copied from slot_lastlock and then the scan sleeps on the lock after releasing any latches held. After wakeup, if page has changed, RESTART_AFTER is done using the [“bob”, 80.2].

[0118] 3. Look Ahead (LA) RID List

[0119] In order to optimize latching, a look ahead list (LA) is used. Multiple rows are qualified and the RIDs of the rows of interest are put in LA. The benefit of LA is that, in the no contention case, the index page needs to be latched once for every BT_SIZEOFLA rows instead of once for every row.

[0120] LA can contain up to BT_SIZEOFLA (defined currently as 60) RIDs. If one wants to track the offset table slot# and RID# for all of the index keys whose RIDs are in LA, there is a 4 byte overhead for each entry in LA. So the system does not track positions of each of those index keys on index page. It is enough to track the position of index key corresponding to the last RID in LA to be able to continue the scan after all the rows in LA have been processed. The blocking module needs to know the slot# (but not the RID#) of the key corresponding to RID in LA, so only these are tracked in index scan context.

[0121] For non-SRs, LA contains only RIDs from qualifying keys. For SRs, LA contains RIDs of qualifying rows as well as the non-qualifying keys in the scan range. This is because, for SRs, non-qualifying keys also need to be locked. Although one may qualify multiple rows ahead, it is not desirable to lock them all at the time of qualification itself. The locking is done only when at the time that the system is returning the row to data layer. This is to reduce lock duration as well as for simplicity. It is not desirable for the qualification module to worry about blocking on locks or the like. LA never spans an index page i.e., all RIDs in LA are from index keys on the same index page.

[0122] There are two cases where LA is prematurely terminated. When an uncommitted delete is encountered (not for cases like dirty reads where SKIP_ALWAYS has been specified for uncommitted deletes), there is likely to be contention on the index and so it may not desirable to qualify further. Not terminating LA on encountering an uncommitted delete would add complexity to blocking/restart logic. If LA contains RIDs from both qualifying and non-qualifying keys, the scan needs to somehow remember which ones correspond to qualifying keys and which ones do not. This requires at least 60 bits. The extra complexity does not appear worthwhile. If the system terminates LA on encountering a non-qualifying key, one would need only one bit to remember whether the last entry in LA corresponds to a qualifying key or not. This means that:

[0123] (A) At most, the last RID in LA can be deleted RID. ALL others are non-deleted ones.

[0124] B) At most, the last RID in LA can correspond to a non-qualifying key.

[0125] 4. Copying Issues

[0126] As discussed in the design overview, there are two reasons why copy may be needed within the index scan module. Since the index scan module releases all latches before returning control to data layer, for covered queries the copying is needed so that the queryproc can be given stable pointers to columns that it needs. This is not an issue for non-covered queries because queryproc takes the columns that it needs from datarow in that case, and data layer provides it with stable pointers to columns in datarow. The system does not optimize copying for covered queries. The index manager makes a copy of every index key that it returns to the data layer. In addition, the index manager itself needs an index key to reposition the scan and hence the key may have to be copied for repositioning purposes. Repositioning is an issue for both covered and non-covered queries alike. The system optimizes copying the key value for non-covered queries in those cases where it is possible to build index key from datarow at the time of repositioning.

[0127] Query processing always allocates BT_MAXCOPYSPACENEEDED bytes of space for the index scan. BT_MAXCOPYSPACENEEDED is an interface macro provided by the index manager to queryproc so that queryproc can find out how much space is needed by the index scan module.

[0128] 5. Copying Modes

[0129] There are three basic modes with respect to copying. Each will be discussed in turn.

[0130] (a) ICOPY Mode

[0131] (1) General

[0132] This is used for covered queries (note that some trace flag may force ICOPY mode which is not discussed here). A shadow buffer is maintained and used to store the key values corresponding to the RIDs in LA, except that if the last RID corresponds to non-qualifying row (SR only), the key value corresponding to it is not stored. In that case, space allocated by the queryproc is used to store LA and also the offsets of the index keys corresponding to the RIDs in LA in the shadow buffer. The index keys are copied into shadow buffer at the same offsets as the original page. Thus, the space needed is the space for LA plus the space for storing BT_SIZEOFLA offsets, which is 6*60+60*2 (i.e., 480 bytes total). The shadow buffer is obtained by taking a buffer from buffer cache. Consider the example is shown in FIG. 3. A leaf page of an index on first name (fixed length column) is shown, where the scan is looking for name>=“bob” and name!=“Jackson”.

[0133] (2) Non-SRs

[0134] LA will contain RIDs corresponding to bob and kate: [80.2, 80.4, 50.7]. The shadow buffer would contain two keys bob and kate at offsets 138 and 98 respectively (i.e., the same offsets as the original leaf page), as shown in FIG. 4A. Note that there is no offset table and also rows have been copied in non-dup format.

[0135] (3) SRs

[0136] Recall that for SRs, even the non-qualifying keys need to be locked. Also, LA is terminated when an entry corresponding to a non-qualifying key is put. LA will contain RIDs corresponding to bob and jackson: [80.2, 80.4, 100.1]. A bit is set in index scan context (BT_SC_LASTRID_NOQUAL) to remember that the last entry in LA is a non-qualifying one so that it will not be returned to data layer. The shadow buffer appears as shown in FIG. 4B. “jackson” is not copied since it is a non-qualifying key value although its RID has been put in LA since it needs to be locked for phantom protection.

[0137] In addition, space allocated by the queryproc is used to store the array of offsets [138, 138, 44]. For each entry in LA, there is an entry in this array of offsets giving the offset of the corresponding key value in the shadow buffer. When the index manager returns first row, sdes→scur will be set to 80.2 and sdes→srow will be made to point to offset 138 in shadow buffer. sdes→srow contains stable copy of the key and the queryproc takes the columns that it needs from that.

[0138] (b) DCOPY Mode

[0139] This is used if (1) the scan is a cursor, or (2) the index manager is not doing locking, or (3) index manager is doing instant duration locking, or (4) if the index columns could be updated during scan. It turns out that these are the cases where index key cannot be built from the datarow at the time that the repositioning is needed, either because no lock is being held on the datarow or, although a lock is held, the same session could have modified the index columns and therefore, building the key from datarow would not give the desired key value. There is no shadow buffer. The key is copied in a space allocated by queryproc. Unlike in the ICOPY mode, there is no need to have an array of offsets in this case. The space allocated is enough to save one key only and so at most one key is saved in this case at any given time. The space needed in this case is the space for LA plus the maximum index key size (i.e., 6*60+650 or 1010 bytes). Ideally, one should be allocating space based on maximum key size for this index rather than max index key size. Accordingly, a variation of the macro BT_MAXCOPYSPACENEEDED is provided which calculates amount of space needed optimally based on max key size for the index involved.

[0140] There are many entries in LA but there is space to store only one key. Now consider at which key is saved at what point. Before the first RID in LA is returned to data layer, the corresponding key value is copied from index page. For other RIDs, the copy of key value is done from data row and only if the data row qualifies 8. It is done at the time data layer has finished qualification and has done any locking that is needed. If the datarow does not qualify, the key value is not copied from datarow. If the key value was not copied, the corresponding RID in LA is zeroed out (so that index manager can remember that the key value corresponding to that entry in LA has not been copied). It is important to understand that the index page does not have to be latched to copy key value while processing the second through the last RID in LA.

[0141] The LA looks exactly the same as in the case of covered queries. However, in that case there is no shadow buffer and no array of offsets associated with LA. When the index manager returns first row, sdes→scur will be set to 80.2 and “bob” would have been copied into space allocated by QP. sdes→srow will be NULL'd. Data layer may set sdes→srow to stable copy of data row or it may make columns needed by QP available elsewhere. Those details are not part of index manager modules and hence will not be presented here. When the index manager is asked to return next row, assuming that the page has not changed, sdes→scur will be set to 80.4 and sdes→srow is set to NULL. The data layer now qualifies 80.4 and does any locking/blocking that it needs to do 9. If row qualifies and any locks needed have been acquired, key value “bob” is copied from datarow 10. Let us assume that datarow 80.2 does not qualify the sargs on non-index columns. Then, the 2nd entry in LA is zeroed out and LA would like [80.2, 0.0, 50.7] for non-SRs and [80.2, 0,0, 100.1] for SRs. The zeroing out is done so that index manager can track what was the last entry in LA for which corresponding key value was copied from datarow. When the index manager is asked to return next row, if the index page has changed, it will search LA backwards from current position looking for non-zero RID and it would find 80.2. The key value is picked up from scan context and in this case it is “bob”. So the scan would do RESTART_AFTER [“bob”, 80.2].

[0142] The benefit of this scheme over ICOPY mode is that no shadow buffer is needed, and if a lot of data rows are not qualifying, there is no need to copy key value from them. Recall that if the scan is not an SR, delayed locking is used when there are sargs on non-index columns. Since the index manager does not do locking, DCOPY mode is used for such non-covered queries. It is expected that a lot of datarows would not qualify the sargs on data columns in such cases.

[0143] (c) NOCOPY Mode

[0144] This mode is used in cases not included in ICOPY/DCOPY modes. In these cases there is no need to copy the key value whenever the index manager returns a RID to the data layer. Copy is done only if there is a need to block. In other cases, if there is a need to reposition the scan, the key is built from the datarow. Another thing to note is, if scan is doing “read past” locking and it fails to get a lock on some RID in LA, it zeroes out that entry in LA and moves on to the next RID in LA. The zeroing out is a way of remembering that the scan did not get a lock on that datarow/datapage and hence it should not try to build index key from such a RID. Note that QP will still allocate BT_MAXCOPYSPACENEEDED bytes of space for the index scan.

[0145] The LA looks exactly same as in the case of DCOPY mode. However the no key value is copied from either index page or data page, unless the scan needs to block or restart. When the index manager returns first row, sdes→scur will be set to 80.2. sdes→srow will be NULL'd as before. When the index manager is asked to return next row, assuming that the page has not changed, sdes→scur will be set to 80.4 and sdes→srow is set to NULL. Nothing is copied from the datarow regardless of whether it qualifies. In case that the system is performing read past locking and the scan cannot get a lock on 80.2, the second entry in LA is zeroed out and LA would appear as [80.2, 0.0, 50.7]. Note that SRs do not do “read past” locking; hence, the scan has to be a non-SR. So when the index manager is asked to return next row, if the index page has changed, it will search LA backwards from current position looking for non-zero RID and it would find 80.2. The key value is built from data row 80.2 and in this case it is “bob”. Thus, the scan would do RESTART_AFTER [“bob”, 80.2]. The benefit of this scheme is that there is no need to copy if no contention exists, i.e., no blocking/re-starts.

[0146] 6. How Copying Modes and LA Affect Restarts

[0147] Previously, it was discussed how restarts would be done in the absence of LA and copying modes. Now one may look at how copying modes and LA affect the three types of restarts.

[0148] (a) Effect of LA

[0149] While processing the first RID in LA, the effect is same as if one did not have LA. When processing other RIDs, however, special casing is needed. The main difference that LA causes is that, when making a conditional lock request on a RID other than first RID in LA, the latch is not held on the index page. Without LA, if the conditional lock request fails, for non-SRs, one would have copied the key on which one failed to get the lock from the index page. This cannot always be done in the presence of LA. Recall that the slot#, rid# corresponding to each entry in LA are not known. One only knows the slot# corresponding to first entry in LA and to the last entry in LA, in cases where LA was prematurely terminated because of encountering an uncommitted delete or a non-qualifying key. So in cases where slot# is not available, the system copies the key from data page. Note that the system does not have a lock on the data row: therefore, the data page access is done using same protocol as dirty reads, i.e., latch data page and check if index page has changed. In case the index page has changed by the time datapage is latched, it is treated as restart without lock wait case.

[0150] Even for SRs, some special casing is needed when the scan is processing nth RID in LA where n is not equal to 1. Recall that for SRs, one needs to maintain the RID that was last locked (rid_lastlock). If it does not correspond to a qualifying key, the slot# corresponding to it also needs to be maintained. LA causes some difference in the way these are obtained. If the scan is current positioned at nth RID in LA, where n is not equal to 1, the previous RID (actually previous the non-zero RID) in LA serves as rid_lastlock. Since RIDs other than last RID in LA always correspond to qualifying keys, slot_lastlock is not needed in this case. Initially, rid_lastlock is initialized to 0.0. Whenever all RIDs in LA have been processed, the last non-zero RID that does not correspond to a committed delete is saved in rid_lastlock. If that corresponds to a qualifying key, slot_lastlock is not needed. Otherwise, it must be the last RID in LA and the corresponding slot# is available in the scan context and is copied into slot_lastlock. Therefore, if the scan is currently positioned at first RID in LA, rid_lastlock and slot_lastlock are available in the same way as they would be if LA were not being used.

[0151] (b) Effect of Copying Modes

[0152] In the previous section on restarts, it was assumed that the index scan would always copy the key before returning the RID. This may be referred to as a SIMPLECOPY mode. In ICOPY mode, this is true except that the shadow buffer has multiple keys and if the scan is currently positioned at nth RID in LA, the corresponding key in shadow buffer needs to be used. Recall that if LA has N entries, scan context has an array of size N holding offsets of the corresponding key values in shadow buffer. That array can be used to get the corresponding key value. In DCOPY mode, the system performs copying if the datarow qualifies. Thus, this is similar to the SIMPLECOPY mode except that what is saved in scan context is a key corresponding to last row returned to queryproc rather than last row returned to data layer. The ZEROed out RIDs in LA correspond to those datarows for which index key qualified but not data. The key that one has in the scan context corresponds to last non-zero RID in LA preceding the current position in LA.

[0153] The NOCOPY mode does not attempt to do any optimization when there is a need to block on addresslock or logical lock. All it optimizes is that when a RID is returned to data layer, no copy is kept of the corresponding key value. In the SIMPLECOPY mode, the key is saved at the time that RID is returned to data layer, but in NOCOPY mode one has the assurance that one can build it from datarow when needed. Thus, the NOCOPY mode is like a “virtual” copy and an easy extension of SIMPLECOPY approach. The Appendix A has details of how each of the three types of retsart are handled in presence of LA and copying modes.

[0154] D. SCANS: Low Level Design

[0155] The main interface functions provided by the index manager are bt_startscan( ), bt_getnext( ) and bt_endscan( ). bt_startscan( ) is called to start an index scan. It just initializes the various fields of index scan context but does no other work. Some of the important fields that it initializes are resources such as locks and kept buffers, path that is saved in scan context, copying mode for the scan i.e., whether scan will be done in NOCOPY, DCOPY or ICOPY mode and the status bits.

[0156] bt_getnext( ) is the routine that returns the rows. The RID is returned in sdes→scur. For covered queries, a stable copy of the key is made available in sdes→srow. This is the work horse routine of the scan. It manages most of the state transitions in the scan by checking what state the scan currently is in and calling the appropriate lower level function to handle that state. bt_endscan( ) is called when scan has finished returning all qualifying rows, indicated by bt_getnext( ) returning NULL. Sometimes it is also called to terminate the scan abruptly either because of errors or because of row limits have been set (through set rowcount, for example). bt_endscan( ) does nothing more than releasing the resources like locks and kept buffers. The following first examines the index scan context and extended scan context, and then the function bt_getnext( ) to get a feel for the control flow in the scan.

[0157] 1. Index Scan Context

[0158] The following is the structure definition and various status bits of index scan context. Index scan context is part of SDES. It exists in a union with oam (i.e., object allocation map) scan context, rid scan context, and sort scan context.

[0159] 2. Extended Scan Context

[0160] An extended scan context may be defined to include those important data items that part of scan state but do not really need to be maintained across calls to bt_getnext( ). So how are they different from local variables in bt_getnext( ). In theory, they are not but many of these data items play very important role in understanding scan and hence a separate structure BT_GNEXT has been defined to contain these. This state maintained in this structure is also called as extended scan context. BT_GNEXT is not part of SDES but is declared on stack in bt_getnext( ) function.

[0161] 3. bt_getnext( )

[0162] The index scan goes through several states and the state transitions are complex to manage. The following examines the important states of scan and which lower level functions handle what states.

[0163] (a) BT_GSTATE_ADVANCELA

[0164] This service to advance the position in LA. This is the main entry state for bt_getnext except in two cases.

[0165] (1) Very First Call to bt_getnext in the Scan

[0166] In this case, bt_getnext( ) calls bt_getstartpg( ) to retrieve the staring page for the scan. bt_getstartpg( ) finds out whether scan has low bound or not and sets up the sargs appropriately to call the traversal routine bt_traverse( ). In the case of index look-aside optimization, it also takes care of passing the search path in the scan context from previous scan to traversal( ). When traversal( ) returns control to scan module, the routine also takes care of saving the path traversed (just the leaf page and the parent page) in the scan context. The repositioing module also calls bt_getstartpg( ) once it has found the restart key and bt_getstartpg( ) takes care of setting up the sargs appropriately and calls traversals. Even in the repositioning case, this routine takes care of transferring the search path from scan module to traversal before calling traversal and then from traversal to scan. When bt_getstartpg( ) returns, LA is empty and so state is set to BT_GSTATE_LADONE.

[0167] (2) If Access Wants SAME Index Row Again Rather Than Next One

[0168] Recall that this happens when index scan has returned a RID to data layer without holding a lock on it but by the time data layer has latched the data page, it found that index page has changed and so it wants the index manager to return same row again. In this case, state is set to BT_GSTATE_RESTART. Note that this state is also entered when bt_getnext wants to skip a rid in LA, for example, if it is a deleted/non-qualifying one.

[0169] (b) BT_GSTATE_PROCESSLA

[0170] After advancing position in LA, bt_getnext enters this state. It also enters this state immediately after filling up LA. If LA has become empty, state is set to BT_GSTATE_LADONE. Otherwise, lock request is made on current RID in LA if locking is needed. If lock is not needed or lock was acquired, state becomes BT_GSTATE_LOCKEDRID. Otherwise, the state becomes BT_GSTATE_COULDNOTLOCK.

[0171] (c) BT_GSTATE_LADONE

[0172] This state is entered when it is found that LA is done. bt_handle_LAdone( ) handles this state. Essentially, its job is to fill LA with RIDs from rows of interest. It calls bt_qualpage( ) to qualify index rows from current scan position onwards and fill LA. If bt_qualpage( ) has put at least one RID in LA, BT_GSTATE_PROCESSLA is entered. If bt_qualpage found that high bound has been exceeded, state becomes BT_GSTATE_ENDSCAN (note that in case of SRs, BT_GSTATE_ENDSCAN is set only after next key lock was obtained). Otherwise, it means current page is done and so BT_GSTATE_PAGEDONE is entered.

[0173] (d) BT_GSTATE_COULDNOTLOCK

[0174] This state is entered if cond lock request fails and bt_handle_couldnotlock( ) is called to handle it. If SKIP_IFNOLOCK has been specified, the state becomes BT_GSTATE_ADVANCELA i.e., the system just moves on to the next RID in LA. Otherwise, bt_handle_couldnotlock( ) calls bt_savekeynblk( ) to save key if needed, drop the latches and to wait on logical lock. bt_savekeynblk has all the blocking logic and it finally returns one of the following.

[0175] (1) BLOCK_PGUNCHANGED

[0176] This means blocking was done and page was not found changed after wakeup. It is a committed delete, state becomes BT_GSTATE_ADVANCELA. Otherwise, it becomes BT_GSTATE_LOCKEDRID.

[0177] (2) BT_BLOCK_PGCHANGED_PRESAVE

[0178] Recall that because of using look ahead list, the conditional lock request could be made without holding latch on index page. In that case, if the scan wants to save the key, it saves from datarow. It is possible that by the time the datapage was latched, the index page has changed and so the key could not be saved from datarow. In that case this code is returned and it means that the system did not block. In this case BT_GSTATE_PGCHANGED_NOWAIT is entered.

[0179] (3) BT_BLOCK_PGCHANGED_POSTSAVE

[0180] This means the scan saved the key that it wanted to save (if any) and blocked on the lock. After wakeup, the page was found to have changed. BT_GSTATE_RETSTART is entered.

[0181] (e) BT_GSTATE_PAGEDONE

[0182] This state is entered when the current page is done. bt_handle_pagedone( ) handles this state. If the current page is full of committed deletes, the scan may decide to shrink the page. bt_maybeshrink( ) is called which decides whether to do shrink and calls bt_shrink( ) if it decides to. If shrink was attempted, the state becomes BT_GSTATE_RESTART. Otherwise, bt_nextscanpage( ) is called which retrieves next scan page taking care of scan direction as well as any broken linkages due to corruptions or concurrent split or shrink. Once the next scan page is returned, if it is undergoing split/shrink and there is a need to block on it, bt_savekeynblk( ) is called and next state is set depending upon its return codes (as in the case of BT_GSTATE_COULDNOTLOCK).

[0183] (f) BT_GSTATE_LOCKEDRID

[0184] This state is entered if locking is not applicable or when lock was obtained successfully. After this point if the RID is a non-qualifying one, it is skipped and otherwise it is the returned. In the ICOPY mode, if the scan is at the first RID in LA, all the key values corresponding to RIDs in LA are copied into shadow buffer before unlatching the page and returning the RID. If the scan is not SR and had to block on lock on first RID, it would have already copied key values into the shadow buffer and so the copying step is skipped. Similarly, in DCOPY mode, if the scan is at the first RID in LA, the key value corresponding to it is copied from index page into scan context. As in the case of ICOPY mode, this step is skipped if it is non-SR and had to block on lock on first RID in LA.

[0185] (g) BT_GSTATE_PGCHANGED_NOWAIT

[0186] If a page changed but there was no lock wait involved, then this state is entered. bt_handle_pgchanged_nowait( ) handles this state. It just does some initialization that BT_GSTATE_RESTART expects and the state is set to BT_GSTATE_RESTART.

[0187] (h) BT_GSTATE_RESTART

[0188] This state is entered if restart is needed. bt_handle_reposition( ) is called to handle this state. It analyzes LA to figure out what is the restart RID and what is the restart key value. If there is no restart RID, it means scan needs to start all over again. This can happen for SR scans if scan needs to restart before it locked its first key. In NOCOPY mode, key value may not be available in scan context. In that case it has to be built from datarow. Once it has been figured out what key if any to use to restart, bt_getstartpg( ) is called which calls traversal module to position the scan appropriately.

[0189] (i) BT_GSTATE_RETRYNKL

[0190] This state is entered when nextkeylock needs retrying. A backward scanning SR needs to do “next key” locking. However this is not symmetrical with FW scanning SR. In the case of FW scanning SR, the “next key” lock is the last lock that is obtained; but for a BWscan, it is the first lock. Consider a BWscan on an index I(x ASC) looking for x>=10 and x<=20. It traverses the tree looking for 20 to start the scan. One traversal has positioned it on 20, it needs to do “next key” locking by looking for the next key in the forward direction. The way this is implemented is that when the BWscan is positioned on 20, it calls bt_nextkeylock( ) which temporarily sets the direction of scan to FW direction and calls bt_getnext( ) to get the next key. That call to bt_getnext( ) is special call because it should not do any repositioning. This is because the module that sets up sargs for repositioning finds that scan direction is FW and it may reposition at 10(note that for a BWscan, low bound is 20 but for FWscan, low bound is 10). So this state BT_GSTATE_RETRYNKL has been introduced. When bt_getnext( ) is called from bt_nextkeylock( ), if there is a need to do repositioning, it sets the state to BT_GSTATE_RETRYNKL and returns NULL. The caller, i.e., bt_nextkeylock again retries the operation by locating 20 and calling bt_getnext( ).

[0191] (j) BT_GSTATE_ENDSCAN

[0192] This state is entered when scan needs to be terminated because there are no more qualifying rows and next key lock if any has been obtained. The scan releases any latches and returns NULL.

[0193] (k) BT_GSTATE_ERROR

[0194] This state is entered when scan encounters error like deadlock or lock interrupt. Otherwise, the system just terminates the scan when an error occurs, with the result that this is not much different from BT_GSTATE_ENDSCAN.

[0195] While the invention is described in some detail with specific reference to a single preferred embodiment and certain alternatives, there is no intent to limit the invention to that particular embodiment or those specific alternatives. Thus, the true scope of the present invention is not limited to any one of the foregoing exemplary embodiments but is instead defined by the appended claims.