Managing Indexes

he directory server uses index files to aid in searching the directory. Directory server indexes greatly improve the performance of searches in the directory databases, but they do so at the cost of potentially slower database modification and creation operations. Indexes will also cost more in terms of system resources, especially in disk-space use.

This chapter discusses these index files, how the directory server uses them, and how you manage them. The following topics are covered in this section:

• The Searching Algorithm

• Types of Indexes

• The Cost of Indexing

• Creating Indexes

 

The Searching Algorithm

The general process for how searching is performed in the directory server is as follows:

1. A search filter is sent to the directory server from an LDAP client such as Netscape Communicator or the directory server gateway.
2. The directory server examines the incoming request to make sure that the specified base DN matches a suffix assigned to the local database. If they do match, the directory server processes the request. If they do not match, the directory server returns an error to the client indicating that the suffix does not match. If the referral parameter is set, the directory server also returns the LDAP URL where the client can attempt to pursue the request.
3. Based on the contents of the search filter, the directory server looks in slapd.conf to see if any relevant indexes exist. If they do, the directory server reads the appropriate index files to generate a list of potential, or candidate, matches. If an appropriate index is not found, the directory server generates a list of all entries in the database. If a search filter containing multiple criteria is used, the directory server consults multiple indexes and then combines the resulting lists of candidate entries.
4. The candidate matches are returned to the directory server in the form of a series of entry ID numbers.
5. The directory server uses the returned entry ID numbers to read the corresponding entries from the id2entry.dbb file. The directory server then examines each of the candidate entries to see if any match the search criteria. Matching entries are returned to the client as each is found. The directory server continues until it either has examined all candidate entries, or until it reaches the limit set on one of the following parameters:

• Size Limit in Entries (see page 319 for a description of this parameter)

• Time Limit in Seconds (see page 319 for a description of this parameter)

• Look Through Limit in Entries (see page 321 for a description of this parameter)

Note

The client may further restrict the number of returned entries by specifying lower values for the Size Limit in Entries and the Time Limit in Seconds parameters on the search request.

 

Types of Indexes

To improve searching efficiency, the directory server maintains five distinct types of indexes:

pres	Presence index. Allows for searches that return every entry that contains the indexed attribute.
eq	Equality index. Allows for searches that return the entries containing an attribute that is set to a specific value.
approx	Approximate index. Used only for string values such as commonName or givenName. Allows for phonetic, or "sounds-like," searching.
sub	Substring index. Allows for searches that return entries containing a specified substring.
matching rule	International index. Allows for searches that return entries that are sorted according to a specified collation order.

Note

Indexes are contained in files whose names are based on the indexed attribute, not the type of index contained in the file. In fact, each index file may contain multiple types of indexes if multiple indexes are maintained for the specific attribute. For example, all the indexes maintained for the common name attribute are contained in the cn.dbb file.

 

The Presence Index

The presence (pres) index is the simplest of the indexes. It lets you efficiently search the directory for entries that contain a specific attribute. This is useful if, for example, you want to examine any entries that have access control information associated with them. Generating a aci.dbb file that includes a presence index lets you efficiently perform the search for ACI=*.

 

The Equality Index

The equality (eq) index allows you to efficiently search for entries containing a specific attribute value. For example, an equality index on the cn attribute allows a user to efficiently perform the search for cn=Babs Jensen.

 

The Approximate Index

The approximate (approx) index allows efficient approximate or "sounds-like" searches. For example, an entry may include the attribute value cn=Robert E Lee. An approximate search would allow a return for searches against cn~=Robert Lee, cn~=Robert, or cn~=Lee. Similarly, a search against l~=San Fransico (note the misspelling) would return entries including l=San Francisco.

The directory server uses a variation of the metaphone phonetic algorithm to perform this type of searching. Each value is treated as a sequence of words, and a phonetic code is generated for each word.

Values entered on an approximate search are similarly translated into a sequence of phonetic codes. An entry is considered to match a query if:

• all of the query string codes are present in the codes generated in the entry string

• all of the query string codes are specified in the same order as the entry string codes

For example:

Table 7.1

Name in the directory (Phonetic code)	Query string (Phonetic code)	Match comments
Alice B Sarette (ALS B SRT)	Alice Sarette (ALS SRT)	Matches. Codes are specified in the correct order.
	Alice Sarrette (ALS SRT)	Matches. Codes are specified in the correct order despite the misspelling of Sarette.
	Surette (SRT)	Matches. The generated code exists in the original name despite the misspelling of Sarette.
	Bertha Sarette (BR0 SRT)	No match. The code BR0 does not exist in the original name.
	Sarette, Alice (SRT ALS)	No match. The codes are not specified in the correct order.

 

