Chapter 6 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

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.

Tuning Indexes for Performance

The use of indexes can enhance performance by reducing the time taken to perform a search. However, indexes also have an associated cost. When an entry is updated, the indexes referring to that entry must also be updated. The more an entry is indexed, the more resources are required to update the index; indexes take up disk space and memory space.

When you design indexes, ensure that you offset the benefit of faster searches against the associated costs of the index. Maintaining useful indexes is good practice; maintaining unused indexes for attributes on which clients rarely search is wasteful.

You can optimize performance of searches in the following ways:

• By preventing Directory Server from performing searches on non-indexed entries

• By limiting the length of an index list

• By ensuring that the size of a data base cache is appropriately tuned

To prevent Directory Server from performing searches on non-indexed entries, set the require-index-enabled suffix property for the suffix.

To limit the number of values per index key for a given search you can set an index list threshold. If the number of entries in the list for a search key exceeds the index list threshold, an unindexed search is performed. The threshold can be set for an entire server instance, for an entire suffix, and for an individual attribute type. You can also set individual thresholds for equality, presence, and substring indexes.

For a detailed procedure on how to change the index list threshold, seeChanging the Index List Threshold in Sun Java System Directory Server Enterprise Edition 6.1 Administration Guide. This procedure modifies the all-ids-threshold configuration property.

The global value of all-ids-threshold for the server instance should be about 5% of the total number of entries in the directory. For example, the default value of 4000 is generally right for instances of Directory Server that handle 80 000 entries or less. You should avoid setting the threshold above 50 000, even for very large deployments. However, you might set all-ids-threshold to a value other than the 5% guideline in the following situations:

• You expect the directory to grow considerably and wish to set the threshold higher than 5 percent of the total.

• You have consumers that support many searches and masters that support mostly writes, and you wish to set a different threshold for consumers and masters.

• You plan to initialize a large directory from an LDIF file and you wish to change the threshold just before initialization.

• Your directory has a deeply hierarchical directory information tree, and you are running one–level or subtree searches. In this case you could set the all-ids-threshold high for parent and ancestor indexes so that all entries below a given branch are indexed.

You should limit the number of unindexed searches that are performed. Use the logconv utility provided with the Directory Server Resource Kit to examine the access logs for evidence of frequent unindexed searches. For more information, see the logconv(1) man page.

System Indexes and Default Indexes

This section addresses the following topics:

• System Indexes

• Default Indexes

System Indexes

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

Table 6–1 System Indexes in Every Suffix

Attribute	Equality Index	Presence Index	Description
aci		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

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 6–2 lists the default indexes that are configured in Directory Server.

Table 6–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.

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

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(5dsat).

Figure 6–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.

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(5dsat).

Figure 6–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.

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 6–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.

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(5dsoc) object class, vlvBase(5dsat), vlvScope(5dsat), and vlvFilter(5dsat). Browsing index are sorted by the following parameter in the vlvIndex(5dsoc) object class, vlvSort(5dsat).

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 6–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

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.

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.