Mailing-List: contact dev-help@directory.apache.org; run by ezmlm
Precedence: bulk
Reply-To: "Apache Directory Developers List" <dev@directory.apache.org>
Received-SPF: pass (athena.apache.org: domain of akarasulu@gmail.com
 designates 74.125.82.44 as permitted sender)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=mime-version:sender:in-reply-to:references:date
         :x-google-sender-auth:message-id:subject:from:to:content-type
         :content-transfer-encoding;
        b=gvGN+Slc/BSKPk9+Dgt5NnjtnAKLB1ozbRbHVB5Ppdlo8Pr7LD7Gczywz6OUrVyiaS
         SoDPn8C9gk34MteUhf34JCCtKyTNoC6iutHZDirao6Jj5o5K54DzfpilHLrs/JXWiR7/
         wGs5Lb9FHJkaN1Ggt1bBtZK9iG8lwFDuz5v5o=
MIME-Version: 1.0
Sender: akarasulu@gmail.com
In-Reply-To: <4E0445C3.90201@apache.org>
References: <4E0367C5.6040705@gmail.com>
	<BANLkTikHg1tJm0nXJysrL12jqqrajbupPg@mail.gmail.com>
	<4E04411C.70302@apache.org>
	<BANLkTi=1apB++wiABZJeBdVnt1yLMTMG9g@mail.gmail.com>
	<4E04443B.8060506@apache.org>
	<BANLkTi=P3nPUy0y_DRtVBziyws+0AFqxOA@mail.gmail.com>
	<4E0445C3.90201@apache.org>
Date: Fri, 24 Jun 2011 11:10:18 +0300
Message-ID: <BANLkTimT1tKjh+9MNVhiHNpkkxGNMkVa2Q@mail.gmail.com>
Subject: Re: Index reverse tables : are they useful ?
From: Alex Karasulu <akarasulu@apache.org>
To: Apache Directory Developers List <dev@directory.apache.org>,
 elecharny@apache.org
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

On Fri, Jun 24, 2011 at 11:07 AM, Emmanuel L=E9charny
<elecharny@apache.org> wrote:
> On 6/24/11 10:04 AM, Alex Karasulu wrote:
>>
>> On Fri, Jun 24, 2011 at 11:00 AM, Emmanuel L=E9charny
>> <elecharny@apache.org> =A0wrote:
>>>
>>> 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 th=
is
>>>>>> we know is not possible. So the lookups against the reverse table wi=
ll
>>>>>> 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 vali=
d
>>>>> candidate can then be done in one shot : do the intersection of the t=
wo
>>>>> sets
>>>>> (they are ordered, so it's a O(n) operation) and just get the matchin=
g
>>>>> entries.
>>>>>
>>>>> Compared to the current processing (ie, accessing the reverse index f=
or
>>>>> *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+IndexE=
ntry,
>>> where I added some paragraphs explaining this idea. We can comment on
>>> this
>>> page.
>>
>> Nice pictures - what did you use for that? Reading further ...
>
> YeD
>>
>> 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?
>
> Right now, I just updated the existing doco with some extended explanatio=
n
> on the existing code. I can move suggestions to another page, sure.

Nah you did good - I spoke too soon.

Thanks,
Alex