On Fri, Mar 28, 2008 at 1:11 PM, Emmanuel Lecharny <elecharny@gmail.com> wrote:
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.

Right.  This is true.  However how do you do that? You have to change the way indices are designed/organized.

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.

Hmmm I'm missing the mechanics of actually how the operation would proceed using the present system of indices.  What new structure would we use for index keys and values?