9 Directory Server Indexing

Like a book index, Directory Server indexes speed up searches by associating search strings with the contents of a directory. For information about indexes used by Directory Server, see following sections:

• Overview of Indexes

• System Indexes and Default Indexes

• Types of Index

9.1 Overview of Indexes

Directory Server uses indexes to speed up search operations by associating lookup information with Directory Server entries. During a search operation, Directory Server uses the index to find entries that match the search key . Without an index, Directory Server must check every entry in a suffix to find matches for the search key.

Indexes are stored in database files, and are created and managed independently for each suffix in a directory. Each index file contains all of the indexes defined in the suffix for a given attribute. For example, all indexes maintained for the cn attribute are stored in the databaseName_cn.db3 file. When an indexed entry is modified, Directory Server updates the index files.

Directory Server supports the following types of indexes:

• Default indexes to improve search performance or support searches performed by other applications. Default indexes are added when a suffix is created.

• System indexes to help Directory Server to function properly and efficiently.

• User indexes, added when a user creates an attribute or defines a new index.

9.2 System Indexes and Default Indexes

This section addresses the following topics:

• System Indexes

• Default Indexes

9.2.1 System Indexes

System indexes are required for Directory Server to function properly and efficiently. System indexes cannot be deleted or modified. Table 9-1 lists the system indexes created automatically in every suffix.

Table 9-1 System Indexes Created Automatically in Every Suffix

Attribute	Equality Index	Presence Index	Description
aciCaret		X	Allows the directory server to quickly obtain the access control information maintained in the directory
ancestorid	X		Enhances directory performance during subtree searches
entrydn	X		Speeds up entry retrieval based on DN searches
id2entry	X		Contains the actual database of directory entries. All other database files can be recreated from this one
nsUniqueId	X		Used to search for specific entries
nscpEntryDN	X		Used internally in Directory Server for replication
nsds5ReplConflict	X	X	Helps to find replication conflicts
numsubordinates		X	Used by Directory Service Control Center to enhance display performance on the Directory tab
objectClass	X		Accelerate subtree searches
parentID	X		Enhances directory performance during one-level searches

9.2.2 Default Indexes

When you create a new suffix in your directory, the server configures a set of default indexes in the corresponding database directory. The default indexes can be modified depending on your indexing needs, although you should ensure that no server plug-ins or other servers in your enterprise depend on an indexed attribute before you eliminate index.

Table 9-2 lists the default indexes that are configured in Directory Server.

Table 9-2 Default Indexes in Every New Suffix

Attribute	Equality Index	Presence Index	Substring Index	Description
cn	X	X	X	Improves the performance of the most common types of directory searches.
givenName	X	X	X	Improves the performance of the most common types of directory searches.
mail	X	X	X	Improves the performance of the most common types of directory searches.
mailAlternateAddress	X			Used by Messaging Server.
mailHost	X			Used by Messaging Server.
member	X			Improves server performance. This index is also used by the referential integrity plug-in.
nsCalXItemId	X	X	X	Used by Calendar Server.
nsLIProfileName	X			Used by roaming feature of Messaging Server.
nsRoleDN	X			Improves the performance of role-based operations.
nswcalCALID	X			Used by Calendar Server.
owner	X			Improves server performance. This index is also used by the referential integrity plug-in.
pipstatus	X			Used by other servers.
pipuid		X		Used by other servers.
seeAlso	X			Improves server performance. This index is used by the referential integrity plug-in.
sn	X	X	X	Improves the performance of the most common types of user directory searches.
telephoneNumber	X	X	X	Improves the performance of the most common types of user directory searches.
uid	X			Improves server performance.
uniquemember	X			Improves server performance. This index is also used by the referential integrity plug-in.

9.3 Types of Index

With the exception of the approximate index, the indexes in this section are used by Directory Server to speed up basic matching rules. This section covers the following index types:

• Presence Index

• Equality Index

• Substring Index

• Browsing Index

• Approximate Index

• International Index

9.3.1 Presence Index

The presence index includes all entries in the database that have a value for a specified attribute, irrespective of that value. The following figure shows a presence index for the nsRoleDN attribute. For information about this attribute, see nsRoleDN.

Figure 9-1 Presence Index

Description of "Figure 9-1 Presence Index"

Directory Server uses the value of the entryid attribute to store a reference to the entry. Directory Server retrieves the entry by using the instance-path/db/dbinstance/dbinstance_id2entry.db3 index file, where dbinstance depends on the database identifier.

