Return-Path: 
 <dev-return-24541-apmail-directory-dev-archive=directory.apache.org@directory.apache.org>
Delivered-To: apmail-directory-dev-archive@www.apache.org
Received: (qmail 72260 invoked from network); 28 Mar 2008 17:12:56 -0000
Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.2)
  by minotaur.apache.org with SMTP; 28 Mar 2008 17:12:56 -0000
Received: (qmail 58761 invoked by uid 500); 28 Mar 2008 17:12:55 -0000
Delivered-To: apmail-directory-dev-archive@directory.apache.org
Received: (qmail 58717 invoked by uid 500); 28 Mar 2008 17:12:55 -0000
Mailing-List: contact dev-help@directory.apache.org; run by ezmlm
Precedence: bulk
List-Help: <mailto:dev-help@directory.apache.org>
List-Unsubscribe: <mailto:dev-unsubscribe@directory.apache.org>
List-Post: <mailto:dev@directory.apache.org>
List-Id: <dev.directory.apache.org>
Reply-To: "Apache Directory Developers List" <dev@directory.apache.org>
Delivered-To: mailing list dev@directory.apache.org
Received: (qmail 58706 invoked by uid 99); 28 Mar 2008 17:12:55 -0000
Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136)
    by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 28 Mar 2008 10:12:55 -0700
X-ASF-Spam-Status: No, hits=-0.0 required=10.0
	tests=SPF_PASS
X-Spam-Check-By: apache.org
Received-SPF: pass (athena.apache.org: domain of elecharny@gmail.com
 designates 72.14.220.154 as permitted sender)
Received: from [72.14.220.154] (HELO fg-out-1718.google.com) (72.14.220.154)
    by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 28 Mar 2008 17:12:12 +0000
Received: by fg-out-1718.google.com with SMTP id e12so274626fga.3
        for <dev@directory.apache.org>; Fri, 28 Mar 2008 10:12:23 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=beta;
        h=domainkey-signature:received:received:message-id:date:from:user-agent:mime-version:to:subject:references:in-reply-to:content-type:content-transfer-encoding;
        bh=q686VCLXxAfULNPHPnMPT0WaVnbxzfsFcQ2dIYhqouY=;
        b=qiM0mOahvhRVvF2WbNPWsh2xZHVeOnQtbJTMdhE//GEwTtDLqHz9G61kVzXiry6CdJXzFj4BbZet0d/M7I9rl58W0/UEWKRq26ecojNcMJknIUKtUSqZag+jocTf9DgRf9M25pL9Wdtp68lhxDDPyC40Pj97W4n6Xrbp9zetfq4=
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=beta;
        h=message-id:date:from:user-agent:mime-version:to:subject:references:in-reply-to:content-type:content-transfer-encoding;
        b=cefyV3DecscMFyGU3lu05jIC+aTs3ZtnXPUUv/4KGk3OxyWnbTcHq2LnYnOjkhz/IUie0XgcV98VTK/5PXSbbGN+FJf4G6ctsFAV3trnpBgaBKJwQ6m29aw0HxD5YTCNjhTViwl+NbMAdS/J0dFDivZNedB8yAtz0imHMZG25VQ=
Received: by 10.86.79.19 with SMTP id c19mr1948755fgb.16.1206724343115;
        Fri, 28 Mar 2008 10:12:23 -0700 (PDT)
Received: from ?192.168.1.5? ( [82.245.116.110])
        by mx.google.com with ESMTPS id 12sm2654884fgg.6.2008.03.28.10.12.21
        (version=TLSv1/SSLv3 cipher=RC4-MD5);
        Fri, 28 Mar 2008 10:12:22 -0700 (PDT)
Message-ID: <47ED26B9.7000904@gmail.com>
Date: Fri, 28 Mar 2008 18:11:21 +0100
From: Emmanuel Lecharny <elecharny@gmail.com>
User-Agent: Thunderbird 1.5.0.14ubu (X11/20080306)
MIME-Version: 1.0
To: Apache Directory Developers List <dev@directory.apache.org>
Subject: Re: [ApacheDS] OR expression optimizations for Cursors and Evaluators
References: <a32f6b020803261402i609d9e44k2210569decd5a74a@mail.gmail.com>
	 <47EB53D6.4050009@gmail.com>
	 <a32f6b020803270831u1c194e8an3fcd99e074e10517@mail.gmail.com>
	 <a32f6b020803271043ve468864l28f798921c074e0f@mail.gmail.com>
	 <47ECD137.6020603@gmail.com>
	 <a32f6b020803280725p6c4aa3c2ob3e7850f3ae93ec8@mail.gmail.com>
 <a32f6b020803280753t75a3f6f5le7bd140043bd4ee0@mail.gmail.com>
In-Reply-To: <a32f6b020803280753t75a3f6f5le7bd140043bd4ee0@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
X-Virus-Checked: Checked by ClamAV on apache.org

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 :

(ou=engineering[100])

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
www.iktek.com
directory.apache.org