Show Table of Contents
Chapter 13. Managing Indexes
Indexing makes searching for and retrieving information easier by classifying and organizing attributes or values. This chapter describes the searching algorithm itself, placing indexing mechanisms in context, and then describes how to create, delete, and manage indexes.
13.1. About Indexes
This section provides an overview of indexing in Directory Server. It contains the following topics:
13.1.1. About Index Types
Indexes are stored in files in the directory's databases. The names of the files are based on the indexed attribute, not the type of index contained in the file. Each index file may contain multiple types of indexes if multiple indexes are maintained for the specific attribute. For example, all indexes maintained for the common name attribute are contained in the
Directory Server supports the following types of index:
- Presence index (pres) contains a list of the entries that contain a particular attribute, which is very useful for searches. For example, it makes it easy to examine any entries that contain access control information. Generating an
aci.dbfile that includes a presence index efficiently performs the search for
ACI=*to generate the access control list for the server.
- Approximate index (approx) is used for efficient approximate or sounds-like searches. For example, an entry may include the attribute value
cn=Robert E Lee. An approximate search would return this value for searches against
cn~=Lee. Similarly, a search against
l~=San Fransisco(note the misspelling) would return entries including
- Substring index (sub) is a costly index to maintain, but it allows efficient searching against substrings within entries. Substring indexes are limited to a minimum of three characters for each entry.For example, searches of the form
cn=*derson, match the common names containing strings such as
Jill Henderson, or
Steve Sanderson. Similarly, the search for
telephoneNumber= *555*returns all the entries in the directory with telephone numbers that contain
- 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 it applies a matching rule by associating an object identifier (OID) with the attributes to be indexed.The supported locales and their associated OIDs are listed in Appendix D, Internationalization. If there is a need to configure the Directory Server to accept additional matching rules, contact Red Hat Consulting.
- Browsing index, or virtual list view (VLV) index, speeds up the display of entries in the Directory Server Console. This index is particularly useful if a branch of your directory contains hundreds of entries; for example, the
ou=peoplebranch. You can create a browsing index on any branch point in the directory tree to improve display performance through the Directory Server Console or by using the
vlvindexcommand-line tool, which is explained in the Red Hat Directory Server Configuration, Command, and File Reference.
13.1.2. About Default and Database Indexes
Directory Server contains a set of default indexes. When you create a new database, Directory Server copies these default indexes from
cn=default indexes,cn=config,cn=ldbm database,cn=plugins,cn=configto the new database. Then the database only uses the copy of these indexes, which are stored in
Directory Server does not replicate settings in the cn=config entry. Therefore, you can configure indexes differently on servers that are part of a replication topology. For example, in an environment with cascading replication, you do not need to create custom indexes on a hub, if clients do not read data from the hub.
To display the Directory Server default indexes:
# ldapsearch -D "cn=Directory Manager" -W -p 389 -h server.example.com \ -b "cn=default indexes,cn=config,cn=ldbm database,cn=plugins,cn=config" \ '(objectClass=nsindex)'
If you update the default index settings stored in
cn=default indexes,cn=config,cn=ldbm database,cn=plugins,cn=config, the changes are not applied to the individual databases in
To display the indexes of an individual database:
# ldapsearch -D "cn=Directory Manager" -W -p 389 -h server.example.com \ -b "cn=index,cn=database_name,cn=ldbm database,cn=plugins,cn=config" \ '(objectClass=nsindex)'
13.1.3. Overview of the Searching Algorithm
Indexes are used to speed up searches. To understand how the directory uses indexes, it helps to understand the searching algorithm. Each index contains a list of attributes (such as the
cn, common name, attribute) and a pointer to the entries corresponding to each value. Directory Serverprocesses a search request as follows:
- An LDAP client application sends a search request to the directory.
- The directory examines the incoming request to make sure that the specified base DN matches a suffix contained by one or more of its databases or database links.
- If they do match, the directory processes the request.
- If they do not match, the directory returns an error to the client indicating that the suffix does not match. If a referral has been specified in the
cn=config, the directory also returns the LDAP URL where the client can attempt to pursue the request.
- The Directory Server examines the search filter to see what indexes apply, and it attempts to load the list of entry IDs from each index that satisfies the filter. The ID lists are combined based on whether the filter used AND or OR joins.
- If the list of entry IDs is larger than the configured ID list scan limit or if there is no index, then the Directory Server searches every entry in the database. This is an unindexed search.
- The Directory Server reads every entry from the
id2entry.dbdatabase or the entry cache for every entry ID in the ID list (or from the entire database for an unindexed search). The server then checks the entries to see if they match the search filter. Each match is returned as it is found.The server continues through the list of IDs until it has searched all candidate entries or until it hits one of the configured resource limits. (Resource limits are listed in Section 14.1.4, “Setting User and Global Resource Limits Using the Command Line”.)
NoteIt's possible to set separate resource limits for searches using the simple paged results control. For example, administrators can set high or unlimited size and look-through limits with paged searches, but use the lower default limits for non-paged searches.
13.1.4. Approximate Searches
In addition, the directory uses a variation of the metaphone phonetic algorithm to perform searches on an approximate index. Each value is treated as a sequence of words, and a phonetic code is generated for each word.
The metaphone phonetic algorithm in Directory Server supports only US-ASCII letters. Therefore, use approximate indexing only with English values.
Values entered on an approximate search are similarly translated into a sequence of phonetic codes. An entry is considered to match a query if both of the following are true:
- All of the query string codes match the codes generated in the entry string.
- All of the query string codes are in the same order as the entry string codes.
|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.|
13.1.5. Balancing the Benefits of Indexing
Before creating new indexes, balance the benefits of maintaining indexes against the costs.
- Approximate indexes are not efficient for attributes commonly containing numbers, such as telephone numbers.
- Substring indexes do not work for binary attributes.
- Equality indexes should be avoided if the value is big (such as attributes intended to contain photographs or passwords containing encrypted data).
- Maintaining indexes for attributes not commonly used in a search increases overhead without improving global searching performance.
- Attributes that are not indexed can still be specified in search requests, although the search performance may be degraded significantly, depending on the type of search.
- The more indexes you maintain, the more disk space you require.
Indexes can become very time-consuming. For example:
- The Directory Server receives an add or modify operation.
- The Directory Server examines the indexing attributes to determine whether an index is maintained for the attribute values.
- If the created attribute values are indexed, then the Directory Server generates the new index entries.
- Once the server completes the indexing, the actual attribute values are created according to the client request.
For example, the Directory Server adds the entry:
dn: cn=John Doe,ou=People,dc=example,dc=com objectclass: top objectClass: person objectClass: orgperson objectClass: inetorgperson cn: John Doe cn: John sn: Doe ou: Manufacturing ou: people telephoneNumber: 408 555 8834 description: Manufacturing lead for the Z238 line of widgets.
The Directory Server maintains the following indexes:
- Equality, approximate, and substring indexes for
cn(common name) and
- Equality and substring indexes for the telephone number attribute.
- Substring indexes for the description attribute.
When adding that entry to the directory, the Directory Server must perform these steps:
- Create the
cnequality index entry for
- Create the appropriate
cnapproximate index entries for
- Create the appropriate
cnsubstring index entries for
- Create the
snequality index entry for
- Create the appropriate
snapproximate index entry for
- Create the appropriate
snsubstring index entries for
- Create the telephone number equality index entry for
408 555 8834.
- Create the appropriate telephone number substring index entries for
408 555 8834.
- Create the appropriate description substring index entries for
Manufacturing lead for the Z238 line of widgets. A large number of substring entries are generated for this string.
As this example shows, the number of actions required to create and maintain databases for a large directory can be resource-intensive.
13.1.6. Indexing Limitations
You cannot index virtual attributes, such as
cos_attribute. Virtual attributes contain computed values. If you index these attributes, Directory Server can return an invalid set of entries to direct and internal searches.