Indexes

The role of an index is to answer the question, "Which entries have an attribute with this corresponding value?"

Each index is therefore specific to an attribute.

Each index is also specific to the comparison implied in the search filter. For example, a directory server maintains distinct indexes for exact (equality) matching and for substring matching. The types of indexes are explained in Index types. Furthermore, indexes are configured in specific directory backends.

An index is implemented as a tree of key-value pairs. The key is a form of the value to match, such as babs jensen. The value is a list of IDs for entries that match the key. The figure that follows shows an equality (case ignore exact match) index with five keys from a total of four entries. If the data set were large, there could be more than one entry ID per key:

This example illustrates how DS uses an index.

When the search filter is (cn=Babs Jensen), DS retrieves the IDs for entries whose CN matches Babs Jensen by looking them up in the equality index of the CN attribute. (For a complex filter, it might optimize the search by changing the order in which it uses the indexes.) A successful result is zero or more entry IDs. These are the candidate result entries.

For each candidate, DS retrieves the entry by ID from a system index called id2entry. As its name suggests, this index returns an entry for an entry ID. If there is a match, and the client application has the right to access to the data, DS returns the search result. It continues this process until no candidates are left.

If there are no indexes that correspond to a search request, DS must check for a match against every entry in the scope of the search. Evaluating every entry for a match is referred to as an unindexed search.

An unindexed search is an expensive operation, particularly for large directories. A server refuses unindexed searches unless the user has specific permission to make such requests. The permission to perform an unindexed search is granted with the unindexed-search privilege. This privilege is reserved for the directory superuser by default. It should not be granted lightly.

If the number of entries is smaller than the default resource limits, you can still perform what appear to be unindexed searches, meaning searches with filters for which no index appears to exist. That is because the dn2id index returns all user data entries without hitting a resource limit that would make the search unindexed.

Use cases that may call for unindexed searches include the following:

When an entry is added, changed, or deleted, the directory server updates each affected index to reflect the change. This happens while the server is online, and has a cost. This cost is the reason to maintain indexes only those indexes that are used.

DS only updates indexes for the attributes that change. Updating an unindexed attribute is therefore faster than updating an indexed attribute.

Index maintenance has its costs. Every time an indexed attribute is updated, the server must update each affected index to reflect the change. This is wasteful if the index is not used. Indexes, especially substring indexes, can occupy more memory and disk space than the corresponding data.

Aim to maintain only indexes that speed up appropriate searches, and that allow the server to operate properly. The former indexes depend on how directory users search, and require thought and investigation. The latter includes non-configurable internal indexes, that should not change.

Begin by reviewing the attributes of your directory data. Which attributes would you expect to see in a search filter? If an attribute is going to show up frequently in reasonable search filters, then index it.

Compare your guesses with what you see actually happening in the directory.

Directory users might complain their searches fail because they’re unindexed.

By default, DS directory servers reject unindexed searches with a result code of 50 and additional information about the unindexed search. The following example attempts, anonymously, to get the entries for all users whose email address ends in .com:

If they’re unintentionally requesting an unindexed search, suggest ways to perform an indexed search instead. Perhaps the application needs a better search filter. Perhaps it requests more results than necessary. For example, a GUI application lets a user browse directory entries. The application could page through the results, rather than attempting to retrieve all the entries at once. To let the user page back and forth through the results, you could add a browsing (VLV) index for the application to get the entries for the current screen.

An application might have a good reason to get the full list of all entries in one operation. If so, assign the application’s account the unindexed-search privilege. Consider other options before you grant the privilege, however. Unindexed searches cause performance problems for concurrent directory operations.

When an application has the privilege or binds with directory superuser credentials—​by default, the uid=admin DN and password—​then DS does not reject its request for an unindexed search. Check for unindexed searches using the ds-mon-backend-filter-unindexed monitoring attribute:

If ds-mon-backend-filter-unindexed is greater than zero, review the access log for unexpected unindexed searches. The following example shows the relevant fields in an access log message:

