|Powered by QM on a Linux server|
KnowledgeBase 00006: Scanning Alternate Key Indices
The hashed file system locates a record by transforming the record id to the position of the group in which the record should be stored and then scanning the small number of records in the group for the one that is required. This provides very fast access regardless of the actual number of records stored in the file so long as the record id is known.
Alternate key indices allow records to be located based on the content of a data field without needing to search the entire file. The AK is effectively a secondary file in which the content of the corresponding data field is used as the key and each record holds a list of data file record ids that have that data value.
To find all records that have a particular value in the indexed field, QM will read the corresponding index record and can then go directly to the data records.
Internally, an AK is stored as a balanced tree structure in which the index keys (data field values) are in sorted order. This enables the index to be used to find records with a specific data field value or a range of values.
QMBasic provides a method by which an application can find an AK record for a specific data value and then walk through the sorted list in either direction.
Setting the Start Position
The SELECTINDEX statement is used by QMBasic programs to build a select list
of records that have a specific value in an indexed field.
As a side effect, SELECTINDEX leaves a pointer into the index structure at the position identified by value. If there are no records with the requested indexed value, the pointer is left positioned where such a value should go. Thus, if the index contained references to records with indexed values 1, 3, 5 and 7, a SELECTINDEX operation to build a list of records with an indexed value of 4 would return an empty list but would leave the index pointer between the entries for 3 and 5.
Alternatively, the SETLEFT or SETRIGHT statements may be used to position the pointer at the extreme left or right of the indexed values.
Walking the Index
The SELECTRIGHT or SELECTLEFT statements can be used to walk through the
index, starting at the position of the index pointer set by SELECTINDEX,
SETLEFT or SETRIGHT and moving to the right (ascending order of indexed value)
or left (descending order of indexed value).
This operation creates a select list of records with the next indexed value in the direction of the scan. The optional key variable receives the indexed value associated with the records included in the select list.
Thus, to walk through an index from beginning to end in ascending order, a program would use SETLEFT to position at the start of the data and then perform a series of SELECTRIGHT operations until no further data is available. For example, if we have an orders file open as ORD.F and there is an index named CUST.NO for the customer number, we could process orders in ascending customer number with a loop such as:
SETLEFT 'CUST.NO' FROM ORD.F LOOP SELECTRIGHT 'CUST.NO' FROM ORD.F SETTING CUST LOOP READNEXT ORD.ID ELSE EXIT ...processing... REPEAT UNTIL STATUS() REPEAT
The outer loop walks through the index returning a select list of orders for each customer, also setting CUST to the corresponding customer number. The inner loop processes the orders for the customer.
A loop similar to that above can be used to perform partial matching on the leading part of an indexed value. If, for example, we want to find all names that begin with a specific prefix string, we could use a loop similar to that below.
SELECTINDEX 'NAME', PREFIX FROM CLIENTS.F LOOP LOOP READNEXT CLIENT.ID ELSE EXIT ...processing... REPEAT SELECTRIGHT 'NAME' FROM CLIENTS.F SETTING NAME WHILE @SELECTED WHILE NAME[1,LEN(PREFIX)] = PREFIX REPEATIn this example, we first try for an exact match against the supplied prefix using SELECTINDEX. As well as possibly returning a list of records for which there is an exact match, this operation also leaves the index scan pointer at the position at which this entry would appear in the index.
The inner loop will process any items returned by the SELECTINDEX operation. We then use SELECTRIGHT to move to the next index entry. The SETTING clause copies the indexed value associated with this entry into the NAME variable. The two WHILE clauses check that we have not run off the end of the index and that the next item still matches the supplied prefix. The inner loop will process these items before we once again attempt to move to the right.
Tracking Sequential Record Ids
Sometimes an application may build an AK on the primary key. This can be useful where, for example, the ids are not simple sequential numbers. For this discussion, we will imagine a log file for which the record id is a timestamp value.
Using a left to right scan loop similar to that above would allow the application to walk through the log records. Instead of terminating the loop when we reach the end of the index data, we could use SLEEP to pause for a while and then try again. This would allow us to process new records as they are added to the log.
Use of SETRIGHT positions after the last record in ascending sort order. Instead of scanning the entire log from left to right, we could use SETRIGHT to position at the extreme right and then process only records added after our program starts.
Migrating Index Processing from D3
Even though QMBasic provides similar capabilities, there is no direct one for one relationship between the ROOT and KEY statements used by the Basic language of D3 and the operations described above.
The c operator of KEY is equivalent to SELECTINDEX followed by a SELECTRIGHT if the SELECTINDEX did not find an exact match.
The l operator is similar to the example of partial key matching in the QM Reference Manual description of the SELECTRIGHT statement.
The n operator is equivalent to use of SELECTRIGHT except that QMBasic returns a select list of all items with the given index value rather than requiring repeated n operations.
The p operator is equivalent to use of SELECTLEFT except that QMBasic returns a select list of all items with the given index value rather than requiring repeated p operations.
The r operator is equivalent to use of SELECTINDEX.
The v operator has no direct equivalent but is broadly similar to use of SELECTINDEX.
The x operator is equivalent to use of SELECTRIGHT.
Migrating Index Processing from UniVerse
UniVerse combines the operations provided by the QMBasic statements described above into the BSCAN statement.
A UniVerse Basic loop such as
BSCAN KEY, ID.LIST FROM FVAR USING 'INDEX.NAME' RESET THEN LOOP LOOP ID = REMOVE(ID.LIST, MORE) ...process data... WHILE MORE REPEAT BSCAN KEY, ID.LIST FROM FVAR USING 'INDEX.NAME' ELSE EXIT REPEAT ENDbecomes
SETLEFT 'INDEX.NAME' FROM FVAR LOOP SELECTRIGHT 'INDEX.NAME' FROM FVAR SETTING KEY UNTIL STATUS() READNEXT ID ELSE EXIT ...process data... REPEAT
Migrating Index Processing from UniData
UniData has functions that are broadly equivelent to those of QMBasic.
The UniBasic SETINDEX statement has options that provide functionality that is similar to SELECTINDEX, SETLEFT and SETRIGHT.
READBCK is similar to SELECTLEFT.
READFWD is similar to SELECTRIGHT.
Assuming that the customer number is stored in field 3 of the order record, a UniData Basic program such as
OPEN 'ORDERS' TO ORD.F ELSE STOP 'Cannot open file' CUST = '1234' SETINDEX 'CUST.NO', CUST ON ORD.F LOOP READFWD ORD.REC FROM ORD.F ELSE EXIT WHILE ORD.REC<3> = CUST ...processing... REPEATbecomes
OPEN 'ORDERS' TO ORD.F ELSE STOP 'Cannot open file' CUST = '1234' SELECTINDEX 'CUST.NO', CUST FROM ORD.F LOOP READNEXT ORD.ID ELSE EXIT READ ORD.REC FROM ORD.F, ORD.ID THEN ...processing... END REPEAT
Walking an Index Record by Record
The SELECTRIGHT and SELECTLEFT statements return a select list of the ids of all records with a specific indexed field value. The BP file of the QMSYS account includes the source code of a QMBasic class module named INDEX.CLS that allows an application to walk through an alternate key index record by record in either direction.
Full details of how to use this class module are included in the source code.