Le 1/11/13 1:51 PM, Howard Chu a écrit :
/* 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
* (1) is faster if the filter candidate list is smaller than the
* and vice versa. Currently only (1) is implemented.
* We don't know the actual size of the subtree, we only know the
* onelevel children. For subtree searches we take a guess.
* Due to the fact pagedResults cookie is only big enough to store
* 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
* if the target entry is moved or deleted. We'd also need to
* 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
* cookie definition is global to all of slapd so the change would
* 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.
ApacheDS stores the number of children, and the bumber of descendants
alltogether, in the dn2id table. That allows use to use the scope as the
primary filter for candidates. The extra cost is when you
add/delete/move an entry, you have to update all the dn2id (in OpenLDAP
terminology) parents from the modified entry down to the root. That's a
price we accept to pay.
Once you have this number, you can use either (1) or (2) to start with.
At least, you are sure to pick the smallest set of candidates.
Before that, we had a OneLevel index and a SubLevel index which were
containing the number of children/descendant for each entry. This is a
way to avoid modifying the dn2id table, but that's two index you have to
update everytime you do an add/del/mod. We get rid of those two tables
recently, gaining some time and disl space in the process.