Re: Some openldap fixes... (fwd)

["Kurt D. Zeilenga" <Kurt@OpenLDAP.org>]

At 08:07 PM 9/19/00 +0200, Marijn Meijles wrote:
>I hope this is clear enough :)

I understand DB_SET_RANGE... I'm just having a tough time
convincing myself that this use of it correct for subtree
searches.  Let me run through some examples...

1) search base is parent of an entry containing the value
the key for this parent is returned, it only contains IDs
only for immediate children of the base with the value.
You say you merge IDLs for <base dn*>.  I assume this
means that for each value the server reads additional keys
and merging IDLs until the key is outside of scope.  This
would means that the server needs to fetch and merge a key
for each container in scope which contains one or more
matching entries.  This can get quite expensive.  Is this
correct?

2) search base is parent of the parent of an entry
containing the value.  The first key as it's greater
than the search key.  Otherwise same as above.

3) search base is child of the parent of an entry
containing the value.   The key is not returned as
it's less than the search base.  Is this correct?

Assuming 1) and 3) are correct, one could fix 3) by
generating a separate subtree index:

relational table where:                                                                   
  tablename: <attribute>
    key:        <prefix><value>|reverse_string(<dn>)
    data:       id-list of all elements that match:
                (<attribute>=<value>) && (<dn>=<dn>)

However, this worsens 1) as one would have to fetch and
merge a key for every matching entry within scope.

Kurt