Return-Path: X-Original-To: apmail-directory-dev-archive@www.apache.org Delivered-To: apmail-directory-dev-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id BA43E91CD for ; Mon, 26 Mar 2012 12:32:31 +0000 (UTC) Received: (qmail 97970 invoked by uid 500); 26 Mar 2012 12:32:31 -0000 Delivered-To: apmail-directory-dev-archive@directory.apache.org Received: (qmail 97907 invoked by uid 500); 26 Mar 2012 12:32:31 -0000 Mailing-List: contact dev-help@directory.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: "Apache Directory Developers List" Delivered-To: mailing list dev@directory.apache.org Received: (qmail 97899 invoked by uid 99); 26 Mar 2012 12:32:31 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 26 Mar 2012 12:32:31 +0000 X-ASF-Spam-Status: No, hits=1.5 required=5.0 tests=HTML_MESSAGE,RCVD_IN_DNSWL_LOW,SPF_PASS X-Spam-Check-By: apache.org Received-SPF: pass (nike.apache.org: domain of akarasulu@gmail.com designates 74.125.82.44 as permitted sender) Received: from [74.125.82.44] (HELO mail-wg0-f44.google.com) (74.125.82.44) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 26 Mar 2012 12:32:23 +0000 Received: by wgbdr13 with SMTP id dr13so3838011wgb.1 for ; Mon, 26 Mar 2012 05:32:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:content-type; bh=Dyi0ajlrDEDA1c+voA6J1eX1VuZpGV16O9fSsWSn+g0=; b=N/9ywPAYZhgIZAVIaVh9jTJanasmMdk3x1y53CiybXDXrParyryjCfTGnRur/gsgeC 5IibURXARxtRWxpNM0yhpjVRp6GyL2SX+NsxI3yHS0ocQ6RcnMVW7g/iDcKacBooO2Xf 0al2ZFkhmwahQPaHeusfu6eLDvOj2WEoWLkdMHlSuHJ7aovE9MhpywQ44qMJbwC9AvVq z/yG6q7rwvwUW/uGOEVMZrEoBM5et/nY6c9B/4Ui2iGYz7zliAfbFX7IoGHd1wNAP+bR Aflw7P3LhCJioSYFPCuV+gE66tpsDHfgmer+F8cavln0G2bZKfa92BJ0DNjTwj1bhjI+ rHOQ== MIME-Version: 1.0 Received: by 10.216.137.163 with SMTP id y35mr12247451wei.33.1332765122887; Mon, 26 Mar 2012 05:32:02 -0700 (PDT) Sender: akarasulu@gmail.com Received: by 10.180.4.1 with HTTP; Mon, 26 Mar 2012 05:32:02 -0700 (PDT) In-Reply-To: <4F6B5F4B.5000209@gmail.com> References: <4F6B5F4B.5000209@gmail.com> Date: Mon, 26 Mar 2012 15:32:02 +0300 X-Google-Sender-Auth: 4F2Rziqw7enBkq1v9tj9iiHY9NQ Message-ID: Subject: Re: [index] reverse index usage for user attributes From: Alex Karasulu To: Apache Directory Developers List Content-Type: multipart/alternative; boundary=0016e6de00d5b8009904bc248f02 --0016e6de00d5b8009904bc248f02 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable On Thu, Mar 22, 2012 at 7:20 PM, Emmanuel L=E9charny w= rote: > Hi, > > Currently, we create a forward and a reverse index for each index > attribute. The forward index is used when we annotate a filter, searching > for the number of candidate it filters. The reverse index usage is a bit > more subtile. > > [Hope you don't mind below I just use concise English to express the process - not trying to insult your description - apologies if it sounds this way.] To state this more concisely, the reverse index facilitates rapid Evaluator evaluations of non-candidate generating assertions in the filter AST. As you know, one assertion in the filter (scope assertions included) is selected as the candidate generating assertion which uses a Cursor to generate candidates matching it's logic. The other filter assertions in the AST are used to evaluate whether or not the generated candidates match. NOTE: the optimizer annotates the AST's nodes with scan counts and this is used to drive selection of the proper candidate generating assertion in the AST. This is done using a DFS through the AST to find the lowest scan count containing leaf node (an assertion). This reduces the search set. Let's consider a filter like (cn=3Djo*). As we don't have any clue about th= e > value (it will start with 'jo', but that's all we know), we can't use the > 'cn' forward index. Yep the scan count annotation used for the cn=3Djo* assertion will be the total count of entries in the DIB since the BTree cannot give us a count figure. So depending on what scope is used it will most likely be the scope assertion that will drive candidate generation since it will most likely have a smaller scan count. > We can't use the 'cn' reverse index either, at least directly. So the > engine will use the scope to determinate a list of candidate : {E1, E2, .= .. > En}. Now, instead of fetching all those entries from the master table, wh= at > we can do is to use the 'cn' reverse table, as we have a list of entry ID= s. > > For each entry id in {E1, E2, ... En}, we will check if the 'cn' reverse > table contain some value starting with 'jo'. > > Yep each candidate generated from the scope assertion E1, E2, ... En will use the ID to look into the reverse BTree and check if the value for that candidate matches jo*. > If th 'cn' index contains the two following table : > forward =3D > john --> {E1, E3} > joe --> {E2, E3, E5} > ... > > reverse =3D > E1 --> john > E2 --> joe > E3 --> joe, john > E5 --> joe > ... > > Yep. > then using the reverse table, we will find that the E1, E2, E3 and E5 > entry match, when all the other aren't. No need to fetch the E4, ... En > entries from the master table. > > Now, exploiting this rverse table means we read a btree. Which has the > same cost than reading the Master Table (except that we won't have to > deserialize the entry). > > IO time agreed. > What if we don't have a reverse table ? > > We will have to deserialize the entries, all of them from the {E1, E2, ..= . > En} set filtered by the scope. > > Is this better then to build a reverse index ? The only issue with this is that it will churn the entry cache. Meaning there's some proximity value in a settled cache due to the kinds of queries that generally occur. Optimally a cache should contain those entires most often looked up. A large master table scan will whip away a settled cache's knowledge. Using a reverse index instead has more value in this case. It's a delicate balance. > Not necessarily. In the case where we have more than one node in the > filter, for instance (&(cn=3Djo*)(sn=3Dtest)(**objectClass=3Dperson)), th= en > using the reverse index means we will access as many btrees as we have > index attributes in the filter node. Here, if cn, sn and objectClass are > indexed, we will potentially access 4 btrees (the scope will force us to > consider using the oneLevel index or the subLevel index). > > At the end, it might be more costly, compared to using the entry and matc= h > it against the nodes in the filter. > > Interesting point! The scan counts might help us out on a better optimization for these kinds of cases. If the search set is constrained (below some configurable threshold i.e. 10-50 entries) and if the filter uses many indices (above some threshold i.e. 3-4 indices) then it might be better to just pull from the master table directly without leveraging indices. This will optimize for speed without blowing out the cache memory. What do you think? > When we have many entries already in the cache, thus sparing the cost of = a > deserialization, then accessing more than one BTree might be costly, > comparing to using the entries themselves. > > Agreed but again let me stress protecting the cache memory from a large master table scan. I think we can take this strategy for the cases mentioned above. > An alternative > -------------- > > The pb is that the Node in the filter use a substring : jo*. Our index ar= e > built using the full normalized value. That does not fit. > > +1 > What if instead of browsing the underlying tree, we use a specific > compare() method instead of an equals() method ? As the tree is ordered, > finding the subset of entries taht will be valid candidate is just a matt= er > of finding the part of the tree which match the comparison. > > In our example, the compare() method will compare the first caracters fro= m > the keys to the filter value. Here, the compare method will be the > String.startWith(), and if it's not true, we will do a compareTo() to kno= w > if we should go donw th tree on the left or on the right of the current k= ey. > > You know I think we might be doing this. I remember lining up a Cursor on these boundaries for the sake of evaluation but this code might NOT be executed because the scan counts are using total DIB count for substring expressions. > For that, we just need the forward index, the reverse index is useless. > > I think this works for when you're generating candidates for an assertion using the substring operator. The reverse lookups will still be needed on the generated candidates and doing away with this is not a wise idea for large search domains since it is guaranteed to wipe away the cache memory. > If we use a substring with a '*' at the beginning, then we need another > index : a reverted index. Tht means all the values will be stored reverte= d > : john will be stored as 'nhoj', so doing a search on (cn=3D*hn) will be = fast. > > Yes we thought about doing this to handle substrings that have ONLY an 'end' component to them but we decided not to deal with it. This is perhaps the worst one of the most inefficient constructs minus the NOT operator. I think removing the reverse index (which I would love to do) is something that can be experimented with but we don't have a diverse test set to show the true impact across different scenarios. And until we have a way to understand the impact across different kinds of DIBs I'm afraid our reasoning for one situation verses another is not good enough to warrant the change. This is not a simple matter we should come to a decision on with even an intelligent guess. --=20 Best Regards, -- Alex --0016e6de00d5b8009904bc248f02 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable

