ITS#7473 back-mdb search

[Howard Chu <hyc@symas.com>]

    /* There are two approaches to the search function:
     * 1) walk the list of filter candidates, and see which are in scope.
     * 2) walk the scope tree, and see which are in the filter candidates.
     * (1) is faster if the filter candidate list is smaller than the scope tree,
     * and vice versa. Currently only (1) is implemented.
     *
     * We don't know the actual size of the subtree, we only know the count of
     * onelevel children. For subtree searches we take a guess.
     *
     * Due to the fact pagedResults cookie is only big enough to store a single
     * entryID, if pagedResults is in use we will always do (1). For (2) to work
     * reliably we need to use the parent's entryID, to avoid losing our place
     * if the target entry is moved or deleted. We'd also need to store the
     * count of where we were under the parent. I.e., we need the cookie to be
     * two words long. We can examine that in the future, but the pagedResults
     * cookie definition is global to all of slapd so the change would impact
     * other backends and overlays.
     */

We could alter the dn2id index format, and maintain a numSubordinates counter 
there. That would avoid the need to guess. Otherwise I figure we fudge a guess 
based on the number of onelevel children and the depth of the baseDN (relative 
to the suffix). I.e., the longer the DN, the smaller the guess, relative to 
the total number of entries in the DB. Naturally I'd prefer to avoid altering 
the dn2id index format.

Suggestions?

--
  -- Howard Chu
  CTO, Symas Corp.           http://www.symas.com
  Director, Highland Sun     http://highlandsun.com/hyc/
  Chief Architect, OpenLDAP  http://www.openldap.org/project/