Beyond the key fields shown in the example, messages in the access log also specify the search filter and scope. Understand the operation that led to each unindexed search. If the filter is appropriate and often used, add an index to ease the search. Either analyze the access logs to find how often operations use the search filter or monitor operations with the index analysis feature, described in Index analysis metrics.

In addition to responding to client search requests, a server performs internal searches. Internal searches let the server retrieve data needed for a request, and maintain internal state information. Sometimes, internal searches become unindexed. When this happens, the server logs a warning similar to the following:

When you see a message like this in the server log, take these actions:

DS servers provide the index analysis feature to collect information about filters in search requests. This feature is useful, but not recommend to keep enabled on production servers, as DS maintains the metrics in memory.

You can activate the index analysis mechanism using the dsconfig set-backend-prop command:

The command causes the server to analyze filters used, and to keep the results in memory. You can read the results as monitoring information:

The ds-mon-backend-filter-use values include the following fields:

The output can include filters for internal use, such as (aci=*). In the example above, you see a filter used by a client application.

In the example, a search filter that led to an unindexed search, (employeenumber=86182), had no matches because, "caseIgnoreMatch index type is disabled for the employeeNumber attribute". Some client application has tried to find users by employee number, but no index exists for that purpose. If this appears regularly as a frequent search, add an employee number index.

To avoid impacting server performance, turn off index analysis after you collect the information you need. Use the dsconfig set-backend-prop command:

Sometimes it is not obvious by inspection how a directory server processes a given search request. The directory superuser can gain insight with the debugsearchindex attribute.

The default global access control prevents users from reading the debugsearchindex attribute. To allow an administrator to read the attribute, add a global ACI such as the following:

The debugsearchindex attribute value indicates how the server would process the search. The server use its indexes to prepare a set of candidate entries. It iterates through the set to compare candidates with the search filter, returning entries that match. The following example demonstrates this feature for a subtree search with a complex filter:

The filter in the example matches person entries whose given name starts with aa. The search scope is not explicitly specified, so the scope defaults to the subtree including the base DN.

Notice that the debugsearchindex value has the following top-level fields:

In the output, notice that the server uses the equality and substring indexes to find candidate entries whose given name starts with aa. If the filter indicated given names containing aa, as in givenName=*aa*, the server would rely only on the substring index.

Notice that the output for the (objectclass=person) portion of the filter shows "candidates": "[LIMIT-EXCEEDED]". In this case, there are so many entries matching the value specified that the index is not useful for narrowing the set of candidates. The scope is also not useful for narrowing the set of candidates. Ultimately, however, the givenName indexes help the server to narrow the set of candidates. The overall search is indexed and the result is 50 matching entries.

The following example shows a subtree search for accounts with initials starting either with aa or with zz:

As shown in the output, the search is not indexed. To fix this, index the initials attribute:

After configuring and building the new index, try the same search again:

Notice that the server can narrow the list of candidates using the equality index you created. The server would require a substring index instead of an equality index if the filter were not matching initial strings.

If an index already exists, but you suspect it is not working properly, see Verify indexes.

DS maintains metrics about index use. The metrics indicate how often an index was accessed since the DS server started.

The following examples demonstrate how to read the metrics for all monitored indexes:

If the number of index uses is persistently zero, then you can eventually conclude the index is unused. Of course, it is possible that an index is needed, but has not been used since the last server restart. Be sure to sample often enough that you know the indexed is unused before taking action.

You can remove unused indexes with one of the following commands, depending on the type of index:

A presence index matches an attribute that is present on the entry, regardless of the value. By default, the aci attribute is indexed for presence:

A presence index takes up less space than other indexes. In a presence index, there is just one key with a list of IDs.

The following command examines the ACI presence index for a server configured with the evaluation profile:

In this case, entries with ACI attributes have IDs 1 and 9.

An equality index matches values that correspond exactly (generally ignoring case) to those in search filters. An equality index requires clients to match values without wildcards or misspellings:

An equality index has one list of entry IDs for each attribute value. Depending on the backend implementation, the keys in a case-insensitive index might not be strings. For example, a key of 6A656E73656E could represent jensen.

