directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Alex Karasulu <akaras...@apache.org>
Subject Re: Index reverse tables : are they useful ?
Date Fri, 24 Jun 2011 08:06:29 GMT
On Fri, Jun 24, 2011 at 11:04 AM, Alex Karasulu <akarasulu@apache.org> wrote:
> On Fri, Jun 24, 2011 at 11:00 AM, Emmanuel L├ęcharny
> <elecharny@apache.org> wrote:
>> On 6/24/11 9:51 AM, Alex Karasulu wrote:
>>>
>>>>> The reverse index has no duplicate keys. The only way to get a
>>>>> duplicate key in the reverse index is if the same entry (i.e. 37)
>>>>> contained the same value ('foo') for the same (sn) attribute. And this
>>>>> we know is not possible. So the lookups against the reverse table will
>>>>> be faster.
>>>>
>>>> I was thinking about something a bit different : as soon as you have
>>>> grabbed
>>>> the list of entry's ID from the first index, looking into the other
>>>> indexes
>>>> will also return a list of Entry's ID. Checking if those IDs are valid
>>>> candidate can then be done in one shot : do the intersection of the two
>>>> sets
>>>> (they are ordered, so it's a O(n) operation) and just get the matching
>>>> entries.
>>>>
>>>> Compared to the current processing (ie, accessing the reverse index for
>>>> *each* candidate), this will be way faster, IMO.
>>>
>>> This is a VERY interesting idea. Maybe we should create a separate
>>> thread for this and drive deeper into it. You got something I think
>>> here.
>>>
>> have a look at
>> https://cwiki.apache.org/confluence/display/DIRxSRVx11/Index+and+IndexEntry,
>> where I added some paragraphs explaining this idea. We can comment on this
>> page.
>
> Nice pictures - what did you use for that? Reading further ...
>
> Also if you're doing this in a branch, hence we're not yet committed
> on the approach, can you please do this on a separate page so you
> don't alter the existing documentation?

I may have spoke too soon. This stuff just seems to elaborate on how
indices works. Maybe we should use some idea sections for the new
concepts we're testing in this area.

Alex

Mime
View raw message