Bug description: If a filter contains a range search, the
search retrieves one ID per one idl_fetch and merge it to
the idlist using idl_union, which is slow especially when
the range search result size is large.

Fix description: When the idlist size is larger than nsslapd-
lookthroughlimit, the range search returns ALLID (default
value of nsslapd-lookthroughlimit is 5000). Then, the range
search filter is evaluated before returning to the client.
If the default value of nsslapd-lookthroughlimit can be used,
the search elapsed time is much shorter than generating a
complete idlist in index_range_read_ext. Since the nsslapd-
lookthroughlimit is shared among all the search operations,
larger value might be required for other cases. To have its
own control, this patch introduces a new config parameter
nsslapd-rangelookthroughlimit for the range search.

Also, this patch replaced idl_union in index_range_read_ext
with idl_append_extend and sort the idlist at the end. It
improves the range search performance, but it is still slower
than just returning ALLID for the large db.

git patch file (master)
0001-Trac-Ticket-519-Search-with-a-complex-filter-includi.patch

Reviewed by Rich (Thank you!!)

Pushed to master: commit f026ef0447b18994e0e9b847698703436e874f84

Pushed to 389-ds-base-1.2.11: commit 0a54aa676341b7f5f1056373a5067a69cbe54b89

389-ds-base is moving from Pagure to Github. This means that new issues and pull requests
will be accepted only in 389-ds-base's github repository.

This issue has been cloned to Github and is available here:
- https://github.com/389ds/389-ds-base/issues/519

If you want to receive further updates on the issue, please navigate to the github issue
and click on subscribe button.

Thank you for understanding. We apologize for all inconvenience.