The Substring Index

The substring (sub) index is a costly index to maintain, but it allows for efficient searching against substrings within entries.

For example, searches of the form

cn=*derson

would match the common names containing strings such as

Bill Anderson
Jill Anderson
Steve Sanderson

and so forth. Similarly, the search for

telephonenumber= *555*

would return all the entries in your directory with telephone numbers that contain 555.

Note

Substring indexes are limited to a minimum of two characters for each entry.

 

The International Index

The international ("") index speeds up searches for information in international directories. The process for creating an international index is similar to the process for creating regular indexes, except that you associate a collation order with the attributes to be indexed. For a listing of supported locales and their associated OIDs, see Table D.1 on page 500.

For more information on creating an international index, see "Creating International Index Entries" on page 165.

 

The Cost of Indexing

Although indexes greatly improve the speed of searches within the directory server database, you should be aware of the costs related to indexing:

• slower database modification and creation times

• higher system resource use

 

Slower Database Modification and Creation Times

The more indexes you maintain, the longer it takes the directory server to update the database. This is especially true for substring indexes that cause the directory server to generate multiple index file entries every time an attribute value is created or changed. Remember that for substring indexes, the number of index entries created is proportional to the length of the string being indexed.

Consider the procedure for creating a specific attribute:

1. The directory server receives an add or modify operation.
2. The directory server examines the indexing parameters to determine whether an index is maintained for the attribute values to be created.
3. If the created attribute values are indexed, then the directory server generates the new index entries.
4. Once the indexing has been finished, the actual attribute values are created according to the client request.

For example, suppose the directory server is asked to add the entry:

	dn: cn=Bill Pumice, ou=People, o=airius.com
	objectclass: top
	objectClass: person
	objectClass: orgperson
	objectClass: inetorgperson
	cn: Bill Pumice
	cn: Bill
	sn: Pumice
	ou: Manufacturing
	ou: people
	telephonenumber: 408 555 8834
	description: Manufacturing lead for the Z238 line.

Further suppose that the directory server is maintaining:

• equality, approximate, and substring indexes for common name and surname attributes.

• equality and substring indexes for the telephone number attribute.

• substring indexes for the description attribute.

Then to add this entry to the directory, the directory server must:

1. Create the common name equality index entry for "Bill" and "Bill Pumice".
2. Create the appropriate common name approximate index entries for "Bill" and "Bill Pumice".
3. Create the appropriate common name substring index entries for "Bill" and "Bill Pumice".
4. Create the surname equality index entry for "Pumice".
5. Create the appropriate surname approximate index entry for "Pumice".
6. Create the appropriate surname substring index entries for "Pumice".
7. Create the telephonenumber equality index entry for "408 555 8834".
8. Create the appropriate telephonenumber substring index entries for "408 555 8834".
9. Create the appropriate description substring index entries for "Manufacturing lead for the Z238 line of foobar widgets." Note that there would be a large number of substring entries generated for this string.

 

Higher System Resource Use

One other cost to maintaining index files is the increased system resources they require. Although the impact to your system depends on how large a database you are using and how many attributes exist within your database, consider that:

• Index files use disk space. The more attributes you index, the more files will be created. Also, creating approximate and substring indexes for attributes that contain long and complex strings can cause these files to quickly grow large.

• Index files use memory. To run more efficiently, the directory server tries to place as many index files in memory as possible. You can control the amount of memory allowed per open index file using the "Maximum DB Cache size in Bytes" parameter (refer to page 346 for details on this parameter). Even so, a large number of index files will require more memory.

• Managing index files uses CPU cycles. Although index files will save you CPU cycles during searches, maintaining indexes that are not frequently used can actually waste CPU cycles because of the need to create and manage unnecessary indexes. This is especially true for substring and approximate indexes that require the parsing of long, complex strings.

 

Creating Indexes

You create indexes for specific attributes by using the "Attribute to be Indexed" parameter (for details on this parameter, refer to page 347). Before you create new indexes, balance the benefits of maintaining indexes against the cost of indexing as described in "The Cost of Indexing" on page 156. Consider that:

• Approximate indexes make little sense for attributes commonly containing numbers, such as telephone numbers.

