Indexing in EMu

EMu has a number of indexing methods for efficient and timely access to data. An indexing method is an algorithm or set of rules to search data in an indirect way. The simplest type of indexing, known as an exhaustive search, is no index at all. In this case, each record is read sequentially and compared against the search terms entered. If there is a match, the record is added to the set of matching records, then the next record is read. The exhaustive search method is very space efficient as only the data needs to be stored. However, a search may take some time to complete if there is a very large number of records (perhaps several hours for 750,000 records).

To facilitate the search of large numbers of records, indexes are built that provide rapid access to data that match given search criteria. Indexes provide an indirect means of searching data in a judicious manner: when a search term is entered, the indexes are consulted to produce the matching records. There is a cost associated with indexing: the need to store indexing information along with the data.

There are a large number of indexing methods available to designers of databases, each one with associated pros and cons. The EMu database engine employs two flexible indexing methods to provide rapid retrieval of data from large numbers of records:

  • The first is known as linear hashing and provides high speed key retrieval.
  • The second goes by the long name of A two level superimposed coding scheme for partial match retrieval, (shortened to the Two Level method) and provides a general purpose framework for implementing a wide range of term based searches. A term is simply a sequence of characters that forms the basic entity for searching. For example, in word based searching (where you need only enter a word to find matching records), a term is a word.

A number of pre-configured indexing options are distributed with EMu. In particular a number of fields that contain name based data already have phonetic based indexing enabled. Also many descriptive fields (e.g. Notes) have stem based indexing set.

It is possible to adjust indexing via Registry entries. These entries allow institutions to tune indexing methods to provide the most efficient searching possible without wasting disk space on unused methods.

Users in group Admin can use an Admin Task to view indexing information:

The View System Indexing Admin Task allows users to view information about indexing set on EMu fields. The task runs the emuindexing script which produces a summary on a per table basis of the (field) type and indexing options set on each column.

To run the task:

  1. Click Admin in the Command Centre to open the Admin Tasks module.

    This lists all tasks grouped by module:

    Admin Tasks

    The Admin heading at the top of the list is for a virtual module that includes all tasks unrelated to a specific module.

  2. Under Admin, select View System Indexing.

    The output of the task is similar to:

View System Indexing

As there may be a large number of tables in some institutions the Admin Task may take some time to process all of the information (up to ten minutes for a large system). The indexing information may also contain columns that are not used by your institution. These columns are sub-classed columns specific to a particular client. Enabling indexing on these columns does not affect the size of the indexes generated as empty fields do not generate any indexing information (unless null based indexing is enabled).

By default, users in group Admin have access to this task. If other users need to run the script, add the following Admin Task Registry entry:

Group group Table eadmin Admin Task View System Indexing emuindexing

where group is the name of the group that requires access.

Details about Indexing are available in Indexing in EMu

Improved indexing methods

Several indexing methods were added to the database engine with EMu 3.1. In particular, support was added for NULL indexing (whether a field is empty or not) and PARTIAL indexing (fast searching for leading characters, e.g. a*). System Administrators are able to configure which fields require these indexing methods using the EMu Registry.

Tools that permit System Administrators to tune the range indexing used by EMu were added with version 4.0.01. Support was also added for automatic optimization of range indexes. Together these tools EMu can provide optimal range indexes with significantly faster range based searches.