directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Emmanuel Lecharny" <>
Subject Re: [ApacheDS] OR expression optimizations for Cursors and Evaluators
Date Sat, 29 Mar 2008 18:32:31 GMT
> > > So this is not so much a great way to implement your idea.
> > As soon as you are using the scope to evaluate the number of candidates
> > for each index (here, for the ou=engineering index), you don't need
> > anymore to add the scope node, as it's already take into account in the
> > first assertion.
> Right.  This is true.  However how do you do that? You have to change the
> way indices are designed/organized.

Well, not the indices (they remain the same). But the Hierarchy index
will carry more infos, like a sub-index for each subtree. For
instance, let's say we have indexed CN. Let's say we have three trees

dc=example,dc=com (with some children excluding the next two entries)
dc=US,dc=example,dc=com (with some children)
dc=FR,dc=example,dc=com (with some children)

we will have three sub indices for the CN attribute : one for each subtree.

This may be costly at first sight, as if you have big hierarchies, you
will have a lot of sub-indices, but you can also consider that indices
will point to sub-indices when going down the tree. Here, suppose we
have the CN_US sub index and the CN_FR sub index. The
dc=example,dc=com CN index will be something like :

<id of the entry>
<id of each children>
<pointer to the CN_FR index>
<pointer to the CN_US index>

In other words, you store two kinds of values : refs to the master
table for the entry itself and all of its children, and a link to the
subtrees if they have children.

This will need something a little bit more complex than a BTree, but
that may improve the performance.

You also have to keep in mind that generally, we don't have big hierarchies.

Of course, this needs a lot of refinment, and may be I'm totally off
track, but there is nothing we can't discuss and clarify in the next
two weeks...

Emmanuel L├ęcharny

View raw message