• Substring indexes make no sense for attributes that do not contain readable strings, such as attributes intended to contain a photograph or password attributes that contain encrypted data.

• Maintaining indexes for attributes that will not be commonly used in a search will increase overhead without improving searching performance.

• Attributes that are not indexed can still be specified in search filters, although the search performance may be degraded significantly, depending on the type of search.

 

Default Indexes

By default, the directory server automatically manages some indexes. These indexes are intended to improve directory server performance:

• Presence index for the ACI attribute. This allows the directory server to quickly obtain the access control information maintained in the database.

• Presence, equality, and substring indexes for the following attributes:

		cn, sn, mail, telephoneNumber


These indexes are added by default to improve the performance of the most 
common types of user directory searches.

• Presence, equality, and substring searches for the ntUserDomainId attribute. This improves NT Synchronization Service performance. Note that this index has no impact on your directory server's performance if you are not using the NT Synchronization Service.

• Equality index for the uid, uniquemember, and member attributes. This is primarily used to improve SuiteSpot performance.

• Equality index for the changenumber attribute. This is primarily used to improve replication performance.

In addition, directory-enabled Netscape SuiteSpot servers maintain a standard set of indexes in the directory. If you are not using the server for which these indexes are maintained, you can either leave them alone (they do not require any resources if you are not using the corresponding server), or you can delete them from your server. For more information, see "Removing Indexes" on page 169.

 

Standard Index Files

Because of the need to maintain default indexes and other internal indexing mechanisms, the directory server maintains several standard index files. They are:

• id2entry.dbb--contains the actual directory database entries. All other database files can be recreated from this one, if necessary.

• id2children.dbb--restricts the scope of one-level searches, that is, searches that examine an entry's immediate children.

• dn.dbb--controls the scope of subtree searches; that is, searches that examine an entry and all the entries in the subtree beneath it.

• dn2id.dbb--begins all searches efficiently by mapping an entry's distinguished name to its ID number.

 

Creating Indexes from the Server Manager

Note

The directory server generates index entries only when database entries are created or modified. For this reason, the following procedure alone is not enough if you want to create or modify an index for attributes that already exist in your database. If you want to create an index for a currently existing attribute, create your new index setting using this procedure, and then use the procedure outlined in "Indexing Currently Existing Attributes" on page 164.

To create an index for a specific attribute from the server manager, do the following:

1. Go to Database Management | Attribute Indexing.
2. Scroll to the bottom of the form. You will find a blank Attribute field there. Enter the name of the attribute you want indexed and click the types of indexes you want maintained for the attribute. Note that you should always use the attribute's primary name (not the attribute's alias) when you create the index. The attribute's primary name is the name displayed for the attribute in the Schema | Edit or View Attributes form.

If you want to create an index for a language other than english, enter the OID for the collation order you want to use in the Matching Rules field. You can index the attribute using multiple languages by listing multiple OIDs separated by commas (but no whitespace). For a list of languages and their associated OIDs, see Table D.1 on page 500.

Note that if an index already exists and you just want to add an international OID value to that index, you can do so by adding the appropriate value to that index's Matching Rules field. However, you should then perform the procedure as described in "Indexing Currently Existing Attributes" on page 164.

3. Click Save&Apply at the bottom of the form. The new index parameter is written to the working configuration file (it has not been applied to the server yet). When you click Save&Apply, the server manager:

• places the new index in its alphabetical order in the list of indexed attributes

• places a new blank Attribute field at the bottom of the form

Repeat steps 3 and 4 until you are finished creating new indexes.

Click Save&Apply. The new index is immediately active for any new data that you might add to your directory. You do not have to restart your server. However, in order to index existing data, you must export and then reimport your directory database. For more information, see "Indexing Currently Existing Attributes" on page 164.

 

Creating Indexes Using slapd.dynamic_ldbm.conf

You can create new indexes from the command line by using the index parameter in slapd.dynamic_ldbm.conf.

Note

You can perform this same operation using slapd.conf. However, you will not be able to manage indexes from the server manager that have been added to slapd.conf directly. For best results, perform these activities in slapd.dynamic_ldbm.conf.

Do the following:

1. Edit slapd.dynamic_ldbm.conf (for a description of where the configuration files reside in your directory server installation, see "Finding the Configuration Files" on page 31).
2. Add an index parameter of the form:

index <attribute> [<list of indexes>][<list of OIDs>]

