directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel Lecharny <>
Subject Re: [ApacheDS] OR expression optimizations for Cursors and Evaluators
Date Fri, 28 Mar 2008 17:11:21 GMT
Alex Karasulu wrote:
> <snip/>
> More thoughts ...
> So if 1000 entries are in scope.  Then the filter above with the first 
> set of scan counts would result in a Cursor over the subtree index 
> (presuming subtree search scope parameter value).  This is because 
> 1000 < 1110.  This is what happens when the scope node is AND'ed up at 
> the top instead of being pushed deeper into the AST in multiple places.
> If we push the scope node down to constrain each assertion in 3 places 
> as well as at the top then the Cursor will still be built on the scope 
> node at the top most conjunction.  This is because and'ing the scope 
> node in lower layers still results in the same scan counts.  For example
> (& (ou=engineering)[100] (scope)[1000] )
> still has a total scan count of 100.  So the filter AST with scope 
> constraints applied all over will still build the candidate generating 
> cursor on the topmost conjunction's scope.  It will require 1000 
> iterations with 1000*6 lookups now.  Without pushing the scope into 
> leaves we get 1000 iterations with 1000*3 lookups.
> So this is not so much a great way to implement your idea.
As soon as you are using the scope to evaluate the number of candidates 
for each index (here, for the ou=engineering index), you don't need 
anymore to add the scope node, as it's already take into account in the 
first assertion.
The filter will be much more simple :


In fact, you will just have to walk the index, and return the candidates.

If you have more assertions, this is exactly the same.
> Alex

cordialement, regards,
Emmanuel L├ęcharny

View raw message