directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel L├ęcharny <elecha...@gmail.com>
Subject [Index] SubLevel removal
Date Thu, 12 Apr 2012 13:01:45 GMT
Hi guys,
I'm currently working on the SubLevelIndex removal. This is slightly 
more complex than the OneLevel  index, and there are some choice to be 
made in this area.

Basically, the idea is that we will first search the entry which is the 
parent, then start fetching all the descendant from this point.

Considering we have such a tree :

cn=A
   cn=B
   cn=C
     cn=D
       cn=G
     cn=E
   cn=F
     cn=H

then a search for entries using a SUBTREE scope and a base DN 'cn=C, 
cn=A' will return the following set of entries (the filter is 
objectClass=*, to keep it simple) :
{
   cn=C,cn=A
   cn=D,cn=C,cn=A
   cn=G,cn=D,cn=C,cn=A
   cn=E,cn=C,cn=A
}

Note that the same search with a ONE scope would return cn=D,cn=C,cn=A 
and cn=E,cn=C,cn=A, excluding the cn=C,cn=A entry, which is the base for 
this search).

Now, we have two ways to get those entries :
- depth-first traversal. We fetch every entry, and if it has some 
children, then we go down one level, and so on recursively, until we 
have exhausted all the descendant. The consequence is that the entries 
will be returned in this order :

   cn=C,cn=A
   cn=D,cn=C,cn=A
   cn=G,cn=D,cn=C,cn=A
   cn=E,cn=C,cn=A

- Breadth-first traversal. This time, we exhaust all the children for 
the current level, and then we go down one level, read all the entries, 
etc. We never go down one level if all the entries at the same level 
have not been processed. The entries will be returned in this order :

   cn=C,cn=A
   cn=D,cn=C,cn=A
   cn=E,cn=C,cn=A
   cn=G,cn=D,cn=C,cn=A

The problem with the breadth-first approach is that it puts way more 
pressure on the memory, as we have to keep in memory all the entries 
that have children. With the depth-first approach, we just proceed with 
a new cursor when we have at least one children, so we will have as many 
cursors in memory as the tree's depth (so if we have a 10 levels tree, 
we will keep 10 cursors max). OTOH, the order might be a bit strange 
(even if there is no guarantee whatsoever that the server will return 
the entry in any given order).

IMO, the depth-first approach is the one which offers the best balance 
between performance and memory consumption. Also the return order is not 
that critical assuming that we have implemented the Sort control (which 
is not yet part of our implementation).

Any better idea, or any comments ?

Thanks !

-- 
Regards,
Cordialement,
Emmanuel L├ęcharny
www.iktek.com


Mime
View raw message