logo
Powered by QM on a Rpi server
Home
About OpenQM
Sales and Downloads
Help and Support
About
Login

KnowledgeBase 00006: Scanning Alternate Key Indices

Last updated: 17 Feb 2017
Applies to: All versions
Search  
Top level index       Full Index Search Tips
Previous article     Next article

Overview

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.
     SELECTINDEX indexname, value FROM filevar {TO listnum}

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).
     SELECTRIGHT indexname FROM filevar {SETTING key} {TO listnum}

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.


Partial Matching

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 
REPEAT 
In 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 
END 
becomes
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... 
REPEAT 
becomes
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.


Related Articles

None.



Please tell us if this article was helpful
Very     Slightly     Not at all
Comments
Email (optional)