6 Understanding the Oracle Unified Directory Indexing Model

Like a book index, Oracle Unified Directory indexes speed up searches by associating search strings with the contents of a directory.

This chapter describes the various index types and the way in which searches are evaluated and includes the following sections:

Section 6.1, "Overview of Indexes"
Section 6.2, "Index Types"
Section 6.3, "Index Entry Limit"
Section 6.4, "Search Evaluation"
Section 6.5, "Maintaining Indexes"

For information about configuring indexes, see Section 16.7, "Indexing Directory Data".

6.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 Chapter 9, "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:

Section 6.1.1, "What is an Index?"
Section 6.1.2, "Understanding the Importance of Indexing"

6.1.1 What is an Index?

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.

6.1.2 Understanding the Importance of Indexing

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.

6.2 Index Types

Oracle Unified Directory supports the following index types:

Section 6.2.1, "Approximate Indexes"
Section 6.2.2, "Equality Indexes"
Section 6.2.3, "Ordering Indexes"
Section 6.2.4, "Presence Indexes"
Section 6.2.5, "Substring Indexes"

6.2.1 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.

6.2.2 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.

6.2.3 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 can not be maintained for attributes that do not have a corresponding ordering matching rule.

6.2.4 Presence 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.

6.2.5 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.

6.3 Index Entry Limit

The index entry limit is a configuration limit that 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.

6.4 Search Evaluation

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 some of the index values having 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).

6.5 Maintaining Indexes

You can 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 Section A.3.16, "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 Section A.3.13, "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 Section 16.7.2, "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 Section D.5.13, "extensible match search filter."