where <attribute> is the attribute to be indexed, <list of indexes> can include pres, eq, sub, and/or approx, and <list of OIDs> is a list of international collation OIDs. Note that if you omit <list of indexes> and instead you specify just <list of OIDs> you must denote the null list of indexes with double quotation marks ("").
Note that you should always use the attribute's primary name (not the attribute's alias) when you create the index. The attribute's primary name is the name displayed for the attribute in the Schema | Edit or View Attributes form.
For a definition of the index keywords, refer to "Types of Indexes" on page 153. For a list of available OIDs, see Table D.1 on page 500.

For example:

index cn,telephoneNumber pres,eq,sub
index cn "" 2.16.840.1.113730.3.3.2.15.1
index cn eq,sub 2.16.840.1.113730.3.3.2.15.1
Specifying an index parameter and attribute name with no indexes causes all indexes to be maintained for the specified attribute. For example:
index cn
causes all indexes to be maintained for the common name attribute. Use the keyword none to specify that no indexes are to be maintained for the attribute. For example:
index cn none
Use the keyword default to specify the list of all attributes not otherwise identified in an index parameter. For example:
index default none
3. When you are finished editing the slapd.dynamic_ldbm.conf file, restart the directory server.

 

Indexing Currently Existing Attributes

If you are adding an attribute that you have never before stored in the database, then you can skip this section because the directory server will automatically generate the appropriate index as you add the new attribute to entries in your database. Simply make sure that you have created the desired index setting before you start using the new attribute with your database.

For details on creating new index settings, refer to either "Creating Indexes from the Server Manager" on page 161, "Creating Indexes Using slapd.dynamic_ldbm.conf" on page 162, or "Creating International Index Entries" on page 165.

If you have created a new index setting for an attribute that your database already uses, then you must reimport your database from LDIF to generate the index for the currently existing attribute. You must do this if you add a new type of index for the currently existing attribute, or if you are adding a new international OID to an existing index.

Do the following:

1. Convert your existing database using the method described in "Converting Databases to LDIF" on page 62. If you decide to use db2ldif to generate the LDIF file, do not specify the -n parameter.
2. Update slapd.conf with the new index parameter as described in "Creating Indexes from the Server Manager" on page 161, or "Creating Indexes Using slapd.dynamic_ldbm.conf" on page 162.
3. Reimport the LDIF file as described in "Managing Databases Using LDIF" on page 60.

 

Creating International Index Entries

You can create international indexes for the locales you support to speed up international searches. The process for creating an international index is similar to the process for creating regular indexes, except that you associate a collation order with the attributes to be indexed.

You can create international indexes by

• using the Server Manager

• editing slapd.dynamic_ldbm.conf

 

Creating International Indexes From the Server Manager

Note

The directory server generates index entries only when database entries are created or modified. For this reason, the following procedure alone is not enough if you want to create or modify an international index for attributes that already exist in your database. If you want to create an index for a currently existing attribute, create your new index setting using this procedure, and then use the procedure outlined in "Indexing Currently Existing Attributes" on page 164.

To create an international index from the server manager, do the following:

1. Go to Database Management | Attribute Indexing.
2. Identify the attribute for which you want to create an international index.

• If the attribute is already indexed in another language, find the attribute on the list and add the OID for the collation order you want to use in the Matching Rules field. For a list of languages and their associated OIDs, see Table D.1. You can index the attribute using multiple languages by listing multiple OIDs separated by commas (but no whitespace).

• If the attribute is not already indexed in another language, scroll to the bottom of the form and enter the name of the attribute in the Attribute to be Indexed field. Click the types of indexes you want maintained for the attribute and type the OID(s) for the languages in which you want the attribute indexed in the Matching Rules. For a list of languages and their associated OIDs, see Table D.1. You can index the attribute using multiple languages by listing multiple OIDs separated by commas (but no whitespace).

Click Save&Apply at the bottom of the form. The new index parameter is written to the working configuration file (it has not been applied to the server yet).

Repeat steps 2 and 3 until you are finished creating new indexes.

Click Save&Apply. The new index is immediately active for any new data that you might add to your directory. You do not have to restart your server. However, in order to index existing data, you must export and then reimport your directory database. For more information, see "Indexing Currently Existing Attributes" on page 164.

 

Creating International Indexes Using slapd.dynamic_ldbm.conf

Note