On Thu, Mar 22, 2012 at 7:20 PM, Emmanue= l L=E9charny <e= lecharny@gmail.com> wrote:
Hi,

Currently, we create a forward and a reverse index for each index attribute= . The forward index is used when we annotate a filter, searching for the nu= mber of candidate it filters. The reverse index usage is a bit more subtile= .


[Hope you don't mind below I just = use concise English to express the process - not trying to insult your desc= ription - apologies if it sounds this way.]=A0

To state this more concisely, the reverse index facilitates rapid Evaluator= evaluations of non-candidate generating assertions in the filter AST. As y= ou know, one assertion in the filter (scope assertions included) is selecte= d as the candidate generating assertion which uses a Cursor to generate can= didates matching it's logic. The other filter assertions in the AST are= used to evaluate whether or not the generated candidates match.=A0

NOTE: the optimizer annotates the AST's nodes with = scan counts and this is used to drive selection of the proper candidate gen= erating assertion in the AST. This is done using a DFS through the AST to f= ind the lowest scan count containing leaf node (an assertion). This reduces= the search set.

Let's consider a filter like (cn=3Djo*). As we don't have any clue = about the value (it will start with 'jo', but that's all we kno= w), we can't use the 'cn' forward index.

Yep the scan count annotation used for the cn=3Djo* assertion wi= ll be the total count of entries in the DIB since the BTree cannot give us = a count figure. So depending on what scope is used it will most likely be t= he scope assertion that will drive candidate generation since it will most = likely have a smaller scan count.
=A0
We can't use the 'cn&#= 39; reverse index either, at least directly. So the engine will use the sco= pe to determinate a list of candidate : {E1, E2, ... En}. Now, instead of f= etching all those entries from the master table, what we can do is to use t= he 'cn' reverse table, as we have a list of entry IDs.

For each entry id in {E1, E2, ... En}, we will check if the 'cn' re= verse table contain some value starting with 'jo'.


Yep each candidate generated from the = scope assertion E1, E2, ... En will use the ID to look into the reverse BTr= ee and check if the value for that candidate matches jo*. =A0
=A0
If th 'cn' index contains the two following table :
forward =3D
=A0john --> {E1, E3}
=A0joe =A0--> {E2, E3, E5}
=A0...

reverse =3D
=A0E1 --> john
=A0E2 --> joe
=A0E3 --> joe, john
=A0E5 --> joe
=A0...


Yep.
=A0
then using the reverse table, we will find that the E1, E2, E3 and E5 entry= match, when all the other aren't. No need to fetch the E4, ... En entr= ies from the master table.

Now, exploiting this rverse table means we read a btree. Which has the same= cost than reading the Master Table (except that we won't have to deser= ialize the entry).


IO time agreed. =A0
=A0
What if we don't have a reverse table ?

We will have to deserialize the entries, all of them from the {E1, E2, ... = En} set filtered by the scope.

Is this better then to build a reverse index ?

=
The only issue with this is that it will churn the entry cache. Meanin= g there's some proximity value in a settled cache due to the kinds of q= ueries that generally occur. Optimally a cache should contain those entires= most often looked up.

A large master table scan will whip away a settled cach= e's knowledge. Using a reverse index instead has more value in this cas= e. It's a delicate balance.
=A0
Not necessarily. In the case where we have more than one node in the filter= , for instance (&(cn=3Djo*)(sn=3Dtest)(objectClass=3Dperson)), t= hen using the reverse index means we will access as many btrees as we have = index attributes in the filter node. Here, if cn, sn and objectClass are in= dexed, we will potentially access 4 btrees (the scope will force us to cons= ider using the oneLevel index or the subLevel index).

At the end, it might be more costly, compared to using the entry and match = it against the nodes in the filter.


Interesting point! The scan counts mig= ht help us out on a better optimization for these kinds of cases.=A0
<= div>
If the search set is constrained (below some configurabl= e threshold i.e. 10-50 entries) and if the filter uses many indices (above = some threshold i.e. 3-4 indices) then it might be better to just pull from = the master table directly without leveraging indices.

This will optimize for speed without blowing out the ca= che memory. What do you think?
=A0
When we have many entries already in the cache, thus sparing the cost of a = deserialization, then accessing more than one BTree might be costly, compar= ing to using the entries themselves.


Agreed but again let me stress protect= ing the cache memory from a large master table scan. I think we can take th= is strategy for the cases mentioned above.
=A0
An alternative
--------------

The pb is that the Node in the filter use a substring : jo*. Our index are = built using the full normalized value. That does not fit.


+1
=A0
What if instead of browsing the underlying tree, we use a specific compare(= ) method instead of an equals() method ? As the tree is ordered, finding th= e subset of entries taht will be valid candidate is just a matter of findin= g the part of the tree which match the comparison.

In our example, the compare() method will compare the first caracters from = the keys to the filter value. Here, the compare method will be the String.s= tartWith(), and if it's not true, we will do a compareTo() to know if w= e should go donw th tree on the left or on the right of the current key.

You know I think we might be doing thi= s. I remember lining up a Cursor on these boundaries for the sake of evalua= tion but this code might NOT be executed because the scan counts are using = total DIB count for substring expressions.
=A0
For that, we just need the forward index, the reverse index is useless.


I think this works for when you're= generating candidates for an assertion using the substring operator. The r= everse lookups will still be needed on the generated candidates and doing a= way with this is not a wise idea for large search domains since it is guara= nteed to wipe away the cache memory. =A0
=A0
If we use a substring with a '*' at the beginning, then we need ano= ther index : a reverted index. Tht means all the values will be stored reve= rted : john will be stored as 'nhoj', so doing a search on (cn=3D*h= n) will be fast.


Yes we thought about doing this to han= dle substrings that have ONLY an 'end' component to them but we dec= ided not to deal with it. This is perhaps the worst one of the most ineffic= ient constructs minus the NOT operator.

I think removing the reverse index (which I would love = to do) is something that can be experimented with but we don't have a d= iverse test set to show the true impact across different scenarios. And unt= il we have a way to understand the impact across different kinds of DIBs I&= #39;m afraid our reasoning for one situation verses another is not good eno= ugh to warrant the change. This is not a simple matter we should come to a = decision on with even an intelligent guess.

--
Best Regards,
-- Alex

--0016e6de00d5b8009904bc248f02--