The following command examines the SN equality index for a server configured with the evaluation profile:

In this case, there are 17 entries that have an SN of Jensen.

Unless the keys are encrypted, the server can reuse an equality index for ordering and initial substring searches.

An approximate index matches values that "sound like" those provided in the filter. An approximate index on sn lets client applications find people even when they misspell surnames:

An approximate index squashes attribute values into a normalized form.

The following command examines an SN approximate index added to a server configured with the evaluation profile:

In this case, there are 74 entries that have an SN that sounds like Jensen.

A substring index matches values that are specified with wildcards in the filter. Substring indexes can be expensive to maintain, especially for large attribute values:

In a substring index, there are enough keys to match any substring in the attribute values. Each key is associated with a list of IDs. The default maximum size of a substring key is 6 bytes.

The following command examines an SN substring index for a server configured with the evaluation profile:

In this case, the SN value Jensen shares substrings with many other entries. The size of the lists and number of keys make a substring index much more expensive to maintain than other indexes. This is particularly true for longer attribute values.

An ordering index is used to match values for a filter that specifies a range. For example, the ds-sync-hist attribute used by replication has an ordering index by default. Searches on that attribute often seek entries with changes more recent than the last time a search was performed.

The following example shows a search that specifies a range on the SN attribute value:

In this case, the server only requires an ordering index if it cannot reuse the (ordered) equality index instead. For example, if the equality index is encrypted, an ordering index must be maintained separately.

A big index is designed for attributes where many, many entries have the same attribute value.

This can happen for attributes whose values all belong to a known enumeration. For example, if you have a directory service with an entry for each person in the United States, the st (state) attribute is the same for more than 30 million Californians (st: CA). With a regular equality index, a search for (st=CA) would be unindexed. With a big index, the search is indexed, and optimized for paging through the results. For an example, refer to Indexes for attributes with few unique values.

A big index can be easier to configure and to use than a virtual list view index. Consider big indexes when:

¹ Many, but not all entries. Do not create a big index for all values of the objectClass attribute, for example. When all entries have the same value for an attribute, as is the case for objectClass: top, indexes consume additional system resources and disk space with no benefit. The DS server must still read every entry to return search results. In practice, the upper limit is probably somewhat less than half the total entries. In other words, if half the entries have the same value for an attribute, it will cost more to maintain the big index than to evaluate all entries to find matches for the search. Let such searches remain unindexed searches.

A virtual list view (VLV) or browsing index is designed to help applications that list results. For example, a GUI application might let users browse through a list of users. VLVs help the server respond to clients that request server-side sorting of the search results.

VLV indexes correspond to particular searches. Configure your VLV indexes using the command line.

In some cases, you need an index for a matching rule other than those described above.

For example, a generalized time-based matching index lets applications find entries with a time-based attribute later or earlier than a specified time.

As described in Big index, big indexes fit the case where many, many entries have the same attribute value.

The default DS evaluation profile generates 100,000 user entries with addresses in the United States, so some st (state) attributes are shared by 4000 or more users. With a regular equality index, searches for some states reach the index entry limit, causing unindexed searches. A big index avoids this problem.

The following commands configure an equality index for the state attribute, and then build the new index:

Once the index is ready, a client application can page through all the users in a state with an indexed search:

When creating a big index that uses an extensible matching rule, model your work on the example in Extensible match index, but use the following options to set the index type and the matching rule:

DS servers support attribute values that have JSON syntax. The following schema excerpt defines a json attribute with case-insensitive matching:

When you index a JSON attribute defined in this way, the default directory server behavior is to maintain index keys for each JSON field. Large or numerous JSON objects can result in large indexes, which is wasteful. If you know which fields are used in search filters, you can choose to index only those fields.

As described in Schema and JSON, for some JSON objects only a certain field or fields matter when comparing for equality. In these special cases, the server can ignore other fields when checking equality during updates, and you would not maintain indexes for other fields.

