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 (nike.apache.org: domain of akarasulu@gmail.com designates
 74.125.82.178 as permitted sender)
MIME-Version: 1.0
Sender: akarasulu@gmail.com
In-Reply-To: <4E10CF11.2060308@gmail.com>
References: <4E10CF11.2060308@gmail.com>
Date: Mon, 4 Jul 2011 23:48:54 +0300
Message-ID: 
 <CADwPi+GXCQkx5yfY-N394+XsqaeVVBiNTzurMv=80YYSHqHuhw@mail.gmail.com>
Subject: Re: About the reverse table removal.
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

On Sun, Jul 3, 2011 at 11:20 PM, Emmanuel Lecharny <elecharny@gmail.com> wrote:
> 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.

Good to have your feedback on this matter. I was hoping that this
simplification could work but did not have the time to actually think
it through.

Thanks,
Alex