To process an LDAP search operation, the JE back end first applies the search filter to the attribute indexes to obtain an initial set of candidate entry IDs. Then the candidates can be further refined by fetching subordinates of the base entry from either the children or subtree databases (depending on the search scope).
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 the DN/ID records, 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).