How you index a JSON attribute depends on the matching rule in the attribute’s schema definition, and on the JSON fields you expect to be used as search keys for the attribute.

The following example shows how to create a VLV index. This example applies where GUI users browse user accounts, sorting on surname then given name:

When you first import directory data, the directory server builds the indexes as part of the import process. DS servers maintain indexes automatically, updating them as directory data changes.

Only rebuild an index manually when it is necessary to do so. Rebuilding valid indexes wastes server resources, and is disruptive for client applications.

However, you must manually intervene when you:

An index is a tree of key-value pairs. The key is what the search is trying to match. The value is a list of entry IDs.

As the number of entries in the directory grows, the list of entry IDs for some keys can become very large. For example, every entry in the directory has objectClass: top. If the directory maintains a substring index for mail, the number of entries ending in .com could be huge.

A directory server therefore defines an index entry limit. When the number of entry IDs for a key exceeds the limit, the server stops maintaining a list of IDs for that key. The limit effectively means a search using only that key is unindexed. Searches using other keys in the same index are not affected.

The following figure shows a fragment from a substring index for the mail attribute. The number of email addresses ending in com has exceeded the index entry limit. For the other substring keys, the entry ID lists are still maintained. To save space, the entry IDs are not shown in the figure.

Ideally, the limit is set at the point where it becomes more expensive to maintain the entry ID list for a key, and to perform an indexed search than to perform an unindexed search. In practice, the limit is a tradeoff, with a default index entry limit value of 4000. Keep the default setting unless you have good reason to change it.

In this example, an LDAP client application helps people look up names using mobile telephone numbers. The mobile numbers stored on the mobile attribute in the directory.

The LDAP client application sees a search for a mobile number failing with error 50:

The application owner tells you there’s a problem searching on mobile numbers.

As administrator, you can see the failures in the DS access logs. The following example includes only the relevant fields of an access log message with the failure:

For this simple filter, (mobile=14120300042), if the search is uninindexed, you can conclude that the attribute must not be indexed. As expected, the mobile attribute does not appear in the list of indexes for the backend:

If the filter were more complex, you could use run the search with the debugsearchindex attribute to determine why it is unindexed.

You notice that telephoneNumber has equality and substring indexes, and decide to add the same for the mobile attribute. Adding a new index means adding the configuration for the index, and then building the index. An index is specific to a given server, so you do this for each DS replica. For example:

Once the index is built, you check that the search is now indexed by looking at the debugsearchindex output:

You tell the application owner to try searching on mobile numbers now that you have indexed the attribute.

The client application now sees that the search works:

Must you do anything more? What about index-entry-limit settings, for example?

Stop the server, and run the backendstat show-index-status command:

Notice that the equality index mobile.telephoneNumberMatch has no keys whose entry ID lists are over the limit, and the average number of values is 1. This is what you would expect. Each mobile number belongs to a single user. DS uses this index for exact match search filters like (mobile=14120300042).

Notice also that the substring index mobile.telephoneNumberSubstringsMatch:6 has 10 keys whose lists are over the (default) limit of 4000 values. These are the keys for substrings that match only a single digit of a mobile number. For example, a search for all users whose mobile telephone number starts with 1 uses the filter (mobile=1*). This search would be unindexed.

Should you raise the index-entry-limit for this substring index? Probably not, no.

The filter (mobile=1*) matches all mobile numbers for the United States and Canada, for example. Someone running this search is not looking up a user’s name by their mobile phone number. They are scanning the directory database, even if it is not intentional. If you raise the index-entry-limit setting to prevent any Over index-entry-limit keys, the server must update enormous entry ID lists for these keys whenever a mobile attribute value changes. The impact on write performance could be a bad tradeoff.

If possible, suggest that the LDAP application refrains from searching until the user has provided enough digits of the mobile number to match, or that it prompts the user for more digits when it encounters an unindexed search.

If you cannot change the application, it might be acceptable that searches for a single mobile telephone digit simply fail. That might be a better tradeoff than impacting write performance due to a very high index-entry-limit setting.