directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel Lecharny <>
Subject About the reverse table removal.
Date Sun, 03 Jul 2011 20:20:33 GMT
Hi guys,

I had time yesterday and today to think a bit more about the reverse 
table we use in index. I thought we were able to remove them and saving 
the time it costs to generate them.

However, one day and a half without coding make me realize that those 
reverse table are a critical part of an efficient evaluation engine. I 
initially thought that using some Sets computation could allow us to 
remove those table, and I was right, put to the point we don't have to 
manipulate big sets of IDs. For instance, with a huge database with 
millions of entries, a OneLevel or SubLevel index will potentially 
contains millions of IDs associated with one ID. In this case, doing an 
intersection operation on this huge set will simply be overkilling in 
term of memory (as we wlll have to keep the resulting set in memory).

OTOH, the reverse table on a OneLevel or SubLevel index will only 
contain a few IDs associated with one entry, unless the tree is 
extremely deep.

This is an issue not only for the OneLevel or SubLevel index, but also 
for the ObjectClass index.

As of now, I don't really think that continuing any further is worthily. 
The best is probably to keep going with trunk, and eventually re-inject 
the few fixes I have applied i my experimental branch.

In any case, this was an interesting exercise : it helped me to get deep 
into this part of the code I was not familiar with, and at the end, 
validate the initial approach.

Emmanuel L├ęcharny

View raw message