directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Stefan Seelmann <seelm...@apache.org>
Subject Re: About reverse index ...
Date Thu, 13 May 2010 09:10:32 GMT
Emmanuel L├ęcharny schrieb:
> On 5/13/10 8:08 AM, Alex Karasulu wrote:
>> Hi Emmanuel,
>>
>> On Sun, May 9, 2010 at 6:42 PM, Emmanuel
>> Lecharny<elecharny@gmail.com>wrote:
>> ...
>>
>> As soon as you consider that a delete operation will need to update
>> all the
>>   
>>> index the deleted entry uses, you see that you can benefit from
>>> having such
>>> reverse index : you don't have to grab the entry from the backend, as
>>> you
>>> already have it's ID, which is all what you need. Thus, a delete
>>> operation
>>> is just about doing :
>>> - get the entry ID
>>> - for each index, if we have an<Entry ID>  stored, then grab the
>>> associated
>>> values, and for each value, delete them from the forward index.
>>> - delete the entry from the MT
>>>
>>>
>>>      
>> Yep this is one benefit of the reverse index.
> At this point, I'm questionning the fact that it's an advantage. We can
> do almost the same thing using the forward index, assuming we know the
> attribute we are dealing with, and we also have the value in the filter,
> so we can check that the entry we are looking at is present in the index
> for this attribuet. Let me explain with some example :
> 
> filter : (cn=value), cn is indexed.
> you are looking for entry E(x)
> The reverse index will contain :
> E(x) --> value
> the forward index will contain :
> vaue --> E(1), E(5), ... E(x)...E(N)
> 
> so you can still in a O(log(N)) find the entry in the forward index
> without fetching the entry first.
> 
>> There are other uses for the
>> reverse index. To start let's just list the various index methods
>> leveraging
>> the reverse index:
>>
>>
>>      boolean reverse( ID id ) throws Exception;
>>
>>
>>      boolean reverse( ID id, K attrVal ) throws Exception;
>>
>>
>>      boolean reverseGreaterOrEq( ID id ) throws Exception;
>>
>>
>>      boolean reverseGreaterOrEq( ID id, K attrVal ) throws Exception;
>>
>>
>>      boolean reverseLessOrEq( ID id ) throws Exception;
>>
>>
>>      boolean reverseLessOrEq( ID id, K attrVal ) throws Exception;
>>    
> In fact, those methods are not existing anymore (don't ask me why, I
> just grepped all the code). I don't know where you get them from ...

Check class org.apache.directory.server.xdbm.Index<K, O, ID>

> The only place where the reverse index is used atm is when checking that
> an entry has a value.
>>
>> These various reverse lookups are used all over the XDBM search code base
>> with various expression Evaluators and Cursors.
> Well, not anymore :)

They are still used. In fact there are more "reverse" methods in Index
class:

    K reverseLookup( ID id ) throws Exception;
    IndexCursor<K, O, ID> reverseCursor() throws Exception;
    IndexCursor<K, O, ID> reverseCursor( ID id ) throws Exception;
    Cursor<K> reverseValueCursor( ID id ) throws Exception;

I listed all callers in [1].

Kind Regards,
Stefan

[1] http://pastebin.com/dsBC3GVr


Mime
View raw message