directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Martin Alderson <eq...@planetquake.com>
Subject Re: [ApacheDS] Using indices while evaluating filters with negation operators (was: Re: svn commit: r567310 - ... )
Date Sun, 19 Aug 2007 21:11:14 GMT
Hi Alex,

OK, so we would just need a way to enumerate over all entries from the 
master table, throwing away all those found in the specified index.

I guess that's more efficient than the way I'm doing it now - where we 
enumerate over all entries in the master table, then (I think!) read 
each and skip it if it doesn't meet the condition in the sub filter. 
For the entries that are skipped we basically have an improvement of 
just requiring a hash lookup rather than a database read and some check 
(usually a string comparison).

Couldn't we use this same optimisation for AND and OR filters - i.e. 
leverage multiple indices?  As an example, for the filter 
(&(objectClass=inetOrgPerson)(roomNumber=52)), we could use indices for 
both objectClass and roomNumber (if they existed) to just read those 
entries from the database that match both filters.  I've been thinking 
about this kind of optimisation for a few days now - am I right in 
thinking this is possible?

I don't fully understand the JDBM API yet, but will keep looking at it 
until it clicks into place.  If the optimisation I am talking about 
above is possible I would be very interested in implementing it.

Martin



Alex Karasulu wrote:
> Hi Martin,
> 
> On 8/18/07, Martin Alderson <equim@planetquake.com> wrote:
>> Hi Alex,
>>
>> We need both the entries that don't pass the specified filter for the
>> attribute, and those that don't have the attribute at all.  We would
>> need a way to get all entries that are not contained in the index for
>> the attribute and a way to join that enumeration to the one we had in
>> the old code (which should be easy enough with a JoinedEnumeration class).
>>
>> I think the current attribute indices need to be modified to store a
>> list of entries that do not have the attribute.  Each index will then
>> take up a bit more space.
> 
> 
> Yeah this could get very large.  If for example theres an index on dc and
> there are 4 entries in the server that have a dc attribute when there are
> millions of entries in the server then the index as it is now will be tiny.
> Now
> if we applied this idea where we included all the entries that do not have
> this attribute at all then we'd millions - 4 entries in that btree of the dc
> index.
> 
> All existing ApacheDS installations would
>> also need their attribute indices rebuilding too.
>>
>> What do you think?
> 
> 
> I think we can logically infer that a value is not present if the entry id
> is not in this attribute
> index and is not in the existence system index.  You see where I'm going
> with this?
> 
> Alex
> 


Mime
View raw message