Re: Some openldap fixes... (fwd)

[peter <peter@twistor.admin.lion-access.net>]

On Wed, Sep 20, 2000 at 07:34:15AM -0700, Kurt D. Zeilenga wrote:
> 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?
true,.. this now takes something like:
O( E_i E_{j<i} n_j + n_i)

however,.. if i change the idl_union call to idl_cat
and post process with qsort it will be like:
O( i + m ln(m)) where: m = E_i n_i

which is much nicer :)
> 
> 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?
you got me here :)

however we're building candidate tables, thus one needs
only provide an upper bound. so my proposition would be
to always include the base id.

Peter