8 Understanding the Oracle Unified Directory Indexing Model

Oracle Unified Directory supports multiple kinds of indexes. You must explore this section to learn more about the index types and the manner is which the search is conducted.

This section contains the following topics:

For information about configuring indexes, see Indexing Directory Data.

8.1 Overview of Indexes

Oracle Unified Directory uses indexes to speed up search operations by associating lookup information with Oracle Unified Directory entries. Each search operation includes a search key that specifies the entries to return. During a search operation the server uses the index to find entries that match the search key. If indexes are not configured, then the server must check every entry in a suffix to locate potential matches for the search key.

Navigating through all entries in the directory is resource-intensive, especially for large directories. In addition, unindexed searches might not be allowed to non-privileged users. For more information about assigning privilege for unindexed search, see Understanding Root Users and the Privilege Subsystem. To make searches more efficient, you can configure indexes to correspond to the searches that clients need to perform.

This section contains the following topics:

8.1.1 About Indexes

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

When you perform a search operation, Directory Server uses the index to find entries that match the index key. Without an index, Directory Server must check every entry in a suffix to find the match.

8.1.2 Understanding the Importance of Indexing

Indexes play an important role in enhancing the performance of search operations. Directory Server indexes speed up searches by associating search strings with the contents of a directory.

  • The most efficient methodology to improve search operations against the directory server is to configure indexes, combined with defining an index entry limit on search results.

  • An index stores the values of specified attributes for an entry without storing any other detail about the entry. This saves space and makes search faster by organizing the index around that attribute. If you perform a search on an attribute that has been indexed, Oracle Unified Directory quickly locates the index for the entries that meet the search criteria.

8.2 Supported Index Types

An index is an optional structure to speed up data access. Oracle Unified Directory supports various index types.

The following table lists the types of indexes:

Table 8-1 Supported index types

Type of index Description

Approximate Indexes

An approximate index is used to match values that sound like the values that are provided in the search filter. The purpose of an approximate index is to locate entries that match values similar to the search filter. For example, an approximate index on the cn attribute allows client applications to locate entries even when the names are misspelled.

Equality Indexes

An equality index identifies which entries are exactly equal to the value that is provided in a search filter. An equality index can only be maintained for attributes that have a corresponding equality matching rule.

Ordering Indexes

An ordering index keeps track of the relative order of values for an attribute. It is similar to an equality index, except that it uses an ordering matching rule instead of an equality matching rule to normalize the values. Ordering indexes cannot be maintained for attributes that do not have a corresponding ordering matching rule.

Presense Indexes

A presence index keeps track of the entries that have at least one value for a specified attribute. There is only a single presence index key per attribute, and its ID list contains the entry ID for all entries that contain the specified attribute. The aci attribute is indexed for presence by default to enable quick retrieval of entries with ACIs.

Substring Indexes

A substring index keeps track of which entries contain specific substrings. Index keys for a substring index consist of six-character substrings taken from attribute values and the corresponding values are an ID list containing the entry ID of the entries containing those substrings. The attribute's substring matching rule is used to normalized value the values for the index keys, and substring indexes cannot be defined for attributes that do not contain substring matching rules.

8.3 What is Index Entry Limit?

The index entry limit is a configuration limit.

The index entry limit can be used to control the maximum number of entries that is allowed to match any given index key (that is, the maximum size of an ID list). This provides a mechanism for limiting the performance impact for maintaining index keys that match a large percentage of the entries in the server. In cases where large ID lists might be required, performing an unindexed search can often be faster than one that is indexed.

8.4 Understanding the Search Evaluation Mechanism

To process an LDAP search operation, the server applies each assertion of the search filter to generate a list of candidate entries, which are then combined to form an initial set of candidate entry IDs.

If a candidate set is obtained, the search is considered to be indexed. Each candidate entry is fetched from the entry database and returned to the client if it matches the search scope and filter.

If no candidate set is obtained (because of a lack of indexes or because some index values exceeded the index entry limit), the search is considered to be not-indexed. In this case, a cursor is opened on the DN database at the base entry to iterate through all records in scope, fetching and filtering the corresponding entries until all the entries under the search base have been processed.

Whenever the number of candidate entry IDs from the indexes is found to be 10 or less, no further attempt is made to reduce the number of candidates. Instead those entries are immediately fetched from the entry database and filtered, on the assumption that this is quicker than continuing to read the index databases. This can pay off for AND search filters in which the first component is the most specific.

Search AND filters are also rearranged so that components that are slow to evaluate (greater-than-or-equal, less-than-or-equal) come after components that are generally faster (for example, equality).

8.5 Maintaining Indexes

You can maintain indexes by running some commands.

Consider the following key points for maintaining indexes:

  • Run the verify-index command to check the consistency between the index and the entry data within the directory server database.

    For more information about the command, see verify-index

  • Run the rebuild-index command to rebuild the directory server indexes, if you create a new index or when the index-entry-limit property of an index changes.

    For more information about the command, see rebuild-index

  • Configure a Virtual List View (VLV) index, which is a mechanism used by the Directory Server database to efficiently process searches with VLV controls. A VLV index effectively notifies the server that a virtual list view, with specific query and sort parameters, will be performed. This index also allows the server to collect and maintain the information required to make using the virtual list view faster. A VLV index stores sorted blocks of ID lists, which are a set of entry IDs and the attribute values of the entry to sort on.

    For more information about configuring VLV indexes, see Configuring VLV Indexes.

  • Configure an extensible match index to accelerate search operations using an extensible match search filter. Index keys are values that have been normalized using a specified matching rule, and the corresponding ID list contains the entry ID for all entries that match the value according to that matching rule.

    For more information about extensible match search filter, see extensible match search filter.