Please review: [389 Project] #519: Search with a complex filter including range search is slow

[Noriko Hosoi]

https://fedorahosted.org/389/ticket/519

https://fedorahosted.org/389/attachment/ticket/519/0001-Trac-Ticket-519-S...

  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.