Overview#

An index is a mechanism used by the Directory Server database that can be used to efficiently find entries matching search criteria. An index maps a key to an ID list, which is the set of entry IDs for the entries that match that index key.

Normally in LDAP there are three basic index types implemented:

  • Equality or Value indexes are used to identify entries containing an attribute value that exactly matches a given assertion value.
  • Presence indexes are used to identify entries that contain at least one value for a given attribute.
  • Substring indexes are used to identify entries that contain an attribute value matching a given substring assertion.

The various LDAP server implementations may have other indexes.

Cost of Indexes#

OpenDS - There are six primary types of indexes in OpenDS:#

  • Approximate indexes are used to identify entries containing attribute values approximately equal to a given Assertion Value.
  • Equality indexes are used to identify entries containing an attribute value that exactly matches a given assertion value.
  • Extensible Match Index are used to identify entries that match a given ExtensibleMatch filter.
  • Ordering indexes are used to identify entries that have values that are greater than or equal to, or less than or equal to, a given assertion value.
  • Presence indexes are used to identify entries that contain at least one value for a given attribute.
  • Substring indexes are used to identify entries that contain an attribute value matching a given substring assertion.

Edirectory Indexes#

Some specific information on Edirectory Indexes.

Indexing in OpenLDAP#

The types of indexing available map 1 to 1 with the types of filter comparisons available in the LDAP protocol. Yes, you should create indices to match the actual filter terms used in search queries.

Almost no applications use presence filters in their search queries. Presence indexing is pointless when the target attribute exists on the majority of entries in the database. In most LDAP deployments presence indexing should not be done, it's just wasted overhead.

Here's the capsule summary of how a search works - if you're searching on a filter that has been indexed, then the search reads the index and pulls exactly the entries that are referenced by the index. If the filter term has not been indexed, then the search must read every single entry in the target scope and test to see if each entry matches the filter. Obviously indexing can save a lot of work when it's used correctly.

But assuming your application actually *does* use presence filters, if the target attribute exists on the majority of entries in your target scope, then all of those entries are going to be read anyway, because they are valid members of the result set. In a sendmail MTA subtree, where 100% of the entries are going to contain the sendmail attributes, the presence index does absolutely NOTHING to benefit the search because 100% of the entries match that presence filter. So the resource cost of generating the index is a complete waste of CPU time, disk, and memory. Don't do it unless you know that it will be used, and that the attribute in question occurs very infrequently in the target data. The most common message you'll see that you should pay attention to is:

"<= bdb_equality_candidates: (foo) index_param failed (18)"

That means somebody tried to use an equality filter (foo=<somevalue>) and attribute foo does not have an equality index. If you see a lot of these messages, you should add the index. If you see one every month or so, it may be acceptable to ignore it.

More Information#

There might be more information for this subject on one of the following:

Add new attachment

Only authorized users are allowed to upload new attachments.
« This page (revision-22) was last changed on 21-Nov-2015 13:21 by jim