Re: slow search when out-of-scope entries match (ITS#2897)

[Kurt@OpenLDAP.org]

At 02:52 AM 1/5/2004, h.b.furuseth@usit.uio.no wrote:
>Kurt D. Zeilenga writes:
>> This is an example of a search were each of the indexed components
>> of the search criteria are ineffective at reducing the number of
>> candidate entries.  Note that the indexed components include both
>> the filter and the scope.
>
>Sure, but the _combination_ of the two would reduce the number of
>candidate entires to nothing.

If both indexes say "cannot narrow the candidate set" (ALLIDS),
then the candidate set cannot be narrowed.

>> There are a number of ways to address such issues:
>>         a) place admin limits on number of candidates,
>>         b) utilize "better" search criteria,
>>         c) utilize a "better" DIT organization,
>>         d) use multiple databases to localize searches/indices,
>>         e) tune slapd(8) (including changing various hardcoded constants)
>
>I don't understand.  Why not
>          f) take the intersection of
>             - the entries that are in scope (DN "index"),
>             - the entries that match the filter (attribute index)
>?  That would yield just the entries that actually need to be tested
>with the filter.

s/filter/search criteria/.

But of the scope index says ALLIDs, then it doesn't help reduce
the number of candidates which need to be examined.  Likewise
for indexes for the filter.  If no reduction is done, then
test_filter(), which tests not only the filter but the scope,
is called to examine the entry to see if it matches the search
criteria.

>Is that impossible because of the 'ALLIDS threshold'
>Pierangelo mentioned?

You have hit the threshold twice.  Once of the filter and once
for the scope.

>I don't know what that is.

It's the threshold which the backend uses for index keys which
are associated with large number of entries.  Instead of managing
a large set of values for a key, the backend replaces large sets
with an indicator called ALLIDS.  That indicator means that the
key is not effective in reducing the candidate set.

>But if so, I think
>this threshold should be configurable - maybe on a per-index basis,
>if there is a good performance reason not to make it too large in
>general.

Feel free to submit code.

>> This is not viewed as a bug in the software, but an inherent aspect
>> of the database backend design.
>
>If the index isn't used, the scope should at least be used

If the scope index is used together with filter indexes.
However, if all the indexes return ALLIDS, then every entry
needs to be tested against the search criteria.

>, so
>that only the entries in scope are tested with the filter.

Well, they need to be tested for the scope and the filter.  That
is what is happening.

>Currently,
>all the entires in the database are tested - in scope or not.

Yes, because the server needs to test whether they are in scope
or not.

Kurt