The directory server generates index entries only when database entries are created or modified. For this reason, the following procedure alone is not enough if you want to create an international index for attributes that already exist in your database. If you want to create an international index for a currently existing attribute, create your new index setting using this procedure, and then use the procedure outlined in "Indexing Currently Existing Attributes" on page 164.

You can create international indexes by editing the slapd.dynamic_ldbm.conf file to add an index parameter that includes the object identifier (OID) for the languages in which you want the attribute indexed.

You can either

• Add a new index parameter to create an international index for an attribute that has not been indexed previously

• Edit an existing index parameter to add an international index for an already indexed attribute

 

Creating a New International Index Using slapd.dynamic_ldbm.conf

To create an international index for an attribute that has not been indexed previously, do the following:

1. Open slapd.dynamic_ldbm.conf (for a description of where the configuration files reside in your directory server installation, see "Finding the Configuration Files" on page 31).
2. On any line below the database parameter, add an index parameter in the form:

index <attribute> "" <OIDs>

where

• <attribute> is the attribute to be indexed.

• <OIDs> is a comma separated list of the OIDs for the languages in which you want the attribute indexed. For a list of languages and their corresponding OIDs, see Table D.1.

For example, to create an index for the cn attribute using the Spanish collation order, add the following line to the slapd.dynamic_ldbm.conf file:

index "" 2.16.840.1.113730.3.3.2.15.1

 

Editing an Existing Index Parameter to Add an International Index

To edit an existing index parameter to add a new international index, do the following:

1. Open the slapd.dynamic_ldbm.conf file (for a description of where the configuration files reside in your directory, see "Finding the Configuration Files" on page 31).
2. Locate the index parameter for the attribute to which you want to add an international index. For example, if you want to add an international index for the cn attribute, locate the line that begins

index cn

3. Add the OID(s) that correspond to the languages in which you want the attribute indexed to the end of the index parameter. For example, to add a spanish index for the cn attribute, which already has the following index parameter in slapd.dynamic_ldbm.conf:

index cn eq,sub

You would add the OID for the spanish collation order to the end of the line as follows:
index cn eq,sub 2.16.840.1.113730.3.3.2.15.1
For a list of list of languages and their corresponding OIDs, see Table D.1.

 

Removing Indexes

You can delete some standard indexes and all indexes that you have created as follows:

1. Go to Database Management | Attribute Indexing.
2. Remove the index either by deleting the attribute name from the attribute field or by unchecking a type of index from beneath the attribute text field. That is, to remove the substring index for the commonName (cn) attribute, find the attribute field that contains cn and uncheck the Presence box. To remove all commonName indexing, delete cn from the Attribute field.
3. Click Save&Apply at the bottom of the form. The index is no longer maintained for the server, although any indexes that were created previous to the deletion are still contained in the database. To eliminate these old indexes, export and reimport your database as described in "Indexing Currently Existing Attributes" on page 164.

 

Removing Standard Indexes

There is a set of standard indexes that you can not delete by using the Database Management | Attribute Indexing form. You can delete these indexes by editing the appropriate configuration file and restarting your server. The exception to this is the presence index for the ACI and copiedFrom attributes. There is no way to remove these indexes from your server.

To delete all other standard indexes from your server (with the exception of the presence index for the ACI and copiedFrom attributes):

1. Edit slapd.dynamic_ldbm.conf to remove the index. Also, if an index is used by a specific SuiteSpot server (such as Messaging or Calendar server), you must also edit the configuration file that corresponds to that server. These configuration files are named:

<NSHOME>/slapd-<serverID>/config/ns-<server>-globopt.c onf

where <server> is the name of the file that requires the index. That is:

Server Type	File Name
Calendar Server	ns-calendar-globopt.conf
Compass Server	ns-compass-globopt.conf
Messaging Server	ns-mail-globopt.conf
Collabra Server	ns-news-globopt.conf
Enterprise Server	ns-web-globopt.conf
Proxy Server	ns-proxy-globopt.conf
Certificate Server	ns-certificate-globopt.conf

2. Remove the index from all configuration files that reference the index. That is, suppose you are maintaining an equality, substring, and presence index for the commonName (cn) attribute. Then slapd.dynamic_ldbm.conf has the following line:

index cn pres,sub,eq

If you wanted to remove the substring index, then edit the line so that it reads:
index cn pres,eq
Similarly, if you want to remove all indexing for the mail attribute, you must remove the appropriate index line from both slapd.dynamic_ldbm.conf and ns-mail-globopt.conf.
3. Restart your server.