When Directory Server receives a request to remove an attribute value indexed for presence, it must remove the entry from the presence index for that attribute before acknowledging the update to the client application.

The cost of presence indexes is generally low, although the list of entries maintained for a presence index may be long. When the index list length is small, presence indexes are useful for attributes in a relatively small percentage of directory entries.

9.3.2 Equality Index

The equality index includes all entries in the database that have a specified value for a given attribute. This index requires a value to be specified in the search filter. The following figure shows an equality index for the sn, surname, attribute. The index maintains a list of values for the sn attribute. For information about this attribute, see sn.

Figure 9-2 Equality Index

Description of "Figure 9-2 Equality Index"

When Directory Server receives a request to update an entry indexed for equality, it must do the following tasks before performing the update and acknowledging the update to the client:

• Determine whether the entry must be removed from the index

• Determine whether a list must be added to or removed from the index

The cost of equality indexes is generally lower than for substring indexes, but equality indexes require more space than presence indexes. Some client applications such as messaging servers might rely on equality indexes for search performance. Avoid using equality indexes for large binary attributes such as photos and hashed passwords.

9.3.3 Substring Index

Substring indexes are used for searches on three-character groups, for example, sn=*abc*. The three-character groups are stored in the index. Substring indexes cannot be applied to binary attributes such as photos. The following figure shows a substring index for the SN attribute.

Figure 9-3 Substring Index for the SN Attribute

Description of "Figure 9-3 Substring Index for the SN Attribute"

The Directory Server search algorithm includes optimizations for the following searches, however, these searches are more likely to reach the index list threshold:

• Searches on two-character substrings with this format sn=*ab*

• Searches on one-character group with this format sn=a*. Searches cannot be performed on one-character groups with this format sn=*a and sn=*a*

Directory Server builds an index of substrings according to its own built-in rules. Substring indexes cannot be configured by the system administrator.

When Directory Server receives a request to update an entry that has an attribute indexed for substrings, it must do the following tasks before performing the update and acknowledging the update to the client:

• Determine whether the entry must be removed from the index

• Determine whether and how modifications to the entry affect the index

• Determine whether the entry IDs or lists of entry IDs must be added to or removed from the index

Maintaining substring indexes is relatively costly; the cost is a function of the length of the string indexed. To minimize cost, avoid unnecessary substring indexes, especially for attributes that have potentially long string values such as a description.

9.3.4 Browsing Index

Browsing indexes are also called virtual list view indexes. Browsing indexes are used for search operations that request server-side sorting or virtual list view, VLV, results. By using browsing indexes, you can improve the performance of searches that request server-side sorting of a large number of results. Depending on your directory configuration, the server may refuse to perform searches that request sorting when no browsing index is defined. This prevents large sorting operations from overloading server resources.

Browsing indexes are configured with the following parameters in the vlvSearch object class, vlvBasevlvScope, vlvScope, and vlvFilter. Browsing index are sorted by the following parameter in the vlvIndex object class, vlvSort.

Browsing indexes are configured in two steps.

1. The base of the search, the scope of the search, and a filter for the search are configured by the vlvBase, vlvScope, and vlvFilter attributes in the vlvSearch object class.

2. The name of the attributes that sort the index are configured by the vlvSort attribute in the vlvIndex object class.

The following figure shows a browsing index.

Figure 9-4 Representation of a Browsing Index

Description of "Figure 9-4 Representation of a Browsing Index"

When Directory Server receives a request to update an entry with a vlvFilter value, it must do the following tasks before performing the update and acknowledging the update to the client:

• Determine whether the entry must be removed from the index

• Determine the correct position of the entry in the list

9.3.5 Approximate Index

Approximate indexes work with the English language only to provide efficient "sounds-like" searches. For example, the approximate index is useful for searching partial names or misspelled names. Directory Server uses a variation of the metaphone phonetic algorithm to perform searches on an approximate index. Because the algorithm is based loosely on syllables, it is not effective for attributes that contain numbers, such as telephone numbers.

9.3.6 International Index

International indexes are also called matching rule indexes. International indexes associate language-specific matching rules with attributes. This index type enables attributes to be sorted and searched for in accordance with the language rules. International indexes use matching rules for particular locales to maintain indexes.

Standard support for international and other types of indexing can be extended by using a custom matching rule server plug-in.